代码随想录第二天｜数组part02
开始时间10:30209.长度最小的子数组
题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。拓展题目可以先不做。
题目链接：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指针到了数组末尾无法继续移动；
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums;
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums;
}
}
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（其实可以用圈数来，不过单独弄一个变量来表示会更加清楚），最后要考虑特殊情况，也就是二维数组是奇数阶，最中心的那个位置需要我们单独进行填充；
int[][] nums = new int;
int startX = 0, startY = 0;// 每一圈的起始点
int offset = 1;
int count = 1;// 矩阵中需要填写的数字
int loop = 1; // 记录当前的圈数
int i, j; // j 代表列, i 代表行;
while (loop <= n / 2) {
// 顶部
// 左闭右开，所以判断循环结束时， j 不能等于 n - offset
for (j = startY; j < n - offset; j++) {
nums = count++;
}
// 右列
// 左闭右开，所以判断循环结束时， i 不能等于 n - offset
for (i = startX; i < n - offset; i++) {
nums = count++;
}
// 底部
// 左闭右开，所以判断循环结束时， j != startY
for (; j > startY; j--) {
nums = count++;
}
// 左列
// 左闭右开，所以判断循环结束时， i != startX
for (; i > startX; i--) {
nums = count++;
}
startX++;
startY++;
offset++;
loop++;
}
if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
nums = count;
}
return nums;
}区间和
前缀和是一种思维巧妙很实用 而且 很有容易理解的一种算法思想，大家可以体会一下
文章讲解：https://www.programmercarl.com/kamacoder/0058.区间和.html
题目感想：
1.区间和就是输入一个数组然后求某两个索引之间的数字的总和，我们在输入的时候，就对数量进行累加，设定一个sum，每输入一个数字就往区间和数组里面加，加了之后区间和数组的索引就向右移动，如此反复；
2.需要注意的是，如果给的索引是0和某个索引，那直接就能得出来了，不用多说，如果给的是两个非0索引，那我们需要考虑好如何算，如3和7，3所在的数字需要包括在内的，所以我们需要用7的区间和减去2的区间和，理解不了的自己画图就明白了。
3.由于是acm需要自己处理输入输出，这个需要注意一下，下面的代码是基于输入的索引先输入左边的再输入右边的写的，如果需要拓展那就自己加逻辑
4.区间和就是把能算的先进行了计算，简化了后续的遍历统计计算，反应更快了
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] vec = new int;
int[] p = new int;
int presum = 0;
for (int i = 0; i < n; i++) {
vec = scanner.nextInt();
presum += vec;
p = presum;
}
while (scanner.hasNextInt()) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int sum;
if (a == 0) {
sum = p;
} else {
sum = p - p;
}
System.out.println(sum);
}
scanner.close();
}开发商购买土地
https://www.programmercarl.com/kamacoder/0044.开发商购买土地.html
题目感想：
1.一开始没怎么看懂怎么进行划分，后面才知道只能划一次，要么纵向要么横向，所以我们可以从横纵两个方面分开讨论，看看能不能的出最小的差；
2.土地差值就是土地的总份额-左边的份额=右边的份额，再用右边的份额-左边的份额得出差值，连起来就是土地总份额-左边的份额*2，这是纵向切割的，横向切割的同理可得；
3.统计部分就是先算出每一行和每一列的土地份额，之后在依此比较差值即可；
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int sum = 0;
int[][] vec = new int;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
vec = scanner.nextInt();
sum += vec;
}
}
// 统计横向
int[] horizontal = new int;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
horizontal += vec;
}
}
// 统计纵向
int[] vertical = new int;
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
vertical += vec;
}
}
int result = Integer.MAX_VALUE;
int horizontalCut = 0;
for (int i = 0; i < n; i++) {
horizontalCut += horizontal;
result = Math.min(result, Math.abs(sum - 2 * horizontalCut));
}
int verticalCut = 0;
for (int j = 0; j < m; j++) {
verticalCut += vertical;
result = Math.min(result, Math.abs(sum - 2 * verticalCut));
}
System.out.println(result);
scanner.close();
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]