![Day 2[代码随想录]长度最小的子数组+螺旋矩阵II+区间和+开发商购买土地+数组总结篇](http://pic.xiahunao.cn/yaotu/Day 2[代码随想录]长度最小的子数组+螺旋矩阵II+区间和+开发商购买土地+数组总结篇)
力扣 209给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。示例输入target 7, nums [2,3,1,2,4,3]输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。提示1 ≤ target ≤ 1091 ≤ nums.length ≤ 1051 ≤ nums[i] ≤ 105暴力做法class Solution { public: int minSubArrayLen(int target, vectorint nums) { int len nums.size(); bool flag false; for (int i 0; i nums.size(); i) { int num 0; int len1 0; for (int j i; j nums.size(); j) { num nums[j]; if (num target) { flag true; len min(len, j - i 1); break; } } } if (!flag) { return 0; } else { return len; } } };不过这个超出了时间限制。滑动窗口法实际上还是一种双指针法起点由于 target 的限制是不可逆的所以说 j 变换的时候 i 的值不会清零重新来。举个例子来说1 2 3 100target 记作 101j0结束位置指针指向 1不够继续j1结束位置指针指向 2不够继续j2结束位置指针指向 3不够继续j3结束位置指针指向 100够了进入 while 循环先算出当前的子串长度len 选择更小的子串长度现在开始移动起始位置指针sum 减去当前初始位置值i 往后移动一位。这是进行一次初始位置指针的移动。然后进入第二次判定还是大于等于 target再来几次这里就省略了。下面进行返回值就好啦。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int i 0; int len n 1; int sum 0; for (int j 0; j n; j) { sum nums[j]; while (sum target) { int sublen j - i 1; len len sublen ? sublen : len; sum - nums[i]; } } if (len n 1) return 0; else { return len; } } };59 螺旋矩阵 II给定一个正整数 n生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。示例输入3 输出[[1, 2, 3], [8, 9, 4], [7, 6, 5]]这个题边界处理比较难要坚持循环不变量原则左闭右开就一直是左闭右开要不循环一定会出错。class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorint num(n, vectorint(n, 0)); int startx 0; int starty 0; int offset 1; int times n / 2; int mid n / 2; int i, j; int count 1; while (times--) { j starty; i startx; for (; j n - offset; j) { num[i][j] count; } for (; i n - offset; i) { num[i][j] count; } for (; j starty; j--) { num[i][j] count; } for (; i startx; i--) { num[i][j] count; } startx; starty; offset; } if (n % 2 ! 0) { num[mid][mid] count; } return num; } };要注意的是当 n 为奇数的时候中间会多出一个格子我们要单独赋值但是我们会出现两种错误想法ij 正好跑到了中间格子我们直接用 ij 赋值吧。当 n 等于 1 的时候不进入 while 循环无法赋值我们直接用 times 吧正好是 n/2。times 在循环中自减已经减成 0 了我们要新设置一个 mid 变量对中间的元素进行处理。前缀和题目描述给定一个整数数组 Array请计算该数组在每个指定区间内元素的总和。输入描述第一行输入为整数数组 Array 的长度 n接下来 n 行每行一个整数表示数组的元素。随后的输入为需要计算总和的区间直至文件结束。输出描述输出每个指定区间内元素的总和。输入示例5 1 2 3 4 5 0 1 1 3输出示例3 9数据范围0 n ≤ 100000#include iostream #include vector using namespace std; int main() { int n, a, b; cin n; vectorint vec(n); for (int i 0; i n; i) cin vec[i]; while (cin a b) { int sum 0; // 累加区间 a 到 b 的和 for (int i a; i b; i) sum vec[i]; cout sum endl; } }前缀和方法即利用一个小递推把前 n 项的和写进一个新数组pre[10] 表示pre[0] 到 pre[10] 的总和。i-1 是因为不能把第 i 项减去。#includebits/stdc.h using namespace std; const int MAX 1e5; int arr[MAX]; int pre[MAX]; int main() { int n; cin n; for (int i 0; i n; i) { cin arr[i]; pre[i] i 0 ? pre[i - 1] arr[i] : arr[i]; } int a, b; while (cin a b) { cout pre[b] - pre[a - 1] \n; } return 0; }C 中用 scanf 和 printf 可以减小耗时这里就不展示了。土地分配问题【题目描述】在一个城市区域内被划分成了 n × m 个连续的区块每个区块都拥有不同的权值代表着其土地价值。目前有两家开发公司A 公司和 B 公司希望购买这个城市区域的土地。现在需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而由于城市规划的限制只允许将区域按横向或纵向划分成两个子区域而且每个子区域都必须包含一个或多个区块。为了确保公平竞争你需要找到一种分配方式使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。注意区块不可再分。【输入描述】第一行输入两个正整数代表 n 和 m。接下来的 n 行每行输出 m 个正整数。输出描述请输出一个整数代表两个子区域内土地总价值之间的最小差距。【输入示例】3 3 1 2 3 2 1 3 1 2 3【输出示例】0【提示信息】如果将区域按照如下方式划分1 2 | 3 2 1 | 3 1 2 | 3两个子区域内土地总价值之间的最小差距可以达到 0。【数据范围】1 ≤ n, m ≤ 100n 和 m 不同时为 1暴力做法#includebits/stdc.h using namespace std; int main() { int n, m; cin n m; int sum 0; vectorvectorint vec(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin vec[i][j]; sum vec[i][j]; } } vectorint horizontal(n, 0); for (int i 0; i n; i) { for (int j 0; j m; j) { horizontal[i] vec[i][j]; } } vectorint vertical(m, 0); for (int j 0; j m; j) { for (int i 0; i n; i) { vertical[j] vec[i][j]; } } int result INT_MAX; int horizontalCut 0; for (int i 0; i n; i) { horizontalCut horizontal[i]; result min(result, abs(sum - horizontalCut - horizontalCut)); } int verticalCut 0; for (int j 0; j m; j) { verticalCut vertical[j]; result min(result, abs(sum - verticalCut - verticalCut)); } cout result endl; }前缀和把行/列总和算出差值进行比较。这一版的优化是不单独建竖列和横列栈累加的时候直接比较count 中间更新一下#includebits/stdc.h using namespace std; int main() { int n, m; cin n m; int sum 0; vectorvectorint vec(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin vec[i][j]; sum vec[i][j]; } } int result INT_MAX; int count 0; for (int i 0; i n; i) { for (int j 0; j m; j) { count vec[i][j]; if (j m - 1) result min(result, abs(sum - count - count)); } } count 0; for (int j 0; j m; j) { for (int i 0; i n; i) { count vec[i][j]; if (i n - 1) result min(result, abs(sum - count - count)); } } cout result endl; }数组总结篇数组是存放在连续内存空间上的相同类型数据的集合下标索引可以获取下标对应的数据数组下标都是从 0 开始的。数组内存空间的地址是连续的→删除或者增添元素的时候就难免要移动其他元素的地址。数组的元素是不能删的只能覆盖。vector 底层由 array 实现但是不是数组二维数组C 连续Java 不连续数组的经典题目二分法O(nlogn) 循环不变量原则双指针法O(n) 快指针慢指针在一个 for 循环内完成两个 for 循环的工作减小时间复杂度滑动窗口O(n) 要确定好如何移动窗口起始位置动态更新窗口大小模拟行为循环不变量原则要确定好边界前缀和前缀和方法即利用一个小递推把前 n 项的和写进一个新数组pre[10] 表示pre[0] 到 pre[10] 的总和。
力扣 209给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。示例输入target 7, nums [2,3,1,2,4,3]输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。提示1 ≤ target ≤ 1091 ≤ nums.length ≤ 1051 ≤ nums[i] ≤ 105暴力做法class Solution { public: int minSubArrayLen(int target, vectorint nums) { int len nums.size(); bool flag false; for (int i 0; i nums.size(); i) { int num 0; int len1 0; for (int j i; j nums.size(); j) { num nums[j]; if (num target) { flag true; len min(len, j - i 1); break; } } } if (!flag) { return 0; } else { return len; } } };不过这个超出了时间限制。滑动窗口法实际上还是一种双指针法起点由于 target 的限制是不可逆的所以说 j 变换的时候 i 的值不会清零重新来。举个例子来说1 2 3 100target 记作 101j0结束位置指针指向 1不够继续j1结束位置指针指向 2不够继续j2结束位置指针指向 3不够继续j3结束位置指针指向 100够了进入 while 循环先算出当前的子串长度len 选择更小的子串长度现在开始移动起始位置指针sum 减去当前初始位置值i 往后移动一位。这是进行一次初始位置指针的移动。然后进入第二次判定还是大于等于 target再来几次这里就省略了。下面进行返回值就好啦。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int i 0; int len n 1; int sum 0; for (int j 0; j n; j) { sum nums[j]; while (sum target) { int sublen j - i 1; len len sublen ? sublen : len; sum - nums[i]; } } if (len n 1) return 0; else { return len; } } };59 螺旋矩阵 II给定一个正整数 n生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的正方形矩阵。示例输入3 输出[[1, 2, 3], [8, 9, 4], [7, 6, 5]]这个题边界处理比较难要坚持循环不变量原则左闭右开就一直是左闭右开要不循环一定会出错。class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorint num(n, vectorint(n, 0)); int startx 0; int starty 0; int offset 1; int times n / 2; int mid n / 2; int i, j; int count 1; while (times--) { j starty; i startx; for (; j n - offset; j) { num[i][j] count; } for (; i n - offset; i) { num[i][j] count; } for (; j starty; j--) { num[i][j] count; } for (; i startx; i--) { num[i][j] count; } startx; starty; offset; } if (n % 2 ! 0) { num[mid][mid] count; } return num; } };要注意的是当 n 为奇数的时候中间会多出一个格子我们要单独赋值但是我们会出现两种错误想法ij 正好跑到了中间格子我们直接用 ij 赋值吧。当 n 等于 1 的时候不进入 while 循环无法赋值我们直接用 times 吧正好是 n/2。times 在循环中自减已经减成 0 了我们要新设置一个 mid 变量对中间的元素进行处理。前缀和题目描述给定一个整数数组 Array请计算该数组在每个指定区间内元素的总和。输入描述第一行输入为整数数组 Array 的长度 n接下来 n 行每行一个整数表示数组的元素。随后的输入为需要计算总和的区间直至文件结束。输出描述输出每个指定区间内元素的总和。输入示例5 1 2 3 4 5 0 1 1 3输出示例3 9数据范围0 n ≤ 100000#include iostream #include vector using namespace std; int main() { int n, a, b; cin n; vectorint vec(n); for (int i 0; i n; i) cin vec[i]; while (cin a b) { int sum 0; // 累加区间 a 到 b 的和 for (int i a; i b; i) sum vec[i]; cout sum endl; } }前缀和方法即利用一个小递推把前 n 项的和写进一个新数组pre[10] 表示pre[0] 到 pre[10] 的总和。i-1 是因为不能把第 i 项减去。#includebits/stdc.h using namespace std; const int MAX 1e5; int arr[MAX]; int pre[MAX]; int main() { int n; cin n; for (int i 0; i n; i) { cin arr[i]; pre[i] i 0 ? pre[i - 1] arr[i] : arr[i]; } int a, b; while (cin a b) { cout pre[b] - pre[a - 1] \n; } return 0; }C 中用 scanf 和 printf 可以减小耗时这里就不展示了。土地分配问题【题目描述】在一个城市区域内被划分成了 n × m 个连续的区块每个区块都拥有不同的权值代表着其土地价值。目前有两家开发公司A 公司和 B 公司希望购买这个城市区域的土地。现在需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而由于城市规划的限制只允许将区域按横向或纵向划分成两个子区域而且每个子区域都必须包含一个或多个区块。为了确保公平竞争你需要找到一种分配方式使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。注意区块不可再分。【输入描述】第一行输入两个正整数代表 n 和 m。接下来的 n 行每行输出 m 个正整数。输出描述请输出一个整数代表两个子区域内土地总价值之间的最小差距。【输入示例】3 3 1 2 3 2 1 3 1 2 3【输出示例】0【提示信息】如果将区域按照如下方式划分1 2 | 3 2 1 | 3 1 2 | 3两个子区域内土地总价值之间的最小差距可以达到 0。【数据范围】1 ≤ n, m ≤ 100n 和 m 不同时为 1暴力做法#includebits/stdc.h using namespace std; int main() { int n, m; cin n m; int sum 0; vectorvectorint vec(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin vec[i][j]; sum vec[i][j]; } } vectorint horizontal(n, 0); for (int i 0; i n; i) { for (int j 0; j m; j) { horizontal[i] vec[i][j]; } } vectorint vertical(m, 0); for (int j 0; j m; j) { for (int i 0; i n; i) { vertical[j] vec[i][j]; } } int result INT_MAX; int horizontalCut 0; for (int i 0; i n; i) { horizontalCut horizontal[i]; result min(result, abs(sum - horizontalCut - horizontalCut)); } int verticalCut 0; for (int j 0; j m; j) { verticalCut vertical[j]; result min(result, abs(sum - verticalCut - verticalCut)); } cout result endl; }前缀和把行/列总和算出差值进行比较。这一版的优化是不单独建竖列和横列栈累加的时候直接比较count 中间更新一下#includebits/stdc.h using namespace std; int main() { int n, m; cin n m; int sum 0; vectorvectorint vec(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin vec[i][j]; sum vec[i][j]; } } int result INT_MAX; int count 0; for (int i 0; i n; i) { for (int j 0; j m; j) { count vec[i][j]; if (j m - 1) result min(result, abs(sum - count - count)); } } count 0; for (int j 0; j m; j) { for (int i 0; i n; i) { count vec[i][j]; if (i n - 1) result min(result, abs(sum - count - count)); } } cout result endl; }数组总结篇数组是存放在连续内存空间上的相同类型数据的集合下标索引可以获取下标对应的数据数组下标都是从 0 开始的。数组内存空间的地址是连续的→删除或者增添元素的时候就难免要移动其他元素的地址。数组的元素是不能删的只能覆盖。vector 底层由 array 实现但是不是数组二维数组C 连续Java 不连续数组的经典题目二分法O(nlogn) 循环不变量原则双指针法O(n) 快指针慢指针在一个 for 循环内完成两个 for 循环的工作减小时间复杂度滑动窗口O(n) 要确定好如何移动窗口起始位置动态更新窗口大小模拟行为循环不变量原则要确定好边界前缀和前缀和方法即利用一个小递推把前 n 项的和写进一个新数组pre[10] 表示pre[0] 到 pre[10] 的总和。
