算法思想
一、二分查找
1. 算法思想
public int search(int key, int[] array) {
int l = 0, h = array.length - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
if (key == array[mid]) return mid;
else if (key < array[mid]) h = mid - 1;
else l = mid + 1;
}
return -1;
}
实现时需要注意以下细节：
在计算 mid 时不能使用 mid = (l + h) / 2 这种方式，因为 l + h 可能会导致加法溢出，应该使用 mid = l + (h - l) / 2。
-
while(left <= right)的终止条件是left == right + 1，写成区间的形式就是[right + 1, right]，或者带个具体的数字进去[3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 33 又小于等于 22 的吧。所以这时候while循环终止是正确的，直接返回-1即可。while(left < right)的终止条件是left == right，写成区间的形式就是[left, right]，或者带个具体的数字进去[2, 2]，这时候搜索区间非空，还有一个数 22，但此时while循环终止了。也就是说这区间[2, 2]被漏掉了，索引 22 没有被搜索，如果这时候直接返回-1就是错误的。 -
对 h 的赋值和循环条件有关，当循环条件为 l <= h 时，h = mid - 1；当循环条件为 l < h 时，h = mid。
解释如下：在循环条件为 l <= h 时，如果 h = mid，会出现循环无法退出的情况，例如 l = 1，h = 1，此时 mid 也等于 1，如果此时继续执行 h = mid，那么就会无限循环；在循环条件为 l < h，如果 h = mid - 1，会错误跳过查找的数，例如对于数组 [1,2,3]，要查找 1，最开始 l = 0，h = 2，mid = 1，判断 key < arr[mid] 执行 h = mid - 1 = 0，此时循环退出，直接把查找的数跳过了。
l 的赋值一般都为 l = mid + 1。
2. 题目
69. X的平方根（简单）
1、题目描述
实现
int sqrt(int x)函数。计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
2、解题思路
一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt 。可以利用二分查找在 0 ~ x 之间查找 sqrt。
3、代码实现
class Solution {
public int mySqrt(int x) {
if(x<=1) return x; //当x<=1时，直接返回x
int low = 1,high = x;
while(low <=high){
int mid = low+(high-low)/2;
int sqrt = x/mid;
//二分查找
if(sqrt == mid) return mid;
else if(sqrt<mid) high=mid-1;
else low = mid +1;
}
//循环结束，此时high<low,
return high;
}
}
举例：
1，2，3，4，5，6，7
//第一步
mid = 1+(7-1)/2=4
sqrt =x/mid =7/4=1
sqrt <mid
high =mid-1=3
//第二步
mid=1+(3-1)/2=2
sqrt =x/mid=7/2=3
sqrt>mid
low=mid+1=3
//第三步
mid=3+(3-3)/2=3
sqrt =7/3=2
sqrt<mid
high =mid-1=2
此时high<low退出循环，因此返回high
另参考：
[图片上传失败...(image-ac1dd4-1574054086254)]
33. 搜索旋转排序数组（中等）
1、题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
2、解题思路：
本题要求算法时间复杂度为:O(log(n))、因此，对于这种题目，数组，有序这两个字眼结合起来，就是要第一时间考虑到二分查找。
由于无法确定target,nums[mid]谁大谁小，以及target和nums[mid]到底在前半段，还是在后一段，不同的情况下，对于令left = mid+1还是right = mid-1是不一样的情况，所以这里分情况进行讨论，把所有的情况讨论一遍，然后就知道，到底是变化left还是变化right，进而去缩小这个区间，找到我们要找到的数。
- 如果mid正好等于target，则返回mid
- 条件1：如果mid在大的一边
//条件1：如果mid在大的一边
if(nums[mid]>=nums[left]){
if(target<nums[mid]&&target>=nums[left]){
right=mid-1;
}else{
left =mid+1;
}
}
[图片上传失败...(image-704474-1574054086254)]
- 条件2：如果mid在小的一边
//条件2：如果mid在小的一边
if(nums[mid]<nums[right]){
if(target>nums[mid]&&target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}
[图片上传失败...(image-d0dfce-1574054086254)]
3、代码实现：
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0)
return -1;
int left=0,right=nums.length-1;
while(left <=right){
int mid=left+(right-left)/2;
if(target==nums[mid]) return mid;
//条件1
//如果mid在大的一边
else if(nums[mid]>=nums[left]){
if(target<nums[mid]&&target>=nums[left]){
right=mid-1;
}else{
left =mid+1;
}
}
//条件2
//如果mid在小的一边
else{
if(target>nums[mid]&&target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}
}
return -1;
}
}
81. 搜索旋转排序数组2（中等）
1、题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
2、解题思路
参考https://cloud.tencent.com/developer/article/1358439
这道题与之前Search in Rotated Sorted Array类似，问题只在于存在重复的数。那么和之前那道题的解法区别就是，不能通过比较A[mid]和边缘值来确定哪边是有序的，会出现A[mid]与边缘值相等的状态。当中间值与边缘值相等时，让指向边缘值的指针分别往前移动，忽略掉这个相同点，再用之前的方法判断即可。 而如果解决掉重复之后，利用一个性质，旋转后两部分一定有一部分有序(自己找两个例子画画看)，那么通过判断左边还是右边有序分为两种情况。然后再判断向左走还是向右走。
这一改变增加了时间复杂度，试想一个数组有同一数字组成{1，1，1，1，1}，target=2, 那么这个算法就会将整个数组遍历，时间复杂度由O(logn)升到O(n)。
3、代码实现
class Solution {
public boolean search(int[] nums, int target) {
int left =0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target)
return true;
//和题33比多了一个相等的条件
if(nums[mid]==nums[left]) left++;
else if(nums[mid]>nums[left]){
if(target<nums[mid]&&target>=nums[left]){
right =mid -1;
}else{
left = mid+1;
}
}
else{
if(target>nums[mid]&&target<=nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}
}
return false;
}
}
153. 寻找旋转排序数组中的最小值（中等）
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
2、解题思路
如果nums[mid] < nums[right]，说明若旋转，最小值只能出现在包括中点的左边一段；不旋转也是在左半段。
反之， 即nums[mid]>=nums[right]，说明旋转了，最小值只能出现在不包括中点的右边一段.
最后返回nums[left]或者nums[right].
3、代码实现
class Solution {
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])
//若旋转说明左半段为无序，最小值在左半段;不旋转最小值也在左半段
right =mid;
else{
//说明旋转后右半段序列为无序，则最小值在右半段序列
left =mid+1;
}
}
return nums[right];
}
}
154. 寻找旋转排序数组中的最小值2（困难）
1、题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
2、解题思路
更上一题类似，只不过要去掉重复元素
3、代码实现
class Solution {
public int findMin(int[] nums) {
int left =0,right=nums.length-1;
while(left <right){
int mid = left+(right-left)/2;
if(nums[mid]<nums[right])
right =mid;
else if(nums[mid]>nums[right]){
left = mid+1;
}else{
right--;//去掉重复元素
}
}
return nums[right];
}
}
35. 搜索插入位置（简单）
1、题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2示例 2:
输入: [1,3,5,6], 2 输出: 1示例 3:
输入: [1,3,5,6], 7 输出: 4示例 4:
输入: [1,3,5,6], 0 输出: 0
2、解题思路
用二分查找寻找目标值，如果找到了则返回下标，如果没找到，返回left即可。
3、代码实现
class Solution {
public int searchInsert(int[] nums, int target) {
int left =0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(target == nums[mid]) return mid;
if(target<nums[mid]){
right=mid-1;
}
else{
left =mid+1;
}
}
return left;
// if(target<nums[0]){
// return 0;
// }
// if(target>nums[nums.length-1]){
// return nums.length;
// }
// if(target!=nums[left]){
// return left;
// }
// return -1;
}
}
378. 有序矩阵中第k小的元素（中等，有点难）
1、题目描述
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2
2、解题思路
- 暴力法（不符合题意）
- 二分：参照LeetCode第一个题解
二分：
3、代码实现
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int row = matrix.length-1;
int col = matrix[0].length-1;
int left = matrix[0][0];
int right = matrix[row][col];
while (left < right) {
// 每次循环都保证第K小的数在start~end之间，当start==end，第k小的数就是start
int mid = (left + right) / 2;
// 找二维矩阵中<=mid的元素总个数
int count = computeK(matrix, mid);
if (count <k) {
// 第k小的数在右半部分，且不包含mid
left = mid + 1;
} else {
// 第k小的数在左半部分，可能包含mid
right = mid;
}
}
return right;
}
//类似于剑指offer第一题：在二维数组中的查找
private int computeK(int[][] matrix, int mid) {
// 以行为单位找，找到每一行最后一个<=mid的数即知道每一行有多少个数<=mid
int row =0;
int col =matrix[0].length-1;
int count=0;
while(row<matrix.length && col>=0){
if(matrix[row][col] <= mid){
count +=col+1; //如果当前数小于mid，则前面的数都小于mid，计算count。
row++; //往下一行找
}else{
col--;
}
}
return count;
}
}
287. 寻找重复数（中等）
1、题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2示例 2:
输入: [3,1,3,4,2] 输出: 3
2、解题思路
- 二分法
- 本题有更好的解法
1、二分法：
小于O(n^2)，使用二分查找 我们不要考虑数组,只需要考虑 数字都在 1 到 n 之间 示例 1: arr = [1,3,4,2,2] 此时数字在 1 — 5 之间 mid = (1 + 5) / 2 = 3 arr小于等于的3有4个(1,2,2,3)，1到3中肯定有重复的值 mid = (1 + 3) / 2 = 2 arr小于等于的2有3个(1,2,2)，1到2中肯定有重复的值 mid = (1 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值 所以重复的数是 2
3、代码实现
1、二分法
class Solution {
public int findDuplicate(int[] nums) {
int left=1;
int right=nums.length;
while(left <right){
int mid =left+(right-left)/2;
int count =0;
for(int i=0;i<nums.length;i++){
if(nums[i]<=mid){
count++;
}
}
if(count<=mid)
left=mid+1;
else
right =mid;
}
return left;
}
}
3. 总结
如果题目中出现有序数组，查找这些关键词，并且时间复杂度要求为o(logn)时，可能就是在暗示使用二分查找。
二、贪心思想
1、算法思想
贪心思想保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
2.题目
455. 分配饼干（简单）
1、题目描述
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 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.
2、解题思路
因为最小的孩子最容易得到满足，因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子，这样大饼干就能拿来给满足度比较大的孩子。（证明看算法.md）
3、代码实现
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i =0,j=0;
while(i<g.length&&j<s.length){
if(g[i]<=s[j])
i++;
j++;
}
return i;
}
}
452. 投飞镖刺破气球
1、题目描述
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量
Example:
输入: [[10,16], [2,8], [1,6], [7,12]] 输出: 2 解释: 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
2、解题思路
先进行转化，变为按照区间结束点进行从小到大排序，得到排序后数组。
-
从数组的第二个元素开始遍历：
若起始点小于等于上个区间的结束点，则说明重叠，共用一支箭即可；若起始点大于上个区间的结束点，则说明不重叠，需要另外一支箭来解决。
3、实现代码
class Solution {
public int findMinArrowShots(int[][] points) {
if(points.length == 0) return 0;
Arrays.sort(points,(a,b)->(a[1]-b[1]));
int curend = points[0][1];
int arrow = 1;
for(int i=1;i<points.length;i++){
if(points[i][0]<=curend)
continue;
curend=points[i][1];
arrow++;
}
return arrow;
}
}
122、股票的最大收益Ⅱ
1、题目描述
2、解题思路
对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加加到收益中，从而在局部最优的情况下也保证全局最优。
3、实现代码
class Solution {
public int maxProfit(int[] prices) {
int maxprofit =0;
for(int i=1;i<prices.length;i++){
if(prices[i-1]<prices[i]){
maxprofit +=prices[i]-prices[i-1];
}
}
return maxprofit;
}
}
605、种植花朵
1、题目描述
花朵之间至少有一个单位的间隔。
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
2、解题思路
如果有连续的3个0，则中间的0可以种植花朵。==注意首尾的特殊处理。==
3、代码实现
// 思路：找三个连续的0
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int nums=0;
for(int i=0;i<flowerbed.length;i++){
if(flowerbed[i]==1) continue;
int pre=i==0?0:flowerbed[i-1];
int next=i==flowerbed.length-1?0:flowerbed[i+1];
if(pre==0&&next==0){
nums++;
flowerbed[i]=1;
}
}
return nums>=n; // 注意一下
}
}
3、总结（待补）
三、动态规划
1、算法思想
递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解。
2、题目
121、 股票的最大收益（思考）
参考：https://mp.weixin.qq.com/s/KVNfoRscId0YlrSC3pYCPA
1、题目描述
2、解题思路
dp[i] 表示为第 i + 1 天可获得的最大利润;
此时最大利润可能是下述两种情况：
当前卖出的的情况是prices[i]-最低价
-
不是当天卖出的情况是dp[i-1]，于是dp[i] = max(prices[i]-最低价, dp[i-1]);
dp中只与前一个元素有关，可以写成简化空间复杂度的写法:max_profit = max(prices[i]-最低价, max_profit)。
比如输入: [7,1,5,3,6,4];
i = 0, min_price = 7, dp[0] = 0;
i = 1, min_price = 1, dp[1] = min(0, 0) = 0;
i = 2, min_price = 1, dp[2] = min(5 - 1, 0) = 4;
i = 3, min_price = 1, dp[3] = min(3 - 1, 4) = 4;
i = 4, min_price = 1, dp[4] = min(6 - 1, 4) = 5;
i = 5, min_price = 1, dp[5] = min(4 - 1, 5) = 5;
3、实现代码
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0) return 0;
int minprice=Integer.MAX_VALUE;
int maxprofit = 0;
for(int i=0;i<prices.length;i++){
minprice = Math.min(minprice,prices[i]);
maxprofit = Math.max(prices[i]-minprice,maxprofit);
}
return maxprofit;
}
}
