LeetCode刷题琐碎笔记
LeetCode
其他知识
访问修饰符public,private,protected
类的成员不写访问修饰时默认为default。默认对于同一个包中的其他类相当于公开（public），对于不是同一个包中的其他类相当于私有（private）。受保护（protected）对子类相当于公开，对不是同一包中的没有父子关系的类相当于私有。
总结如下表
版权声明：本文为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,1
public 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1 | |
优化 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.滑动窗口问题如果一下子没有思路，先考虑暴力解法，然后再纸上写写画画，进而考虑优化的解法，通常考虑「剪枝」或者「空间换时间」。
1 | |
1 | |
双指针
1 | |
快速幂
