刷LeetCode的一些笔记
LeetCode
其他知识
访问修饰符public,private,protected类的成员不写访问修饰时默认为default。默认对于同一个包中的其他类相当于公开（public），对于不是同一个包中的其他类相当于私有（private）。受保护（protected）对子类相当于公开，对不是同一包中的没有父子关系的类相当于私有。
总结如下表
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y1V7iYJk-1682045273898)(LeetCode.assets/Center.png)]
版权声明：本文为CSDN博主「所谓简爱」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_33342248/article/details/54090038
1.二分查找法
思路一：
while(left<=right)
直接找出目标元素
public class Solution {
// 「力扣」第 704 题：二分查找public int search(int[] nums, int target) {int len = nums.length;int left = 0;int right = len - 1;// 目标元素可能存在在区间 [left, right]while (left <= right) {// 推荐的写法是 int mid = left + (right - left) / 2;int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {// 目标元素可能存在在区间 [mid + 1, right]left = mid + 1;} else {// 目标元素可能存在在区间 [left, mid - 1]right = mid - 1;}}return -1;
}
}
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/xsz9zc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.排除不可能区间
思路二时候
1.while(left<right)
2.如果有left=mid,则向上取整mid = (left+right+1) /2
public class Solution {
// 「力扣」第 704 题：二分查找public int search(int[] nums, int target) {int len = nums.length;int left = 0;int right = len - 1;// 目标元素可能存在在区间 [left, right]while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {// 下一轮搜索区间是 [mid + 1, right]left = mid + 1;} else {// 下一轮搜索区间是 [left, mid]right = mid;}}if (nums[left] == target) {return left;}return -1;
}
}
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/xs41qg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.HashMap
时间复杂度o（1）
因为是数组
3.排序·
1.选择排序
2.插入排序
public class Solution {
// 「力扣」第 912 题：排序数组public int[] sortArray(int[] nums) {int len = nums.length;// 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组for (int i = 1; i < len; i++) {for (int j = i; j > 0; j--) {if (nums[j - 1] > nums[j]) {swap(nums, j - 1, j);} else {break;}}}return nums;
}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}
}
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/556rgm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3.希尔排序
升级版的插入排序
import java.util.Arrays;
public class Solution {
// 「力扣」第 912 题：排序数组
// 希尔排序，使用 Shell 建议的序列 N/2,N/4,...,2,1public int[] sortArray(int[] nums) {int len = nums.length;int h = 1;int gap = len / 2;while (gap >= 1) {// 缩小增量的插入排序for (int i = h; i < len; i++) {insertionForDelta(nums, gap, i);}gap /= 2;}return nums;
}/*** 将 nums[end] 插入到对应分组的正确位置上，其实就是将原来 1 的部分改成 gap** @param nums* @param gap 间隔* @param end*/
private void insertionForDelta(int[] nums, int gap, int end) {int temp = nums[end];int j = end;while (j >= gap && nums[j - gap] > temp) {nums[j] = nums[j - gap];j -= gap;}nums[j] = temp;
}
}
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55k961/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
4.归并
编写递归函数，通常要遵守下面的编写模式：
先写递归终止条件；
再假定小规模的问题已经解决（是通过递归解决的）；
最后处理小规模问题已经解决的情况下，与当前问题之间的逻辑联系。
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55ghq7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public int[] sortArray(int[] nums) {int len = nums.length;mergeSort(nums, 0, len - 1);return nums;}private void mergeSort(int[] nums, int left, int right) {if(left == right) {return;}int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);mergeOfTwoSortedArray(nums, left, mid, right);}private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right) {// 合并后数组长度int len = right - left + 1;// 定义新的临时数组int[] temp = new int[len];int i = left;int j = mid + 1;int k = 0;// 从左到右比较两数组的大小，将较小的值添加到temp中while(i <= mid && j <= right) {if(nums[i] <= nums[j]) {temp[k++] = nums[i++];}else {temp[k++] = nums[j++];}}// 剩下的数组元素，可以依次赋值while(i <= mid) {temp[k++] = nums[i++];}while(j <= right) {temp[k++] = nums[j++];}// 将temp排好序的依次赋值给numsint b = 0;for(int a = left; a <= right; a++) {nums[a] = temp[b++];}}作者：豚豚
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55ghq7/?discussion=ngEXjW
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
优化 1：在小区间里使用插入排序
如果区间里只有 22 个元素，例如 [4, 3][4,3]，只要把它们直接交换一下位置就可以了。但是这种情况还太特殊，对于区间里有 33 个元素、44 个元素的情况就不奏效了，一个更直接且有效的做法是：在小区间里使用插入排序。
事实上，在归并排序的子过程里，可以使用插入排序的原因是：
首先，操作的指令数更少；
其次，插入排序也是稳定的排序算法，修改成插入排序并不影响归并排序的稳定性。
当然这个子区间不能很大，子区间在多长的时候转而使用插入排序，这需要通过实验才能知道。学习过机器学习的朋友，就会知道它是一个超参数，目前 Java 语言的库函数将它定义成 4747。
优化 2：子区间本身有序则无需归并
如果这个子区间本身就是有序的，我们没有必要执行归并的过程。
例如：[1, 3, 4, 5, 6, 7, 8, 9]。 在上一节介绍的分治算法的时候，需要将它一分为二，前半部分是 [1, 3, 4, 5]，后半部分是 [6, 7, 8, 9]，事实上这一步是没有必要的。
优化 3：在整个归并的过程中，使用同一个辅助数组
上一节的做法，我们每次归并之前都得创建一个临时数组，在 Java 语言中，使用完以后就会被垃圾回收机制回收。
这个频繁创建数组和销毁数组的过程，有一定性能消耗；
不管是复制数组，还是把归并的结果赋值回去，都得计算偏移量。而事实上，当我们全局使用一个临时数组用于归并的时候，可以省略偏移量的计算。
下面我们就从代码层面讲解如何优化归并排序。
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55gb35/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
优化归并
public class Solution {
/*** 列表大小等于或小于该大小，将优先于 mergesort 使用插入排序*/
private static final int INSERTION_SORT_THRESHOLD = 47;public int[] sortArray(int[] nums) {int len = nums.length;// 优化 3：全局使用一份临时数组int[] temp = new int[len];mergeSort(nums, 0, len - 1, temp);return nums;
}private void mergeSort(int[] nums, int left, int right, int[] temp) {// 优化 1：小区间使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(nums, left, right);return;}int mid = left + (right - left) / 2;mergeSort(nums, left, mid, temp);mergeSort(nums, mid + 1, right, temp);// 优化 2：数组已经有序的情况下，不再合并if (nums[mid] <= nums[mid + 1]) {return;}mergeOfTwoSortedArray(nums, left, mid, right, temp);
}private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {for (int i = left; i <= right; i++) {temp[i] = nums[i];}int i = left;int j = mid + 1;for (int k = left; k <= right; k++) {if (i == mid + 1) {nums[k] = temp[j];j++;} else if (j == right + 1) {nums[k] = temp[i];i++;} else if (temp[i] <= temp[j]) {// 注意：这里一定要写成 <=，否则就变成了非稳定排序nums[k] = temp[i];i++;} else {nums[k] = temp[j];j++;}}
}/*** 对数组给定的部分使用插入排序** @param arr 给定数组* @param left 左边界，能取到* @param right 右边界，能取到*/
private void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = arr[i];int j = i;while (j > left && arr[j - 1] > temp) {arr[j] = arr[j - 1];j--;}arr[j] = temp;}
}
}
作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/55gb35/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
滑动窗口（双指针）
时间复杂度：O(n)
right一直往右移动
如果碰上条件，left就收缩
所以是
时间复杂度是o（n）
空间复杂度是O（1）
1.从暴力解法优化，类似于剪枝法从O(n2)->O(n1)
2.利用的是left固定住之后，right一直向右，只要遇上了重复字符，当前的res就再也不可能变大，于是可以left当前值的循环可以跳过，可以直接left+1
3.滑动窗口问题如果一下子没有思路，先考虑暴力解法，然后再纸上写写画画，进而考虑优化的解法，通常考虑「剪枝」或者「空间换时间」。
class Solution {public int lengthOfLongestSubstring(String s) {int len =s.length();int res = 0;if(len==0)return 0;//[left,right]int left = 0;int right = 0;HashMap<Character,Integer> map = new HashMap<>();for(right = 0;right<len;right++){// right右移map.put(s.charAt(right),map.getOrDefault(s.charAt(right),0)+1);//如果需要，则收缩while(left < right && map.get(s.charAt(right))>=2){map.put(s.charAt(left),map.get(s.charAt(left))-1);left++;}res= Math.max(res,right-left+1);}return res;}
}
public class Solution {public String minWindow(String s, String t) {// 同方向移动，起始的时候，都位于 0，表示我们定义搜索区间为 [left, right) ，此时区间为空区间int left = 0;int right = 0;while (right < sLen) {if ( 在右移的过程中检测是否满足条件 ) {// 对状态做修改，好让程序在后面检测到满足条件}// 右边界右移 1 格right++;while ( 满足条件 ) {// ① 走到这里是满足条件的，左边界逐渐逐渐左移，可以取最小值if ( 在左移的过程中检测是否不满足条件 ) {// 对状态做修改，好让程序在后面检测到不满足条件}// 左边界左移 1 格left++;}// ② 走到这里是不满足条件的，右边界逐渐右移，可以取最大值}return 需要的结果变量;}
}作者：liweiwei1419
链接：https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/x1vsvd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
双指针
class Solution {public int numRescueBoats(int[] people, int limit) {Arrays.sort(people);int len = people.length;int left=0;int right = len-1;int res = 0;while(left<right){//最轻的可以带上最重的if(people[left]+people[right] <=limit){left++;right--;res++;}//最轻的带不上最重的else//最重的只能自己走{right--;res++;}}if(left==right){res++;}return res;}
}