逆向思维

字数统计: 4.8k字 | 阅读时长: 21分

2020-09-24

摘要: 本文梳理了 leetcode 上用逆向思维的思想解决的问题。

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

本文梳理力扣上 9 道用逆向思维的思想解决的问题，总览如下：

1558. 得到目标数组的最少函数调用次数

给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。

请你返回将 arr 变成 nums 的最少函数调用次数。

答案保证在 32 位有符号整数以内。

示例 1：
输入：nums = [1,5]
输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。

示例 2：
输入：nums = [2,2]
输出：3
解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
总操作次数为： 2 + 1 = 3 。

示例 3：
输入：nums = [4,2,5]
输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 数组）。

示例 4：
输入：nums = [3,2,2,4]
输出：7

示例 5：
输入：nums = [2,4,8,16]
输出：8

提示：

1 2	1 <= nums.length <= 10^5 0 <= nums[i] <= 10^9

分析

正向思维

初始为全零数组，给定以下两种操作:

让序列中某个数加 1；
让序列中所有数全体乘以 2。

问需要多少次操作能得到目标数组。

逆向思维

初始为目标数组，给定以下两种操作:

让序列中某个数减 1；
让序列中所有数全体除以 2。（要求序列中均为偶数）

问需要多少次操作能得到全零数组。

代码 (C++)

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        bool flag = true;
        while(flag)
        {
            flag = false;
            for(int i = 0; i < n; ++i)
            {
                if(nums[i] > 0)
                    flag = true;
                if(nums[i] & 1)
                {
                    --nums[i];
                    ++ans;
                }
            }
            bool flag2 = false;
            for(int i = 0; i < n; ++i)
            {
                if(nums[i] > 0)
                {
                    flag2 = true;
                    nums[i] /= 2;
                }
            }
            if(flag2)
                ++ans;
        }
        return ans;
    }
};

453. 最小移动次数使数组元素相等

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。

示例 1：
输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

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

提示：

n == nums.length
1 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9
答案保证符合 32-bit 整数

分析

正向思维

对 n - 1 个数加 1。

逆向思维

对 1 个数减 1。

代码 (C++)

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        int mx = nums[0]; // 当前最小值
        int result = 0;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] >= mx)
                result += nums[i] - mx;
            else
            {
                result += (mx - nums[i]) * i;
                mx = nums[i];
            }
        }
        return result;
    }
};

880. 索引处的解码字符串

给定一个编码字符串 S。请你找出解码字符串并将其写入磁带。解码时，从编码字符串中每次读取一个字符，并采取以下步骤：

如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。

现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

提示：

2 <= S.length <= 100
S 只包含小写字母与数字 2 到 9 。
S 以字母开头。
1 <= K <= 10^9
题目保证 K 小于或等于解码字符串的长度。
解码后的字符串保证少于 2^63 个字母。

示例 1：
输入：S = “leet2code3”, K = 10
输出：”o”
解释：
解码后的字符串为 “leetleetcodeleetleetcodeleetleetcode”。
字符串中的第 10 个字母是 “o”。

示例 2：
输入：S = “ha22”, K = 5
输出：”h”
解释：
解码后的字符串为 “hahahaha”。第 5 个字母是 “h”。

示例 3：
输入：S = “a2345678999999999999999”, K = 1
输出：”a”
解释：
解码后的字符串为 “a” 重复 8301530446056247680 次。第 1 个字母是 “a”。

分析

正向思维

将 s 展开到长度大于等于 K，然后返回第 K 个元素。

逆向思维

每当解码的字符串等于 prefix 重复 num 次时，我们就可以将 K 减少到 K % (prefix.size())。

代码 (C++)

class Solution {
public:
    string decodeAtIndex(string S, int K) {
        using ll = long long;
        int n = S.size();
        int left = 0;
        vector<string> strs;
        vector<ll> nums;
        vector<ll> lens;
        // num1, num2, ..., numm
        // str1, str2, ..., strm
        // len1, len2, ..., lenm
        // len[i] = (prev_len + num[i]) * num[i]
        ll prev_len = 0;
        while(left < n)
        {
            int right = left;
            while(right < n && S[right] >= 'a' && S[right] <= 'z')
                ++right;
            strs.push_back(S.substr(left, right - left));
            left = right;
            while(right < n && S[right] >= '2' && S[right] <= '9')
                ++right;
            ll num = 1;
            while(left < right && num <= K)
            {
                int a = S[left] - '0';
                num *= a;
                ++left;
            }
            nums.push_back(num);
            ll len = num * (prev_len + strs.back().size());
            lens.push_back(len);
            prev_len = lens.back();
            if(len >= K)
                break;
        }
        int k = lens.size() - 1;
        while(k >= 0)
        {
            int l = lens[k] / nums[k];
            int offset = (K - 1 + l) % l + 1;
            if(k == 0)
                return string(1, strs[k][offset - 1]);
            if(lens[k - 1] < offset)
                return string(1, strs[k][offset - lens[k - 1] - 1]);
            K = offset;
            --k;
        }
        return "-1";
    }
};

779. 第K个语法符号

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:
输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:
输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01

示例 3:
输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

提示:

1 2	1 <= n <= 30 1 <= k <= 2n - 1

算法：递归

正向思维

求出第 N 行的数列，然后求第 K 个元素。

逆向思维

第 N 行的第 K 个元素来自与第 N - 1 行的第 (K + 1) / 2 个元素。

代码 (C++)

class Solution {
public:
    int kthGrammar(int N, int K) {
        return solve(N, K);
    }

private:
    int solve(int N, int K)
    {
        if(N == 1)
            return 0;
        int ans = -1;
        int top_ans = solve(N - 1, (K + 1) / 2);
        if(top_ans == 0)
        {
            if(K & 1)
                ans = 0;
            else
                ans = 1;
        }
        else
        {
            if(K & 1)
                ans = 1;
            else
                ans = 0;
        }
        return ans;
    }
};

950. 按递增顺序显示卡牌

牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。

最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。

现在，重复执行以下步骤，直到显示所有卡牌为止：

从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。

返回能以递增顺序显示卡牌的牌组顺序。

答案中的第一张牌被认为处于牌堆顶部。

提示：

1
2
3

1 <= A.length <= 1000
1 <= A[i] <= 10^6
对于所有的 i != j，A[i] != A[j]

示例：

输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。

分析

正向思维

初始数组，重复以下两步直至得到结果数组：抽取一个，将牌顶置底。

逆向思维

结果数组，重复以下两步直至得到初始数组：放回一个，将牌底置顶。

代码 (C++)

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int n = deck.size();
        sort(deck.begin(), deck.end());
        list<int> start;
        for(int i = n - 1; i >= 0; --i)
        {
            start.push_front(deck[i]);
            if(i > 0)
            {
                start.push_front(start.back());
                start.pop_back();
            }
        }
        return vector<int>(start.begin(), start.end());
    }
};

991. 坏了的计算器

在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：

双倍（Double）：将显示屏上的数字乘 2；
递减（Decrement）：将显示屏上的数字减 1 。

给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。

示例 1：
输入：startValue = 2, target = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.

示例 2：
输入：startValue = 5, target = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.

示例 3：
输入：startValue = 3, target = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.

提示：

1	1 <= startValue, target <= 1e9

分析

正向思维

对 X 执行乘 2 或减 1 操作。

逆向思维

对 Y 执行除 2（当 Y 是偶数时）或者加 1 操作。

代码 (C++)

class Solution {
public:
    int brokenCalc(int X, int Y) {
        return solve(X, Y);
    }

private:
    int solve(int X, int Y)
    {
        if(X == Y) return 0;
        if(X > Y) return X - Y;
        // 若 Y 奇数
        // Y 无法除以 2
        if(Y & 1)
            return 1 + solve(X, Y + 1);
        return 1 + solve(X, Y / 2);
    }

};

1354. 多次求和构造目标数组

给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：

令 x 为你数组里所有元素的和
选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。

提示：

1
2
3

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

示例 1：
输入：target = [9,3,5]
输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5，选择下标 2
[1, 3, 5], 和为 9，选择下标 0
[9, 3, 5] 完成

示例 2：
输入：target = [1,1,1,2]
输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。

示例 3：
输入：target = [8,5]
输出：true

算法：逆向思维

n == 1 时，a[0] = 1 则 true，a[0] != 1 则 false。

n > 1 时，最后一次改动后，必须有且仅有 1 个最大值 maxx = A[j]，且 maxx > sum(other)，否则 false。

A[j] -= sum(other) 就回退到了上一步。如果若干次回退可以到达全一数组，则 true。

利用取模的性质加速模拟。

maxx / sum(other) 商 k 余 m。则 A[j] 可以直接减 sum(other) * K，变为 m。

代码 (C++)

class Solution {
public:
    bool isPossible(vector<int>& target) {
        int n = target.size();
        if(n == 1)
            return target[0] == 1;
        using ll = long long;
        ll sum = 0;
        multiset<int> setting;
        for(int i: target)
        {
            sum += i;
            setting.insert(i);
        }
        // 必须有且仅有一个最大的数字
        // 且 maxx > sum(other)
        while(true)
        {
            int maxx = *setting.rbegin();
            if(maxx == 1)
                return true;
            int sum_other = sum - maxx;
            if(maxx <= sum_other)
                return false;
            if(sum_other <= 0)
                return false;
            setting.erase(--setting.end());
            int k = maxx / sum_other;
            int m = maxx % sum_other;
            setting.insert(m);
            sum -= sum_other * k;
        }
    }
};

936. 戳印序列

你想要用小写字母组成一个目标字符串 target。

开始的时候，序列由 target.length 个 ‘?’ 记号组成。而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。

举个例子，如果初始序列为 “?????”，而你的印章 stamp 是 “abc”，那么在第一回合，你可以得到 “abc??”、”?abc?”、”??abc”。（请注意，印章必须完全包含在序列的边界内才能盖下去。）

如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。

例如，如果序列是 “ababc”，印章是 “abc”，那么我们就可以返回与操作 “?????” -> “abc??” -> “ababc” 相对应的答案 [0, 2]；

另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。

示例 1：
输入：stamp = “abc”, target = “ababc”
输出：[0,2]
（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）

示例 2：
输入：stamp = “abca”, target = “aabcaca”
输出：[3,0,1]

提示：

1 2	1 <= stamp.length <= target.length <= 1000 stamp 和 target 只包含小写字母。

分析

正向思维

从一串问号序列通过 stamp 的戳印变为 target。

逆向思维

从 target 开始，看能否变成问号序列。

若能够成功，则最后一步一定是 target 中某个等于 stamp 的子串。将其覆盖范围变为问号，然后继续搜索下一个可以匹配 stamp 的位置，如果没找到则匹配失败，在匹配时问号可以视为任意字符。直至将整个序列变为问号。限定记录的path的最大深度为 10 * length。

每一轮在寻找匹配点的时候，只要找到一个，就可以返回然后值搜索该匹配点即可，没必要将每个都找到然后都搜索一遍。

代码 (C++)

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int n = target.size();
        int m = stamp.size();
        if(m > n)
            return {};
        vector<int> path;
        if(!dfs(target, stamp, path))
            return {};
        reverse(path.begin(), path.end());
        return path;
    }

private:
    bool dfs(string& board, const string& stamp, vector<int>& path)
    {
        int n = board.size();
        bool getit = true;
        // 终点判断 O(N)
        for(const char &ch: board)
            if(ch != '?')
            {
                getit = false;
                break;
            }
        if(getit)
            return true;
        if((int)path.size() == n * 10)
            return false;
        // 找到 board 中不全是 ? 的与 target 匹配的位置
        int idx = match(board, stamp);
        if(idx == -1)
            return false;
        int m = stamp.size();
        for(int offset = 0; offset < m; ++offset)
            board[idx + offset] = '?';
        path.push_back(idx);
        if(dfs(board, stamp, path))
            return true;
        return false;
    }

    int match(const string& board, const string& pattern)
    {
        int n = board.size();
        int m = pattern.size();
        for(int i = 0; i <= n - m; ++i)
        {
            bool all_question_mark = true;
            bool is_match = true;
            for(int offset = 0; offset < m; ++offset)
            {
                if(board[i + offset] != pattern[offset] && board[i + offset] != '?')
                {
                    is_match = false;
                    break;
                }
                if(board[i + offset] != '?')
                    all_question_mark = false;
            }
            if(is_match && !all_question_mark)
                return i;
        }
        return -1;
    }
};

1591. 奇怪的打印机 II

给你一个奇怪的打印机，它有如下两个特殊的打印规则：

每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
一旦矩形根据上面的规则使用了一种颜色，那么相同的颜色不能再被使用。

给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 targetGrid[row][col] 是位置 (row, col) 的颜色。

如果你能按照上述规则打印出矩形 targetGrid ，请你返回 true ，否则返回 false 。

提示：

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

示例 1：
输入：targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出：true

示例 2：
输入：targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出：true

示例 3：
输入：targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
输出：false
解释：没有办法得到 targetGrid ，因为每一轮操作使用的颜色互不相同。

示例 4：
输入：targetGrid = [[1,1,1],[3,1,3]]
输出：false

算法：逆向分析

与 936. 戳印序列类似。

预处理颜色信息：

1 2	unordered_map<int, Rec> mapping mapping[color] = {x1, y1, x2, y2}

每一轮，先检查是否是终态，若是则返回 true，若不是则尝试打印：

枚举所有颜色 color，检查(check)颜色的范围(mapping[color])内是否均为 color 或者为 0
若是(check通过)：该范围内置零，mapping 中删掉 color，跳到下一轮
若不是(check不通过)：看下一个颜色

如果某一轮内所有颜色 check 均不通过，返回 false

代码 (C++)

struct Rec
{
    int x1, y1, x2, y2;
    Rec(){}
    Rec(int x1, int y1, int x2, int y2):x1(x1),y1(y1),x2(x2),y2(y2){}
};

class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        vector<vector<int>> &grid = targetGrid;
        int n = grid.size(), m = grid[0].size();
        unordered_map<int, Rec> mapping;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                int color = grid[i][j];
                if(mapping.count(color) == 0)
                    mapping[color] = Rec(i, j, i, j);
                else
                {
                    mapping[color].x1 = min(mapping[color].x1, i);
                    mapping[color].y1 = min(mapping[color].y1, j);
                    mapping[color].x2 = max(mapping[color].x2, i);
                    mapping[color].y2 = max(mapping[color].y2, j);
                }
            }
        while(!getit(grid))
        {
            bool flag = false;
            for(auto color_info: mapping)
            {
                if(check(grid, color_info.first, color_info.second))
                {
                    flag = true;
                    update(grid, color_info.second);
                    mapping.erase(color_info.first);
                    break;
                }
            }
            if(!flag)
                return false;
        }
        return true;
    }

private:
    void update(vector<vector<int>>& grid, const Rec& rec)
    {
        for(int i = rec.x1; i <= rec.x2; ++i)
            for(int j = rec.y1; j <= rec.y2; ++j)
                grid[i][j] = 0;
    }

    bool check(const vector<vector<int>>& grid, const int color, const Rec& rec)
    {
        for(int i = rec.x1; i <= rec.x2; ++i)
            for(int j = rec.y1; j <= rec.y2; ++j)
            {
                if(grid[i][j] != color && grid[i][j] != 0)
                    return false;
            }
        return true;
    }

    bool getit(const vector<vector<int>>& grid)
    {
        int n = grid.size(), m = grid[0].size();
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] != 0)
                    return false;
            }
        return true;
    }
};