算法基础算法

贪心-删数,拼数,选数,改数

字数统计: 6.2k字   |   阅读时长: 28分
, ,

摘要: 贪心算法解决数字构造问题：删数、拼数、选数、改数

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

本文罗列一下力扣上的一大类问题，也就是贪心算法解决的数字构造问题，包括删数、拼数、选数、改数等。主要涉及的题目如下：

$1 删数

316. 去除重复字母 / 1081. 不同字符的最小子序列

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

提示：

1
2
1 <= s.length <= 1e4
s 由小写英文字母组成

示例 1：
输入：s = “bcabc”
输出：”abc”

示例 2：
输入：s = “cbacdcbc”
输出：”acdb”

算法：贪心

1
2
3
4
5
6
从前向后枚举，当前字符 ch: 
    (1) 栈空，进栈
    (2) 栈顶 <= ch，进栈
    (3) 栈顶 > ch，问：ch 之后有无栈顶元素：
        若有，先出栈再进栈
        若无，直接进栈

代码 (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
class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.empty()) return "";
        vector<int> mapping(26); // a~z -> 最右出现位置
        int n = s.size();
        for(int i = 0; i < n; ++i)
            if(mapping[s[i] - 'a'] < i)
                mapping[s[i] - 'a'] = i;
        string result = "";
        vector<bool> used(26, false);
        for(int i = 0; i < n; ++i)
        {
            char ch = s[i];
            if(used[ch - 'a']) continue;
            while(!result.empty() && result.back() > ch && mapping[result.back() - 'a'] > i)
            {
                used[result.back() - 'a'] = false;
                result.pop_back();
            }
            result += ch;
            used[ch - 'a'] = true;
        }
        return result;
    }
};

402. 移掉K位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

提示：

1
2
3
1 <= k <= num.length <= 1e5
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零

示例 1 ：
输入：num = “1432219”, k = 3
输出：”1219”
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：
输入：num = “10200”, k = 1
输出：”200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：
输入：num = “10”, k = 2
输出：”0”
解释：从原数字移除所有的数字，剩余为空就是 0 。

算法：贪心

1
2
从前向后枚举数字，当前枚举到 cur，用一个栈存储当前数字之前的数字：
    若 cur < 栈顶：则不断出栈直至 cur < 栈顶不成立，或者栈空，或者已经删除了 k 个

代码 (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
class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num.empty()) return "0";
        int n = num.size();
        if(k == n) return "0";
        stack<char> st;
        st.push(num[0]);
        for(int i = 1; i < n; ++i)
        {
            while(k > 0 && !st.empty() && st.top() > num[i])
            {
                st.pop();
                --k;
            }
            st.push(num[i]);
        }
        while(k > 0)
        {
            st.pop();
            --k;
        }
        int m = st.size();
        string result(m, ' ');
        for(int i = m - 1; i >= 0; --i)
        {
            result[i] = st.top();
            st.pop();
        }
        int start = 0;
        while(start < m && result[start] == '0')
            ++start;
        if(start == m) return "0";
        return result.substr(start);
    }
};

$2 拼数

321. 拼接最大数

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]

示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]

示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

算法：贪心

考虑从一个数组中取 k 个数，可以用贪心算法，类似于 402. 移掉K位数字。

当有两个数组 nums1 和 nums2 时，从 nums1 取 k1 个，形成结果 vec1，从 nums2 取 k2 个，形成结果 vec2，然后合并到一起。

合并的过程需要比较 vec1 和 vec2 的字典序，可以直接用 lexicographical_compare。

算法:

1
2
3
4
5
6
7
枚举 `k1 + k2 = k`
对于每个 k1, k2，求两次单数组取 k 个数形成最大数的结果 vec1 和 vec2
    vec1 = solve(nums1, k1);
    vec2 = solve(nums2, k2);
    merge(vec1, vec2)

类似分治的思想。

代码 (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
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result;
        int n1 = nums1.size(), n2 = nums2.size();
        for(int k1 = 0; k1 <= k; ++k1)
        {
            int k2 = k - k1;
            if(k1 > n1 || k2 > n2)
                continue;
            result = max(result, merge(solve(nums1, k1), solve(nums2, k2)));
        }
        return result;
    }

private:
    vector<int> solve(const vector<int>& nums, int k)
    {
        if(k == 0) return {};
        vector<int> result;
        int n = nums.size();
        int k_delete = n - k;
        for(int i = 0; i < n; ++i)
        {
            while(!result.empty() && result.back() < nums[i] && k_delete > 0)
            {
                result.pop_back();
                --k_delete;
            }
            result.push_back(nums[i]);
        }
        // 取前 k 个
        result.resize(k);
        return result;
    }

    vector<int> merge(const vector<int>& vec1, const vector<int>& vec2)
    {
        vector<int> result;
        auto s1 = vec1.cbegin();
        auto e1 = vec1.cend();
        auto s2 = vec2.cbegin();
        auto e2 = vec2.cend();
        while(s1 != e1 || s2 != e2)
            result.push_back(lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++);
        return result;
    }
};

1363. 形成三的最大倍数

本题相关的内容参考文章：同余类分解状态优化DP。

$3 选数

矩阵选数

$N \times M$ 正整数矩阵，从每行选出一个数，使得 N 个数的和最大， 1 <= N, M, <+ 100

算法：贪心

要使得总和尽可能大，就要使每个数都尽可能大，因此每个数都选每行最大的那个数。

334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

1
2
1 <= nums.length <= 5 * 1e5
-2^31 <= nums[i] <= 2^31 - 1

算法：贪心

主要维护次大值。使得当前次大值尽可能小。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        int l = INT_MAX, r = INT_MAX;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] <= l)
                l = nums[i];
            else if(nums[i] <= r)
                r = nums[i];
            else
                return true;
        }
        return false;
    }
};

1561. 你可以获得的最大硬币数目

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

  • 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
  • Alice 将会取走硬币数量最多的那一堆。
  • 你将会取走硬币数量第二多的那一堆。
  • Bob 将会取走最后一堆。
  • 重复这个过程，直到没有更多硬币。

给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

提示：

1
2
3
3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4

示例 1：
输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。

示例 2：
输入：piles = [2,4,5]
输出：4

示例 3：
输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end());
        int n = piles.size();
        int cnt = 0;
        int ans = 0;
        for(int i = n - 2; i >= 0; i -= 2)
        {
            ++cnt;
            if(cnt > n / 3)
                break;
            ans += piles[i];
        }
        return ans;
    }
};

944. 删列造序

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = [“abc”, “bce”, “cae”] 可以排列为：

1
2
3
abc
bce
cae

你需要找出并删除 不是按字典序升序排列的 列。在上面的例子（下标从 0 开始）中，列 0（’a’, ‘b’, ‘c’）和列 2（’c’, ‘e’, ‘e’）都是按升序排列的，而列 1（’b’, ‘c’, ‘a’）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：
输入：strs = [“cba”,”daf”,”ghi”]
输出：1
解释：网格示意如下：
cba
daf
ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：
输入：strs = [“a”,”b”]
输出：0
解释：网格示意如下：
a
b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：
输入：strs = [“zyx”,”wvu”,”tsr”]
输出：3
解释：网格示意如下：
zyx
wvu
tsr
所有 3 列都是非升序排列的，所以都要删除。

提示：

1
2
3
4
n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 1000
strs[i] 由小写英文字母组成

代码 (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:
    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].size();
        if(n == 1) return {};
        int ans = 0;
        for(int j = 0; j < m; ++j)
            if(!check(j, A))
                ++ans;
        return ans;
    }

private:
    bool check(int j, const vector<string>& A)
    {
        int n = A.size();
        for(int i = 1; i < n; ++i)
        {
            if(A[i][j] < A[i - 1][j])
                return false;
        }
        return true;
    }
};

955. 删列造序 II

给定由 n 个字符串组成的数组 strs，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = [“abcdef”, “uvwxyz”]，删除索引序列 {0, 2, 3}，删除后 strs 为[“bef”, “vyz”]。

假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] … <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。

示例 1：
输入：strs = [“ca”,”bb”,”ac”]
输出：1
解释：
删除第一列后，strs = [“a”, “b”, “c”]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。

示例 2：
输入：strs = [“xc”,”yb”,”za”]
输出：0
解释：
strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= … 不一定成立。

示例 3：
输入：strs = [“zyx”,”wvu”,”tsr”]
输出：3
解释：
我们必须删掉每一列。

提示：

1
2
3
4
n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] 由小写英文字母组成

代码 (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
class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].size();
        if(n == 1) return 0;
        int ans = 0;
        vector<bool> rows(n, true);
        rows[0] = false;
        int n_rows = n - 1;
        for(int j = 0; j < m; ++j)
        {
            if(!check(j, A, rows, n_rows))
                ++ans;
            else if(n_rows == 0)
                return ans;
        }
        return ans;
    }

private:
    bool check(int j, const vector<string>& A, vector<bool>& rows, int& n_rows)
    {
        int n = A.size();
        vector<int> tmp;
        for(int i = 0; i < n; ++i)
        {
            if(!rows[i]) continue;
            if(A[i - 1][j] > A[i][j])
                return false;
            if(A[i - 1][j] < A[i][j])
            {
                tmp.push_back(i);
            }
        }
        for(int i: tmp)
        {
            --n_rows;
            rows[i] = false;
        }
        return true;
    }
};

1262. 可被三整除的最大和

本题相关的内容参考文章：同余类分解状态优化DP。

$4 改数

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

提示:

1
0 <= n <= 1e9

示例 1:
输入: n = 10
输出: 9

示例 2:
输入: n = 1234
输出: 1234

示例 3:
输入: n = 332
输出: 299

算法：贪心

1
2
3
4
5
记位数为 t，新数字 x 与原数字 N 位数相同，位数不同的时候可以将前几位视为 0
N1, N2, ..., Nt -> x1, x2, ..., xt
枚举 i : 1,2,...,t，维护当前的数字 cur
若 Ni <= cur: 则将 Ni 压进结果
若 Ni > cur: 则上一位减一，从这一位开始到最后都是 9

其中上一位减一这一步，可能需要连续减多个位，例如 N=2215，枚举到 i=3, Ni=1 时，结果中为 22，将结果中的上一位减一得 21，需要继续将上一位也减一，直至减一不影响单调性为止：

1
2
3
4
5
6
7
8
9
flag = true;
int iter = m - i - 2;
while(iter >= 1 && result[iter] == result[iter - 1])
    --iter;
--result[iter];
++iter;
while(iter <= m - i - 2)
    result[iter++] = 9;
result[m - i - 1] = 9;

代码 (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
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        vector<int> digits;
        while(N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }
        int m = digits.size();
        // 1245 -> [5,4,2,1]
        int cur = 0;
        vector<int> result(m, -1);
        bool flag = false;
        for(int i = m - 1; i >= 0; --i)
        {
            if(flag)
            {
                result[m - i - 1] = 9;
                continue;
            }
            if(digits[i] >= cur)
            {
                result[m - i - 1] = digits[i];
                cur = digits[i];
            }
            else
            {
                flag = true;
                int iter = m - i - 2;
                while(iter >= 1 && result[iter] == result[iter - 1])
                    --iter;
                --result[iter];
                ++iter;
                while(iter <= m - i - 2)
                    result[iter++] = 9;
                result[m - i - 1] = 9;
            }
        }
        int ans = 0;
        for(int d: result)
        {
            ans *= 10;
            ans += d;
        }
        return ans;
    }
};

861. 翻转矩阵后的得分

给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。

一次 移动 是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的 得分 就是这些数字的总和。

在执行任意次 移动 后（含 0 次），返回可能的最高分数。

提示：

1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid[i][j] 为 0 或 1

示例 1：
输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

示例 2：
输入：grid = [[0]]
输出：1

算法：贪心

通过横着反转保证最右边一列均为 1。

j = 1,2,…,m-1 枚举列，如果该列上 1 的个数小于 0 的个数，则使用列翻转。

代码 (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
class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        for(vector<int>& row: A)
        {
            if(row[0] == 0)
                for(int &j: row)
                    j ^= 1;
        }
        vector<int> p2(m, 1);
        for(int i = 1; i < m; ++i)
            p2[i] = p2[i - 1] * 2;
        for(int j = 1; j < m; ++j)
        {
            int cnt0 = 0, cnt1 = 0;
            for(int i = 0; i < n; ++i)
            {
                if(A[i][j] == 0)
                    ++cnt0;
                else
                    ++cnt1;
            }
            if(cnt1 < cnt0)
            {
                for(int i = 0; i < n; ++i)
                    A[i][j] ^= 1;
            }
        }
        int ans = 0;
        for(int j = 0; j < m; ++j)
        {
            int cnt1 = 0;
            for(int i = 0; i < n; ++i)
                cnt1 += A[i][j];
            ans += cnt1 * p2[m - j - 1];
        }
        return ans;
    }
};

1053. 交换一次的先前排列

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

如果无法这么操作，就请返回原数组。

提示：

1
2
1 <= arr.length <= 1e4
1 <= arr[i] <= 1e4

示例 1：
输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1

示例 2：
输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列

示例 3：
输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7

算法：贪心

在 [0..n-2] 找到最右边的 ii 满足：存在 j > i, A[ii] > A[j]。

在 [ii+1..n-1] 找到满足 A[jj] < A[i] 的最大的 A[jj]。

代码 (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
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size();
        if(n <= 1)
            return A;
        deque<int> deq;
        int ii = -1;
        for(int i = 1; i < n; ++i)
        {
            if(A[i] < A[i - 1])
                ii = i - 1;
        }
        if(ii == -1)
            return A;
        // [ii+1..n-1] 中寻找 A[j] < A[ii] 的最大的 A[j]
        int jj = ii + 1;
        for(int j = ii + 2; j < n; ++j)
        {
            if(A[j] < A[ii] && A[j] > A[jj])
                jj = j;
        }
        swap(A[ii], A[jj]);
        return A;
    }
};

1432. 改变一个整数能得到的最大差值

给你一个整数 num 。你可以对它进行如下步骤恰好 两次 ：

  • 选择一个数字 x (0 <= x <= 9).
  • 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
  • 将 num 中所有出现 x 的数位都用 y 替换。
  • 得到的新的整数 不能 有前导 0 ，得到的新整数也 不能 是 0 。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

提示：

1
1 <= num <= 10^8

示例 1：
输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：
输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：
输入：num = 123456
输出：820000

示例 4：
输入：num = 10000
输出：80000

示例 5：
输入：num = 9288
输出：8700

算法：贪心

先找从右到左第一个不是 9 的，将其变为 9。

若第一个数字不是 1 则将其变为 1，否则从第二个数字开始，找到第一个不是 0 的。

代码 (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
class Solution {
public:
    int maxDiff(int num) {
        // 先找从右到左第一个不是 9 的，将其变为 9
        // 若第一个数字不是 1 则将其变为 1，否则从第二个数字开始，找到第一个不是 0 的
        if(num < 10) return 8;
        string str_min = to_string(num);
        string str_max = str_min;
        int n = str_min.size();
        char target = '9';
        for(int i = 0; i < n; ++i)
        {
            char cur = str_max[i];
            if(cur != '9')
            {
                target = cur;
                break;
            }
        }
        for(char &c: str_max)
            if(c == target)
                c = '9';
        int m1;
        stringstream ss;
        ss << str_max;
        ss >> m1;

        if(str_min[0] != '1')
        {
            target = str_min[0];
            for(char &c: str_min)
                if(c == target)
                    c = '1';
        }
        else
        {
            target = '0';
            for(int i = 1; i < n; ++i)
            {
                char cur = str_min[i];
                if(cur != '0' && cur != '1')
                {
                    target = cur;
                    break;
                }
            }
            for(char &c: str_min)
                if(c == target)
                    c = '0';
        }
        int m2;
        stringstream ss2;
        ss2 << str_min;
        ss2 >> m2;
        return m1 - m2;
    }
};

1005. K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

提示：

1
2
3
1 <= nums.length <= 1e4
-100 <= nums[i] <= 100
1 <= k <= 1e4

示例 1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        auto it_nonnega = lower_bound(A.begin(), A.end(), 0);
        auto it = A.begin();
        while(it != it_nonnega && K > 0)
        {
            *it = -(*it);
            ++it;
            --K;
        }
        if(K & 1)
        {
            auto min_it = min_element(A.begin(), A.end());
            *min_it = -(*min_it);
        }
        return accumulate(A.begin(), A.end(), 0);
    }
};

1509. 三次操作后最大值与最小值的最小差

给你一个数组 nums 。

每次操作你可以选择 nums 中的任意一个元素并将它改成 任意值 。

在 执行最多三次移动后 ，返回 nums 中最大值与最小值的最小差值。

示例 1：
输入：nums = [5,3,2,4]
输出：0
解释：我们最多可以走 3 步。
第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。
第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。
第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。
执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。

示例 2：
输入：nums = [1,5,0,10,14]
输出：1
解释：我们最多可以走 3 步。
第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。
第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。
第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。
执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。
可以看出，没有办法可以在 3 步内使差值变为0。

示例 3：
输入：nums = [3,100,20]
输出：0
解释：我们最多可以走 3 步。
第一步，将 100 改为 7 。 nums 变成 [4,7,20] 。
第二步，将 20 改为 7 。 nums 变成 [4,7,7] 。
第三步，将 4 改为 3 。 nums 变成 [7,7,7] 。
执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。

提示：

1
2
1 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if(n <= 4)
            return 0;
        nth_element(nums.begin(), nums.begin() + 4, nums.end());
        vector<int> minxs(nums.begin(), nums.begin() + 4);
        nth_element(nums.begin(), nums.end() - 4, nums.end());
        vector<int> maxxs(nums.end() - 4, nums.end());
        sort(maxxs.begin(), maxxs.end());
        sort(minxs.begin(), minxs.end());
        vector<int> cand{
            maxxs[0] - minxs[0],
            maxxs[1] - minxs[1],
            maxxs[2] - minxs[2],
            maxxs[3] - minxs[3]
        };
        return *min_element(cand.begin(), cand.end());
    }
};

1328. 破坏回文串

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，”abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。

提示：

1
2
1 <= palindrome.length <= 1000
palindrome 只包含小写英文字母。

示例 1：
输入：palindrome = “abccba”
输出：”aaccba”
解释：存在多种方法可以使 “abccba” 不是回文，例如 “zbccba”, “aaccba”, 和 “abacba” 。
在所有方法中，”aaccba” 的字典序最小。

示例 2：
输入：palindrome = “a”
输出：””
解释：不存在替换一个字符使 “a” 变成非回文的方法，所以返回空字符串。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size();
        for(int i = 0; i < n / 2; ++i)
        {
            if(palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }
            if(i == n / 2 - 1)
            {
                palindrome[n - 1] = 'b';
                return palindrome;
            }
        }
        return "";
    }
};
Share