这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
