题目
由范围 [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]
分析
这道题目很明显我们可以记录一个最小值和最大值,当s[i] == ‘I’ 的时候perm[i]比perm[i+1]小1,那么perm[i]可以是最小值,perm[i+1]比他大即可。当s[i]=='D’的时候perm[i]可以是最大值,perm[i+1]比他小即可,每遍历完一次就更新这个最小值和最大值,但是这种思路把问题复杂化了,这种思路每遍历一个元素要求同时更新perm[i]和perm[i+1],但是我们怎么能重复更新元素呢,而且也不能确定下一个元素到底是I还是D。所以这种思路是有问题的.
正确的思路是每遍历一个元素更新当前元素就可以了,s[i] == ‘I’ 的时候反应的是未来的i+1要比它大,如果下个元素是D那么用最大值更新如果是I那么就用最小值+1更新,然后循环这个过程。由于数组元素是长度加1,所以最终最小值和最大值肯定趋于一致,
public class findtheShortestSuperstring {
public static void main(String[] args) {
String str = "IDID";
int[] arr = getArr(str);
for(int i = 0;i<arr.length;i++) {
System.out.println(arr[i]);
}
}
public static int[] getArr(String str) {
int len = str.length();
int min = 0;
int max = len;
int[] res = new int[len+1];
int j = 0;
for(int i = 0;i<len;i++) {
if(str.charAt(i) == 'I') {
res[j++] = min++;
} else {
res[j++] = max--;
}
}
res[j] = max;
return res;
}
}