leetcode讲解--942. DI String Match
文章目录
942. DI String Match
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", thenA[i] < A[i+1] - If
S[i] == "D", thenA[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-
Sonly contains characters"I"or"D".
算法:默认是递增的,然后根据D修改顺序,每遇到一串D,就reverse一段A。
java代码
class Solution {
public int[] diStringMatch(String S) {
int[] A = new int[S.length()+1];
for(int i=0;i<=S.length();i++){
A[i] = i;
}
char[] c = S.toCharArray();
int count=0;
for(int i=0;i<c.length;i++){
if(c[i]=='I'){
continue;
}
while(i<c.length && c[i]=='D'){
i++;
count++;
}
reverse(A, i-count, i);
count=0;
}
return A;
}
private void reverse(int[] A, int begin, int end){
for(int i=0;i<(end-begin+1)/2;i++){
int temp=A[begin+i];
A[begin+i] = A[end-i];
A[end-i] = temp;
}
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论