逆向思维

  |  

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

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


疑难杂症

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

问题

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

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

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

代码

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
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。

分析

正向思维

对 n - 1 个数加 1

逆向思维

对 1 个数减 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 个字母。

提示:

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

分析

正向思维

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

逆向思维

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

代码

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
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个语法符号

问题

01,1替换为10。

给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始)

注意:

1
2
N 的范围 [1, 30].
K 的范围 [1, 2^(N-1)].

分析

正向思维

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

逆向思维

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

代码

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
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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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. 坏了的计算器

问题

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

  • 双倍(Double):将显示屏上的数字乘 2;
  • 递减(Decrement):将显示屏上的数字减 1 。

最初,计算器显示数字 X。

返回显示数字 Y 所需的最小操作数。

分析

正向思维

对 X 执行乘 2 或 减 1 操作

逆向思维

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 。

分析

逆向思维

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

代码

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
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 个回合内完成。任何超过此数字的答案将不被接受。

分析

正向思维

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

逆向思维

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

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

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

代码

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
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 。

分析

936. 戳印序列 类似。

逆向思维

预处理颜色信息

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

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

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

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

代码

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
72
73
74
75
76
77
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;
}
};

Share