这是悦乐书的第361次更新,第388篇原创
01 看题和准备
今天介绍的是LeetCode
算法题中Easy
级别的第223
题(顺位题号是942
)。给定仅包含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]。
例如:
输入:“IDID”
输出:[0,4,1,3,2]
输入:“III”
输出:[0,1,2,3]
输入:“DDI”
输出:[3,2,0,1]
注意:
-
1 <= S.length <= 10000
-
S仅包含字符I或D。
02 第一种解法
题目的意思是,给了一个字符串,字符串中只包含字符I
和D
,遇到I表示要增加,取值顺序是[0,1,2,...,n]
,而D则下降,取值顺序是[n,n-1,n-2,...,0]
,而通过观察题目中的例子,结果数组的长度要比S
的长度多一位,那么在算完增减后,最后一位元素则需要计算一番才能得出。
我们来分析下题目中的例一,以便更好理解题目,S = "IDID"
,结果数组A = [0,4,1,3,2]
,我们先不看A中的第五个元素,只看前四个元素是怎么来的。
S[0]='I'
,表示增加,所以A[0]=0
,S[2]='I'
,继续增加,而前面在第一位已经加过一次,所以A[2]=1
。S[1]
和S[3]
都等于'D'
,都做减法,从4开始,所以A[1]=4
,A[3]=3
,整合起来,A
中的前四位元素就是[0,4,1,3]
了。
A的最后一位元素,可以通过算0到n的和减去已经从[0,n]
中取过元素之和的差来得到,而0到n的和是一个公差为1的等差数列,利用求和公式很快就可以算出,另外一个和,我们可以定义一个变量sum
,在每次从[0,n]
中取值时就累加一个,算出差值后,赋值给结果数组最后一位元素即可。
class Solution {
public int[] diStringMatch(String S) {
int n = S.length(), i = 0, d = S.length();
int[] result = new int[n+1];
int index = 0;
int sum = 0;
for (int j=0; j<n; j++) {
char c = S.charAt(j);
if (c == 'I') {
sum += i;
result[index++] = i++;
} else {
sum += d;
result[index++] = d--;
}
}
result[n] = (n+1)*n/2 - sum;
return result;
}
}
03 第二种解法
在第一种解法中,我们计算结果数组result
的最后一位元素是通过等差数列求和再减去已经累加的和得到的,但是通过分析,我们可以发现,要找剩下的元素,在n不断递减、i不断递增的情况下,最后剩下的值肯定在中间,和相遇问题类似。例如,0,1,2,3,4
,4减2次到达2,0加两次到达2,而2正好是经过4此计算后剩下的元素。换成其他的数组合,结论依旧。
所以,数组最后一个元素,可以取i
,也可以取d
,效果一样。
class Solution {
public int[] diStringMatch(String S) {
int n = S.length(), i = 0, d = S.length();
int[] result = new int[n+1];
int index = 0;
for (int j=0; j<n; j++) {
char c = S.charAt(j);
if (c == 'I') {
result[index++] = i++;
} else {
result[index++] = d--;
}
}
// result[n] = d; 效果等价
result[n] = i;
return result;
}
}
04 小结
算法专题目前已连续日更超过七个月,算法题文章229+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
网友评论