942. DI String Match
942. DI String Match
下班到家后,刷了刷leetcode,发现了一道很有意思的小题,题目如下:
Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.
Return any permutation A of [0, 1, …, N] such that for all i = 0, …, N-1:
If S[i] == “I”, then A[i] < A[i+1]
If S[i] == “D”, then A[i] > A[i+1]
Example 1:
Input: “IDID”
Output: [0,4,1,3,2]
Example 2:
Input: “III”
Output: [0,1,2,3]
Example 3:
Input: “DDI”
Output: [3,2,0,1]
Note:
1 <= S.length <= 10000
S only contains characters “I” or “D”.
题目大意是,输入一个字符串S,S只包含"I" 或 “D”。"I"表示,当前数小于下一个数,"D"表示当前数大于下一个数;
举个例子:
Input: S = “IDID”
Output: [0,4,1,3,2]
S | 关系 |
---|---|
I | 0 < 4 |
D | 4 > 1 |
I | 1 < 3 |
D | 3 > 2 |
现在给出S,输出任意一满足关系的数组,可能有多个答案,输出其中一个就好。
我的思路如下,欢迎探讨:
首先从头到尾扫描S,遇到"I"就赋值,赋值从0开始,依次赋值0、1、2、3...n
然后从尾到头扫描S,遇到"D"就赋值,赋值从n开始,依次赋值n、n+1、n+2...
对于S = “IDID”
首先从头到尾扫描S,遇到"I"赋值,则扫描一遍后的数组是【0、0、1、0、2】
然后从尾到头扫描S,遇到"D"赋值,扫描一遍后的数组是【0、4、1、3、2】
代码如下:
class Solution {
public int[] diStringMatch(String s) {
int n = s.length() + 1;
int[] result = new int[n];
int num = 0;
// 从头到尾扫描数组,遇到"I",就把num赋值给数组的对应位置
for(int i = 0; i < n-1; i++) {
if('I' == s.charAt(i)) {
result[i] = num++;
}
}
// 注意给数组最后一位赋值
result[n-1] = num++;
// 从尾到头扫描数组,遇到"D",就把num赋值给数组的对应位置
for(int i = n-2; i >= 0; i--) {
if('D' == s.charAt(i)) {
result[i] = num++;
}
}
return result;
}
}
写完代码后,比较幸运地通过了测试用例,一次搞定~