【代码随想录】二刷-数组

半生瓜的blog

发布于 2023-05-13 14:21:31

3290

发布于 2023-05-13 14:21:31

文章被收录于专栏：半生瓜のblog

数组

二分查找

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.top();
            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;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除

int