echo

任生命穿梭 时间的角落

0%

Leetcode第201场周赛

Posted on In Valine:

前言

第二次参加周赛，又是AC两道暴力题，菜鸡只会暴力/(ㄒoㄒ)/~~。

5483. 整理字符串(Easy)

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

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：s = "s"
输出："s"

提示：

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

这题目描述简直离谱，一句话来说就是：不断删除字符串中的 “xX” 或 “Xx”两个字符，x 为某个字母小写，X 为小写字母 x 对应的大写字母。

我们直接使用 StringBuffer 来进行字符的删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String makeGood(String s) {
        StringBuffer sb = new StringBuffer(s);
        for(int i = 0; i <= sb.length() - 2;){
            if( Math.abs(sb.charAt(i) - sb.charAt(i + 1)) == 32 ){
                sb.delete(i, i + 2);
                i = 0;
            }else{
                i++;
            }
        }
        return sb.toString();
    }
}

1545. 找出第 N 个二进制字符串中的第 K 位(Medium)

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

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

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

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

  • S1 = "0"
  • S2 = "011"
  • S3 = "0111001"
  • S4 = "011100110110001"

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：n = 1, k = 1
输出："0"

示例 4：

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

提示：

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

方法一：暴力

菜鸡只会暴力。/(ㄒoㄒ)/~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public char findKthBit(int n, int k) {
        StringBuffer sb = new StringBuffer("0");
        
        for(int i = 2; i <= n; i++){
            StringBuffer temp = invertAndReverse(sb);
            sb.append(1).append(temp);
        }
        return sb.charAt(k - 1);
    }
    
    public StringBuffer invertAndReverse(StringBuffer s){
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '0'){
                sb.append(1);
            }else{
                sb.append(0);
            }
        }
        return sb.reverse();
    }
}

方法二：数学

将 n 个字符串从大到小遍历 n - 1 次，计算第 n 个字符串中间位置 midPos，并判断 k 与 midPos 的位置关系：

  1. 如果 k > midPos，第 n 个字符串第 k 个数字等于 第 n - 1 个字符串的第 midPos * 2 - k 个数字，并累加当前取反次数。

  2. 如果 k < midPos，无需处理，直接遍历第 n - 1 个字符串。

  3. k == midPos，当前位置为 1，根据取反次数计算返回即可。

思路来自___rj。

1
2
3
4
5
6
以 n = 3， k = 5 来解释第 3 条规则：
s1 = 0
s2 = 011
s3 = 0111001

所有的下标都是从 1 开始，n = 3 时，midPos = 2 ^ 2 = 4，而 k = 5，S3[5] 为 reverse(invert(S2))[5 - 4],为invert(s2)[4 - (5 - 4)],即 invert(s2)[3]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public char findKthBit(int n, int k) {
        int invertNum = 0;
        while(n > 1){
            //计算第 n 个字符串的中间位置
            int midPos = (int)Math.pow(2, n - 1);
            if(k == midPos){//等于中间位置，中间位置为 1 变换 invertNum 次得到的数
                return invertNum % 2 == 0 ? '1' : '0';
            }else if(k > midPos){//在第 n - 1个字符串中查找
                k = 2 * midPos - k;
                ++invertNum;
            }
            --n;
        }
        //结果为 初始值 0 变换 invertNum 次得到
        return invertNum % 2 == 0 ? '0' : '1';
    }
}

方法三：递归

和方法二类似，这里用递归实现。

思路来自小名的魔法少爷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public char findKthBit(int n, int k) {
        if(n == 1){
            return '0';
        }

        int mid = (int)Math.pow(2, n - 1);
        if(k == mid){
            return '1';
        }else if(k < mid){
            return findKthBit(n - 1, k);
        }else{
            return findKthBit(n - 1, 2 * mid - k) == '0' ? '1' : '0';
        }
    }
}

1546. 和为目标值的最大数目不重叠非空子数组数目(Medium)

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

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

示例 1：

1
2
3
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组 [(1,1),1,(1,1)] ，它们的和为目标值 2 。

示例 2：

1
2
3
4
输入：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：

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

示例 4：

1
2
输入：nums = [0,0,0], target = 0
输出：3

提示：

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

我们使用前缀和 + 哈希表来实现，此题与560. 和为K的子数组类似，使用 pre[i] 来表示[0 … i] 的子数组的和。使用一个 HashSet 存储已经出现过的连续子数组和 pre[i] ，在遍历的过程中判断是否存在和为 sum - target 的值（连续子数组 pre[j - 1]）：

  • 存在，证明 [j … i]是一个满足条件的结果。此时，需要将 HashSet 和 sum 清空，保证不会用到 [j … i] 的元素 ，同时将 sum 加入 HashSet。
  • 不存在，继续将 pre[i] 加入 HashSet。

思路来自scyq。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        set.add(0);
        int sum = 0, ans = 0;
        for(int x : nums){
            sum += x;
            if(set.contains(sum - target)){
                set.clear();
                sum = 0;
                ++ans;
            }
            set.add(sum);
        }
        return ans;
    }
}

1547. 切棍子的最小成本(Hard)

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

image-20200810164134879

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

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

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

返回切棍子的 最小总成本 。

示例 1：

image-20200810170104715

image-20200810164337518

1
2
3
4
5
6
输入：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：

1
2
3
输入：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[i][j] 表示切割[i, j]这段木棍所需要的最小成本，那么就在[i, j]之间找一个切割点，使切割成本最小。

状态转移方程为：
$$
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cus[j] - cuts[i])
$$
dp[0][n]为最后结果。我们从较小的木棍长度开始 dp，[i, j] 长度最短为 2 ，否则就没有切割点。

思路来自Evelyn 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> list = new ArrayList<>();
        //添加头尾
        list.add(0);
        list.add(n);
        for(int x : cuts){
            list.add(x);
        }
		//排序
        Collections.sort(list);
        int m = list.size();
        int[][] dp = new int[m][m];
        //[i, j]从最短长度 2 开始 dp
        for(int len = 2; len < m; len++){
            for(int i = 0; i + len < m; i++){
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                //list.get(j) - list.get(i)为切割[i, j]的成本
                for(int k = i + 1; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + list.get(j) - list.get(i));
                }
            }
        }
        return dp[0][m - 1];
    }
}