leetcode 第201场周赛 (2020/08/09)

1. 整理字符串

代码1

暴力

class Solution {
public:
    string makeGood(string s) {
        int N = s.length();
        string ans = s;
        while(1)
        {
            N = ans.length();
            string tmp = "";
            bool flag = false;
            int i = 0;
            while(i<N)
            {
                if(ans[i]+32==ans[i+1]||ans[i+1]+32==ans[i])
                {
                    flag = true;
                    i+=2;
                    continue;
                }
                tmp+=ans[i];
                i++;
            }
            
            ans = tmp;
            if(!flag)
                break;
        }
        return ans;
    }
};
           

代码2

栈

class Solution {
public:
    string makeGood(string s) {
        int N = s.length();
        stack<char> st;
        st.push(s[0]);
        for(int i=1;i<N;i++)
        {
            if(!st.empty())
            {
                char top = st.top();
                if(top+32==s[i]||top==s[i]+32)
                {
                    st.pop();
                    continue;
                }
            }
            
            st.push(s[i]);
        }
        string ans = "";
        while(!st.empty())
        {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
           

2. 找出第 N 个二进制字符串中的第 K 位

代码

class Solution {
public:
    string getter(int n)
    {
        if(n==1)
            return "0";
        string str = getter(n-1);
        string tmp = str;
        for(int i=0;i<tmp.length();i++)
        {
            if(tmp[i]=='0')
                tmp[i] = '1';
            else tmp[i] = '0';
        }
        reverse(tmp.begin(),tmp.end());
        return str+'1'+tmp;
    }
    char findKthBit(int n, int k) {
        string ans = getter(n);
        return ans[k-1];
    }
};
           

3. 和为目标值得最大数目不重叠非空子数组数目

思路

使用哈希表记录前缀和的位置。

代码

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int N = nums.size();
        unordered_map<int,int> m;
        m[0] = -1;
        int presum = 0;
        int ends = -1;
        int ans = 0;
        for(int i=0;i<N;i++)
        {
            presum += nums[i];
            if(m.find(presum-target)!=m.end())
            {
                if(m[presum-target]+1>ends)
                {
                    ans++;
                    ends = i;
                }
            }
            m[presum] = i;
        }
        return ans;
    }
};
           

4. 切棍子的最小长度

思路

dp[i][j]表示从i个切割点切到第j个切割点所付出的最小代价

于是有dp[i][j] = min{dp[i][k]+dp[k][j]+cuts[j]-cuts[i]} (i<k<j)

然后需要由短棍至长棍遍历

代码

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        int N = cuts.size();
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(),cuts.end());
        vector<vector<int>> dp(N+2, vector<int>(N+2));
        //棍长由短至长
        for(int cnt=2;cnt<=N+1;cnt++)
        {
            for(int i=0;i+cnt<=N+1;i++)
            {
                int j = i+cnt;
                dp[i][j] = INT_MAX;
                for(int k=i+1;k<j;k++)
                {
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cuts[j]-cuts[i]);
                }
            }
        }
        return dp[0][N+1];
    }
};