企业官网建设流程全解析

力扣 209：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

• 输入：target = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

• 1 ≤ target ≤ 109
• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 105

暴力做法

class Solution { public: int minSubArrayLen(int target, vector<int>& 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 100；target 记作 101；

• j=0，结束位置指针指向 1，不够，继续
• j=1，结束位置指针指向 2，不够，继续
• j=2，结束位置指针指向 3，不够，继续
• j=3，结束位置指针指向 100，够了，进入 while 循环，先算出当前的子串长度，len 选择更小的子串长度，现在开始移动起始位置指针，sum 减去当前初始位置值，i 往后移动一位。

这是进行一次初始位置指针的移动。

然后进入第二次判定，还是大于等于 target，再来几次，这里就省略了。

下面进行返回值就好啦。

class Solution { public: int minSubArrayLen(int target, vector<int>& 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: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> num(n, vector<int>(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 为奇数的时候，中间会多出一个格子，我们要单独赋值，但是我们会出现两种错误想法：

1. i，j 正好跑到了中间格子，我们直接用 i，j 赋值吧。
   当 n 等于 1 的时候，不进入 while 循环，无法赋值
2. 我们直接用 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; vector<int> 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 项减去。

#include<bits/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 ≤ 100
• n 和 m 不同时为 1

暴力做法

#include<bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; int sum = 0; vector<vector<int>> vec(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> vec[i][j]; sum += vec[i][j]; } } vector<int> horizontal(n, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { horizontal[i] += vec[i][j]; } } vector<int> 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 中间更新一下；

#include<bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; int sum = 0; vector<vector<int>> vec(n, vector<int>(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] 的总和。