1 二分查找
- 题目链接：704. 二分查找
1.1 题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1 。
示例1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
示例2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
1.2 思路
简单二分法，如果 nums[m]==target 说明找到下标直接返回即可。
完整代码如下：
Cpp实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while(l <= r){ //可以改为（l < r）
int m = l + (r-l)/2;
if(nums[m] == target){
return m;
}else if(nums[m] < target){
l = m + 1;
}else{
r = m - 1; //如果循环条件更改，则需要改为 `r = m;`
}
}
return -1;
}
};C实现
int search(int* nums, int numsSize, int target){
int left=0,right=numsSize-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
return -1;
} 2 移除元素
- 题目链接：27. 移除元素
2.1 题目描述
给你一个数组 nums 和一个值 val ，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组 。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例1:
输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2]
示例2:
输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,4,0,3]
2.2 思路
设置两个指针，首先判断快指针对应的数组中的值是否等于 val， 如果是则不进行操作，如果不等于则说明这个当前遍历到的元素应该进行保留，因而将其赋给慢指针指向的位置。整体的思路就是遍历一遍数组，遇到与 val 不一样的元素就把该元素插到原数组的前端(用慢指针指定位置)，最后返回慢指针即为答案。
完整代码如下：
Cpp实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0, slow = 0;
for(; fast < nums.size(); ++fast){
if(nums[fast] == val){
continue;
}
nums[slow++] = nums[fast];
}
return slow;
}
};C实现
int removeElement(int* nums, int numsSize, int val){
int order=0;
for(int i=0;i<numsSize;i++){
if(nums[i]!=val){
nums[order++]=nums[i];
}
}
return order;
} 3 有序数组的平方
- 题目链接：977. 有序数组的平方
3.1 题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例1:
输入: nums = [-4,-1,0,3,10]
输出: [0,1,9,16,100]
示例2:
输入: nums = [-7,-3,2,3,11]
输出: [4,9,9,49,121]
3.2 思路
最简单的方法就是先遍历一遍数组，遍历过程中对元素进行平方处理，然后最后再对平方过后的数组进行排序即可。(C++实现)
或者新建一个数组 res，容量与 nums 的容量相同，然后创建一个位置指针指向该数组的最后一个位置。创建两个指针分别指向 nums 的开头与结尾(因为 nums 中有负数，平方过后的最大值只会出现在最左侧或最右侧)，对左右两个指针指向的元素进行平方，大者写入答案数组 res 中并将指针前移一位，而指向原数组中那个平方后较大的指针移动一位。(C实现)
完整代码如下：
Cpp实现
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0; i < nums.size(); ++i){
nums[i] = nums[i]*nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};C实现
int* sortedSquares(int* nums, int numsSize, int* returnSize){
int *ret = malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
int i = numsSize - 1;
int right = numsSize - 1;
for(int left = 0; left <= right;){
int lSquare = nums[left]*nums[left];
int rSquare = nums[right]*nums[right];
if(lSquare < rSquare){
ret[i--] = rSquare;
right--;
}else{
ret[i--] = lSquare;
left++;
}
}
return ret;
} 4 长度最小的子数组
- 题目链接：209. 长度最小的子数组
4.1 题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例1:
输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
示例2:
输入: target = 4, nums = [1,4,4]
输出: 1
示例3:
输入: target = 11, nums = [1,1,1,1,1,1,1,1]
输出: 0
4.2 思路
经典滑动窗口题目，设置两个指针，右指针用来遍历数组，左指针置 0. 创建一个 sum 变量用来记录当前滑动窗口中的元素的加和。当 sum < target 时不进行操作，只将当前元素的值加到 sum 中；当sum >= target 说明当前窗口中有符合条件的连续子数组，将当前子数组的长度与当前res 进行比较并将较小者赋给 res， 并将左指针右移一位，相当于窗口缩短一位。
完整代码如下：
Cpp实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0,sum = 0, res = INT_MAX;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
while(sum >= target){
res = min(res, i - left + 1);
sum -= nums[left++];
}
}
return res==INT_MAX ? 0:res;
}
};C实现
int minSubArrayLen(int target, int* nums, int numsSize){
int ans = INT_MAX;
int leftIdx = 0;
int sum = 0;
for(int i = 0; i < numsSize; i++){
sum += nums[i];
while(sum >= target){
ans = fmin(ans,i-leftIdx+1);
sum -= nums[leftIdx++];
}
}
return ans == INT_MAX ? 0 : ans;
} 5 螺旋矩阵 II
- 题目链接：59. 螺旋矩阵 II
5.1 题目描述
给你一个正整数 n ，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例1:
输入: n = 3
输出: [[1,2,3],[8,9,4],[7,6,5]]
示例2:
输入: n = 1
输出: [[1]]
5.2 思路
直接模拟即可。设置上下左右的边界(0，n),然后创建两个变量，分别存放当前行和当前的列，然后创建 cnt 变量用来记录当前待插入的元素。
4个for循环即可解决问题：第一个 for 循环解决正向行插入(从左到右)，第二个 for 解决下行列插入(从上到下)，第三个 for 循环解决反向行插入(从右到左)，第四个 for 解决上行列插入(从下到上)。
但是需要注意终止循环的条件是什么。举几个例子可以发现，最后的终止条件就是第一个 for 循环结束后和第三个 for 循环结束后判断是否有 cnt > n*n ，如果这个条件成立说明已经插入完成，跳出循环并返回答案。
另外，每个 for 循环结束后都需要对边界进行更新，第一个 for 循环结束后需要对 右边界 进行减 1,第二个 需要对 下边界 进行减 1,第三个 需要对 左边界 进行加 1,第四个需要对 上边界 进行加 1.
还有一个细节，就是每次 for 循环结束后，都需要对行变量和列变量进行操作，因为 上一个循环会往当前循环的方向多走一步 ，所以进行下一次循环前需要将这一步减去，然后再往要走的方向迈一步，为实现代码的统一，则将行变量和列变量均初始化为 -1。
完整代码如下：
Cpp实现
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res;
vector<int> tmp(n);
res.resize(n, tmp); //定义二维vector的容量为n*n
int left = 0, right = n, high = 0, low = n; //边界
int cnt = 1, c = -1, r = -1; //依次为当前待插入数值、列变量、行变量
while(1){
for(++r, ++c; c < right; ++c){
res[r][c] = cnt++;
}
if(cnt > n*n) break; //判断是否插入已经完成，待插入数值最大为n^2
--right; //更新右边界
for(++r, --c; r < low; ++r){
res[r][c] = cnt++;
}
--low; //更新下边界
for(--c, --r; c >= left; --c){
res[r][c] = cnt++;
}
if(cnt > n*n) break;
++left; //更新左边界
for(--r, ++c; r > high; --r){
res[r][c] = cnt++;
}
++high; //更新上边界
}
return res;
}
};C实现
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
bool flag = 0;
*returnSize = n;
int **res = (int **)malloc(sizeof(int *)*n);
*returnColumnSizes = (int *)malloc(sizeof(int)*n);
for(int i = 0; i < n; i++){
res[i] = (int *)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
memset(res[i], 0, sizeof(int) * n);
}
int cnt = 1;
int col = 0, row = -1;
int colLeft = 0, rowLeft = 0;
int colRight = n, rowRight = n;
res[0][0] = cnt++;
if(cnt > n) return res;
while(1){
for(row+=1,col += 1; col < colRight; col++){
res[row][col] = cnt++;
}
if(cnt > n*n){
break;
}
colRight--;
for(row += 1,col-=1; row < rowRight; row++){
res[row][col] = cnt++;
}
rowRight--;
for(col -= 1, row -= 1; col >= colLeft; col--){
res[row][col] = cnt++;
}
if(cnt > n*n){
break;
}
colLeft++;
for(col+=1,row -= 1; row > rowLeft; row--){
res[row][col] = cnt++;
}
//break;
rowLeft++;
}
return res;
} 总结
本章都相对简单，涉及二分法、滑动窗口、双指针三种最基本的算法以及过程模拟。
前三种方法在后边会经常用到，二分法常用来解决在一个指标的约束遍历整个数组最少/最大的值，滑动窗口则是解决连续子数组(或串)的问题，双指针用处太多了，一时写不出来，等强一点再来总结，这里先挖个坑，模拟比较锻炼思维，要把整个过程在脑中过一遍，与之相对的是递归，递归不能想太深，一想深就乱！
