class Solution {
public:
vector<int> findPermutation(string s) {
}
};
484. 寻找排列
由范围 [1,n] 内所有整数组成的 n 个整数的排列 perm 可以表示为长度为 n - 1 的字符串 s ，其中:
perm[i] < perm[i + 1] ，那么 s[i] == ' i 'perm[i] > perm[i + 1] ，那么 s[i] == 'D' 。给定一个字符串 s ，重构字典序上最小的排列 perm 并返回它。
示例 1：
输入： s = "I" 输出： [1,2] 解释： [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串，数字 1 和 2 构成递增关系。
示例 2：
输入： s = "DI" 输出： [2,1,3] 解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI"， 但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。
提示：
1 <= s.length <= 105s[i] 只会包含字符 'D' 和 'I'。原站题解
golang 解法, 执行用时: 152 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-22 10:54:28
func findPermutation(s string) []int {
ans := make([]int, len(s)+1)
for i:=0; i<len(ans); i++ {
ans[i] = i+1
}
flag := true //用来判断是否有变动
for flag { //如果没有变动了，则返回
flag = false
for i,j:=0,1; i<len(s)&&j<=len(s); i,j=i+1,j+1 {
if (s[i] == 'D' && ans[i] < ans[j]) || (s[i] == 'I' && ans[i] > ans[j]) {
ans[i], ans[j] = ans[j], ans[i]
flag = true
}
}
}
return ans
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 10.4 MB, 提交时间: 2023-10-22 10:53:59
class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> res;
stack<char> stk;
for(int i=0; i<=s.size(); i++){
if(s[i] == 'D'){
stk.push(s[i]);
}else{
int j = i+1;
while(!stk.empty()){
stk.pop();
res.push_back(j--);
}
res.push_back(j);
}
}
return res;
}
};
python3 解法, 执行用时: 80 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-22 10:53:45
class Solution:
def findPermutation(self, s: str) -> List[int]:
if not s: return [1]
res, asc = [1], 0
for i in range(len(s)):
if s[i:i+1] == 'D':
res.insert(asc, i + 2)
else:
res.append(i + 2)
asc = i + 1
return res