题目1 209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
思路
这道题可以使用暴力法嵌套循环去解决，但这种方式的时间复杂度为O(n2)。另一种解决方法是使用双指针的滑动窗口法，右指针rht负责寻找满足大于target的情况，左指针负责缩小满足target情况的范围。通过考虑滑动窗口的最坏情况来确认时间复杂度，
1.左指针和右指针在循环内每次都要移动一次，时间复杂度为:
\[O(\sum_{i=1}^{n}(1+1))=O(2n)=O(n) \]2.左指针只有最后一次从数组开头移动到数组的结尾，时间复杂度为:
\[O(\sum_{i=1}^{n-1}(1)+(1+n))=O(2n)=O(n) \]通过这样分析可以得出滑动窗口法比暴力迭代法要高效。
代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT_MAX;
int lft = 0, rht = 0;
int sum = 0;
while(rht < nums.size())
{
sum += nums[rht++];
while(sum >= target)
{
result = min(result, rht - lft);
sum -= nums[lft++];
}
}
return result == INT_MAX ? 0 : result;
}
};
题目2 59. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
思路
这道题就是模拟题，将1-n*n按顺时针放入到矩阵中。顺时针放入则需要设置放置的顺序为[右，下，左，上]，每次放置前也需要注意越界问题，有效区域为[0, n-1]；此外，还需要注意放置的位置是否已经放置其他元素。这道题的算法复杂度为:
\[O(\sum_{i=1}^{n}(\sum_{i=1}^{n-2}(1) + 2*2))=O(n^2) \]代码
//设置的方向
enum orient{rht = 0,down,lft,up};
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n, INT_MAX));
int cur = 1;
int x = 0, y = -1;
int nextStep = orient::rht;
while(cur <= n*n)
{
if(nextStep == orient::rht)
{
if(y+1 < n && result[x][y+1] == INT_MAX)
{
result[x][++y] = cur;
}
else
{
nextStep = orient::down;
continue;
}
}
else if(nextStep == orient::down)
{
if(x+1 < n && result[x+1][y] == INT_MAX)
{
result[++x][y] = cur;
}
else
{
nextStep = orient::lft;
continue;
}
}
else if(nextStep == orient::lft)
{
if(y-1 >= 0 && result[x][y-1] == INT_MAX)
{
result[x][--y] = cur;
}
else
{
nextStep = orient::up;
continue;
}
}
else if(nextStep == orient::up)
{
if(x-1 >= 0 && result[x-1][y] == INT_MAX)
{
result[--x][y] = cur;
}
else
{
nextStep = orient::rht;
continue;
}
}
cur++;
}
return std::move(result);
}
};
题目3 区间和
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
提示信息
数据范围：
0 < n <= 100000
思路
- 可以用暴力遍历法，但是提交后会发现超时，因为时间复杂度为O(n*m)
- 可以使用前缀和来处理这道题目，前缀和指的是将数组中的每个元素和之前的所有元素累加并记录到数组对应位置，当需要计算[a,b]元素之间的总和时，只需要\(\sum_{i=1}^{b}(elem(i)) - \sum_{i=1}^{a-1}(elem(i))\)一步操作就行了，而累加操作之前已经完成了，通过这种方法得出的时间复杂度为O(n+m)
代码
#include <iostream>
using namespace std;
int main()
{
int num;
cin >> num;
int arr[num+1]{0};
for(int i = 1; i <= num; i++)
{
cin >> arr[i];
arr[i] += arr[i-1];
}
int lft, rht;
while(cin >> lft >> rht)
{
cout << arr[rht + 1] - arr[lft] << endl;
}
return 0;
}
题目4 开发商购买土地
题目描述
在一个城市区域内，被划分成了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。
思路
思路1. 可以用暴力法来解决这道题，在将数据保存到数组后，横切(m-1)次，竖切(n-1)次并计算每块的总和并计算差值最后取最小值，但这样计算时间复杂度为:
\[O(n*m+(m-1)*n*m+(n-1)*n*m)=O(n^3)(假设n=m) \]通过暴力法需要太多时间代价了。
思路2. 可以用前缀和的方法来解决这道题，因为每个区域都是要统计n个数或者m个数的和来进行计算的，因此可以将统计的过程分离出来保存到数组中。通过这种方法的时间复杂度为：
\[O(n*m+n*m+n+m)=O(n*m) \]代码
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int block[n][m];
int hor[n+1]{0}, col[m+1]{0};
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> block[i][j];
hor[i+1]+=block[i][j];
}
hor[i+1] += hor[i];
}
for(int j = 1; j <= m; j++)
{
for(int i = 1; i <= n; i++)
{
col[j] += block[i-1][j-1];
}
col[j] += col[j-1];
}
int result = INT_MAX;
for(int i = 1; i < n; i++)
{
//cout << hor[i] << " ";
result = min(result, abs(hor[n] - 2 * hor[i]));
}
//cout << endl;
for(int j = 1; j < m; j++)
{
//cout << col[j] << " ";
result = min(result, abs(col[m] - 2 * col[j]));
}
//cout << endl;
cout << result << endl;
return 0;
}