LeetCode第942题,难度为简单。
原题地址:https://leetcode-cn.com/problems/di-string-match/
题目描述:
给定只含 "I"(增大)或 "D"(减小)的字符串 S ,令 N = S.length。
返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1,都有:
如果 S[i] == "I",那么 A[i] < A[i+1]
如果 S[i] == "D",那么 A[i] > A[i+1]
示例 1:
输出:"IDID"
输出:[0,4,1,3,2]
示例 2:
输出:"III"
输出:[0,1,2,3]
示例 3:
输出:"DDI"
输出:[3,2,0,1]
提示:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/di-string-match
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这道题,看上去很难的样子,其实很简单。
首先,我们设定两个指针,分别表示最大和最小值。然后让我们从头往后遍历,如果遇到I,说明要增加了,那么就把当前值设定为最小值+1,如果遇到了D,说明要减小了,那么就把当前值设定为最大值-1。反正它不要求顺序。那么这样的话,每次遇到I,都是加1,遇到D,就会瞬间变成剩下所有数中的最小值。
中文官网题解:
https://leetcode-cn.com/problems/di-string-match/solution/
个人题解:
class Solution {
public int[] diStringMatch(String S) {
int n = S.length();
int[] a = new int[n + 1];
int l = 0;
int r = n;
for (int i = 0; i < n; i++) {
if (S.charAt(i) == 'I') {
a[i] = l++;
} else {
a[i] = r--;
}
}
a[n] = l;
return a;
}
}
结果:
没想到啊,居然又是一道100%的题目。