153. 寻找旋转排序数组中的最小值
方法一: 思想: 看旋转发生在前半部分,还是后半部分, 如果旋转发生在前半部分,找到的规律就是 7 0 1 2 4 5 6 那么有nums[mid - 1] > nums[mid]; return nums[mid]; 如果旋转发生在后半部分, 找到的规律就是4, 5, 6, 7, 0, 1 , 2 那么有nums[mid] > nums[mid + 1]; return nums[mid + 1]; 变化点特点 所有变化点左侧元素 > 数组第一个元素 所有变化点右侧元素 < 数组第一个元素 找到数组的中间元素 mid。 如果中间元素 > 数组第一个元素，我们需要在 mid 右边搜索变化点, 即 nums[mid] > nums[0] 则 left = left + 1 如果中间元素 < 数组第一个元素，我们需要在 mid 左边搜索变化点, 即 nums[mid] < nums[0] 则 right = mid - 1
/* 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。 示例 1: 输入: [3,4,5,1,2] 输出: 1 示例 2: 输入: [4,5,6,7,0,1,2] 输出: 0 */ /* 注意点一: 这里while (left <= right) 写成while (left < right)也可以, 因为数组中不存在重复元素, 肯定最小的元素。 注意点二: if (nums.length == 1) return nums[0]; int left = 0, right = nums.length - 1; if (nums[right] > nums[0]) return nums[0]; 边界条件的判断 [0, 1, 2, 4, 5, 6, 7] [4, 5, 6, 7, 0, 1, 2] [7, 9, 1, 2, 4, 5, 6] */ public int findMin(int[] nums) { if (nums.length == 1) return nums[0]; int left = 0, right = nums.length - 1; if (nums[right] > nums[0]) return nums[0]; while (left <= right) { mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) return nums[mid + 1]; if (nums[mid - 1] > nums[mid]) return nums[mid]; if (nums[mid] > nums[0]) { left = mid + 1;// 突变在右边部分, 且从上面下来满足 nums[mid - 1] < nums[mid] < nums[mid + 1], 所以mid不是突变的值 } if (nums[mid] < nums[0]) { right = mid - 1;// 突变在右边部分, 且从上面下来满足 nums[mid - 1] < nums[mid] < nums[mid + 1], 所以mid不是突变的值 } } return -1; }方法二: 题目就是要我们找出两个单增区间的边界
很容易想到二分查找 在循环中求出 中间元素，循环条件是 left < right，结束遍历时，我们让left和right是相邻的整数，并且我们让left是我们要的 如果 nums[mid] > nums[right] ，则说明 mid 处在左边的单增区间，目标元素在mid的右侧，所以我们让 left = mid + 1; 否则，mid 处在右边的单增区间中，目标元素在mid的左侧，我们让right = mid;
public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ while (left < right) { /* 循环不变式，如果left == right，则循环结束 */ int mid = left + (right - left) / 2; /* 地板除，mid更靠近left */ if (nums[mid] > nums[right]) { /* 中值 > 右值，最小值在右半边，收缩左边界 */ left = mid + 1; /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ } else if (nums[mid] < nums[right]) { /* 明确中值 < 右值，最小值在左半边，收缩右边界 */ right = mid; /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ } } return nums[left]; /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */ }为什么比较mid与right而不比较mid与left？ 具体原因前面已经分析过了，简单讲就是因为我们找最小值，要偏向左找，目标值右边的情况会比较简单，容易区分，所以比较mid与right而不比较mid与left。 那么能不能通过比较mid与left来解决问题？ 能，转换思路，不直接找最小值，而是先找最大值，最大值偏右，可以通过比较mid与left来找到最大值，最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余）。
以下是先找最大值的代码，可以与前面找最小值的比较：
public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left + 1) / 2; /* 先加一再除，mid更靠近右边的right */ if (nums[left] < nums[mid]) { left = mid; /* 向右移动左边界 */ }else if (nums[left] > nums[mid]) { right = mid - 1; /* 向左移动右边界 */ } } return nums[(right + 1) % nums.length];/* 最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余） */ }使用left < right作while循环条件可以很方便推广到数组中有重复元素的情况， 即：154. 寻找旋转排序数组中的最小值 II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。 示例 1： 输入: [1,3,5] 输出: 1 示例 2： 输入: [2,2,2,0,1] 输出: 0 只需要在nums[mid] == nums[right]时挪动右边界就行：
public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] < nums[right]) { right = mid; } else { right--; } } return nums[left]; }33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
方法一:暴力法 O(N)
public int search(int[] nums, int target) { for (int i = 1; i < nums.length - 1; i++) { if (nums[i + 1] < nums[i]) { return i; } } return -1; }方法二: 递归 二分查找O(logN)
public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; helper(nums, target, left, right); } 7, 0, 2, 4, 6 public int helper(int[] nums, int target, int left, int right) { if (left > right) {return -1;} int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[left] == target) return left; if (nums[right] == target) return right; if (nums[left] < nums[mid]) { if (nums[left] < target && target < nums[mid]) { helper(nums, target, left + 1, mid - 1); }else { helper(nums, target, mid + 1, right - 1); } }else { if (nums[mid] < target && target < nums[right]) { helper(nums, target, mid + 1, right - 1); }else { helper(nums, target, left + 1, mid - 1); } } }方法三: 迭代 二分查找O(logN)
public int search(int[] nums, int target) { if (nums == null) return - 1; int len = nums.length; if (len == 1) return nums[0] == target ? 0 : -1; int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; }else { left = mid + 1; } }else { if (nums[right] >= target && nums[mid] < target) { left = mid + 1; }else { right = mid - 1; } } } return -1; }55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
/* 伪代码 int reach = 0, n = size() for (int i = 0; i < n; i++) { if (i > reach) { // 假如当前遍历的i已经超过了reach, 表明这个位置是我们跳不到的,因为i已经遍历到了我们已经到达最远位置更靠后的i的位置上, 直接返回false, 如果不是这种情况,就表示当前位置是我们可以到的,并且我们可以在这个位置上继续向前跳远 return false; } reach = Math.max(i + A[i], reach); } // 从i = 0到i = 1全部都遍历到了 return true */ public boolean canJump(int[] nums) { if (nums == null) { return false; } int n = nums.length; int reach = 0; for (int i = 0; i < n; ++i) { if (i > reach) { return false; } reach = Math.max(i + nums[i], reach); } return true; }优化 for (int i = 0; i <= reach && reach < n - 1; ++i) { // 当reach已经达到了很远的值,已经超过了最后的那个位置就可以提前返回结果, 或者当前遍历的值不能超过reach,超过reach就表示遍历不到了,跳出了循环, 并且reach的结果小于n - 1, 如果大于等于n - 1说明已经跳到最后的位置了 reach = Math.max(i + A[i], reach); } return reach >= n - 1; 3 2 1 0 4
public boolean canJump(int[] nums) { if (nums == null) { return false; } int n = nums.length; int reach = 0; for (int i = 0; i <= reach && reach < n - 1; ++i) { reach = Math.max(i + nums[i], reach); } return reach >= n - 1; }方法二:
public boolean canJump(int[] nums) { if (nums == null) {return false;} int endReachable = nums.length - 1; for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] + i >= endReachable) { endReachable = i; } } return endReachable == 0; }455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 注意： 你可以假设胃口值为正。 一个小朋友最多只能拥有一块饼干。 示例 1: 输入: [1,2,3], [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。 示例 2: 输入: [1,2], [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2. 给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。 因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。
public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int i = 0; int j = 0; int count = 0; while (i < g.length && j < s.length) { if (s[j] >= g[i]) { count++; i++; } j++; } return count; }