leetCode進(jìn)階算法題+解析（五十三）

國慶+年假一共十幾天乳规，我是一點沒碰電腦形葬，這次放假忙了好多事，現(xiàn)在要把刷題補回來了驯妄。而且最近發(fā)現(xiàn)了個b站比較不錯的up主荷并，叫狂神，最近在看他的視頻青扔，有興趣的也可以自己看看源织，用一種講故事的方式傳輸思維和知識，推薦一波微猖。
開始刷題啦（ps：今天發(fā)現(xiàn)ac的題目數(shù)超過500了谈息，從一開始的簡單難度的題都能卡兩三天，到現(xiàn)在形成了一定的邏輯思維能力凛剥，會了很多小技巧焦匈，各種排序先紫，查找方法，簡單的dp，回溯梯投，拓?fù)涞龋瑘猿炙㈩}快一年了再来，感謝自己奔穿，只要學(xué)不死，就要往死學(xué)炊昆。）

一和零

題目：在計算機(jī)界中桨吊，我們總是追求用有限的資源獲取最大的收益⊥現(xiàn)在，假設(shè)你分別支配著 m 個 0 和 n 個 1视乐。另外洛搀，還有一個僅包含 0 和 1 字符串的數(shù)組。你的任務(wù)是使用給定的 m 個 0 和 n 個 1 佑淀，找到能拼出存在于數(shù)組中的字符串的最大數(shù)量留美。每個 0 和 1 至多被使用一次。

示例 1:
輸入: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出: 4
解釋: 總共 4 個字符串可以通過 5 個 0 和 3 個 1 拼出渣聚，即 "10","0001","1","0" 独榴。
示例 2:
輸入: strs = ["10", "0", "1"], m = 1, n = 1
輸出: 2
解釋: 你可以拼出 "10"，但之后就沒有剩余數(shù)字了奕枝。更好的選擇是拼出 "0" 和 "1" 棺榔。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 僅由 '0' 和 '1' 組成
1 <= m, n <= 100

思路：這個題怎么說呢，我審了好幾遍題才理解隘道，感覺是個很明顯的最優(yōu)解的題目症歇，我暫時第一反應(yīng)是從字符串短的開使拼，莫名其妙的覺得最優(yōu)解都可以用dp實現(xiàn)谭梗。我先去試試看忘晤。
我感覺我的思路還是不錯的，寫了一個排序激捏，根據(jù)1的個數(shù)/根據(jù)0的個數(shù)排序设塔，然后兩個數(shù)組看哪個能走的結(jié)果長，就選擇哪個結(jié)果远舅。最開始排序是字符串排序闰蛔，但是真正做了發(fā)現(xiàn)轉(zhuǎn)化成二維數(shù)組更好，每一個元素用一個數(shù)組表示图柏，數(shù)組第一個數(shù)字是需要的0的個數(shù)序六，第二個數(shù)字是需要的1的個數(shù)。等ac了再過來分享蚤吹。
好吧例诀，上面的思路完美的失敗了，果然還是要dp裁着。我去專心研究怎么套模板吧繁涂。
直接貼代碼:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length == 0) return 0;
        //字符串?dāng)?shù)組轉(zhuǎn)成二維數(shù)組
        int[][] arr = new int[strs.length][];
        for(int i = 0;i<arr.length;i++){
            arr[i] = new int[2];
            for(char c:strs[i].toCharArray()) {
                arr[i][c-'0']++;
            }
        }
        //動態(tài)規(guī)劃，用數(shù)組記錄中間過程的遞歸
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        for(int k = 1;k<=strs.length;k++){
            int[] temp = arr[k-1];
            for(int i = 0;i<=m;i++){
                for(int j = 0;j<=n;j++){
                    if(temp[0]<=i && temp[1]<=j){
                        dp[k][i][j] = Math.max(dp[k-1][i][j],1+dp[k-1][i-temp[0]][j-temp[1]]);
                    }else{
                        dp[k][i][j] = dp[k-1][i][j];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

}

需要注意下二驰，上面代碼的主要邏輯在于三層for循環(huán)里面的if-else中扔罪。else中很好理解，就是當(dāng)前的數(shù)值已經(jīng)湊不出來了诸蚕，那么直接湊出來的最大數(shù)就是上一個元素能湊出來的最大數(shù)步势，所以沒啥好說的。問題就是當(dāng)前元素能湊出來背犯，那么減去當(dāng)前用掉的0和1坏瘩，然后存入湊成的個數(shù)。
因為這個是個三維數(shù)組漠魏，我在畫草圖方便理解的時候把自己都繞懵了倔矾。其實這個性能也不咋地，三層for循環(huán)柱锹，mnl的時間復(fù)雜度哪自。這里說是dp還不如說就是記錄中間過程的暴力破解。
看了官方題解中的另一種寫法禁熏。感覺比我的要明了多了壤巷，我直接貼出來：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length == 0) return 0;
        //字符串?dāng)?shù)組轉(zhuǎn)成二維數(shù)組
        int[][] arr = new int[strs.length][];
        for(int i = 0;i<arr.length;i++){
            arr[i] = new int[2];
            for(char c:strs[i].toCharArray()) {
                arr[i][c-'0']++;
            }
        }
        //動態(tài)規(guī)劃，用數(shù)組記錄中間過程的遞歸
        int[][] dp = new int[m+1][n+1];
        for(int k = 1;k<=strs.length;k++){
            int[] count = arr[k-1];
            for (int zeroes = m; zeroes >= count[0]; zeroes--)
                for (int ones = n; ones >= count[1]; ones--)
                    dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);

        }
        return dp[m][n];
    }

這種方式怎么說呢瞧毙，二維維數(shù)組看著更簡單了胧华，簡單來說就是每一個元素選擇/不選擇都作為一條線走下去。然后求最優(yōu)解宙彪。我一般遇到這種問題都是按照思路模板套的：

判斷是不是可以用選/不選 來解決這道題矩动。（本題是可以的，每一個字符串選/不選去拆）
確定是dp释漆。那么狀態(tài)轉(zhuǎn)移方程是什么悲没？（這個元素選了的當(dāng)前最優(yōu)解和不選這個元素的當(dāng)前最優(yōu)解。因為雖說是1和0男图，但是本質(zhì)是一個串示姿。）
帶入到這個題，因為他本身要考慮0和1兩個因素享言。所以用傳統(tǒng)的一維數(shù)組是記錄不了的峻凫，所以這里一定是二維dp確定下來了。
二維數(shù)組怎么記錄呢览露？到了關(guān)鍵是時候了荧琼，到這里我一般都是用最笨的方法：帶入法來理解這個中題目（我dp不行，所以這里用最笨的方法差牛，其實很多大佬都能看出狀態(tài)轉(zhuǎn)移方程命锄，我反正不行）。隨便寫五個元素偏化，然后從第一個開始一點點判斷脐恩。如下圖。

我的思路

其實比較low侦讨，不夸張的說這個題我推演了三四個小時驶冒。確實dp這里稍微難一點就賊費勁苟翻。不過好歹是做出來了，這個題就這樣了骗污。下一道題了崇猫。

漢明距離總和

題目：兩個整數(shù)的漢明距離指的是這兩個數(shù)字的二進(jìn)制數(shù)對應(yīng)位不同的數(shù)量。計算一個數(shù)組中需忿，任意兩個數(shù)之間漢明距離的總和诅炉。

示例:
輸入: 4, 14, 2
輸出: 6
解釋: 在二進(jìn)制表示中，4表示為0100屋厘，14表示為1110涕烧，2表示為0010。（這樣表示是為了體現(xiàn)后四位之間關(guān)系）
所以答案為：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
數(shù)組中元素的范圍為從 0到 10^9汗洒。
數(shù)組的長度不超過 10^4议纯。

思路：這個題的難度，我不知道是不是在超時上溢谤，反正我個人感覺單純的實現(xiàn)不是很難痹扇。首先兩兩比較獲得結(jié)果。其次雙層for循環(huán)第一層0-數(shù)組長溯香。第二層第一層下一個到最后一一判斷相加鲫构。我去實現(xiàn)下試試。我預(yù)感告訴我會超時玫坛。哈哈结笨。

暴力法超時

怎么說呢，一點不遺憾湿镀，意料之中的結(jié)果炕吸。畢竟中等難度的題不至于這么簡單。剩下的就該是優(yōu)化了勉痴。其實我是有個大膽的想法的赫模。本質(zhì)上某一位數(shù)上比如3個1,4個0。那么是可以算出這位數(shù)中不同的個數(shù)是多少的蒸矛。每個1和其余四個0都是四種不同瀑罗。所以這個位數(shù)上不同數(shù)目是3*4=12.
然后所有數(shù)字一共就12位。我去試試這種方式能不能ac雏掠。
居然acl斩祭，隨著時間的執(zhí)行我這個心都在顫抖，雖然是低空略過乡话，只超過百分之五的人摧玫，我先把代碼貼上：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        //第一個32是位數(shù)。每一位分0绑青，1兩種情況诬像。所以是二維數(shù)組屋群。
        int[][] d = new int[32][2];
        for(int i : nums){
            int j = 0;
            //因為最大是10的九次方，也就是30位
            while(j<30){
                if((i&1)==0){
                    d[j][0]++;
                } else{
                    d[j][1]++;
                }
                i /= 2;
                j++;
            }
        }
        for(int[] i : d) {
            res += i[0]*i[1];
        }
        return res;
    }

}

起碼說明思路是沒問題的坏挠。我覺得其實還有優(yōu)化的空間谓晌，比如說這個前置0要賦值為1的這個問題。我再想想癞揉。第二版本代碼：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        int len = nums.length;
        //第一個32是位數(shù)。每一位分0溺欧，1兩種情況喊熟。所以是二維數(shù)組。
        int[][] d = new int[32][2];
        for(int i : nums){
            int j = 0;
            while(i!=0){
                if((i&1)==0){
                    d[j][0]++;
                } else{
                    d[j][1]++;
                }
                i /= 2;
                j++;
            }
        }
        for(int[] i : d) {
            if(i[0]+i[1] == len) {
                res += i[0]*i[1];
            }else{//走到這說明出現(xiàn)了某位數(shù)只有1.0是前置位0所以沒計數(shù)
                res += i[1]*(len-i[1]);
            }
        }
        return res;
    }
}

通過這個變化姐刁，我又有了新思路芥牌。其實不用統(tǒng)計1的個數(shù)0的個數(shù)。只統(tǒng)計一個就行了聂使。畢竟不是1就是0.我再去改下壁拉。
最終版代碼：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        int len = nums.length;
        //計算二進(jìn)制每一位1的個數(shù)。
        int[] d = new int[32];
        for(int i : nums){
            int j = 0;
            while(i!=0){
                //當(dāng)結(jié)果是1則計數(shù)
                if((i&1)==1) d[j]++;
                j++;
                i /= 2;
            }
        }
        for(int i : d) {
            if(i!=0)res += i*(len-i);
        }
        return res;
    }
}

說一個很悲哀的故事：這么多版本柏靶，就沒有一個性能是好的弃理。哭了屎蜓。我去看看性能排行第一的代碼吧痘昌。

超過百分之五的用戶

！＞孀Ａ咎Α！說實話扼劈，除了是用二進(jìn)制計算驻啤，其余的思路是一樣一樣的，人家是性能第一荐吵，我是性能慘不忍睹骑冗。。附上代碼下一題：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += (num >>> i) & 1;
            }
            res += cnt * (n - cnt);
        }
        return res;
    }
}

在圓內(nèi)隨機(jī)生成點

題目：給定圓的半徑和圓心的 x先煎、y 坐標(biāo)沐旨，寫一個在圓中產(chǎn)生均勻隨機(jī)點的函數(shù) randPoint 。

說明:

輸入值和輸出值都將是浮點數(shù)榨婆。

圓的半徑和圓心的 x磁携、y 坐標(biāo)將作為參數(shù)傳遞給類的構(gòu)造函數(shù)。

圓周上的點也認(rèn)為是在圓中良风。

randPoint 返回一個包含隨機(jī)點的x坐標(biāo)和y坐標(biāo)的大小為2的數(shù)組谊迄。

示例 1：
輸入:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
輸出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：
輸入:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
輸出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
輸入語法說明：
輸入是兩個列表：調(diào)用成員函數(shù)名和調(diào)用的參數(shù)闷供。Solution 的構(gòu)造函數(shù)有三個參數(shù)，圓的半徑统诺、圓心的 x 坐標(biāo)歪脏、圓心的 y 坐標(biāo)。randPoint 沒有參數(shù)粮呢。輸入?yún)?shù)是一個列表婿失，即使參數(shù)為空，也會輸入一個 [] 空列表啄寡。

思路：簡單來說豪硅，是保證給定的橫縱坐標(biāo)是圓范圍內(nèi)的。其實我覺得這個比較難的是隨機(jī)圓的范圍吧挺物。如果是正方形長方形等是很容易算出邊框的懒浮。在這區(qū)間random就好，但是因為是圓识藤，所以還是挺不好實現(xiàn)的砚著。我去畫圖理理思路。
這個題著實是我的知識盲區(qū)痴昧。畢竟我數(shù)學(xué)基礎(chǔ)一直是渣渣稽穆。看了一種題解覺得很適合我（微積分的那個屬于看都不想看）赶撰。就是半徑形成正方形秧骑。正方形內(nèi)取點。如果點在圓上則返回扣囊。否則重新取點乎折。我是覺得這種方式我能理解也能做出來，去寫代碼試試了侵歇。
我直接貼代碼：

class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while(true) {
            double xg = x0 + Math.random() * rad * 2;
            double yg = y0 + Math.random() * rad * 2;
            if (Math.sqrt(Math.pow((xg - xc) , 2) + Math.pow((yg - yc), 2)) <= rad)
                return new double[]{xg, yg};
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

怎么說呢骂澄，感覺對我這種數(shù)學(xué)渣很不友好啊。而且get不到考點是什么惕虑。反正現(xiàn)在對付實現(xiàn)了（看到題解有的思路）坟冲。也不多bb，下一題溃蔫。

神奇字符串

題目：神奇的字符串 S 只包含 '1' 和 '2'健提，并遵守以下規(guī)則：字符串 S 是神奇的，因為串聯(lián)字符 '1' 和 '2' 的連續(xù)出現(xiàn)次數(shù)會生成字符串 S 本身伟叛。字符串 S 的前幾個元素如下：S = “1221121221221121122 ......”如果我們將 S 中連續(xù)的 1 和 2 進(jìn)行分組私痹，它將變成：

1 22 11 2 1 22 1 22 11 2 11 22 ......

并且每個組中 '1' 或 '2' 的出現(xiàn)次數(shù)分別是：

1 2 2 1 1 2 1 2 2 1 2 2 ......

你可以看到上面的出現(xiàn)次數(shù)就是 S 本身。給定一個整數(shù) N 作為輸入，返回神奇字符串 S 中前 N 個數(shù)字中的 '1' 的數(shù)目紊遵。注意：N 不會超過 100,000账千。

示例：
輸入：6
輸出：3
解釋：神奇字符串 S 的前 6 個元素是 “12211”，它包含三個 1暗膜，因此返回 3匀奏。

思路：怎么說呢，這個串確實是挺神奇的学搜，畢竟我看了好幾遍才看懂娃善。我暫時的想法就是前19位是確定的。其實根據(jù)這19位是可以繼續(xù)往下無線順延的瑞佩。我去試試代碼聚磺。
三次過的。第一次是截取字符串的時候用的n-1.最近學(xué)redis學(xué)多了钉凌，redis的截取就是閉區(qū)間。但是java中是含前不含后的捂人，所以這里錯了御雕。第二次是我沒想到n還能等于0.所以補了下第一句代碼。第三次ac滥搭，雖然性能差點酸纲。

class Solution {
    public int magicalString(int n) {
        if(n==0) return 0;
        if(n<=3) return 1;
        StringBuffer sb = new StringBuffer("122");
        int idx = 2;//從下標(biāo)為2的開始遍歷
        int flag = 2;//當(dāng)前是1還是2
        int realIdx = 2;//從下標(biāo)為2的開始算。
        while(realIdx<n) {
            char c = sb.charAt(idx);         
            if(flag == 1) {
                //如果上一個是1這個續(xù)2
                sb.append(c=='1'?"2":"22");
                flag = 2;
            }else {//上一個是2瑟匆，這個續(xù)1
                sb.append(c=='1'?"1":"11");
                flag = 1;
            }
            idx++;
            realIdx += (c=='1'?1:2);
        }
        //有可能最后是兩個數(shù)闽坡，sb長度大于n
        String res = sb.toString().substring(0, n).replace("2", "");
        return res.length();
    }
}

整體來說其實這個題給了前兩個數(shù)就可以自己往下編了，我這里是把所有的數(shù)追加了下愁溜，再判斷這個字符串的1的個數(shù)疾嗅。這樣也是讓思路更清晰的。至于性能問題不知道是不是因為我選擇stringbuffer這種方式才這樣的冕象〈校可能用隊列會更好？我去試一下渐扮。

class Solution {
    public int magicalString(int n) {
        if(n == 0) return 0;
        int res = 1;
        if(n<=3) return res;
        boolean flag = true;
        int num = 3;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(2);
        while(num<n) {
            queue.add(flag==true?1:2);
            if(flag) res++;//說明插入的是1论悴，計數(shù)+1
            num++;
            if(queue.poll()==2 && num<n) {//如果num=n了后面的不用計算了
                queue.add(flag==true?1:2);
                if(flag) res++;//說明插入的是1，計數(shù)+1
                num++;
            }
            flag = !flag;           
        }
        return res;
    }
}

說真的這個改動差不多是新做了一次墓律，不過性能沒好多少膀估，貼上個截圖我去看性能排行第一的代碼了：

提交記錄

看了性能排行第一的代碼，只能說可能是越簡單的越美好耻讽。人家的簡單的多了察纯，就是數(shù)組操作，但是性能好。貼出來大家一起看看：

class Solution {
    public int magicalString(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 3) {
            return 1;
        }
        boolean[] nums = new boolean[n];
        nums[1] = true;
        int i1 = 1, i2 = 1;
        boolean cur = true;
        while(i2 < n) {
            nums[i2++] = cur;
            if (i2 == n) {
                break;
            }
            if (nums[i1]) {
                nums[i2++] = cur;
            }
            i1++;
            cur = !cur;
        }
        int res = 0;
        for (boolean b : nums) {
            if (!b) {
                res++;
            }
        }
        return res;
    }
}

好了捐寥，下一題吧笤昨。

預(yù)測贏家

題目：給定一個表示分?jǐn)?shù)的非負(fù)整數(shù)數(shù)組。玩家 1 從數(shù)組任意一端拿取一個分?jǐn)?shù)握恳，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分?jǐn)?shù)瞒窒，然后玩家 1 拿，…… 乡洼。每次一個玩家只能拿取一個分?jǐn)?shù)崇裁，分?jǐn)?shù)被拿取之后不再可取。直到?jīng)]有剩余分?jǐn)?shù)可取時游戲結(jié)束束昵。最終獲得分?jǐn)?shù)總和最多的玩家獲勝拔稳。給定一個表示分?jǐn)?shù)的數(shù)組，預(yù)測玩家1是否會成為贏家锹雏。你可以假設(shè)每個玩家的玩法都會使他的分?jǐn)?shù)最大化巴比。

示例 1：
輸入：[1, 5, 2]
輸出：False
解釋：一開始，玩家1可以從1和2中進(jìn)行選擇礁遵。
如果他選擇 2（或者 1 ）轻绞，那么玩家 2 可以從 1（或者 2 ）和 5 中進(jìn)行選擇。如果玩家 2 選擇了 5 佣耐，那么玩家 1 則只剩下 1（或者 2 ）可選政勃。
所以，玩家 1 的最終分?jǐn)?shù)為 1 + 2 = 3兼砖，而玩家 2 為 5 奸远。
因此，玩家 1 永遠(yuǎn)不會成為贏家讽挟，返回 False 懒叛。
示例 2：
輸入：[1, 5, 233, 7]
輸出：True
解釋：玩家 1 一開始選擇 1 。然后玩家 2 必須從 5 和 7 中進(jìn)行選擇耽梅。無論玩家 2 選擇了哪個芍瑞，玩家 1 都可以選擇 233 。
最終褐墅，玩家 1（234 分）比玩家 2（12 分）獲得更多的分?jǐn)?shù)拆檬，所以返回 True，表示玩家 1 可以成為贏家妥凳。
提示：
1 <= 給定的數(shù)組長度 <= 20.
數(shù)組里所有分?jǐn)?shù)都為非負(fù)數(shù)且不會大于 10000000 竟贯。
如果最終兩個玩家的分?jǐn)?shù)相等，那么玩家 1 仍為贏家逝钥。

思路：我不知道為啥leetcode里的人這么愛玩游戲屑那，還他媽都是高智商的游戲拱镐。太扎心了。反正這個題目總而言之應(yīng)該可以用暴力法破解吧持际。其實每個人都選擇最大的結(jié)果沃琅，那么另一個人就是最小的結(jié)果，這個是一個四重選擇的操作蜘欲。也可以說是遞歸操作益眉。思路是有的，我去實現(xiàn)下試試姥份。
直接貼代碼：

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        return dfs1(nums,0,nums.length-1)*2>=sum;
    }
    public int dfs1(int[] nums,int l,int r) {
        //說明只有一個元素了那么下一手的人沒得選.所以一個是元素值郭脂，一個是0
        if(l==r) return nums[l];
        //剩兩個元素，選擇大的那個
        if(l==r-1) return Math.max(nums[l],nums[r]);
        //其實這是四個選擇澈歉。 我可以選左/右展鸡，下一個人可以選左/右
        //假如我選擇了左，下一個人要么選左2.要么選右埃难。我只能獲取較小的那個
        int left = Math.min(dfs1(nums, l+1, r-1), dfs1(nums, l+2, r))+nums[l];
        //假如我選了右莹弊，下一個人要么左1，要么右2
        int right = Math.min(dfs1(nums, l, r-2), dfs1(nums, l+1, r-1))+nums[r];
        //聰明人選擇結(jié)果大的那個
        return Math.max(left, right);
    }
}

我覺得我備注寫的很清楚了涡尘，畢竟自己一點點理出來的思路忍弛。總體來說沒超時我就覺得很驚喜了悟衩，但是這種暴力遍歷絕對是可以用dp實現(xiàn)的剧罩，但是怎么實現(xiàn)我只有正著寫出來了反著去看才有可能分析出來栓拜，太扎心了座泳。我去試試了。

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[length - 1] >= 0;
    }
}

直接看的題解幕与，放棄這么復(fù)雜的思路了挑势，年紀(jì)大了，沒追求了啦鸣，哎潮饱。
這篇筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關(guān)注诫给。也祝大家工作順順利利!java技術(shù)交流群130031711香拉，歡迎各位踴躍加入！