LeetCode.942-DI字元串比對(DI String Match)

這是悅樂書的第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+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！