LeetCode冲刺：Day9

发布于 2022-11-16  36 次阅读

今天的感想，做题两大不可或缺的东西：心态，草稿。

1. 最小化数组中的最大值

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

学到了一个新的解题手段——二分查找答案。

参考这篇

本题的目的在于，找到一个最小的k，使得在题设操作下，能够使所有的数字都小于k。

在二分查找答案的题目中，首先确定答案所在范围，本题中，k的范围是1-1e9，就是我们要查找的范围。然后确定检查mid是否符合的方法。我们写一个辅助函数check，如果下标较小的数字的“承载量”能够使得mid通过，那就是一个备选答案。在这个基础上，让mid尽可能小。就是说mid通过的时候，使得right=mid。如果mid不能通过，说明太小了，要放大一点，所以让left=mid+1。最后返回left。

代码

class Solution {
private:
    static bool check(vector<int>& nums,int k) {
        long long have=0;
        for (auto num:nums) {
            if (num<=k) have+=k-num;
            else have-=num-k;
            if (have<0) return 0;
        }
        return 1;
    }
public:
    int minimizeArrayValue(vector<int>& nums) {
        int left = 0, right = *max_element(nums.begin(), nums.end());
        while (left<right) {
            int mid = left+(right-left)/2;
            if (check(nums,mid)) right=mid;
            else left=mid+1;
        }
        return left;
    }
};

2. 处理用时最长的那个任务的员工

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

简单题，模拟即可。

代码

class Solution {
public:
    int hardestWorker(int n, vector<vector<int>>& logs) {
        int min=INT_MIN;
        int ans=INT_MAX;
        int start=0;
        for (int i=0;i<logs.size();++i) {
            if (logs[i][1]-start>min) {
                min=logs[i][1]-start;
                ans=logs[i][0];
            } else if (logs[i][1]-start==min) {
                if (logs[i][0]<ans) ans=logs[i][0];
            }
            start=logs[i][1];
        }
        return ans;
    }
};

3. 找出前缀异或的原始数组

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

感觉这道应该算简单题……只要知道性质：a和b异或得到c，则b和c异或等于a，就能直接写出来。

代码

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        vector<int> ans(pref.size());
        ans[0]=pref[0];
        for (int i=1;i<pref.size();++i) ans[i]=pref[i]^pref[i-1];
        return ans;
    }
};

4. 使用机器人打印字典序最小的字符串

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

参考这篇

思考过程中没意识到t是一个栈，尝试去遍历和划分字符串，结果失败了。

实际上，利用栈不难发现，每次我们将当前字符入栈，如果栈顶字符小于剩余字符串中的最小字符，就弹出并加入ans。

记录剩余字符串中的最小字符，我们可以用一个容量26的数组，记录每个字母的余量，再用一个int表示当前最小字符，如果其余量为0，则+1。

代码

class Solution {
public:
    string robotWithString(string s) {
        string ans="";
        vector<int> count(26,0);
        for (auto c:s) ++count[c-'a'];
        int min=0;
        stack<char> st;
        for (int i=0;i<s.size();++i) {
            count[s[i]-'a']--;
            while (min<25&&count[min]==0) ++min;
            st.push(s[i]);
            while (!st.empty()&&st.top()-'a'<=min) {
                ans+=st.top();
                st.pop();
            }
        }
        return ans;
    }
};

5. 矩阵中和能被 K 整除的路径

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

我的想法是回溯法，但超时了。答案用的是动态规划。

参考这篇

这是第一次遇到三维的动态规划。多出来的一维，表示的是模k余数。这题还需要细细品味。

代码

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        vector<vector<vector<int>>> dp(grid.size()+1,vector<vector<int>>(grid[0].size()+1,vector<int>(k,0)));
        dp[0][1][0]=1;
        for (int i=0;i<grid.size();++i) {
            for (int j=0;j<grid[0].size();++j) {
                for (int m=0;m<k;++m) {
                    dp[i+1][j+1][(m+grid[i][j])%k]=(dp[i+1][j][m]+dp[i][j+1][m])%(1000000007);
                }
            }
        }
        return dp[grid.size()][grid[0].size()][0];
    }
};

6. 公因子的数目

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

数据量不大，先用gcd求最大公因子，再遍历寻找最大公因子的因子即可。

代码

class Solution {
private:
    int gcd(int a,int b) {
        if (a<b) {
            int temp=a;
            a=b;
            b=temp;
        }
        if (b!=0) return gcd(b,a%b);
        else return a;
    }
public:
    int commonFactors(int a, int b) {
        int ans=2;
        int res=gcd(a,b);
        if (res==1) return 1;
        int factor=res-1;
        while (factor>1) {
            if (res%factor==0) ++ans;
            --factor;
        }
        return ans;
    }
};

7. 沙漏的最大总和

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

数据量不大，遍历所有漏斗即可。固定漏斗左上角元素坐标后，所有位置坐标都可得。

代码

class Solution {
public:
    int maxSum(vector<vector<int>>& grid) {
        int maxSum=INT_MIN;
        int m=grid.size(),n=grid[0].size();
        for (int i=0;i<m-2;++i) {
            for (int j=0;j<n-2;++j) {
                int sum=grid[i][j]+grid[i][j+1]+grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2];
                maxSum=sum>maxSum?sum:maxSum;
            }
        }
        return maxSum;
    }
};

8. 最小 XOR

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

思路绕了点，但是可以通过，且时间超过100%。

用辅助函数convert把两个数字转换成二进制字符串。统计第二个数中1的数量，然后按如下规则构造x的二进制串：

  1. 对照第一个数的二进制字符串，由高位开始（下标0），遇1补1，遇0补0，1不够了也补0。
  2. 如果此时还有多余的1，对x的二进制串，由低位（字符串尾）开始，遇0就换成1，直到1用完。
  3. 如果此时还有1剩，那么直接加到x的二进制串上，前后都一样。
  4. 将x转为int。

代码

class Solution {
private:
    string convert(int x) {
        string ans="";
        while (x) {
            ans.insert(ans.begin(),x%2==0?'0':'1');
            x/=2;
        }
        return ans;
    }
public:
    int minimizeXor(int num1, int num2) {
        int cntOf1=0;
        string num1_str=convert(num1);
        string num2_str=convert(num2);
        for (int i=0;i<num2_str.size();++i) {
            if (num2_str[i]=='1') ++cntOf1;
        }
        string ans_str="";
        for (int i=0;i<num1_str.size();++i) {
            if (cntOf1==0) ans_str+='0';
            else {
                if (num1_str[i]=='1') {
                    ans_str+='1';
                    --cntOf1;
                }
                else ans_str+='0';
            }
        }
        if (cntOf1>0) {
            for (int i=ans_str.size()-1;i>=0&&cntOf1>0;--i) {
                if (ans_str[i]=='0') {
                    ans_str[i]='1';
                    --cntOf1;
                }
            }
        }
        if (cntOf1>0) {
            while (cntOf1>0)
            {
                ans_str.insert(ans_str.begin(),'1');
                --cntOf1;
            }

        }
        int ans=0;
        int pow=1;
        for (int i=ans_str.size()-1;i>=0;--i) {
            ans+=(int(ans_str[i])-48)*pow;
            pow*=2;
        }
        return ans;
    }
};

9. 对字母串可执行的最大删除数

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

参考这篇

使用了两次DP，第一次是用于判断子串是否相等，第二次是判断删除所需最大次数。

本身第一次DP也可以出道题了，判断相同子字符串的最大长度。

代码

class Solution {
public:
    int deleteString(string s) {
        int n=s.size();
        vector<vector<int>> lcs(n+1,vector<int>(n+1,0));
        for (int i=n-1;i>=0;--i) {
            for (int j=n-1;j>=0;--j) {
                if (s[i]==s[j]) lcs[i][j]=lcs[i+1][j+1]+1;
            }
        }

        vector<int> dp(n+1,0);
        for (int i=n-1;i>=0;--i) {
            dp[i]=1;
            for (int j=1;i+2*j<=n;++j) {
                if (lcs[i][i+j]>=j) dp[i]=max(dp[i],dp[i+j]+1);
            }
        }
        return dp[0];
    }
};

10. 删除字符使频率相同

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

这题我写的太烂了。明明是个很简单的题，自己绕自己。

好吧，看了别人的题解，分类讨论法本来就代码很长orz

必须要打草稿，不然会浪费很多时间，干想能想出什么呢？

代码

class Solution {
public:
    bool equalFrequency(string word) {
        if (word.length()==2) return true;
        vector<int> freq(26,0);
        for (auto c:word) ++freq[c-'a'];
        int minFreq=INT_MAX;
        int maxFreq=INT_MIN;
        for (auto elem:freq) {
            if (elem!=0) {
                minFreq=min(minFreq,elem);
                maxFreq=max(maxFreq,elem);
            }
        }

        int maxCnt=0;
        int minCnt=0;
        for (auto elem:freq) {
            if (elem!=0) {
                if (elem==maxFreq) ++maxCnt;
                if (elem==minFreq) ++minCnt;
                if (elem!=minFreq&&elem!=maxFreq) return false;
            }
        }
        if (maxFreq==minFreq) {
            if (maxFreq==1||(maxCnt==minCnt&&maxCnt==1)) return true;
            else return false;
        }
        if (maxCnt>minCnt) {
            if (minCnt!=1) return false;
            else {
                if (minFreq!=1) return false;
            }
        } else if (maxCnt<minCnt) {
            if (maxCnt!=1) return false;
            else if (maxFreq-minFreq>1) return false;
        } else if (maxCnt!=1) return false;
        else if ((maxFreq-minFreq)>1&&minFreq>1) return false;
        return true;
    }
};