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

作者: 程序员小川 | 来源:发表于2019-06-23 16:36 被阅读4次

    这是悦乐书的第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 第一种解法

    题目的意思是,给了一个字符串,字符串中只包含字符ID,遇到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]=0S[2]='I',继续增加,而前面在第一位已经加过一次,所以A[2]=1S[1]S[3]都等于'D',都做减法,从4开始,所以A[1]=4A[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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode.942-DI字符串匹配(DI String M

        本文链接:https://www.haomeiwen.com/subject/nyfwqctx.html