本文主要是介绍leetcode942.增减字符串匹配,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:
由范围 [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,则返回其中 任何一个 。
示例一:
输入:s = "IDID"
输出:[0,4,1,3,2]
示例二:
输入:s = "III"
输出:[0,1,2,3]
示例三:
输入:s = "DDI"
输出:[3,2,0,1]
问题解决:
本题其实就是根据所给的增减顺序来使0~n的数满足这个顺序,其实横简单。在上升的时候给最先
小的数,下降的时候给最大的数,这样就可以保证上升的时候再随便来一个数都是上升的,下降的
时候随便来一个数也是下降的,这里也是贪心算法的体现,对应的代码实现如下:
class Solution
{
public:vector<int> diStringMatch(string s) {int left = 0;int right = s.size();vector<int> ret;for(auto ch : s){if(ch == 'I'){ret.push_back(left++);}elseret.push_back(right--);}ret.push_back(left);return ret;}
};
这篇关于leetcode942.增减字符串匹配的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!