On the shoulders of giants.

weekly-contest-201

整理字符串

给你一个由大小写英文字母组成的字符串 s

一个整理好的字符串中,两个相邻字符 s[i]s[i + 1] 不会同时满足下述条件:

  • 0 <= i <= s.length - 2
  • s[i] 是小写字符,但 s[i + 1] 是相同的大写字符;反之亦然

请你将字符串整理好,每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除,直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下,测试样例对应的答案是唯一的。

注意:空字符串也属于整理好的字符串,尽管其中没有任何字符。

示例 1:

输入:s = "leEeetcode"
输出:"leetcode"
解释:无论你第一次选的是 i = 1 还是 i = 2,都会使 "leEeetcode" 缩减为 "leetcode" 。

示例 2:

输入:s = "abBAcC"
输出:""
解释:存在多种不同情况,但所有的情况都会导致相同的结果。例如:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

示例 3:

输入:s = "s"
输出:"s"

提示:

  • 1 <= s.length <= 100
  • s 只包含小写和大写英文字母
题解

直接使用栈模拟即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    string makeGood(string s) {
        string result = "";
        int n = s.size();
        stack<char> sta;
        for(int i = 0; i < n; i++) {
            if(sta.empty()) {
                sta.push(s[i]);
            } else if(abs(sta.top() - s[i]) == 'a' - 'A') {
                sta.pop();
            } else sta.push(s[i]);
        }
        while(!sta.empty()) {
            result = sta.top() + result;
            sta.pop();
        }
        return result;
    }
};

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

给你两个正整数 nk,二进制字符串  Sn 的形成规则如下:

  • S1 = "0"
  • i > 1 时,Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)

例如,符合上述描述的序列的前 4 个字符串依次是:

  • S= "0"
  • S= "011"
  • S= "0111001"
  • S4 = "011100110110001"

请你返回  Snk 位字符 ,题目数据保证 k 一定在 Sn 长度范围以内。

示例 1:

输入:n = 3, k = 1
输出:"0"
解释:S3 为 "0111001",其第 1 位为 "0" 。

示例 2:

输入:n = 4, k = 11
输出:"1"
解释:S4 为 "011100110110001",其第 11 位为 "1" 。

示例 3:

输入:n = 1, k = 1
输出:"0"

示例 4:

输入:n = 2, k = 3
输出:"1"

提示:

  • 1 <= n <= 20
  • 1 <= k <= 2n - 1
题解

显然,该问题存在子问题,我们可以把问题规模变小。

时间复杂度:\(O(\log n)\)

class Solution {
public:
    int solve(long long n, long long k) {
        if(n == 1) return 0;
        if(2 * k - 1 == n) return 1;
        if(k <= n / 2) return solve(n / 2, k);
        return solve(n / 2, n - k + 1) + 1;
    }
    char findKthBit(int n, int k) {
        long long m = 1;
        for(int i = 0; i < n - 1; i++) m = 2 * m + 1;
        return '0' + (solve(m, k) & 1);
    }
};

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

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目,且每个子数组中数字和都为 target 。

示例 1:

输入:nums = [1,1,1,1,1], target = 2
输出:2
解释:总共有 2 个不重叠子数组(加粗数字表示) [1,1,1,1,1] ,它们的和为目标值 2 。

示例 2:

输入:nums = [-1,3,5,1,4,2,-9], target = 6
输出:2
解释:总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

示例 3:

输入:nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出:3

示例 4:

输入:nums = [0,0,0], target = 0
输出:3

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6
题解

贪心,显然,我们要让一个区间的右端点最小,那就是找到第一个符合的区间,然后在之后的区间也是这样,我们使用集合去记录之前出现过的总和为多少。

时间复杂度:\(O(n \log n)\)

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size(), sum = 0, result = 0;
        set<int> s;
        s.insert(0);
        for(int i = 0; i < n; i++) {
            sum += nums[i];
            if(s.find(sum - target) != s.end()) {
                s.clear();
                result++;
                sum = 0;
            }
            s.insert(sum);
        }
        return result;
    }
};

切棍子的最小成本

有一根长度为 n 个单位的木棍,棍上从 0n 标记了若干位置。例如,长度为 6 的棍子可以标记如下:

给你一个整数数组 cuts ,其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割,也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度,切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍(这两根木棍的长度和就是切割前木棍的长度)。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本

示例 1:

输入:n = 7, cuts = [1,3,4,5]
输出:16
解释:按 [1, 3, 4, 5] 的顺序切割的情况如下所示:

第一次切割长度为 7 的棍子,成本为 7 。第二次切割长度为 6 的棍子(即第一次切割得到的第二根棍子),第三次切割为长度 4 的棍子,最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后,总成本 = 16(如示例图中 7 + 4 + 3 + 2 = 16)。

示例 2:

输入:n = 9, cuts = [5,6,1,4,2]
输出:22
解释:如果按给定的顺序切割,则总成本为 25 。总成本 <= 25 的切割顺序很多,例如,[4,6,5,2,1] 的总成本 = 22,是所有可能方案中成本最小的。

提示:

  • 2 <= n <= 10^6
  • 1 <= cuts.length <= min(n - 1, 100)
  • 1 <= cuts[i] <= n - 1
  • cuts 数组中的所有整数都 互不相同
题解

动态规划,设 \(dp_{x,y}\) 为第 x 根棍到第 y 根棍切割完的最小代价。

有动态转移方程:\(dp_{x,y}=\min (dp_{x,k} + dp_{k+1,y}+cuts_{y+1}-cuts_x)\)

为了处理方便,要把 0 和 n 都放去 cuts 里面去,最后排序。

时间复杂度:\(O(n^3)\)

const int INF = 1E9;
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        int m = cuts.size() - 1;
        sort(cuts.begin(), cuts.end());
        vector<vector<int>> dp(m, vector<int> (m, INF));
        for(int i = 0; i < m; i++) dp[i][i] = 0;
        for(int l = 2; l <= m; l++) {
            for(int i = 0; i + l - 1 < m; i++) {
                int j = i + l - 1, cost = cuts[j + 1] - cuts[i];
                for(int k = i; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost);
                }
            }
        }
        return dp[0][m - 1];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注