算法题-数组相关
数组
记住：先判断边界条件！！！
二分查找
二分查找采用第一种写法
第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] 。
区间的定义这就决定了二分法的代码应该如何写，因为定义 target 在[left, right]区间，所以有如下两点：
- while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool Find(int target, vector<vector<int> >& array) {
if(array.size()==0) return false;
int n=array.size();
if(array[0].size()==0) return false;
int m=array[0].size();
for(int i=n-1,j=0;i>=0&&j<m;){
if(array[i][j]>target) i--;
else if(array[i][j]<target) j++;
else return true;
}
return false;
}
|
快慢指针移除元素
题目是给定数组 nums 和一个值 val，原地移除所有数值为 val 的元素，返回移除后数组的新长度
1
2
3
4
5
6
7
8
9
| int removeElement(vector<int>& nums, int val) {
int slowIndex=0,fastIndex=0;
while(fastIndex<nums.size()){
if(nums[fastIndex]!=val)
nums[slowIndex++]=nums[fastIndex];
fastIndex++;
}
return slowIndex;
}
|
写法：先定义快慢指针，然后快指针先走 根据题目条件写不等于时的情况，里面 slowIndex++，最后 fastIndex++
关联题目：26. 删除有序数组中的重复项 - 力扣（LeetCode）
【双指针】比较含退格的字符串 - 比较含退格的字符串 - 力扣（LeetCode）😵 这题需要从后向前遍历 使用双指针
其他包含双指针的题目：双指针——三数之和、四数之和 剑指 Offer 05. 替换空格 - 力扣（Leetcode）
151. 反转字符串中的单词 - 力扣（Leetcode） 快慢指针移除元素
滑动窗口
滑动窗口的题目主要确定三点：
窗口内是什么？
如何移动窗口的开始位置？跟随判断条件来
如何移动窗口的结束位置？ 跟随循环来 😙
最小滑窗模板
给定数组 nums，定义滑窗的左右边界 i，j，求满足某个条件的滑窗的最小长度
1
2
3
4
5
6
7
8
9
10
11
| while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
j += 1
作者：frostep
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
相关题目：209. 长度最小的子数组 - 力扣（LeetCode） 🤣
76. 最小覆盖子串 - 力扣（LeetCode）
最大滑窗模板
给定数组 nums，定义滑窗的左右边界 i，j，求满足某个条件的滑窗的最大长度
1
2
3
4
5
6
7
8
9
10
11
| while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
作者：frostep
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
904. 水果成篮 - 力扣（LeetCode）
题目汇总：
209. 长度最小的子数组 - 力扣（LeetCode） 🤣
这题是求满足和大于等于 target 的最小连续子数组的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
| int minSubArrayLen(int target, vector<int>& nums) {
int res=INT32_MAX;
int sum=0,start=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
while(sum>=target){
int curlen=i-start+1;
res=min(res,curlen);
sum-=nums[start++];
}
}
return res==INT32_MAX?0:res;
}
|
904. 水果成篮 - 力扣（LeetCode）
两个篮子装尽可能多的水果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int totalFruit(vector<int>& fruits) {
unordered_map<int,int> s;
int left=0,right=0;
int res=0;
while(right<fruits.size()){
s[fruits[right]]+=1;
while(s.size()>2){
s[fruits[left]]--;
if(s[fruits[left]]==0) s.erase(fruits[left]);
++left;
}
res=max(res,right-left+1);
++right;
}
return res;
}
|
76. 最小覆盖子串 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> need,win;
for(auto &c:t) ++need[c];
int right=0,left=0,start=0,len=INT_MAX;;
int count=0;
while(right<s.size()){
if(need.find(s[right])!=need.end()){
++win[s[right]];
if(win[s[right]]==need[s[right]]) ++count;
}
while(count==need.size()){
if(len>right-left+1){
len=right-left+1;
start=left;
}
if(need.find(s[left])!=need.end()){
if(win[s[left]]==need[s[left]]) --count;
--win[s[left]];
}
++left;
}
++right;
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
|
排序算法
归并排序
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <vector>
class Solution {
public:
void merge(vector<int>& nums,int left,int mid,int right,int &res){
vector<int> tmp(right-left+1);
int i=left,j=mid+1;
int k=0;
while(i<=mid&&j<=right){
if(nums[i]>nums[j]){
tmp[k++]=nums[j++];
res+=(mid-i+1);
res%=1000000007;
}else{
tmp[k++]=nums[i++];
}
}
while(i<=mid) tmp[k++]=nums[i++];
while(j<=right) tmp[k++]=nums[j++];
for(int idx=left,j=0;j<k;idx++){
nums[idx]=tmp[j++];
}
}
void mergeSort(vector<int>& nums,int left,int right,int &res){
*if(left>=right) return;
int mid=left+((right-left)>>1);
mergeSort(nums, left,mid,res);
mergeSort(nums,mid+1,right,res);
merge(nums,left,mid,right,res);
}
int InversePairs(vector<int>& nums) {
int res=0;
mergeSort(nums,0,nums.size()-1,res);
return res;
}
};
|