LeetCode 第 201 场周赛

题目

思路:
1. 遍历字符串
2. 如果栈为空, 放入字符
3. 如果栈顶元素与当前元素是大小写关系, 弹栈
4. 否则入栈
5. 循环结束, 将栈中元素逆序拼接成字符串, 返回

代码:

class Solution {
public:
    string makeGood(string s) {
        stack<char> ss;
        int num = 'a' - 'A';
        for (auto it = s.begin(); it != s.end(); ++it) {
            if (ss.empty()) {
                ss.push(*it);
            } else {
                if (num == abs(*it - ss.top())) {
                    ss.pop();
                } else {
                    ss.push(*it);
                }
            }
        }
        string ans;
        while(!ss.empty()) {
            ans = ss.top() + ans;
            ss.pop();
        }
        return ans;
    }
};

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

思路:
1. 暴力法找到第 n 个字符串, 返回第 k 位
2. 使用递归来进行降治获得目标字符串

代码:

class Solution {
public:
    char findKthBit(int n, int k) {
        return getString(n)[k - 1];
    }

    string getString(int n) {
        if (n == 0) {
            return "";
        }
        if (n == 1) {
            return "0";
        }
        string tmp = getString(n - 1);
        return tmp + '1' + reverse(invert(tmp));
    }

    string invert(string str) {
        for (auto& i : str) {
            i = i == '0' ? '1' : '0';
        }
        return str;
    }

    string reverse(const string& str) {
        return string(str.rbegin(), str.rend());
    }

};

和为目标值的最大数目不重叠非空子数组数目

思路:
1. 贪心算法, 不知道为啥对
2. 从头开始记录前缀和, 然后放到 set 容器里, 然后判断 sum - target 是否在容器中
3. 如果在就证明有一个子数组符合要求, 累加 1
4. 因为数组不能重叠, 所以用完需要清空 set
5. 然后要添加 0 到容器中, 因为存在 sum == target 的情况

代码:

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int ans = 0;
        int sum = 0;
        unordered_set<int> s;
        s.insert(0);
        for (auto& i : nums) {
            sum += i;
            if (s.find(sum - target) != s.end()) {
                s.clear();
                ans++;
                sum = 0;
            }
            s.insert(sum);
        }
        return ans;
    }
};

切棍子的最小成本

思路:
1. 区间 dp, 主要是找到区间的转移方程
2. dp[i][j]代表从 i 到 j 所花费的最小值
3. 枚举 i 到 j 直接的点, 判断最小值
4. 可以得到 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + points[j] - points[i])
5. 因为 dp 开始时, i 和 j 直接只有一个 k, 所以, 在遍历所有 i 到 j 之间的数时, 所有的 k 都会被计算完毕
6. 返回 dp[0][n]即可

代码:

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        vector<int> points;
        points.push_back(0);
        points.push_back(n);
        for (int& i : cuts) {
            points.push_back(i);
        }
        sort(points.begin(), points.end());
        vector<vector<int>> dp(points.size(), vector<int>(points.size(), 0));
        for (int len = 2; len < points.size(); ++len) {
            for (int i = 0; i + len < points.size(); ++i) {
                dp[i][i + len] = INT_MAX;
                for (int k = i + 1; k < i + len; ++k) {
                    dp[i][i + len] = min(dp[i][i + len], dp[i][k] + dp[k][i + len] + points[i + len] - points[i]);
                }
            }
        }
        return dp[0][cuts.size() + 1];
    }
};