排序
快排
核心思想是选定一个阈值temp
通过左右指针，将比temp小的放左边，比temp大的放右边。
对两个子序列重复排序。
public static void quickSort(int[] nums){
doQuickSort(nums,0,nums.length-1);
}
public static void doQuickSort(int[] nums, int left, int right){
if (left>=right){
return;
}
int temp=nums[left];
int min=left;
int max=right;
while (min<max){
//右指针左移
while (min<max&&nums[max]>=temp){
max--;
}
//将找到的小于标志数的放在左指针上，同时左指针右移
if (min<max){
nums[min]=nums[max];
min++;
}
//左指针右移
while (min<max&&nums[min]<=temp){
min++;
}
//将找到的大于标志数的放在右指针上，同时右指针左移
if (min<max){
nums[max]=nums[min];
max--;
}
}
nums[min]=temp;
doQuickSort(nums,left,min-1);
doQuickSort(nums,min+1,right);
}
二分查找
二分的前提是有序，通过规定两个边界，每次比较中间的值是否是目标值来决定下次边界的范围。
在代码随想录中对边界的总结挺有特点的，在我个人的感知中左开右闭这种处理，既不美观，也不好懂，因此只需要记住left<=right的这种处理就好。
力扣-35搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
public int searchInsert(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 mid;
}else if(nums[mid]>target){
right=mid-1;
}else{
left=mid+1;
}
}
//这里需要思考一下
//当进入到最后一次循环的时候，由于left=right，那么mid=left=right；
//所以对于if的三种情况，第一种相等就直接返回下标.
//后两种，从left角度分析，如果nums[left]>target,那么left正好是要被插入的位置；如果nums[left]<target，那么要插入的位置就是下一个，即left+1，刚好在else中的逻辑就是这样，因此，最后虽然只是return left，但是会根据不同的情况落到不同的位置
// return left
//那如果以right角度分析呢，如果nums[right]>target,那就应该返回right，但是由于在elseif中right-1，因此right还得再加回来即right+1,如果nums[right]<target,那就应该返回right+1；
return right+1;
}
力扣-69x的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
思路:
其实和上面的题一样，换个说法就是在1,x中，寻找sqrt(x)。但是需要额外注意的有两点，
1是返回值，由于返回的是取整的结构，从上面的分析可以知道return left表示的是返回结果将要占得位置，2.x之类的结果会得到3，所以需要返回left-1或者right。
public int mySqrt(int x) {
int left=1,right=x;
while(left<=right){
int mid=left+(right-left)/2;
long sum=(long)mid*mid;
if(sum==x){
return mid;
}else if(sum>x){
right=mid-1;
}else{
left=mid+1;
}
}
return right;
}
双指针
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
使用双指针，start指针用于记录最终的返回结果，当nums[start]和val不等，表示要保留 因此指针要++，反之则表示当前位置的这个值可以被替换，因此需要另一个指针遍历所有值来进行比较
public int removeElement(int[] nums, int val) {
int start=0,cur=0;
while(cur<nums.length){
if(nums[cur]!=val){
nums[start++]=nums[cur];
}
cur++;
}
return start;
}
比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
思路一：
使用双指针覆写的思想，当遇到#代表start指针可以被覆写，和移除元素的思想很像。这种方法也可以使用栈的思想，当不等于#号就入栈，等于#号就弹出顶部的元素。最后比较栈内的结果。
class Solution {
public boolean backspaceCompare(String s, String t) {
return doSolution(s).equals(doSolution(t));
}
public String doSolution(String s){
int start=0,cur=0;
char[] arr=s.toCharArray();
while(cur<s.length()){
if(arr[cur]=='#'){
if(start>0){
start--;
}
cur++;
continue;
}
arr[start++]=arr[cur];
cur++;
}
StringBuilder build=new StringBuilder();
for(int i=0;i<start;i++){
build.append(arr[i]);
}
return build.toString();
}
}
思路二：
上面其实已经用到了双指针，但是会发现必须遍历完整个字符串，才能确定最终是什么，那有没有可能在遍历的过程中直接比较呢？
正着遍历肯定不行，因为比较的时候不清楚后面是不是会删除当前字符，但如果反着遍历呢？
假如反着遍历，当前字符是#，那么表明遇到的下一个不是#的字符要被删除，跳过就好了。
假如字符不是#，那就要看当前字符是否要被删除（即遍历到当前字符的过程中有几个#），要么被删除，要么#号不足保留，同时比较两个字符串每一轮保留的字符，既可以确定是否是相同的字符串了。
另外，两个字符串长度不等也不相同。
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int delI = 0, delJ = 0;
while (i >= 0 || j >= 0) {
//跳出条件为当前不是#，且没有删除标记
while (i >= 0) {
//如果是#号，那么增加删除标记
if (s.charAt(i) == '#') {
delI++;
//如果不是#号，且存在删除标记,那么就减少删除标记,即当前元素被删除
} else if (delI > 0) {
delI--;
//直到不能删除，那就表示这一位一定在了
} else {
break;
}
i--;
}
while (j >= 0) {
if (t.charAt(j) == '#') {
delJ++;
} else if (delJ > 0) {
delJ--;
} else {
break;
}
j--;
}
//如果都没走到头，且当前字符不相等，那表明两个字符串不相等
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) {
return false;
}
//如果只有任意一方走到头，那也表明不相等
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
- 输入：nums = [-7,-3,2,3,11]
- 输出：[4,9,9,49,121]
思路：
首先可以想到通过双指针来比较最左和最右两个位置的平方值，可以得出一个较大值并将指针移动。但是不能在原数组原地移动，因为单纯的交换值并不能做到其他位置一起移动。因此需要额外借助另一个数组，即每次将较大值放入result[n–]中去。
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] resultArray = new int[n];
int left = 0, right = n - 1;
while (left <= right) {
int leftValue = nums[left] * nums[left];
int rightValue = nums[right] * nums[right];
int value = leftValue;
if (leftValue > rightValue) {
left++;
} else {
value = rightValue;
right--;
}
resultArray[--n] = value;
}
return resultArray;
}
}
滑动窗口
长度最小的子数组
看到题之后首先想到的肯定就是滑动窗口了，而滑动窗口基本上也都是双指针实现，通过控制两个指针来表示窗口。因此这个题我们首先要不断右移指针来判断是否满足条件，当满足条件之后再不断缩小窗口（即移动左指针）。
注意看题，题目中说的是总和大于等于 target，而不是等于，如果是等于len那里要额外判断的。
public int minSubArrayLen(int target, int[] nums) {
int start = 0, end = 0;
int sum = 0, len = nums.length;
boolean flag = false;
while (end < nums.length) {
sum = sum + nums[end];
while (sum >= target) {
len = Math.min(len, end - start + 1);
flag = true;
sum -= nums[start];
start++;
}
end++;
}
return flag ? len : 0;
}
水果成篮
依然是滑动窗口算法，但是窗口里记录什么决定了代码怎么写，下面这种方式好理解且简单，窗口中记录的是每个种类出现的次数，这样子，就是简单的移入，移除就可以了。
而如果是记录的每个种类出现的位置，需要额外关心两个点：
第一个是11223和112213这两种情况不同处理，当size大于2的时候，不能简单的移除left，由于不好决定移除哪个，所以就只能clear重新添加了
第二个112213，map获取上次出现的地址，应该获取最新的位置，而不是最开始的位置
这里我取巧了：当两个相邻的元素不同时表明元素位置需要刷新了。
public int totalFruit(int[] fruits) {
int left = 0, right = 0,len=0;
HashMap<Integer, Integer> map = new HashMap<>();
while (right < fruits.length) {
map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
while (map.size() > 2) {
map.put(fruits[left], map.getOrDefault(fruits[left], 0) - 1);
if (map.get(fruits[left]) == 0) {
map.remove(fruits[left]);
}
left++;
}
len=Math.max(len,right-left+1);
right++;
}
return len;
}
public int totalFruit(int[] fruits) {
if(fruits.length<=2){
return fruits.length;
}
int len=0;
int start=0,end=0,n=fruits.length-1;
HashMap<Integer,Integer> kindMap=new HashMap<>();
while(end<=n){
if(!kindMap.containsKey(fruits[end])||
(kindMap.size()==2&&fruits[end]!=fruits[end-1])
){
kindMap.put(fruits[end],end);
}
//当篮子满了的时候
if(kindMap.size()>2){
len=Math.max(len,end-start);
start=kindMap.get(fruits[end-1]);
kindMap.clear();
kindMap.put(fruits[end],end);
kindMap.put(fruits[end-1],start);
}
len=Math.max(len,end-start+1);
end++;
}
return len;
}
螺旋矩阵2
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
主要是边界情况的处理，我习惯的做法是完整写完一个方向后就移动边界。对于这种处理方案，第一次是处理的最上方，因此第一行写完后top要进行++，然后处理最右边这列，right–，以此类推。
public static int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int count = 1, target = n * n;
int left = 0, right = n - 1, top = 0, bottom = n - 1;
int i , j ;
while (count <= target) {
for ( i = left; count <= target&&i <= right; i++) {
result[top][i] = count++;
}
top++;
for ( j = top; count <= target&&j <= bottom; j++) {
result[j][right] = count++;
}
right--;
for ( i = right;count <= target&& i >= left; i--) {
result[bottom][i] = count++;
}
bottom--;
for ( j = bottom; count <= target&&j >= top; j--) {
result[j][left] = count++;
}
left++;
}
return result;
}