代码随想录第二天｜数组part02

开始时间10:30
209.长度最小的子数组
题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。  拓展题目可以先不做。
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.长度最小的子数组.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
题目感想：
题目讲解中很精髓的一句话，滑动窗口其实就是双指针，这个让我很好理解，首先因为要进行滑动，所以我们的循环代表的指针用来决定窗口结束位置，每次right指针向右一动一位，我们就把这一位加入sum，直到sum大于等于目标值，此时我们统计两个指针之间的距离，并和之前保留的距离相比，如果更小则更新最短距离，然后我们需要将sum减去left指针所在的数值，left向右移动一位，之后再进行sum比较的循环，如果小于目标值，则right继续滑动，又将新的数值添加进sum，再次进入sum比较循环，如此反复，直到right指针到了数组末尾无法继续移动；

1. int left = 0;
2.         int sum = 0;
3.         int result = Integer.MAX_VALUE;
4.         for (int right = 0; right < nums.length; right++) {
5.             sum += nums[right];
6.             while (sum >= s) {
7.                 result = Math.min(result, right - left + 1);
8.                 sum -= nums[left++];
9.             }
10.         }
11.         return result == Integer.MAX_VALUE ? 0 : result;

复制代码

59.螺旋矩阵II
题目建议：  本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.螺旋矩阵II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
题目感想：
1.首先就是面对循环时一定要遵循循环不变量原则，我的理解是如果有多个循环，然后你又不遵循循环不变量，那么每个循环拿到前一个循环传过来的值的时候，想要进行处理就得又重新写一套逻辑，之后每个循环都需要重新写，而且还不是统一的逻辑，不仅让数据处理的难度大大上升，同时代码的可复用程度大大下降，所以为了降低逻辑设计的复杂度，我们要保证每个变量的更新以及截止是有统一标准的；
2.然后就是我们要确定循环的思路，大体思路是，一圈一圈循环，然后就是每一圈都会有上下左右四个循环，为此，我们需要的循环逻辑有了，然后就是定义所需要的变量，循环的圈数（这里要注意，循环的最大圈数是二维数组阶数/2），遍历用的i，j也就是横纵坐标，每一圈遍历的起始点同时也是用来控制上下左右循环的截止变量，还有控制每圈遍历的长度的offset（其实可以用圈数来，不过单独弄一个变量来表示会更加清楚），最后要考虑特殊情况，也就是二维数组是奇数阶，最中心的那个位置需要我们单独进行填充；

1. int[][] nums = new int[n][n];
2.         int startX = 0, startY = 0;  // 每一圈的起始点
3.         int offset = 1;
4.         int count = 1;  // 矩阵中需要填写的数字
5.         int loop = 1; // 记录当前的圈数
6.         int i, j; // j 代表列, i 代表行;
8.         while (loop <= n / 2) {
10.             // 顶部
11.             // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
12.             for (j = startY; j < n - offset; j++) {
13.                 nums[startX][j] = count++;
14.             }
16.             // 右列
17.             // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
18.             for (i = startX; i < n - offset; i++) {
19.                 nums[i][j] = count++;
20.             }
22.             // 底部
23.             // 左闭右开，所以判断循环结束时， j != startY
24.             for (; j > startY; j--) {
25.                 nums[i][j] = count++;
26.             }
28.             // 左列
29.             // 左闭右开，所以判断循环结束时， i != startX
30.             for (; i > startX; i--) {
31.                 nums[i][j] = count++;
32.             }
33.             startX++;
34.             startY++;
35.             offset++;
36.             loop++;
37.         }
38.         if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
39.             nums[startX][startY] = count;
40.         }
41.         return nums;
42.     }

复制代码

区间和
前缀和是一种思维巧妙很实用 而且 很有容易理解的一种算法思想，大家可以体会一下
文章讲解：https://www.programmercarl.com/kamacoder/0058.区间和.html
题目感想：
1.区间和就是输入一个数组然后求某两个索引之间的数字的总和，我们在输入的时候，就对数量进行累加，设定一个sum，每输入一个数字就往区间和数组里面加，加了之后区间和数组的索引就向右移动，如此反复；
2.需要注意的是，如果给的索引是0和某个索引，那直接就能得出来了，不用多说，如果给的是两个非0索引，那我们需要考虑好如何算，如3和7，3所在的数字需要包括在内的，所以我们需要用7的区间和减去2的区间和，理解不了的自己画图就明白了。
3.由于是acm需要自己处理输入输出，这个需要注意一下，下面的代码是基于输入的索引先输入左边的再输入右边的写的，如果需要拓展那就自己加逻辑
4.区间和就是把能算的先进行了计算，简化了后续的遍历统计计算，反应更快了

1. Scanner scanner = new Scanner(System.in);
3.         int n = scanner.nextInt();
4.         int[] vec = new int[n];
5.         int[] p = new int[n];
7.         int presum = 0;
8.         for (int i = 0; i < n; i++) {
9.             vec[i] = scanner.nextInt();
10.             presum += vec[i];
11.             p[i] = presum;
12.         }
14.         while (scanner.hasNextInt()) {
15.             int a = scanner.nextInt();
16.             int b = scanner.nextInt();
18.             int sum;
19.             if (a == 0) {
20.                 sum = p[b];
21.             } else {
22.                 sum = p[b] - p[a - 1];
23.             }
24.             System.out.println(sum);
25.         }
27.         scanner.close();
28.     }

复制代码

开发商购买土地
https://www.programmercarl.com/kamacoder/0044.开发商购买土地.html
题目感想：
1.一开始没怎么看懂怎么进行划分，后面才知道只能划一次，要么纵向要么横向，所以我们可以从横纵两个方面分开讨论，看看能不能的出最小的差；
2.土地差值就是土地的总份额-左边的份额=右边的份额，再用右边的份额-左边的份额得出差值，连起来就是土地总份额-左边的份额*2，这是纵向切割的，横向切割的同理可得；
3.统计部分就是先算出每一行和每一列的土地份额，之后在依此比较差值即可；

1. Scanner scanner = new Scanner(System.in);
2.         int n = scanner.nextInt();
3.         int m = scanner.nextInt();
4.         int sum = 0;
5.         int[][] vec = new int[n][m];
6.         for (int i = 0; i < n; i++) {
7.             for (int j = 0; j < m; j++) {
8.                 vec[i][j] = scanner.nextInt();
9.                 sum += vec[i][j];
10.             }
11.         }
13.         // 统计横向
14.         int[] horizontal = new int[n];
15.         for (int i = 0; i < n; i++) {
16.             for (int j = 0; j < m; j++) {
17.                 horizontal[i] += vec[i][j];
18.             }
19.         }
21.         // 统计纵向
22.         int[] vertical = new int[m];
23.         for (int j = 0; j < m; j++) {
24.             for (int i = 0; i < n; i++) {
25.                 vertical[j] += vec[i][j];
26.             }
27.         }
29.         int result = Integer.MAX_VALUE;
30.         int horizontalCut = 0;
31.         for (int i = 0; i < n; i++) {
32.             horizontalCut += horizontal[i];
33.             result = Math.min(result, Math.abs(sum - 2 * horizontalCut));
34.         }
36.         int verticalCut = 0;
37.         for (int j = 0; j < m; j++) {
38.             verticalCut += vertical[j];
39.             result = Math.min(result, Math.abs(sum - 2 * verticalCut));
40.         }
42.         System.out.println(result);
43.         scanner.close();

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！