目录
一、二分查找
704. 二分查找 - 力扣（LeetCode）
https://leetcode.cn/problems/binary-search/description/
给定一个
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]之间。
1. 方法一
定义 target 在一个在左闭右闭的区间里，也就是 [left, right] 。
class Solution {
public:
int search(vector<int>& nums, int target) {
// 二分查找
// 方法1 [left, right]
int left = 0, right = nums.size() - 1;
int middle = left + ((right - left) / 2); // 防止 left + right 溢出
while(left <= right)
{
middle = left + ((right - left) / 2);
if(nums[middle] > target)
{
right = middle - 1;
}
else if(nums[middle] < target)
{
left = middle + 1;
}
else if(nums[middle] == target)
{
return middle;
}
}
return -1;
}
};
- 因为 left == right 是有意义的，所以 while (left <= right) 要使用 <= 。
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle] 一定不是 target，那么 接下来 要查找的左区间 结束 下标位置就是 middle - 1。
2. 方法二
定义 target 是在一个在左闭右开的区间里，也就是 [left, right) 。
class Solution {
public:
int search(vector<int>& nums, int target) {
// 二分查找
// 方法2 [left, right)
int left = 0, right = nums.size();
int middle = left + ((right - left) / 2); // 防止 left + right 导致溢出
while(left < right)
{
middle = left + ((right - left) / 2);
if(nums[middle] > target)
{
right = middle;
}
else if(nums[middle] < target)
{
left = middle + 1;
}
else if(nums[middle] == target)
{
return middle;
}
}
return -1;
}
};
- 因为 left == right 在区间 [left, right) 是没有意义的，所以 while (left < right)，这里使用 < 。
- if (nums[middle] > target) right 更新为 middle，因为当前 nums[middle] 不等于 target，去 左区间 继续寻找，而寻找 区间是 左闭右开区间，所以 right 更新为 middle，即：下一个 查询区间不会去比较 nums[middle]。
二、移除元素
27. 移除元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-element/description/
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 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 个元素之外留下了什么并不重要（因此它们并不计入评测）。1. 暴力破解
两层 for 循环，一个 for 循环 遍历数组元素 ，第二个 for 循环更新数组。找到一个，后面的数字整体向前移一位。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = nums.size();
for(int i = 0; i < len; i++)
{
if(nums[i] == val)
{
for(int j = i + 1; j < len; j++)
{
nums[j - 1] = nums[j];
}
i--; // 因为 i之后的数字都往前移了一位，所以这里i也往前移一位
len--;
}
}
return len;
}
};2. 双指针法
通过一个 快指针和慢指针在一个 for 循环下 完成两个 for 循环的工作。
用 快指针赋值给满指针，可以实现 暴力破解中 数字整体 向前移一位的 操作。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
// 快指针、慢指针
int slowindex = 0;
for(int fastindex = 0; fastindex < nums.size(); fastindex++)
{
if(nums[fastindex] != val)
{
nums[slowindex++] = nums[fastindex];
}
}
return slowindex;
}
};三、有序数组的平方
977. 有序数组的平方 - 力扣（LeetCode）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]双指针法
数组是有序的， 只不过 负数平方之后 可能成为 最大数了。那么 数组平方的 最大值就在 数组的 两端，不是 最左边就是 最右边，不可能 是中间。 此时 可以考虑 双指针法，left 指向 起始位置，right 指向终止位置。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int len = nums.size() - 1;
vector<int> result(nums.size());
int left = 0, right = len;
while(left <= right)
{
int le = nums[left] * nums[left];
int ri = nums[right] * nums[right];
if(le > ri)
{
result[len--] = le;
left++;
}
else if(le <= ri)
{
result[len--] = ri;
right--;
}
}
return result;
}
};四、长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/description/
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 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]
输出：01. 暴力破解
使用 两个 for 循环，然后 不断的寻找符合条件的 子序列。一个 for 循环滑动窗口的 起始位置，一个 for 循环为滑动窗口的终止位置，用两个 for 循环 完成了一个不断搜索区间的过程。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int len = nums.size();
int pan = 0;
for(int i = 0; i < len ; i++)
{
int sum = 0;
for(int j = i; j < len; j++)
{
sum += nums[j];
if(sum >= target)
{
pan = j - i + 1;
result = result > pan ? pan : result;
break;
}
}
}
return result == INT32_MAX ? 0 : result;
}
};2. 滑动窗口
滑动窗口，就是不断的 调节 子序列的 起始位置 和 终止位置，从而 得出我们要 想的 结果。滑动窗口 只用一个 for 循环，那么 这个循环的索引，一定是表示 滑动窗口的终止位置。
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的 起始位置 如何移动：如果当前窗口的值大于等于 s 了，窗口就要向前移动了（也就是该缩小了）。
窗口的 结束位置 如何移动：窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索引。
解题的关键在于 窗口的起始位置如何移动，
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑动窗口
int result = INT32_MAX;
int len = nums.size();
int sum = 0;
int j = 0; // 窗口起始位置
for(int i = 0; i < len; i++)
{
sum += nums[i];
while(sum >= target)
{
int pan = i - j + 1;
result = result > pan ? pan : result;
sum -= nums[j++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
五、螺旋矩阵 II
59. 螺旋矩阵 II - 力扣（LeetCode）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]]模拟 顺时针画矩阵的 过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向 内一圈一圈 这么 画下去。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
int take_x = 0, take_y = 0; // 每次循环起始位置定位
int nums = n / 2; // 循环几次
int mid = n / 2; // 矩阵中心位置
int count = 1; // 填入的数字
int offset = 1; // 循环离右边界的距离
int i, j;
while(nums--)
{
i = take_x;
j = take_y;
// 循环一圈
for(; j < n - offset; j++)
{
result[i][j] = count++;
}
for(; i < n - offset; i++)
{
result[i][j] = count++;
}
for(; j > take_x; --j)
{
result[i][j] = count++;
}
for(; i > take_y; --i)
{
result[i][j] = count++;
}
// 更新循环起点位置
take_x++;
take_y++;
offset++;
}
// 奇数中间没填
if(n % 2 != 0)
{
result[mid][mid] = count;
}
return result;
}
};
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。这也是坚持了每条边左闭右开的原则。