- 数组理论基础
- 二分法
- 力扣相关题目
- 使用前提条件
- 704.二分查找
- 双指针法
- 力扣相关题目
- 27.移除元素
- 滑动窗口（参考labuladong算法小抄）
- 套用模板
- 力扣相关题目
- 76.最小覆盖子串
- 螺旋矩阵（模拟行为）
- 54/offer29.螺旋矩阵（二维变一维）
- 59.螺旋矩阵（一维变二维）
- 数组是存放在连续内存空间上的相同类型数据的集合。
- 数组下标都是从0开始的。数组内存空间的地址是连续的。
- 数组的元素是不能删的，只能覆盖。
- C++中要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
- array 定义的时候必须定义数组的元素个数，且只能包含整型字面值常量，枚举常量或者用常量表达式初始化的整型const对象，非const变量以及需要到运行阶段才知道其值的const变量都不能用来定义数组的维度；而vector 不需要；
- array 定义后的空间是固定的了，不能改变；而vector 要灵活得多，可再加或减
- vector有一系列的函数操作，非常方便使用；和vector不同，array数组不提供 push_back或者其他的操作在数组中添加新元素，array数组一经定义就不允许添加新元素，若需要则要充许分配新的内存空间，再将原数组的元素赋值到新的内存空间。
- array数组和vector不同，一个数组不能用另一个数组初始化，也不能将一个数组赋值给另一个数组。
-
数组为有序数组
-
数组中无重复元素（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的）
如果题目描述满足如上条件，可想一想是不是可以用二分法了。
//注意边界条件
class Solution {
public:
int search(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
双指针法
双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，在数组和链表的操作中是非常常见的。此外还有双向指针法：两个指针分别从前后开始进行遍历并进行操作。
力扣相关题目 27.移除元素//快慢双指针
class Solution {
public:
int removeElement(vector& nums, int val) {
int slowIndex = 0;
for(int fastIndex = 0;fastIndex
if(val!=nums[fastIndex]){
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
//相向双指针
class Solution {
public:
int removeElement(vector& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size()-1;
while(leftIndex <= rightIndex){
while(leftIndex <= rightIndex && nums[leftIndex]!=val){
leftIndex++;
}
while(leftIndex <= rightIndex && nums[rightIndex]==val){
rightIndex--;
}
if(leftIndex < rightIndex){
nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex;
}
};
滑动窗口（参考labuladong算法小抄）
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
套用模板先思考如下问题：
-
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
void slidingWindow(string s, string t) {
unordered_map need, window;
//unordered_map 容器和 map 容器仅有一点不同：
//即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
for (char c : t) need[c]++;
//这里的for(char c:chars)就是定义一个遍历字符c，让它分别等于字符串数组chars里面的各个字符，然后执行下面的语句，当c被赋值为chars里面所有字符各一次后，就会退出这个循环.
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
// printf("window: [%d, %d)n", left, right);
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
力扣相关题目
76.最小覆盖子串
class Solution {
public:
string minWindow(string s, string t) {
unordered_map need,window;
for (char c : t) need[c]++;
int left = 0;
int right = 0;
int count = 0;
int start = 0;
int len = INT_MAX;
while(right
char c = s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
count++;
}
}
while(count == need.size()){
if (right - left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d])
count--;
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
螺旋矩阵（模拟行为）
54/offer29.螺旋矩阵（二维变一维）
示例 ：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
class Solution {
public:
vector spiralOrder(vector>& matrix) {
vector ans;
if(matrix.empty()) {
return ans;
}
//一定要先做判空，若这段代码放到int定义结束之后，则如果matrix为空，那么在matrix[0].size()时会报错。
int up = 0;
int down = matrix.size() - 1;
int left = 0;
int right = matrix[0].size() - 1;
while(1){
for(int j = left;j<=right;j++){
ans.push_back(matrix[up][j]);
}
if(++up>down){
break;
}
for(int i = up;i<=down;i++){
ans.push_back(matrix[i][right]);
}
if(--right
break;
}
for(int j = right;j>=left;j--){
ans.push_back(matrix[down][j]);
}
if(--down
break;
}
for(int i = down;i>=up;i--){
ans.push_back(matrix[i][left]);
}
if(++left>right){
break;
}
}
return ans;
}
};
59.螺旋矩阵（一维变二维）
示例 ：
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
class Solution {
public:
vector> generateMatrix(int n) {
vector> res(n,vector(n,0)); //二维数组
int i = 0;
int j = 0;
res[i][j] = 1;
while(res[i][j]!=n*n){
while(j+1
res[i][j+1]=res[i][j]+1;
j++;
}
while(i+1
res[i+1][j]=res[i][j]+1;
i++;
}
while(j>0 && 0 == res[i][j-1]){
res[i][j-1]=res[i][j]+1;
j--;
}
while(i>0 && 0 == res[i-1][j]){
res[i-1][j]=res[i][j]+1;
i--;
}
}
return res;
}
};
