数组
- 《代码随想录》
二分查找
704. 二分查找
方法1
- 注意:
- 边界控制。
- 前提是有序数组。
- 循环控制
- 解释: 这里使用我最好理解的一种方式。
- 使用mid控制下标访问，nums[mid]大于target，+1更新左边界，反之，-1更新右边界。相等即找到目标数。
- while循环条件left<=right,left=right仍有需要判断的数。即目标数的索引在数组的
边界。- 防止left+right过大会溢出，所以写成(right-left)/2，等同于(right+left)/2
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n-1;
while(left <= right){
int mid = left+((right-left)/2);
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
}
};
方法2
- 与上一种方法的区别在于区间的控制不同，方法1为[left,right]，方法2为[left,right)。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while(left < right){// 等于时无意义
int mid = left + (right-left)/2;
if(nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid+1;
}else{
return mid;
}
}
return -1;
}
};
- 感悟:
- 算是比较基础的算法了，前两天给群友回答问题的时候，也重新复习了一下，这次顺利AC。
- 这两天可能也是没啥状态，被KMP困住了好久，希望数组可以给我找回点自信。
- 不过这题上来我写了个for循环，md，还是错了下。
35. 搜索插入位置
- 同上一题，不过需要多想一下插入的位置。
- 分析每种情况:
- 目标值在数组所有元素之前
- 目标等于数组中的某一个元素
- 目标值插入到数组中
- 目标值在所有元素之后
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n-1;
while(left <= right){
int mid = left + ((right-left)/2);
if(nums[mid] > target){
right = mid-1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;// 等于数组中某个存在元素
}
}
return right+1;// 其它三种情况
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
- 分析每一种情况
- target在数组的范围内，但是不存在于数组中。
- target在数组范围内，存在于数组中。
- target不在数组范围内。同样也不存在与数组中。
- 在最基础的二分查找上减少了判断，不断收缩边界。结合示例带入进行运算下。
class Solution {
public:
/*
nums: 5 7 7 8 8 10
index: 0 1 2 3 4 5
*/
int getLeftBorder(vector<int>& nums,int target){
int left = 0;
int right = nums.size()-1;
int ret = -2;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] >= target){
right = mid - 1;
ret = right;
}else{
left = mid + 1;
}
}
return ret;
}
int getRightBorder(vector<int>& nums,int target){
int left = 0;
int right = nums.size()-1;
int ret = -2;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
ret = left;
}
}
return ret;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = getLeftBorder(nums,target);
int rightBorder = getRightBorder(nums,target);
if(leftBorder == -2 || rightBorder == -2){// 情况三
return {-1,-1};
}
if(rightBorder - leftBorder > 1){
return {leftBorder+1,rightBorder-1};// 情况二
}
return {-1,-1};// 情况一
}
};
69. x 的平方根
// 时间复杂度 O(logn)
// 空间复杂度 o(1)
class Solution {
public:
int mySqrt(int x) {
int left = 0;
int right = x;
int ret = -1;
while(left <= right){
int mid = left + (right-left)/2;
if((long long)mid * mid <= x){
ret = mid;
left = mid + 1;
}else{
right = mid -1;
}
}
return ret;
}
};
367. 有效的完全平方数
- 二分法的使用，注意根据题意进行判断。
- 个人感觉比上面那两道题要好理解
// 时间复杂度 O(logn)
// 空间复杂度 O(1)
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 0;
int right = num;
while(left <= right){
int mid = left + (right-left)/2;
if((long long)mid*mid < num){
left = mid + 1;
}else if((long long)mid* mid > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
};
双指针
27. 移除元素
- 暴力
// 时间复杂度O(n²)
// 空间复杂度O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
/*3 3 2 2 3 3
3 3 2 3 3
*/
int n = nums.size();
for(int i = 0 ; i < n ;i++){
if(nums[i] == val){
for(int j = i+1;j < n;j++){
nums[j-1] = nums[j];
}
i--;// 后面整体前移，i也前移
n--;
}
}
return n;
}
};
- 双指针
- 快指针负责搜寻目标值，当找到目标，慢指针停住，将后面的非目标值换上来。
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int slowIndex = 0;
for(int fastIndex = 0;fastIndex < n;fastIndex++){
if(nums[fastIndex] != val){// 找到目标值了，慢指针就不动了
nums[slowIndex++] = nums[fastIndex];// 把后面不是目标值的替换上来
}
}
return slowIndex;
}
};
26. 删除有序数组中的重复项
- 双指针，快指针带路，将挑选出来的数，传递给慢指针。完成去重效果。
// 时间复杂度 O(n)
// 空间复杂度 O(1)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1;
int fast = 1;
int n = nums.size();
if(n == 0){
return 0;
}
while( fast < n){
if(nums[fast] != nums[fast-1]){
nums[slow++] = nums[fast];
}
fast++;
}
// 从题目中可以看出，根据新的长度来遍历数组进行判断
return slow;
}
};
283.移动零
- 双指针
// 时间复杂度O(N)
// 空间复杂度O(1)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 在不赋值数组的情况下原地对数组进行操作
int n = nums.size();
if(n == 0)return ;
int fast = 0;
int slow =0;
while(fast < n){
if(nums[fast] != 0){
swap(nums[slow++],nums[fast]);
}
fast++;
}
}
};
844.比较含退格的字符串
- 双指针: 遇到‘#’t将，#后面的数与#前面的交换，最后根据slow指针截取长度。
// 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
string build(string s){
int n = s.size();
int slow = 0;
for(int fast = 0;fast < n;fast++){
if(s[fast] != '#'){
s[slow] = s[fast];
slow++;
}else if(slow > 0){
slow--;
}
}
return s.substr(0,slow);
}
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};
- 用栈很简单,主要还是掌握双指针。
// 时间复杂度 O(m+n) 即O(n)
// 空间复杂度 O(m+n)
class Solution {
public:
string build(string s){
stack<char>st;
for(char c:s){
if(c != '#'){// 刚开始这里多了个条件，st.empty()然后把我坑了。
st.push(c);
}else if(c == '#' && !st.empty()){
st.pop();
}
}
string ret = "";
while(!st.empty()){
ret += ();
st.pop();
}
return ret;
}
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};
977.有序数组的平方
- 双指针: 默认是从升序，但是负数平方后不一定比右边大的整数平方小，i指针从前遍历，j指针从后遍历，取出较大的放入结果集，并移动指针。
// 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = 0;
int j = nums.size() - 1;
int k = nums.size() - 1;
vector<int>ret(nums.size());
while(i <= j){
if(nums[j]*nums[j] > nums[i]*nums[i]){
ret[k--] = nums[j]*nums[j];
j--;
}else{
ret[k--] = nums[i] * nums[i];
i++;
}
}
return ret;
}
};
- 暴力
// 时间复杂度 O(n+nlogn)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n;i++){
nums[i] *= nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};
滑动窗口
- 所谓滑动窗口，就是不断的调节子序列和起始位置和终止位置，从而得出我们想要的结果。
- 滑动窗口三部曲
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
209. 长度最小的子数组
- 本题中:
- 窗口: 为满足和 >= s的长度最小的连续子数组
- 窗口的起始位置如何移动: 如果当前窗口的值大于s了，窗口就要向前移动了(即，该缩小了)。
- 窗口的结束位置如何移动: 窗口结束位置就是遍历数组的指针，也就是for循环里的索引。
- 解题的关键在于窗口的其实位置如何移动。
- j负责便利数组，即j为窗口右侧，i为窗口左侧，当窗口内的值sum大于targat了。
- 就开始计算长度，保存结果，并使窗口的左侧右移。更新窗口内数字和。
- 这是个循环的过程，因为可能去掉左侧的一个值，当前和扔大于target。
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = INT_MAX;// 结果
int sum = 0;// 窗口内元素之和
int i = 0;// 窗口的左侧
int subLength = 0;// 窗口的长度
for(int j = 0; j < n ; j++){
sum += nums[j];
while(sum >= target){// 维护窗口
subLength = j - i + 1;
ret = ret > subLength?subLength:ret;
sum -= nums[i++];
}
}
return ret == INT_MAX ? 0 : ret;
}
};
904. 水果成篮
- 本题中的滑动窗口为一个只能装两种水果的水果篮。
- 使用一个哈希表来记录窗口中的元素数量，当窗口中的种类>2(即==3了)，就开始判断上一次的窗口长度(即水果数量)。
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int,int>mp;
int n = fruits.size();
int ret = 0;// 保存结果，摘取的水果数量
for(int i = 0,j = 0;i < n; i++){
mp[fruits[i]]++;// 摘取水果
while(mp.size() > 2){// 维护滑动窗口
int cur = fruits[j++];
if(--mp[cur] == 0)mp.erase(cur);// 将水果篮中的一种水果拿光了，这时栏中又只剩两种水果了
}
ret = max(ret,i-j+1);// 求长度，即数量
}
return ret;
}
};
76. 最小覆盖子串
- 相关题解-最小覆盖子串 | 图解滑动窗口 | 最通俗易懂的讲解【c++/java版本】
- 大致步骤:
- 本题中维护的滑动窗口为使用哈希表保存遍历s每一个的字符，j为窗口左边界，i为窗口右边界，同时负责向后遍历。
- 如果在我们当前遍历过的s中，其中的某一个字符出现的次数大于在t中出现的次数，此时我们可以尝试收缩边界，即j–。
- 使用一个变量cnt来记录当前遍历过的s中，包含在t中的字符个数，当t==t.size()时，说明我们要找的字符都已经找到了，然后开始获取结果，
- 详细流程详见代码中的注释。
// 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
string minWindow(string s, string t) {
//ts为统计我们需要的字符与其对应的数量，ss为我们维护的滑动窗口
unordered_map<char,int>ts,ss;
// 先统计要查找字符串中各个字符的数量
for(char& c:t)ts[c]++;
int n = s.size();
string ret;
int cnt = 0;// 统计当前应该收集元素的个数
for(int i = 0,j=0;i<n;i++){
ss[s[i]]++;
// 统计收集的指定元素数量和，即找到t中的所有字符，在s中。
if(ss[s[i]] <= ts[s[i]])cnt++;
// 窗口收缩，如果当前的元素s[j](窗口左边界)收集的数量已经大于我们需要的，那就收缩左边界。或者去掉t中没有的元素。
while(ss[s[j]] >ts[s[j]])ss[s[j++]]--;
if(cnt == t.size()){// 每种元素都收集到了，开始计算长度
if(ret.empty() || i-j+1 < ret.size()){// 减少计算次数，如果没计算过或找到更小的连续子数组，才计算，收集结果。
ret = s.substr(j,i-j+1);
}
}
}
return ret;
}
};
模拟行为
59. 螺旋矩阵 II
- 顺时针转，注意控制边界和起始位置。左闭右开。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>ret(n,vector<int>(n,0));
int starX = 0;// 每圈开头
` int starY = 0;
int loop = n / 2;// 转几圈
int mid = n / 2;// 矩阵中间的位置
int count = 1;// 每个元素值
int offset = 1;// 收缩个数
// 顺时针转
int i = 0,j =0;
while(loop--){
i = starX;
j = starY;
// 左闭右开
for(j = starY;j < n-offset;j++){
ret[starX][j] = count++;
}
for(i = starX;i < n-offset;i++){
ret[i][j] = count++;
}
for(;j > starY;j--){
ret[i][j] = count++;
}
for(;i > starX;i--){
ret[i][j] = count++;
}
offset++;
starX++;
starY++;
}
if(n % 2){// 给中间位置单独赋值
ret[mid][mid] = count;
}
return ret;
}
};
54. 螺旋矩阵
- 同上，不过这题是获取元素，注意本体的获取元素以及控制边界的方法，还是与上一题有所不同的。
- 可以理解≈左开右闭。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rc = matrix.size()-1;// 行数-下边界
int cc = matrix[0].size()-1;// 列数-右边界
int row = 0;// 标记当前行-上边界
int col = 0;// 标记当前列-左边界
vector<int>ret;
while(true){
for(int i = col;i <= cc;i++){
ret.push_back(matrix[row][i]);
}
if(++row > rc)break;// 收缩上边界
for(int i = row;i <= rc;i++){
ret.push_back(matrix[i][cc]);
}
if(--cc < col)break;// 收缩右边界
for(int i = cc;i >= col;i--){
ret.push_back(matrix[rc][i]);
}
if(--rc < row)break;// 收缩下边界
for(int i = rc;i>= row;i--){
ret.push_back(matrix[i][col]);
}
if(++col > cc)break;// 收缩左边界
}
return ret;
}
};
剑指 Offer 29. 顺时针打印矩阵
- 与上一题完全相同，但是要加入矩阵是否为空的判断，因为这题给的数据可以为空。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>ret;
if(matrix.empty())return ret;
int rc = matrix.size()-1;// 下
int cc = matrix[0].size()-1;// 右
int row = 0;//上
int col = 0;// 左
while(true){
for(int i = col;i <=cc;i++){
ret.push_back(matrix[row][i]);
}
if(++row > rc)break;
for(int i = row;i <= rc;i++){
ret.push_back(matrix[i][cc]);
}
if(--cc < col)break;
for(int i = cc; i >= col;i--){
ret.push_back(matrix[rc][i]);
}
if(--rc < row)break;
for(int i = rc; i >= row;i--){
ret.push_back(matrix[i][col]);
}
if(++col > cc)break;
}
return ret;
}
};
