LeetCode冲刺：Day13

发布于 2022-11-20  38 次阅读

今天是这个系列倒数第二天了，明天下午去找老师考核，成败在此一举。

还是那句话，尽人事，看天命。不论结果如何，这两周以来的收获，已经使我受益匪浅。

1. 数组中不等三元组的数目

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

暴力遍历即可。

代码

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int ans=0;
        int n=nums.size();
        for (int i=0;i<n;++i) {
            for (int j=i+1;j<n;++j) {
                if (nums[j]!=nums[i]) {
                    for (int k=j+1;k<n;++k) {
                        if ((nums[k]!=nums[i])&&(nums[k]!=nums[j])) {
                            ++ans;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

2. 二叉搜索树最近节点查询

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

没考虑到二叉搜索树不平衡的情况。

正解是中序遍历把元素都拿出来变成数组，再逐个二分查找结果。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<int> nums;
    void inorder(TreeNode* root) {
        if (root==nullptr) return;
        inorder(root->left);
        nums.push_back(root->val);
        inorder(root->right);
    }
    int searchForMin(vector<int>& nums,int target){
        int ans=INT_MIN;
        int left=0;
        int right=nums.size()-1;
        while (left<=right) {
            int mid=left+(right-left)/2;
            if (nums[mid]<=target) {
                ans=max(ans,nums[mid]);
                if (ans==target) break;
                left=mid+1;
            } else right=mid-1;
        }
        return ans==INT_MIN?-1:ans;
    }
    int searchForMax(vector<int>& nums,int target) {
        int ans=INT_MAX;
        int left=0;
        int right=nums.size()-1;
        while (left<=right) {
            int mid=left+(right-left)/2;
            if (nums[mid]>=target) {
                ans=min(ans,nums[mid]);
                if (ans==target) break;
                right=mid-1;
            } else left=mid+1;
        }
        return ans==INT_MAX?-1:ans;
    }
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        nums.clear();
        // nums={1,2,4,6,9,13,14,15};
        inorder(root);
        int n=queries.size();
        vector<vector<int>> ans(n,vector<int>(2));
        for (int i=0;i<n;++i) {
            ans[i][0]=searchForMin(nums,queries[i]);
            ans[i][1]=searchForMax(nums,queries[i]);
        }
        return ans;
    }
};

3. 得到 K 个黑块的最少涂色次数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

看到连续子序列，想到滑动窗口。初始化窗口，统计需要操作的次数。然后每次向后移动一位，根据首尾元素确定操作次数的增减，最终取最小操作次数即可。

代码

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int numOfB=0;
        for (int i=0;i<k;++i) {
            if (blocks[i]=='B') ++numOfB;
        }
        int ans=k-numOfB;
        if (ans==0) return ans;
        int cnt=ans;
        for (int i=k;i<blocks.size();++i) {
            if (blocks[i]=='B'&&blocks[i-k]=='W') {
                cnt--;
            } 
            else if (blocks[i]=='W'&&blocks[i-k]=='B') {
                cnt++;
            }
            ans = min(ans,cnt);
        }
        return ans;
    }
};

4. 二进制字符串重新安排顺序需要的时间

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

想到了把这个过程看作1不断左移的过程，但没能进一步抽象去得出其中的性质。

对于一个1，他左移需要的时间至少是：max(左侧0的数量，左侧1左移所需时间+1)，所以，根据这个递推来从左至右遍历一遍即可。

代码

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int ans=0;
        for (int cnt=0,i=0;i<s.size();++i) {
            if (s[i]=='0') ++cnt;
            else if (cnt>0) ans=max(ans+1,cnt);
        }
        return ans;
    }
};

5. 字母移位 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

我的思路是暴力，但效率很差。

从题解中学到新方法——差分数组，利用它，可以不用再遍历区间。

这部分还要仔细研究。

代码

class Solution {
private:
    char newC(char& c,int& ops) {
        ops%=26;
        int newPos=int(c)+ops;
        if (newPos<'a') newPos+=26;
        else if (newPos>'z') newPos-=26;
        return char(newPos);
    }
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n=shifts.size();
        int m=s.size();
        vector<int> ops(m+1,0);
        for (int i=0;i<n;++i) {
            int tem=1;
            if (shifts[i][2]==0) tem=-1;
            ops[shifts[i][0]]+=tem;
            ops[shifts[i][1]+1]-=tem;
        }
        int sum=ops[0];
        for (int i=0;i<m;++i) {
            s[i]=newC(s[i],sum);
            sum+=ops[i+1];
        }

        return s;
    }
};

6. 不同路径 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

二维DP数组，初始化时要考虑横竖边缘遇到障碍之后，障碍之后的单元格都是0。递推过程中，只更新无障碍的单元格。有障碍单元格默认为0。

代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for (int i=0;i<m;++i) {
            if (obstacleGrid[i][0]==1) break;
            dp[i][0]=1;
        }
        for (int i=0;i<n;++i) {
            if (obstacleGrid[0][i]==1) break;
            dp[0][i]=1;
        }
        for (int i=1;i<m;++i) {
            for (int j=1;j<n;++j) {
                if (obstacleGrid[i][j]==0) {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

7. [整数拆分]()

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

递推公式判断错误。

递推逻辑应当是，当前数字拆成两个数，要么两个数直接相乘，要么接着拆分其中一个。由于遍历已经是从小到大，所以不用重复判断。

代码

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        if (n==2) return 1;
        if (n==3) return 2;
        if (n==4) return 4;
        dp[2]=1;
        dp[3]=2;
        dp[4]=4;
        for (int i=5;i<=n;++i) {
            for (int j=2;j<i-1;++j) {
                dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j));
            }
        }
        return dp[n];
    }
};

8. 最长递增⼦序列

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

两层循环，固定i之后，遍历i之前的元素j。如果i元素大于j元素，那么i元素的最大长度应当是其自身与j最大长度加一之间取最大值。此外，更新i的值时也应当更新整个数组的最大长度ans，最后返回ans。

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        int ans=1;
        vector<int> dp(n,1);
        for (int i=1;i<n;++i) {
            for (int j=0;j<i;++j) {
                if (nums[i]>nums[j]) {
                    dp[i]=max(dp[i],dp[j]+1);
                    ans=max(ans,dp[i]);
                }
            }
        }
        return ans;
    }
};

9. 最长连续递增序列

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

滑动窗口法应该也可以做，但DP更清晰一些。

代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n=nums.size();
        int ans=1;
        vector<int> dp(n,1);
        for (int i=1;i<n;++i) {
            if (nums[i]>nums[i-1]) {
                dp[i]=dp[i-1]+1;
                ans=max(ans,dp[i]);
            }
        }
        return ans;
    }
};

10. 最长公共⼦序列

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

DP，如果当前位置字符相同，就等于i j各退一位的dp值+1；如果当前位置字符不同，那么就在，i退一位，和，j退一位，两者对应的dp值间取最大的。

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size();
        int n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for (int i=1;i<=m;++i) {
            for (int j=1;j<=n;++j) {
                if (text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};