LeetCode977.有序数组的平方
● 今日学习的文章链接和视频链接
题目链接
● 自己看到题目的第一想法
昨天正好做了这道题目，总体来说就是用双指针法，要么从绝对值最小的数开始排序，要么从绝对值最大的数开始排序。
如果是从绝对值最小的数开始排序，那么就要先找到负数和整数的交界点，然后从这个交界点开始左指针往左，右指针往右以此比较；这里需要注意的是，当比较的时候发现一个指针开始超出数组的范围了，就可以开始只移动一个方向的指针，因此while循环的判断条件是只要有一个指针还在当前数组中就可以，我们的目的是把数组中所有的数都遍历到；也正是因此，if中的判断要先行判断指针的位置，才能进行后续的对数组下标取元素的操作，这个顺序是很重要的。
如果是从绝对值最大的数开始排序，那么指针分别从头和尾开始比较就可以了，把元素从最大的开始放进新数组，代码写起来会简洁很多，因此是一个更好的思路。
两个方法都需要借助O(n)的空间复杂度来保存新的数组，但是时间复杂度比通过排序要优秀一些，仅为O(n)
public class LeetCode977 { public int[] sortSquares(int[] arr) { int neg = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] < 0) { neg = i; } else { break; } } int[] res = new int[arr.length]; int index = 0; int left = neg; int right = neg + 1; while (left >= 0 || right < arr.length) { //任意一个指针还在这个循环里都可以 //我们要做的就是把所有的数都遍历完 if (left < 0) { //当左指针先跳出了数组，就要开始只移动右指针了 res[index] = arr[right] * arr[right]; right++; } else if (right == arr.length) { //当右指针先跳出了数组，就要开始只移动左指针了 res[index] = arr[left] * arr[left]; left--; } //只要左指针或者右指针跳出循环了，就不会再进入下面的判断逻辑了 else if (Math.abs(arr[left]) <= Math.abs(arr[right])) { res[index] = arr[left] * arr[left]; left--; } else if (Math.abs(arr[left]) > Math.abs(arr[right])) { res[index] = arr[right] * arr[right]; right++; } index++; } return res; } //还是第二个方法比较妙，从最大的开始比较而不是从最小的比 //这样就省去了很多麻烦 public int[] sortSquares2(int[] arr) { int[] res = new int[arr.length]; for (int i = 0, j = arr.length - 1, index = arr.length - 1; i <=j;) { if (Math.abs(arr[i]) > Math.abs(arr[j])) { res[index] = arr[i] * arr[i]; i++; } else { res[index] = arr[j] * arr[j]; j--; } index--; } return res; } }
● 看完代码随想录之后的想法
题解主要聚焦在第二种方法
● 自己实现过程中遇到哪些困难
初次实现的时候没有想到可以在一个while循环中完成所有数的遍历，而是在一个指针走到尽头后，在循环外面继续判断是哪一个指针走到尽头了，后来发现这个判断可以统一在循环内层的判断逻辑中。
并且也没有能想到第二种方式，即从绝对值大的数开始排。
● 今日收获，记录一下自己的学习时长
0.3h
LeetCode209.长度最小的子数组
● 今日学习的文章链接
题目链接
● 自己看到题目的第一想法
一开始只想到暴力解法，但是在长度统计的地方都走了一些弯路，忽略了当前子数组长度可以直接通过下标来计算，并且只需要在大于target的时候再去比较min和当前长度，如果本轮计算根本没有到达target那么都不需要进行此轮运算。
//暴力解法，同样有需要注意的地方 public static int minSumArrayLen(int target, int[] arr) { int min = arr.length + 1; int len; for (int i = 0; i < arr.length; i++) { int sum = 0; for (int j = i; j < arr.length; j++) { sum += arr[j]; if (sum >= target) { len = j - i + 1;//根据下标就可以知道子数组的长度 min = Math.min(len, min);//每一次都比较当前轮的len是否更小 break; } //说明没有到达target,需要继续往后添加元素 //有可能到最后一个元素仍未到达target，此时直接舍弃该轮的统计值 } } if (min <= arr.length) { return min; } return 0; }
那么用双指针做就可以只用一轮循环就完成判断，具体思路就是每次移动右指针把新的数加入数组中计算，一旦达到了target，就开始移动左指针，直到左指针和右指针之间的数又跌破了target。就继续开始移动右指针，这里再仔细地思考一下，为什么左指针可以不断进行右移（只要数组中的和大于target）？换个角度思考这个指针，右指针代表终止位置，左指针代表起始位置，如果不考虑大于target的条件限制，我们可以取到的子数组一共有n!个。当右指针固定的时候，左指针右移之后不需要再回头，如果它还要再回到开始的位置，再往右移动指针，子数组的长度只会增加不会减少。这就好比开工没有回头箭，左指针往后走了，就只考虑它后面的新元素了。
说的有点绕，总结一下就是一开始没明白为什么在循环中左指针可以一直往后，其实就是可以一边判断一边舍弃左边元素的意思，由于我们要求的子数组总是最短的，所以起始指针只会不断往右移动。
public static int minSumArrayLen2(int target, int[] arr) { int i = 0; int sum = 0; int min = arr.length + 1; for (int j = 0; j < arr.length; j++) { sum += arr[j]; while (sum >= target) { int len = j - i + 1; min = Math.min(len, min); sum -= arr[i];//挪动左指针，把左边的元素排除掉 i++;//重新计算子数组长度 } //如果sum不满足条件，则继续移动右指针把新的元素加进来计算 } if (min > arr.length) { return 0; } return min; }
● 看完代码随想录之后的想法
主要提到了把j指针当作起始位置还是终止位置，其实还没太明白为什么这么思考
● 自己实现过程中遇到哪些困难
一开始写的循环是if里面又套了一个while判断，发现代码写起来很绕且有重复，经过调试之后发现只需要while循环判断就可以了
● 今日收获，记录一下自己的学习时长
1.5h
LeetCode59.螺旋矩阵II
● 今日学习的文章链接
题目链接：
● 自己看到题目的第一想法
要把数一个一个的往二维数组里填，那么怎么样的遍历顺序才能达到这种顺时针填充的效果呢？这让我难住了，普通的顺序遍历根本就无法满足这个要求啊。于是我去稍微看了一下卡尔的思路，说这道题要用模拟，于是我就开始尝试先把最外层填充起来，看看能不能找到规律，于是我一边写for循环一边发现，欸当填完外层后内层填充的逻辑也是一样的，那我是不是可以把这个过程抽象成一个函数然后循环一下？只要改变每次传入函数的起始位置就可以了。于是一边debug一边改，最后就写出来了。我在写的时候发现循环终止的位置可以统一不放进来，这样每条边遍历的个数就是一样的，于是凭着感觉这么写，后面听卡尔讲的时候也是如此，这样会清晰一些。倒也不是不规则的遍历做不出来，应该是容易写的很乱。
第一版代码：
class Solution { public int[][] generateMatrix(int n) { int[][] arr = new int[n][n]; int num = 1; int start = 0; int len = n; while (len > 0) { if (len == 1) { arr[start][start] = num; break; } num = insertLoop(start, len, arr, num); start++; len -= 2;//每一轮矩阵的长度会减2 } return arr; } private int insertLoop(int start, int len, int[][] arr, int num) { int i = start; int j; for (j = start; j < start + len - 1; j++) { arr[i][j] = num; num++; } j = start+len - 1; for (i = start; i < start + len - 1; i++) { arr[i][j] = num; num++; } i = start+len - 1; for (j = start + len - 1; j > start; j--) { arr[i][j] = num; num++; } j = start; for (i = start + len - 1; i > start; i--) { arr[i][j] = num; num++; } return num; } }
● 看完代码随想录之后的想法
可以发现我用的是矩阵的长度作为遍历条件，并且每次都给循环变量重新赋值。但是实际上，随着变量的自增，它自然会从start来到我们所需要的位置。并且对于边长为基数的矩阵，我在debug的时候发现进不去循环中的赋值条件，于是基数矩阵的中心总是会被落下来。于是需要一个额外的逻辑处理一下。那么其实只要在最后判断一下n是否为奇数，如果为奇数再最后补一下中心的值就可以了。
class Solution { public int[][] generateMatrix(int n) { int[][] arr = new int[n][n]; int num = 1; int start = 0; int end = n - 1;//这两个表示起始和终止的下标 while (start < n / 2) { num = insertLoop(start, end, arr, num); start++; end--;//每一轮的起始下标右移一格，终止下标左移一格 } if (n % 2 == 1) { arr[n / 2][n / 2] = num; } return arr; } private int insertLoop(int start, int end, int[][] arr, int num) { int i = start; int j = start;//i和j从左上角出发 for (; j < end; j++) { arr[i][j] = num; num++; } for (; i < end; i++) { arr[i][j] = num; num++; } //i和j都走到了右下角 for (; j > start; j--) { arr[i][j] = num; num++; } for (; i > start; i--) { arr[i][j] = num; num++; } return num; } }
● 自己实现过程中遇到哪些困难
这道题初次做的时候需要不断地调试才可以得到满意的答案，但是只要想通了每一圈的处理逻辑是一样的就可以
● 今日收获，记录一下自己的学习时长
1.5h
总结：
为了便于后续复习，在这里记录一些问题：
1.数组基础
- 数组的优点的是？
在内存上是连续存储，这样可以基于下标直接计算地址访问内存
- 数组的缺点是？
一旦初始化长度就确定了，而且必须要给出初始长度。但是这样对于使用是很不方便的，于是继续开发集合类，虽然它的底层实现也还是数组，但是可以支持动态扩容，这是基于拷贝来实现的。
- Java中二维数组的存储一定是连续的吗？
不一定，二维数组是数组的数组，其中外部数组的存储是连续的，每一个内部数组里面的元素存储也是连续的，但是打印每一个内部数组的地址值会发现并不连续。因此，内部数组的长度可以是不一样的，具体可以看图。但是，在C++中二维数组在地址空间上是连续的，（也就是说在内存中可以看成是一维连续的）
2.二分查找
- 什么时候二分查找会失效？
如果数组不是有序的，或者数组中有重复的元素
- 什么是循环不变量？
就是每次处理问题的区间，对于不同定义的区间，处理问题的逻辑一定要有一致性。比如说，我直观的就会取左闭右闭的区间，那么二分得到了mid，不管是取左边的一半还是取右边的一半，还是要取闭区间，所以最外层的判断条件一定是i<=j，要把区间内的元素包含进来
3.移除元素
- 数组的删除是靠什么实现的？
虽然库函数封装了删除的相关api，但是实际上由于数组的长度一经确定就无法改变，所以底层其实是通过维护一个size值来表示当前数组的大小的，所以删除操作是通过对删除位置的覆盖来完成的。
4.双指针
- 双指针的好处是什么
在删除数组的特定值中，如果暴力循环要两层遍历。但是会发现其实每一次不用移动那么多元素。因此，双指针可以解决这样的问题，只需要一次遍历，快指针用来判断当前元素是否属于新数组，慢指针用来更新新数组的元素，这样就为我们节省了很多不必要的移动操作。
解决删除数组的重复元素同样是用这样的思路，快指针判断当前的元素是否为数组的元素，慢指针来更新
5.滑动窗口
- 滑动窗口的好处是什么
同样是可以减少遍历的次数，降低时间复杂度。同样是用到两个指针表示当前窗口的大小，但是和双指针的区别是判断的条件在于区间内部的所有元素。在求长度最小的数组中，窗口的左边界是只会向右移动的，需要想明白为什么
6.模拟行为
- 螺旋矩阵怎么思考
考虑赋值的过程很难一次想清楚，所以需要发现规律，找到共通的地方。最重要的是要发现这是一个模拟问题，并不是算法问题。
● 今日收获，记录一下自己的学习时长
1.2h