Leetcode刷题
一. 数组 二分法 双指针–滑动窗口 螺旋数组
题目索引
1. LeetCode 704. 二分查找
https://leetcode-cn.com/problems/binary-search/
2. LeetCode 26. 删除排序数组中的重复项
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
3. LeetCode 27. 移除元素
https://leetcode-cn.com/problems/remove-element/
4. LeetCode 209. 长度最小的子数组
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
5. LeetCode 59. 螺旋矩阵 II
https://leetcode-cn.com/problems/spiral-matrix-ii/
解题笔记
1. LeetCode 704. 二分查找
https://leetcode-cn.com/problems/binary-search/
关于left与right比较的问题
-
如果是while(left < right)，类似于[)
left = 0, right = nums.size()-1;
修改区间时应该是right = mid; left = mid + 1; -
如果是while(left <= right)，类似于[]
left = 0, right = nums.size()-1;
修改区间时应该是right = mid - 1; left = mid + 1;
方法一：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0,right = nums.size();
while(left < right){
int mid = (left + right)>>1;
if(nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
};
方法二：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0,right = nums.size() - 1;
while(left<=right){
int mid = (left + right)>>1;
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
};
二分法的y总模板
二分流程：
- 确定二分的边界；
- 设计一个chexkh函数；
- 判断区间如何更新；
二分本质的理解
两段性的性质，在一部分成立，在另一部分不成立；
根据性质分为两段（一般来说是找一段的端点）
如图：
例如找绿色部分的端点：
1. mid位于绿色区域内，【L,R】–>【L,mid】(找对了，但需要找的是最靠左的)
2. mid位于红色区域内，【L,R】–>【mid+1,R】（找错了，需要往右找）
3. mid的变化为（l + r >> 1）
假如找红色部分的端点：
1. mid位于绿色区域内，【L,R】–>【L,mid-1】(找错了，往左走)
2. mid位于红色区域内，【L,R】–>【mid，R】（找对了，但需要找最靠右的）
3. 注意，mid取值需要向上取整（l + r + 1 >> 1）
解释：例如当L = R - 1时，mid = L + R >> 1 = L；假如此时mid取值在红色区域，则L = mid没有更新，会出现死循环
写法一
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0,r = nums.size()-1;
while(l < r){
int mid = (l + r >> 1);
if(nums[mid] >= target){
r = mid;
}else{
l = mid + 1;
}
}
if(nums[l] == target){
return l;
}
return -1;
}
};
写法二
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0,r = nums.size()-1;
while(l < r){
int mid = (l + r + 1 >> 1);
if(nums[mid] <= target){
l = mid;
}else{
r = mid - 1;
}
}
if(nums[l] == target){
return l;
}
return -1;
}
};
2. LeetCode 26. 删除排序数组中的重复项
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
特征
排序数组：重复的元素只出现在相邻元素之间
位置为i的元素与前一个数不一样，就写在前面
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for(int i = 0; i < nums.size(); i++){
if(!i || nums[i] != nums[i-1]){
nums[k++] = nums[i];
}
}
return k;
}
};
3. LeetCode 27. 移除元素
https://leetcode-cn.com/problems/remove-element/
类似于26
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] != val){
nums[k++] = nums[i];
}
}
return k;
}
};
4. LeetCode 209. 长度最小的子数组
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
特征
固定i,然后寻找最靠右的j
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX;
int sum = 0;
for(int i = 0, j = 0, sum = 0; i < nums.size(); i++){
sum += nums[i];
while(sum - nums[j] >= target){
sum -= nums[j];
j++;
}
if(sum >= target){
res = min(res,i - j + 1);
}
}
if(res == INT_MAX){
res = 0;
}
return res;
}
};
LeetCode 59. 螺旋矩阵 II
https://leetcode-cn.com/problems/spiral-matrix-ii/
定义方向数组
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n,vector<int>(n));
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
for(int i = 1, x = 0, y = 0, d = 0; i <= n*n; i++){
res[x][y] = i;
int a = x + dx[d];
int b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
d = (d + 1)%4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
return res;
}
};
