LeetCode.942-DI字符串匹配(DI String Match)

佚名 6年前 (2019-06-23) 算法 989人围观抢沙发百度已收录

这是悦乐书的第361次更新，第388篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第223题（顺位题号是942）。给定仅包含I（增加）或D（减少）的字符串S，令N = S.length。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

返回元素值范围为[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;
    }
}