01数组
二分查找
题目
链接：https://leetcode.cn/problems/binary-search/
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
题解
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r){
int mid = (l + r) / 2;
if(nums[mid] > target) r = mid - 1;
else if(nums[mid] < target) l = mid + 1;
else return mid;
}
return -1;
}
};本题相对简单，可以关注一下二分边界问题。
移除元素
题目
链接：https://leetcode.cn/problems/remove-element/
给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设
nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。- 返回
k。用户评测：
评测机将使用以下代码测试您的解决方案：
int[] nums = [...]; // 输入数组 int val = ...; // 要移除的值 int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。 int k = removeElement(nums, val); // 调用你的实现 assert k == expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素 for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; }如果所有的断言都通过，你的解决方案将会 通过。
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_] 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_] 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
题解
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int p = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] != val) nums[p++] = nums[i];
}
return p;
}
};本题思路：使用p指向放置非val元素的位置，i指针后移，找到非val元素放入p指向位置
有序数组的平方
题目
链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/
给你一个按 非递减顺序 排序的整数数组
nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums已按 非递减顺序 排序进阶：
- 请你设计时间复杂度为
O(n)的算法解决本问题
题解
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> res;
int l = 0, r = nums.size() - 1;
while(l <= r){
if(abs(nums[l]) > abs(nums[r])){
res.push_back(nums[l] * nums[l++]);
}else {
res.push_back(nums[r] * nums[r--]);
}
}
reverse(res.begin(), res.end());
return res;
}
};本题思路：需要考虑到负数的平方也较大，所以从左右向中间夹击（归并排序思想）
长度最小的子数组
题目
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
给定一个含有
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] <= 104进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
题解
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int front = 0, rear = 0, min = 100010, tmp = 0;
int DQueue[100010]; //定义双端队列,最大长度为110即可
for(int i = 0; i < nums.size(); i++){
//不论如何，先加入元素
DQueue[rear++] = nums[i];
tmp += nums[i];
//找到最小位置
if(tmp >= target){
while(tmp >= target) {
tmp -= DQueue[front++];
}
tmp += DQueue[--front];
}
if(tmp >= target && rear - front < min) min = rear - front;
}
return min == 100010 ? 0 : min;
}
};本题思路：采用滑动窗口的思想，代码中的
DQueue多余，本题实现并不需要双端队列，普通队列即可。
螺旋矩阵II
题目
链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
给你一个正整数
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 <= 20
题解
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int cnt = 1;
//上层循环标识当前层数
for(int i = 0; i <= n / 2; i++){
//上
for(int j = i ; j < n - i; j++){
res[i][j] = cnt++;
}
//右
for(int j = i + 1; j < n - i; j++){
res[j][n - i - 1] = cnt++;
}
//下
for(int j = n - i - 2; j >= i ; j--){
res[n - i - 1][j] = cnt++;
}
//左
for(int j = n - i - 2; j >= i + 1; j--){
res[j][i] = cnt++;
}
}
return res;
}
};本题思路：本题主要在于处理好上下左右四条边的边界问题。
模拟类题目，不难，但是相对比较绕。
区间和
题目
链接：https://kamacoder.com/problempage.php?pid=1070
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5 1 2 3 4 5 0 1 1 3输出示例
3 9提示信息
数据范围： 0 < n <= 100000
题解
#include<iostream>
using namespace std;
int main(){
int n, a, b;
int s[100010] = {0};
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s[i];
s[i] += s[i - 1];
}
while(~scanf("%d", &a) && ~scanf("%d", &b)){
a += 1; b += 1;
cout << s[b] - s[a - 1] << endl;
}
}本题思路：本题主要是
前缀和的基础应用，可以温习一下前缀和的内容。
开发商购买土地
题目
链接：https://kamacoder.com/problempage.php?pid=1044
题目描述
在一个城市区域内，被划分成了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<iostream>
using namespace std;
int main(){
int n, m, min = -1;
cin >> n >> m;
int o[n + 1][m + 1], a[n + 1] = {0}, b[m + 1] = {0};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> o[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i] += o[i][j];
b[j] += o[i][j];
}
}
//前缀和数组
for(int i = 1; i <= n; i++) a[i] += a[i - 1];
for(int i = 1; i <= m; i++) b[i] += b[i - 1];
//行核算
for(int i = 1; i < n; i++){
if(min == -1) min = abs(a[n] - a[i] * 2);
else if(abs(a[n] - a[i] * 2) < min) min = abs(a[n] - a[i] * 2);
}
//列核算
for(int i = 1; i < m; i++){
if(min == -1) min = abs(b[m] - b[i] * 2);
else if(abs(b[m] - b[i] * 2) < min) min = abs(b[m] - b[i] * 2);
}
cout << min;
}本题思路：本题是一个二维形式的前缀和，作行和和列和，即可转化为一维的前缀和问题。