开始刷一下算法，目标是leetcode的热题100，从数组开始！希望大家共同进步！
1.二分法查找
链接：二分查找
二分法：快速找到目标值的位置，前提是数组是有序的
1：标明两个指针，计算数组的中间值，头指针指向数组头部，尾指针指向数组尾部
2：用目标值与中间值进行比较，会出现三个结果
（1）目标值 > 中间值，则证明目标值在中间值的右边
（2）目标值 < 中间值，则证明目标值在中间值的左边
（3）目标值 = 中间值，则证明目标值在中间值
3：对上述三种结果进行对应的处理
（1）移动左指针到中间值的右边，因为中间值已经比较过了，所以，左指针 = 中间值 + 1
（2）移动右指针到中间值的左边
（3）直接返回
4：移动之后我们重复 1 2两步的操作，直到得到 目标值 = 中间值
注意的点：循环条件我们需要判断好，当左指针大于右指针的时候终止循环
代码如下：
public class BinarySearch {/*** 二分法查找*/public int search(int[] nums, int target) {//数组的长度int length = nums.length;//数组左界限int left = 0;//数组右界限int right = length - 1;//因为右界限大于左界限，所以当left大于或等于right的时候，证明没有可分界的值while (left <= right) {//每次循环的数组中间值int mid = left + (right - left) / 2;//中间值正好为目标值if (nums[mid] == target) {return mid;// 1 2 3 4 5 6 7 目标值小于中间值，证明目标值在左边} else if (nums[mid] > target) {right = mid - 1;// 1 2 3 4 5 6 7 目标值大于中间值，证明目标值在右边} else {left = mid + 1;}}return -1;}}
2.移除元素
链接：移除元素
1：标明两个指针，一个为快指针，一个为慢指针，快指针负责遍历数组，慢指针负责元素覆盖
2：快指针先移动，慢指针再移动，会出现两种情况
（1）当快指针指向的元素为目标元素时，快指针继续遍历移动，慢指针停止移动
（2）快指针指向的元素不为目标元素时，让慢指针的当前索引位元素变为快指针当前指向的元素，然后慢指针移动
3：返回慢指针
举例：12334，删除3
快慢指针都指向1，元素未改变，慢指针移动，快指针移动遍历
快慢指针都指向2，同上
快慢指针都指向3，属于第一种情况，快指针移动遍历，慢指针停止保存当前位置
快指针指向4，属于第二种情况，慢指针将4写入到3的当前位置，进行元素覆盖，然后慢指针移动
为什么返回慢指针，因为慢指针所遍历的是修改后的数组长度，大家可以想一想，比如说
1233334，返回的结果应该是3，快指针一定会遍历到最后，而慢指针此时会在第一个3时停下，索引位为2，完成覆盖后进移动，返回结果为3
代码如下：
public class ElementDeletion {/*** 删除数组指定位置元素*/public int remove(int[] nums, int val) {//快慢双指针//慢指针：进行元素覆盖int slow = 0;//快指针：获取元素值int fast;//循环查找，如果是目标元素，快指针移动，而慢指针不动且指向目标元素的索引位，直到快指针指向非目标元素，进行元素覆盖for (fast = 0; fast < nums.length; fast++) {if (nums[fast] != val) {nums[slow] = nums[fast];slow++;}}return slow;}
}
3.合并区间
链接：合并区间
这道题有点复杂，要理清一下思路
比如说[1,3]，[2,6]最后得到的结果为[1,6]
[1,3] [3,6]得到的结果为[1,3],[3,6]
这里发现只需要判断，前一个数组的第二个位置的元素 和 后一个数组的第一个元素大小就可以了
（1）前数组的尾部 < 后数组的头部，不用进行合并
（2）前数组的尾部 > 后数组的头部，进行合并
合并格式为 [ 前数组的头部，（前数组和后数组尾部最大值） ]
实现的思路：
1.将数组进行排序，排序的规则为，第一个元素的大小，进行升序排列
2.声明结果集合，用于返回和规则判断
3.遍历所有数组
（1）结果集合为空或者是第（1）种情况，我们将遍历的数组添加到结果集合
（2）第（2）种情况，我们比较前数组的尾部和当前数组的尾部哪个大，然后进行进行合并
代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;public class MergeIntervals {/*合并区间*/public int[][] merge(int[][] intervals) {//对二维数组的头节点进行排序Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});List<int[]> result = new ArrayList<>();for (int[] interval : intervals) {if (result.isEmpty() || result.get(result.size() - 1)[1] < interval[0]) {result.add(interval);} else {int[] ints = result.get(result.size() - 1);ints[1] = Math.max(ints[1], interval[1]);}}return result.toArray(new int[result.size()][2]);}
}
4.最大子数组和
这里使用的算法叫贪心算法，去遍历所有的元素，算出局部数组最大的和，将这些局部最大的和加在一起，就是我们的目标，整个数组的最大连续子数组和
举例：1 3 -1 -5 2 -5
首先遍历到1，这时开启连续子数组，当前的最大和为1
然后遍历到2，当前最大和为 1+3 = 4
遍历到-1，4 - 1 = 3，当前连续数组为 1，3，-1 ，当前连续数组和为3，最大数组和还是4
遍历到-4，因为 3 - 5 < 0，当前连续数组停止，我们重新开始一个连续数组，因为无论后面的数是正数还是负数，都没有意义了，只要连续和还是正数就会 对后面的元素 起到增大总和的作用。 所以只要连续和为正数我们就保留，负数就重置连续和。
代码如下：
public class MaxSubArray {/*最大子数组和*/public int maxSubArray(int[] nums) {//返回的最大值int result = Integer.MIN_VALUE;int sum = 0;for (int num : nums){if (sum < 0){sum = 0;}sum = sum + num;result = Math.max(result,sum);}return result;}
}
5.轮转数组
链接：轮转数组
这道题目是，将所有元素移动指定的次数，比如123456，k=2，就是所有元素向右移动两次
第一次：612345 第二次： 561234
我们可以找一下规律，如果将123456 变成 561234
因为如果靠指针移动，这个复杂度很高，并且很难，所以能想到移动位置的方法，就是反转了
先将数组反转看一下，654321 结果：561234
我们可以观察一下，发现4321经过反转就变成了1234，65反转就变成了56，如果通过反转来实现我们需要经过三次反转
我们的轮转次数为2，而5和6的索引对应的不就是0，1，只需要反转前k个就好了
所以我们只需要反转前k个 和 剩下的n-k
代码如下：
public class RotatingArray {/*轮转数组*/public void rotate(int[] nums, int k){int len = nums.length;k = k % len;reverse(nums,0,len -1);reverse(nums,0,k-1);reverse(nums,k,len-1);}public void reverse(int[] nums, int start, int end){while (start < end){int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}}
首先需要一个反转方法，一个常规的三变量交换赋值，然后在主逻辑里，先将整个数组进行反转，然后再对前k个元素进行反转，最后反转剩下的元素。
这里解释一下为什么需要 k = k % len;
比如轮转123，轮转3次。第一次312，第二次231，第三次123
可以发现轮转的次数为数组的长度时，最后得到的结果是原数组，所以我们需要计算正确的轮转次数
那么当轮转的次数大于数组的长度时，k = len + x，x才是我们实际有效的轮转次数
那么取模就可以帮助我们获得正确的轮转次数。
比如k=8，k%n = 8%3 = 2，我们实际的轮转次数为2
今天的算法就到这里啦，明天会进行链表，哈希，动态规划，双指针，贪心等算法的练习，自己也是在学习的过程中，哪里错了请大家指出，谢谢大家
