做怎么样的自己的网站,网站建设设计公司+知乎,网站主持人制作,优秀文创产品设计案例文章目录1. 题目2. 解题1. 题目
现在给定一个只由字符 ‘D’ 和 ‘I’ 组成的 秘密签名。 ‘D’ 表示两个数字间的递减关系#xff0c;‘I’ 表示两个数字间的递增关系。 并且 秘密签名 是由一个特定的整数数组生成的#xff0c;该数组唯一地包含 1 到 n 中所有不同的数字‘I’ 表示两个数字间的递增关系。 并且 秘密签名 是由一个特定的整数数组生成的该数组唯一地包含 1 到 n 中所有不同的数字秘密签名的长度加 1 等于 n。 例如秘密签名 “DI” 可以由数组 [2,1,3] 或 [3,1,2] 生成但是不能由数组 [3,2,4] 或 [2,1,3,4] 生成因为它们都不是合法的能代表 “DI” 秘密签名 的特定串。
现在你的任务是找到具有最小字典序的 [1, 2, ... n] 的排列使其能代表输入的 秘密签名。
示例 1
输入 I
输出 [1,2]
解释 [1,2] 是唯一合法的可以生成秘密签名 I 的特定串
数字 1 和 2 构成递增关系。示例 2
输入 DI
输出 [2,1,3]
解释 [2,1,3] 和 [3,1,2] 可以生成秘密签名 DI
但是由于我们要找字典序最小的排列因此你需要输出 [2,1,3]。注
输出字符串只会包含字符 D 和 I。
输入字符串的长度是一个正整数且不会超过 10,000。来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-permutation 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先生成一个正序数字序列找到连续的D的区间左端点遇到D记录下来为l右端点遇到I记录下来为r反转[l,r]的数字
class Solution {
public:vectorint findPermutation(string s) {int n s.size(), idx, l 0, r 0;vectorint ans(n1);for(idx 1; idx n1; idx)ans[idx-1] idx;while(r n){if(s[r] I){if(l r){reverse(ans, l, r);l r;}l, r;}else//下降r;}if(l r)reverse(ans, l, r);return ans;}void reverse(vectorint ans, int i, int j){while(i j)swap(ans[i], ans[j--]);}
};8 ms 9.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
