算法leetcode

leetcode第279场周赛：思维量大、代码量小

字数统计: 3.2k字   |   阅读时长: 13分
,

摘要: 本文是 leetcode 第 279 周赛的记录。主要涉及的算法包括下标映射、模拟、设计、惰性更新、前缀和

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

这是 leetcode 第 279 场周赛，本场比赛的赞助公司就是力扣自己，前 500 名可获得建立免筛，实物奖励也很多：

本场比赛主要涉及到的算法是下标映射、模拟、设计、惰性更新、前缀和。这次的亮点是第 4 题，需要对问题做一定的分析，转换，正确理解问题之后会发现解法是一个常规的算法知识点，代码量非常小。但是问题的分析与转换，思维量很大，比赛时候我是没写出来。

各题的知识点以及参考文章如下：

A题

给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：

按 非递增 顺序排列 nums 奇数下标 上的所有值。
举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。
按 非递减 顺序排列 nums 偶数下标 上的所有值。
举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。
返回重排 nums 的值之后形成的数组。

1
2
3
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100

示例 1：
输入：nums = [4,1,2,3]
输出：[2,3,4,1]
解释：
首先，按非递增顺序重排奇数下标（1 和 3）的值。
所以，nums 从 [4,1,2,3] 变为 [4,3,2,1] 。
然后，按非递减顺序重排偶数下标（0 和 2）的值。
所以，nums 从 [4,1,2,3] 变为 [2,3,4,1] 。
因此，重排之后形成的数组是 [2,3,4,1] 。

示例 2：
输入：nums = [2,1]
输出：[2,1]
解释：
由于只有一个奇数下标和一个偶数下标，所以不会发生重排。
形成的结果数组是 [2,1] ，和初始数组一样。

算法: 构造中间数组+下标映射

首先将奇数位置的元素放到中间数组 A 中；偶数位置的元素放到中间数组 B 中。

对 A 从小到大排序，对 B 从大到小排序，然后用中间数组 A, B 组装新数组 result。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        int n = nums.size();
        int na = (n + 1) / 2;
        int nb = n / 2;
        vector<int> A(na), B(nb);
        for(int i = 0; i < na; ++i)
            A[i] = nums[i * 2];
        for(int i = 0; i < nb; ++i)
            B[i] = nums[i * 2 + 1];
        sort(A.begin(), A.end());
        sort(B.begin(), B.end(), greater<int>());
        vector<int> result(n);
        for(int i = 0; i < n; ++i)
        {
            if(i & 1)
                result[i] = B[(i - 1) / 2];
            else
                result[i] = A[i / 2];
        }
        return result;
    }
};

B题

给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。

返回不含前导零且值最小的重排数字。

注意，重排各位数字后，num 的符号不会改变。

1
2
提示：
-1015 <= num <= 1015

示例 1：
输入：num = 310
输出：103
解释：310 中各位数字的可行排列有：013、031、103、130、301、310 。
不含任何前导零且值最小的重排数字是 103 。

示例 2：
输入：num = -7605
输出：-7650
解释：-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。
不含任何前导零且值最小的重排数字是 -7650 。

算法: 模拟

首先判断正负，如果是负数，则 sign = -1 并将 num 变为其相反数，否则 sign = 1。然后我们在非负的 num 上完成重排，然后将结果乘以 sign 即可。

遍历 num 的所有十进制位，用数组 digits 记录所有数字，n_zero 记录 0 的个数。

然后将 num 排序，若 sign 为 1 则从小到大排序；否则从大到小排序。

如果 sign 为 1，还有额外将 digits[0] 与 digits[n_zero] 交换一下。

最后用 digits 组装新数字即可。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    long long smallestNumber(long long num) {
        if(num == 0)
            return 0;
        vector<int> digits;
        int sign = 1;
        if(num < 0)
        {
            sign = -1;
            num = -num;
        }
        int n_zero = 0;
        while(num != 0)
        {
            if(num % 10 == 0)
                ++n_zero;
            digits.push_back(num % 10);
            num /= 10;
        }
        int m = digits.size();
        if(sign == 1)
        {
            sort(digits.begin(), digits.end());
            swap(digits[n_zero], digits[0]);
        }
        else
            sort(digits.begin(), digits.end(), greater<int>());
        long long ans = 0;
        for(int i = 0; i < m; ++i)
        {
            ans *= 10;
            ans += digits[i];
        }
        ans *= sign;
        return ans;
    }
};

C题

位集 Bitset 是一种能以紧凑形式存储位的数据结构。

请你实现 Bitset 类。

Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
boolean one() 检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
int count() 返回 Bitset 中值为 1 的位的 总数 。
String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。

1
2
3
4
5
6
提示：
1 <= size <= 1e5
0 <= idx <= size - 1
至多调用 fix、unfix、flip、all、one、count 和 toString 方法 总共 1e5 次
至少调用 all、one、count 或 toString 方法一次
至多调用 toString 方法 5 次

示例：

输入
[“Bitset”, “fix”, “fix”, “flip”, “all”, “unfix”, “flip”, “one”, “unfix”, “count”, “toString”]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
输出
[null, null, null, null, false, null, null, true, null, 2, “01010”]

解释
Bitset bs = new Bitset(5); // bitset = “00000”.
bs.fix(3); // 将 idx = 3 处的值更新为 1 ，此时 bitset = “00010” 。
bs.fix(1); // 将 idx = 1 处的值更新为 1 ，此时 bitset = “01010” 。
bs.flip(); // 翻转每一位上的值，此时 bitset = “10101” 。
bs.all(); // 返回 False ，bitset 中的值不全为 1 。
bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = “00101” 。
bs.flip(); // 翻转每一位上的值，此时 bitset = “11010” 。
bs.one(); // 返回 True ，至少存在一位的值为 1 。
bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = “01010” 。
bs.count(); // 返回 2 ，当前有 2 位的值为 1 。
bs.toString(); // 返回 “01010” ，即 bitset 的当前组成情况。

算法: 惰性更新

当 flip 发生时，记录下该动作，也就是此时 n_flip 加 1。

当调用 toString 时，才需要真正执行 flip 动作。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Bitset {
private:
    int n1;
    int n;
    string setting;
    int n_flip;

public:
    Bitset(int size) {
        n1 = 0;
        n = size;
        n_flip = 0;
        setting = string(size, '0');
    }

    void fix(int idx) {
        if(setting[idx] != '1' && (n_flip % 2 == 0))
        {
            setting[idx] = '1';
            ++n1;
        }
        else if(setting[idx] == '1' && (n_flip % 2 == 1))
        {
            setting[idx] = '0';
            ++n1;
        }
    }

    void unfix(int idx) {
        if(setting[idx] != '0' && (n_flip % 2 == 0))
        {
            setting[idx] = '0';
            --n1;
        }
        else if(setting[idx] == '0' && (n_flip % 2 == 1))
        {
            setting[idx] = '1';
            --n1;
        }
    }

    void flip() {
        n1 = n - n1;
        n_flip += 1;
    }

    bool all() {
        return n1 == n;
    }

    bool one() {
        return n1 > 0;
    }

    int count() {
        return n1;
    }

    string toString() {
        if(n_flip & 1)
        {
            string result(n, '1');
            for(int i = 0; i < n; ++i)
                if(setting[i] == '1')
                    result[i] = '0';
            return result;
        }
        else
            return setting;
    }
};

D题

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = ‘0’ 表示第 i 节车厢 不 含违禁货物，而 s[i] = ‘1’ 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

1
2
3
提示：
1 <= s.length <= 2 * 1e5
s[i] 为 '0' 或 '1'

示例 1：
输入：s = “1100101”
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：

  • 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
  • 从右端移除一节车厢 1 次。所用时间是 1 。
  • 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
    总时间是 2 + 1 + 2 = 5 。
    一种替代方法是：
  • 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
  • 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
    总时间也是 2 + 3 = 5 。
    5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
    没有其他方法能够用更少的时间移除这些车厢。

示例 2：
输入：s = “0010”
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：

  • 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
    总时间是 3.
    另一种从序列中移除所有载有违禁货物的车厢的方法是：
  • 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
    总时间是 2.
    另一种从序列中移除所有载有违禁货物的车厢的方法是：
  • 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
    总时间是 2.
    2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
    没有其他方法能够用更少的时间移除这些车厢。

算法: 前缀和

本题属于智商题，难点在于标红的那句话，想到的话这题完全没难度，但是还是挺难想到的。

首先最坏的情况就是直接删除最左侧车厢 n 次，花费 n 时间。

如果想要花费小于 n 时间，可以只删除最左侧的 [0..i-1] ，花费 i，和最右侧的 [j+1..n-1]，花费 n - j - 1。中间的 [i, j] 可能还存在若干个 1，假设是 m 个，那么每个 1 都要花费 2 个单位时间删除，共 2m 时间。

如果我们定义 sums[i] 表示 [0..i-1] 中 1 的个数，也就是 [0..i-1] 的前缀和。那么 m = sums[j] - sums[i - 1]。

于是总的花费时间为 i + n - j - 1 + 2(sums[j] - sums[i - 1])。

我们把上面的式子整理一下，可以分为三个部分，其中一个分跟 i 有关，另一部分跟 j 有关，第三部分是 n + 1：

我们要求上式的最小值，只需要从左到右遍历一次 j。

过程中记录 i - 2sums[i - 1] 的最小值 x，也就是 0 <= i <= j-1 中，i - 2sums[i - 1] 的最小值。

x + (2sums[j] - j) 就是 [0..j] 上当 0 <= i < j 时 (i - 2sums[i - 1]) + (2sums[j] - j) 可以取到的最小值。

我们记录 j = 0,1,...,n-1 过程中该最小值可以取到的最小值。最后把这个最小值再加上 n + 1 即可。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumTime(string s) {
        int n = s.size();
        int x = n;
        int sums = 0;
        int ans = INT_MAX;
        for(int j = 0; j < n; ++j)
        {
            x = min(x, j - 2 * sums);
            sums += s[j] - '0';
            ans = min(ans, x + 2 * sums - j);
        }
        return min(ans + n - 1, n);
    }
};
Share