1.classical-binary-search(经典二分查找问题）【二分查找模板】
在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1
public class Solution { /** * @param nums: An integer array sorted in ascending order * @param target: An integer * @return an integer */ public int findPosition(int[] nums, int target) { // Write your code here if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; } }
2.first-position-of-target(二分查找）
给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
class Solution { /** * @param nums: The integer array. * @param target: Target to find. * @return: The first position of target. Position starts from 0. */ public int binarySearch(int[] nums, int target) { //write your code here if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return start; } if (nums[end] == target) { return end; } return -1; } }
3.last-position-of-target（目标最后位置）
给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1
public class Solution { /** * @param nums: An integer array sorted in ascending order * @param target: An integer * @return an integer */ public int lastPosition(int[] nums, int target) { // Write your code here if (nums == null || nums.length == 0) { return -1; } int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] > target) { end = mid; } else { start = mid; } } if (nums[end] == target) { return end; } if (nums[start] == target) { return start; } return -1; } }
第一境界:
二分位置 之 OOXX 一般会给一个数组 找数组中第一个/最后一个满足某个条件的位置OOOOOOO...OOXX….XXXXXX
4.first-bad-version（第一个错误的代码版本）
代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，java的调用方式是SVNRepo.isBadVersion(v)
/** * public class SVNRepo { * public static boolean isBadVersion(int k); * } * you can use SVNRepo.isBadVersion(k) to judge whether * the kth code version is bad or not. */ class Solution { /** * @param n: An integers. * @return: An integer which is the first bad version. */ public int findFirstBadVersion(int n) { // write your code here int start = 1; int end = n; while (start + 1 < end) { int mid = start + (end - start) / 2; if (SVNRepo.isBadVersion(mid)) { end = mid; } else { start = mid; } } if (SVNRepo.isBadVersion(start)) { return start; } return end; } }
注意：函数要有返回值，判断start和end时不能都使用if。
5.search-in-a-big-sorted-array（在大数组中查找）
给一个按照升序排序的正整数数组。这个数组很大以至于你只能通过固定的接口 ArrayReader.get(k) 来访问第k个数，并且你也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。如果找不到target，返回-1。如果你访问了 ArrayReader 中一个不可访问的下标（比如越界），ArrayReader 会返回 MAXINT = 2,147,483,647。
/** * Definition of ArrayReader: * * class ArrayReader { * // get the number at index, return -1 if index is less than zero. * public int get(int index); * } */ public class Solution { /** * @param reader: An instance of ArrayReader. * @param target: An integer * @return : An integer which is the index of the target number */ public int searchBigSortedArray(ArrayReader reader, int target) { // write your code here int index = 1; while (reader.get(index - 1) < target) { index = index * 2; } int start = 0; int end = index - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (reader.get(mid) < target) { start = mid; } else { end = mid; } } if (reader.get(start) == target) { return start; } if (reader.get(end) == target) { return end; } return -1; } }
注意：使用倍增思想先找到右边界，先看第一个数是不是target,再看第二个数是不是target,再看第4个数是不是target,......肯定能在2*k内找到右边界。
int index = 1; while (reader.get(index - 1) < target) { index = index * 2; }
6.find-minimum-in-rotated-sorted-array（寻找旋转排序数组中的最小值）【高频++】
假设一个旋转排序数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。可以假设数组中不存在重复的元素。
public class Solution { /** * @param nums: a rotated sorted array * @return: the minimum number in the array */ public int findMin(int[] nums) { // write your code here int start = 0; int end = nums.length - 1; //首先选择一个target int target = nums[end]; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] <= target) { end = mid; } else { start = mid; } } if (nums[start] <= target) { return nums[start]; } else { return nums[end]; } } }
注意：首先要取一个target=last number，然后如果mid > target, start = mid;mid <= target, end = mid;(相等的情况由 0 1 2 3 4 5 6 7进行判断）
第二境界:
二分位置 之 Half half ,并无法找到一个条件，形成 OOXX 的模型, 但可以根据判断，保留下有解的那一半或者去掉无解的一半
7.find-peak- element(寻找峰值）
给出一个整数数组(size为n)，其具有以下特点：相邻位置的数字是不同的，A[0] < A[1] 并且 A[n - 2] > A[n - 1]。假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。数组可能包含多个峰值，只需找到其中的任何一个即可。
class Solution { /** * @param A: An integers array. * @return: return any of peek positions. */ public int findPeak(int[] A) { // write your code here int start = 1; int end = A.length - 2; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] < A[mid - 1]) { end = mid; } else if (A[mid] > A[mid - 1]) { start = mid; } } if (A[start] > A[end]) { return start; } else { return end; } } }
注意：只有两种情况：mid < mid - 1 (mid > mid + 1) end = mid或者mid > mid - 1(mid < mid + 1) start = mid。
8.search-in-rotated-sorted-array（搜索旋转排序数组）【会了这道题，才敢说自己会二分法】
假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。可以假设数组中不存在重复的元素。
public class Solution { /** *@param A : an integer rotated sorted array *@param target : an integer to be searched *return : an integer */ public int search(int[] A, int target) { // write your code here if (A == null || A.length == 0) { return -1; } int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { return mid; } if (A[start] < A[mid]) { if (A[start] <= target && target <= A[mid]) { end = mid; } else { start = mid; } } else { if (A[mid] <= target && target <= A[end]) { start = mid; } else { end = mid; } } } if (A[start] == target) { return start; } if (A[end] == target) { return end; } return -1; } }
注意：两次二分法！第一次：start和mid比较，判断是在左上还是右下：A[start] < A[mid]在左上；A[start] > A[mid] 在右下
第二次：在有解的那一半中继续二分：左上start<=target<=mid end = mid;否则start = mid;
右下mid<=target<=end start = mid;否则end = mid;
第三境界：
二分答案,Binary Search on Result,往往没有给你一个数组让你二分,而且题目压根看不出来是个二分法可以做的题,同样是找到满足某个条件的最大或者最小值。
9.sqrtx(x的平方根)
实现 int sqrt(int x) 函数，计算并返回 x 的平方根。
class Solution { /** * @param x: An integer * @return: The sqrt of x */ public int sqrt(int x) { // write your code here long start = 1; long end = x; while (start + 1 < end) { long mid = start + (end - start) / 2; if (mid * mid <= x) { start = mid; } else { end = mid; } } if (end * end <= x) { return (int) end; } else { return (int) start; } } }
注意：首先确定答案范围（1~x），然后二分这个范围。start,mid和end声明为long类型，最后要先判断end的平方是否<=X，转为int类型输出。
10.sqrtx-ii（x的平方根）
实现double sqrt(double x) 并且x >= 0，计算并返回 x 的平方根。
public class Solution { /** * @param x a double * @return the square root of x */ public double sqrt(double x) { // Write your code here double start = 0.0; double end = x; double eps = 1e-12; if (end < 1.0) { end = 1.0; } while (end - start > eps) { double mid = start + (end - start) / 2; if (mid * mid <= x) { start = mid; } else { end = mid; } } if (end * end <= x) { return end; } return start; } }
注意：答案范围为（0.0~x）。start,mid和end声明为double类型。
double eps = 1e-12; //若end < 1.0,sqrt(end)>end,但右边界设定的是end,就求不出正确结果。所以要把end 设为1.0 if (end < 1.0) { end = 1.0; } 二分浮点数 和二分整数不同 一般都有一个精度的要求 譬如这题就是要求小数点后八位, 也就是只要我们二分的结果达到了这个精度的要求就可以,所以 需要让 right 和 left 小于一个我们事先设定好的精度值 eps,一般eps的设定1e-8,因为这题的要求是到1e-8,所以我把精度调到了1e-12。最后 选择 left 或 right 作为一个结果即可 while (end - start > eps) {... }
11.search-a-2d-matrix（搜索二维矩阵）
写出一个高效的算法来搜索 m × n矩阵中的值（target）。这个矩阵具有以下特性：每行中的整数从左到右是排序的。每行的第一个数大于上一行的最后一个整数。
public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ public boolean searchMatrix(int[][] matrix, int target) { // write your code here if (matrix == null || matrix.length == 0) { return false; } if (matrix[0] == null || matrix[0].length == 0) { return false; } int m = matrix.length; int n = matrix[0].length; int start = 0; int end = m * n - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; int number = matrix[mid / n][mid % n]; if (number == target) { return true; } else if (number < target) { start = mid; } else { end = mid; } } if (matrix[start / n][start % n] == target) { return true; } if (matrix[end / n][end % n] == target) { return true; } return false; } }
注意：这个矩阵实质上是一个从小到大的排序数组。矩阵中每个数坐标的求法，m行n列。横坐标（start,mid,end）/n纵坐标（start,mid,end）%n
由（0,0）0 （0,1）1 （0,2）2 （0,3）3
（1,0）4 （1,1）5 （1,2）6 （1,3）7
（2,0）8 （2,1）9 （2,2）10 （2,3）11 可得以上规律。
12.search-a-2d-matrix-ii（搜索二维矩阵-II）【智力题】
写出一个高效的算法来搜索m×n矩阵中的值（target），返回这个值出现的次数。这个矩.阵具有以下特性： 每行中的整数从左到右是排序的。每一列的整数从上到下是排序的。在每一行或每一列中没有重复的整数。
public class Solution { /** * @param matrix: A list of lists of integers * @param: A number you want to search in the matrix * @return: An integer indicate the occurrence of target in the given matrix */ public int searchMatrix(int[][] matrix, int target) { // write your code here if (matrix == null || matrix.length == 0) { return 0; } if (matrix[0] == null || matrix[0].length == 0) { return 0; } int m = matrix.length; int n = matrix[0].length; int x = m - 1; int y = 0; int count = 0; while (x >= 0 && y < n) { if (matrix[x][y] == target) { count++; x--; y++; } else if (matrix[x][y] < target) { y++; } else { x--; } } return count; } }
注意：从左下角元素或右上角元素开始分析。以左下角元素为例，如果M[x][y]==target,x--,y++;如果M[x][y]<target,y++;如果M[x][y]>target,x--。
13.search-for-a-range（搜索区间）
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回[-1, -1]
public class Solution { /** *@param A : an integer sorted array *@param target : an integer to be inserted *return : a list of length 2, [index1, index2] */ public int[] searchRange(int[] A, int target) { // write your code here int[] result = new int[2]; result[0] = -1; result[1] = -1; if (A == null || A.length == 0 || target < A[0] || target > A[A.length - 1]) { return result; } int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] >= target) { end = mid; } else { start = mid; } } if (A[start] == target) { result[0] = start; } else if (A[end] == target) { result[0] = end; } else { return result; } start = 0; end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] <= target) { start = mid; } else { end = mid; } } if (A[end] == target) { result[1] = end; } else if (A[start] == target) { result[1] = start; } else { return result; } return result; } }
注意：两次二分法，第一次找first location，第二次找last location,第二次二分前start和end要赋初值。即使已经判断了target是否小于A[0]，大于A[A.length-1]也要考虑target不在目标数组中的情况。例如：A=[1,2,3,5,6,7],target=4。
14.total-occurrence-of-target（目标出现总和）
给一个升序的数组，以及一个target，找到它在数组中出现的次数。
public class Solution { /** * @param A an integer array sorted in ascending order * @param target an integer * @return an integer */ public int totalOccurrence(int[] A, int target) { // Write your code here int[] result = new int[2]; result[0] = 0; result[1] = 0; if (A == null || A.length == 0 || target < A[0] || target > A[A.length - 1]) { return 0; } int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] >= target) { end = mid; } else { start = mid; } } if (A[start] == target) { result[0] = start; } else if (A[end] == target) { result[0] = end; } else { return 0; } start = 0; end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] <= target) { start = mid; } else { end = mid; } } if (A[end] == target) { result[1] = end; } else if (A[start] == target) { result[1] = start; } else { return 0; } return result[1] - result[0] + 1; } }
注意：13题的变形。返回值为result[1] - result[0] + 1。若target不在目标数组中返回0。
15.maximum-number-in-mountain-sequence（山序列中的最大数）
给出一个先增加然后减少的n个整数的山序列，找到山顶。
public class Solution { /** * @param nums a mountain sequence which increase firstly and then decrease * @return then mountain top */ public int mountainSequence(int[] nums) { // Write your code here int start = 0; int end = nums.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (nums[mid] < nums[mid + 1]) { start = mid; } else if (nums[mid] > nums[mid + 1]) { end = mid; } } if (nums[start] < nums[end]) { return nums[end]; } else { return nums[start]; } } }
注意：考虑mid <mid + 1 和mid > mid + 1 两种情况，最后取start和end的较大值。
16.search-insert-position（搜索插入位置）
给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。你可以假设在数组中无重复元素。
public class Solution { /** * param A : an integer sorted array * param target : an integer to be inserted * return : an integer */ public int searchInsert(int[] A, int target) { // write your code here if (A == null || A.length == 0 || target < A[0]) { return 0; } if (target > A[A.length - 1]) { return A.length; } int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { return mid; } else if (A[mid] < target) { start = mid; } else { end = mid; } } if (A[end] == target) { return end; } else if (A[start] == target) { return start; } else { return end; } } }
注意：最后的判断条件，如果A[end]==target，返回end;A[start]==target.返回start;否则返回end.
17.recover-rotated-sorted-array（恢复旋转排序数组）【三步翻转法】是指：[4,5,1,2,3] → [5,4,1,2,3] → [5,4,3,2,1] → [1,2,3,4,5]
给定一个旋转排序数组，在原地恢复其排序。什么是旋转数组？比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
public class Solution { /** * @param nums: The rotated sorted array * @return: void */ public void recoverRotatedSortedArray(ArrayList<Integer> nums) { // write your code for (int i = 0; i < nums.size() - 1; i++) { if (nums.get(i) > nums.get(i + 1)) { reverse(nums, 0, i); reverse(nums, i + 1, nums.size() - 1); reverse(nums, 0, nums.size() - 1); break; } } } private void reverse(ArrayList<Integer> nums, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { int temp = nums.get(i); nums.set(i, nums.get(j)); nums.set(j, temp); } } }
18.rotate-string（旋转字符串）
给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)
public class Solution { /** * @param str: an array of char * @param offset: an integer * @return: nothing */ public void rotateString(char[] str, int offset) { // write your code here if (str == null || str.length == 0) { return; } offset = offset % str.length; reverse(str, 0, str.length - offset - 1); reverse(str, str.length - offset, str.length - 1); reverse(str, 0, str.length - 1); } private void reverse(char[] str, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } } }
注意：偏移量offset要对字符串长度取余。依然是三步翻转法。
19.wood-cut（木材加工）【hard】
有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。注意事项：木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可。
public class Solution { /** *@param L: Given n pieces of wood with length L[i] *@param k: An integer *return: The maximum length of the small pieces. */ public int woodCut(int[] L, int k) { // write your code here if (L == null || L.length == 0) { return 0; } int max = Integer.MIN_VALUE; for (int i = 0; i < L.length; i++) { if (L[i] > max) { max = L[i]; } } int start = 1; int end = max; while (start + 1 < end) { int mid = start + (end - start) / 2; if (count(L, mid) < k) { end = mid; } else { start = mid; } } if (count(L, end) >= k) { return end; } if (count(L, start) >= k) { return start; } return 0; } private int count(int[] L, int len) { int num = 0; for (int i = 0; i < L.length; i++) { num += L[i] / len; } return num; } }
注意：木材长度的最小值是1（可以切总长度这么多段），最大值是这些木头中最长的那个（只切一段）。count()函数计算能够切割得到的木材段数。
20.copy-books（书籍复印）【hard】
给出一个数组A包含n个元素，表示n本书以及各自的页数。现在有个k个人复印书籍，每个人只能复印连续一段编号的书，比如A[1],A[2]由第一个人复印，但是不能A[1],A[3]由第一个人复印，求最少需要的时间复印所有书。返回值是复印的页数。
public class Solution { /** * @param pages: an array of integers * @param k: an integer * @return: an integer */ public int copyBooks(int[] pages, int k) { // write your code here if (pages == null || pages.length == 0) { return 0; } int max = Integer.MIN_VALUE; int sum = 0; for (int i = 0; i < pages.length; i++) { max = Math.max(max, pages[i]); sum += pages[i]; } int start = max; int end = sum; while (start + 1 < end) { int mid = start + (end - start) / 2; if (countCopyiers(pages, mid) > k) { start = mid; } else { end = mid; } } if (countCopyiers(pages, start) <= k) { return start; } return end; } private int countCopyiers(int[] pages, int limit) { int copyiers = 1; int sum = pages[0]; for (int i = 1; i < pages.length; i++) { if (sum + pages[i] > limit) { copyiers++; sum = 0; } sum +=page[i]; } return copyiers; } }
注意：复印页数的最小值是数组中元素的最大值（n个人一起，一人一本），最大值是数组中所有元素和（一个人复印完全部）。countCopiers()函数计算需要多少人能复印完书。
最后要先判断countCopyiers(pages, start)是否<=k,再判断end。考虑pages={1,2},k=5。start=2,end=3。如果先判断end会得到结果3，而实际上结果2用时更少。
private int countCopyiers(int[] pages, int limit) { int copyiers = 1; int sum = pages[0]; for (int i = 1; i < pages.length; i++) { if (sum + pages[i] > limit) { copyiers++; sum = 0; } sum +=page[i]; } return copyiers; } pages[0]+pages[1]>limit时只有pages[0]是这个人的工作，pages[1]就是下个人的工作了，所以copyiers++,sum清零。
21.closest-number-in-sorted-array（排序数组中最接近元素）【思路有障碍】
在一个排好序的数组 A 中找到 i 使得 A[i] 最接近 target。数组中可以有重复的元素，我们可以返回任何具有相同值的索引。
public class Solution { /** * @param A an integer array sorted in ascending order * @param target an integer * @return an integer */ private int firstIndex(int[] A, int target) { int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { //return mid; end = mid; } else if (A[mid] < target) { start = mid; } else { end = mid; } } if (A[start] >= target) { return start; } if (A[end] >= target) { return end; } return A.length; } public int closestNumber(int[] A, int target) { // Write your code here if (A == null || A.length == 0) { return -1; } int index = firstIndex(A, target); if (index == 0) { return 0; } if (index == A.length) { return A.length - 1; } if (target - A[index - 1] < A[index] - target) { return index - 1; } return index; } }
注意：先使用二分法找到>=target的第一个位置index, 如果index等于0，返回0；如果index=A.length返回A.length-1；如果target-A[index-1]<A[index]-target返回index-1；否则返回index。
public class Solution { /** * @param A an integer array sorted in ascending order * @param target an integer * @return an integer */ public int closestNumber(int[] A, int target) { // Write your code here if (A == null || A.length == 0) { return -1; } if (target < A[0]) { return 0; } if (target > A[A.length - 1]) { return A.length - 1; } int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { return mid; } else if (A[mid] > target) { end = mid; } else { start = mid; } } if (target - A[start] < A[end] - target) { return start; } return end; } }
上述为个人思路，先判断target是否<A[0]或>A[A.length-1]，然后二分法找到start和end，如果target-A[start]<A[end]- target,返回start,否则返回end。
22.k-closest-numbers-in-sorted-array（在排序数组中找最接近的k个数）【思路有障碍】
给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。
public class Solution { /** * @param A an integer array * @param target an integer * @param k a non-negative integer * @return an integer array */ public int[] kClosestNumbers(int[] A, int target, int k) { // Write your code here int[] result = new int[k]; if (A == null || A.length == 0 || k > A.length) { return A; } int index = firstIndex(A, target); int left = index - 1; int right = index; for (int i = 0; i < k; i++) { if (left < 0) { result[i] = A[right++]; } else if (right >= A.length) { result[i] = A[left--]; } else { if (target - A[left] <= A[right] - target) { result[i] = A[left--]; } else { result[i] = A[right++]; } } } return result; } private int firstIndex(int[] A, int target) { int start = 0; int end = A.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { end = mid; } else if (A[mid] > target) { end = mid; } else { start = mid; } } if (A[start] >= target) { return start; } if (A[end] >= target) { return end; } return A.length; } }
注意：先使用二分法找到>=target的第一个位置index, 然后left=index-1,right=index。在k个循环的过程中，如果left<0，result[i]=A[right++]；如果right>=A.length,result[i]=A[left--]；如果target-A[left]<=A[right]-target result[i]=A[left--]；否则result[i]=A[right++]。
23.find-minimum-in-rotated-sorted-array-ii（寻找旋转排序数组中的最小值-II）
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。数组中可能存在重复的元素。
public class Solution { /** * @param num: a rotated sorted array * @return: the minimum number in the array */ public int findMin(int[] num) { // write your code here int min = Integer.MAX_VALUE; for (int i = 0; i < num.length; i++) { min = Math.min(min, num[i]); } return min; } }
注意：考点是能不能想得到最坏情况[1,1,1,...,1]里有一个0。时间复杂度o(n)是必须的。一个for循环即可。二分法也可以做。
24.search-in-rotated-sorted-array-ii（搜索旋转排序数组-II）
跟进“搜索旋转排序数组”，假如有重复元素。写出一个函数判断给定的目标值是否出现在数组中。
public class Solution { /** * param A : an integer ratated sorted array and duplicates are allowed * param target : an integer to be search * return : a boolean */ public boolean search(int[] A, int target) { // write your code here for (int i = 0; i < A.length; i++) { if (A[i] == target) { return true; } } return false; } }
注意：考点是能不能想得到最坏情况[1,1,1,...,1]里有一个0。时间复杂度o(n)是必须的。
25.divide-two-integers（两个整数相除）
将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。
public class Solution { /** * @param dividend the dividend * @param divisor the divisor * @return the result */ public int divide(int dividend, int divisor) { // Write your code here //处理特殊情况 if (divisor == 0) { return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } if (dividend == 0) { return 0; } if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } //判断最终结果是否为负数 boolean isNegative = (dividend < 0 && divisor > 0) ||(dividend > 0 && divisor < 0); //将a与b都转变成正数运算 long a = Math.abs((long) dividend); long b = Math.abs((long) divisor); int result = 0; while (a >= b){ int shift = 0; while (a >= (b << shift)){ shift++; } //a -= b << (shift - 1); //result += 1 << (shift - 1); a = a - (b << (shift - 1)); result = result + (1 << (shift - 1)); } return isNegative ? -result : result; } }
注意：先处理各类特殊情况，然后判断结果的正负性，最后使用位运算求出结果。具体分析过程见笔记。
26.maximum-average-subarray（最大平均值子数组）
给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。保证数组的大小 >= k。
public class Solution { /** * @param nums an array with positive and negative numbers * @param k an integer * @return the maximum average */ public double maxAverage(int[] nums, int k) { // Write your code here double l = Integer.MAX_VALUE; double r = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { if (nums[i] < l) { l = nums[i]; } if (nums[i] > r) { r = nums[i]; } } while (r - l >= 1e-6) { double mid = l + (r - l) / 2; if (check_valid(nums, mid, k)) { l = mid; } else { r = mid; } } return l; } private boolean check_valid(int[] nums, double mid, int k) { int n = nums.length; double min_pre = 0; double[] sum = new double[n + 1]; sum[0] = 0; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + nums[i - 1] - mid; if (i >= k && sum[i] - min_pre >= 0) { return true; } if (i >= k) { min_pre = Math.min(min_pre, sum[i + 1 - k]); } } return false; } }
思路：
1、一个数组的子数组的最大平均数一定在数组的最大值和最小值之间，所以二分法的第一步限定average位于[min,max]之中。
2、接下去要做的就是不断的缩小范围，直至max-min足够小（如1e-6），那我们就得到了想要的结果。
缩小范围的思想如下：
每一轮设置mid=(min+max)/2，然后将原数组中的每一个数减去这个mid，如果能找到k个相邻数的总和大于0的情况，
那么说明最终结果一定比这个mid要更大，限定下一轮寻找范围在[mid,max]之中。反之在限定在[min,mid]之中。
那么在实际算法中我们需要解决的关键一步就是，如何判断“有k个相邻数的总和大于0的情况存在”。
首先，我们可以用sum数组来存储减掉mid值的原数组的各总和（sum[i]存储num[0]-mid到num[i-1]-mid的总和），
当sum[i]存储的总和个数超过k时（即i>k），也就是说我们保证了这个子数组的长度达到k后，可以砍掉之前一些拖后腿的数。
这些拖后腿的数用min_pre来实现的。当之前拖后腿的数值小于min_pre时，更新min_pre=sum[i - k + 1]。
sum[i]存储的是num[0]~num[i-1]减去mid的总和，而min_pre存储的是num[0]~num[k]减掉mid的总和，这样sum[i]-min_pre得到的是sum[k+1]~sum[i-1]，
它所记录的总和个数也就是到num[i]为止能够找到的最大平均数子数组的长度。