关键词：力扣，LeetCode，题解，解析，942，Python, C++, Java, 题意
题目地址：https://leetcode.cn/problems/di-string-match/open in new window
题目描述
由范围[0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
- 如果 perm[i] `< perm[i + 1] ，那么 s[i] == 'I'
- 如果 perm[i] >` perm[i + 1] ，那么 s[i] == 'D'
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列 perm，则返回其中 任何一个 。
示例1：
输入：s = "IDID"
输出：[0,4,1,3,2]
示例2：
输入：s = "III"
输出：[0,1,2,3]
示例3：
输入：s = "DDI"
输出：[3,2,0,1]
提示：
- 1
<= s.length<= 10^5 - s 只包含字符 "I" 或 "D"
题目大意
给出一个字符串只包含 I和 D，求数组 [0～N]的一个排列，使得：
- 如果字符串的某个位置是 I，那么数组下一个数字是增加的；
- 如果字符串的某个位置是 D，那么数组下一个数字是减小的。
用下面的图帮助理解，我用了题目中的两个例子s = "IDID"和 "s = DDI"。
根据图，我再解释一下s = "IDID"这个例子。
这个字符串的含义是让我们找到一个 增减增减的数组。数组的长度是 s的长度 +1，即 5；数组中的数字必须是 [0,1,2,3,4]这 5 个数字，必须不重复、不遗漏。
直白点就是问我们，怎么把 [0,1,2,3,4]排列成 增减增减的形状。
所以题目，给出了一种答案：[0,4,1,3,2]这样。
有没有其他答案呢？也是有的，比如 [1,4,0,3,2]也是 增减增减的形状。
题目也说了，只要是符合 s要求的任意一个排列，都是正确答案。所以上面两种排列都是对的。
解题方法
贪心算法
这个题其实有规律可循的，如果注意看题目给的例子，其实也是有规律的。
我们尝试进行分析，仍以s = "IDID"为例，即要把[0,1,2,3,4]重新排列 ：
1、 假如s当前的字符是I，说明数组中的下一个数字比当前数字大；
1、 假如我们把数组中的当前安排成4，那就完犊子了，因为不存在比4更大的数字了；
2、 所以我们当遇到I的时候，我们最好的选择是当前能放的最小数字这样，无论下一个数字放谁，都会比当前数字大都能符合I；
2、 假如s当前的字符是D，说明数组中的下一个数字比当前数字小；
1、 假如我们把数组中的当前安排成0，那就完犊子了，因为不存在比0更小的数字了；
2、 所以我们当遇到D的时候，我们最好的选择是当前能放的最大数字这样，无论下一个数字放谁，都会比当前数字小都能符合D；
所以对于s = "IDID"而言，待重新排序的数组是 [0,1,2,3,4]。我们对 s进行遍历：
1、 s第一个的字符是I，当前候选集是[0,1,2,3,4]，我们选择最小值0（无论下一个数字放谁，都比0大，所以都是增加）；此时结果数组为[0]；
2、 s第二个的字符是D，当前候选集是[1,2,3,4]，我们选择最大值4（无论下一个数字放谁，都比4小，所以一定减小）；此时结果数组为[0,4]；
3、 s第三个的字符是I，当前候选集是[1,2,3]，我们选择最小值1（无论下一个数字放谁，都比1大，所以都是增加）；此时结果数组为[0,4,1]；
4、 s第四个的字符是D，当前候选集是[2,3]，我们选择最大值3（无论下一个数字放谁，都比3小，所以一定减小）；此时结果数组为[0,4,1,3]；
5、 s遍历完成，候选集还剩[2]，我们把最后这个数字放在结果数组中，结果数组为[0,4,1,3,2]；
总之，就是一个贪心策略，遇到 I就选剩余候选集的最小值，遇到 D就选剩余候选集的最大值。
下面的代码中，为了保存当前的最小值和最大值，分别使用了两个变量 ni和 nd。
Python 代码如下：
class Solution:
def diStringMatch(self, S):
"""
:type S: str
:rtype: List[int]
"""
N = len(S)
ni, nd = 0, N
res = []
for s in S:
if s == "I":
res.append(ni)
ni += 1
else:
res.append(nd)
nd -= 1
res.append(ni)
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
C++代码如下：
class Solution {
public:
vector<int> diStringMatch(string s) {
int ni = 0;
int nd = s.size();
vector<int> res;
for (char c : s) {
if (c == 'I') {
res.push_back(ni);
ni ++;
} else {
res.push_back(nd);
nd --;
}
}
res.push_back(ni);
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Java 代码如下：
class Solution {
public int[] diStringMatch(String s) {
int[] res = new int[s.length() + 1];
int ni = 0;
int nd = s.length();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == 'I') {
res[i] = ni;
ni ++;
} else {
res[i] = nd;
nd --;
}
}
res[s.length()] = ni;
return res;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)
总结
1、 这种找规律题目，不妨按照题目给出的示例，自己去琢磨一下；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发