?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅(jiān)持，因?yàn)樗哂泻芨叩膬r(jià)值，算法就是這樣?
?? 作者簡介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者??，保研|國家獎(jiǎng)學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗(yàn)分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？????

?? 知識回顧

該題和我們之前的題目在求解的思路上相似之處，感興趣的同學(xué)可以學(xué)習(xí)一下相關(guān)的內(nèi)容。

• 【LeetCode: 1043. 分隔數(shù)組以得到最大和 | 暴力遞歸=＞記憶化搜索=＞動態(tài)規(guī)劃 | 線性dp & 區(qū)間dp】

?? 題目鏈接

• 2369. 檢查數(shù)組是否存在有效劃分

? 題目描述

給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，你必須將數(shù)組劃分為一個(gè)或多個(gè) 連續(xù) 子數(shù)組。

如果獲得的這些子數(shù)組中每個(gè)都能滿足下述條件 之一 ，則可以稱其為數(shù)組的一種 有效 劃分：

子數(shù)組 恰 由 2 個(gè)相等元素組成，例如，子數(shù)組 [2,2] 。
子數(shù)組 恰 由 3 個(gè)相等元素組成，例如，子數(shù)組 [4,4,4] 。
子數(shù)組 恰 由 3 個(gè)連續(xù)遞增元素組成，并且相鄰元素之間的差值為 1 。例如，子數(shù)組 [3,4,5] ，但是子數(shù)組 [1,3,5] 不符合要求。
如果數(shù)組 至少 存在一種有效劃分，返回 true ，否則，返回 false 。

示例 1：

輸入：nums = [4,4,4,5,6]
輸出：true
解釋：數(shù)組可以劃分成子數(shù)組 [4,4] 和 [4,5,6] 。
這是一種有效劃分，所以返回 true 。
示例 2：

輸入：nums = [1,1,1,2]
輸出：false
解釋：該數(shù)組不存在有效劃分。

提示：

2 <= nums.length <= 105
1 <= nums[i] <= 106

?? 求解思路&實(shí)現(xiàn)代碼&運(yùn)行結(jié)果

? 暴力遞歸

?? 求解思路

1. 想要快速的求解題目，那么讀懂理解題目是必須的環(huán)節(jié)，題目給定我們?nèi)N決策方案，看能夠存在一種有效劃分的方案，如果有，返回true，否則，返回false。
2. 三種決策方案如下：

• 子數(shù)組 恰 由 2 個(gè)相等元素組成，例如，子數(shù)組 [2,2] 。
• 子數(shù)組 恰 由 3 個(gè)相等元素組成，例如，子數(shù)組 [4,4,4] 。
• 子數(shù)組 恰 由 3 個(gè)連續(xù)遞增元素組成，并且相鄰元素之間的差值為 1 。例如，子數(shù)組 [3,4,5] ，但是子數(shù)組 [1,3,5] 不符合要求。

3. 那我們就設(shè)計(jì)一個(gè)遞歸函數(shù)就可以了，怎么寫呢？直接根據(jù)題目的意思來就OK。

?? 實(shí)現(xiàn)代碼

注意:下面提供倆種不同的代碼實(shí)現(xiàn)方式，大家選擇自己喜歡的就可以，無強(qiáng)制要求。

實(shí)現(xiàn)方式1:

class Solution {
    public boolean validPartition(int[] nums) {
        return process(0,nums);
    }

    public boolean process(int index,int[] nums){
        if(index>=nums.length) return true;
        if(index<=nums.length-2&&nums[index]==nums[index+1]&&process(index+2,nums)){
            return true;
        }
        if(index<=nums.length-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]&&process(index+3,nums)){
            return true;
        }
        if(index<=nums.length-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]&&process(index+3,nums)){
            return true;
        }
        return false;
    }
}

實(shí)現(xiàn)方式2:

class Solution {
    public boolean validPartition(int[] nums) {
        return process(0,nums);
    }

    public boolean process(int index,int[] nums){
        if(index>=nums.length) return true;
        boolean flag=false;
        if(index<=nums.length-2&&nums[index]==nums[index+1]){
            flag|=process(index+2,nums);
        }
        if(index<=nums.length-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){
            flag|=process(index+3,nums);
        }
        if(index<=nums.length-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){
            flag|=process(index+3,nums);
        }
        return flag;
    }
}

?? 運(yùn)行結(jié)果

時(shí)間超限了，不要緊哦，我還有錦囊妙計(jì)！

? 記憶化搜索

?? 求解思路

1. 根據(jù)我們遞歸的分析，在遞歸的過程中會產(chǎn)生重復(fù)的子過程，所以我們想到了加一個(gè)緩存表，也就是我們的記憶化搜索。

?? 實(shí)現(xiàn)代碼

實(shí)現(xiàn)方式1:

class Solution {
    int[] dp;
    public boolean validPartition(int[] nums) {
        int n=nums.length;
        dp=new int[n];
        Arrays.fill(dp,-1);
        return process(0,nums);
    }

    public boolean process(int index,int[] nums){
        if(index>=nums.length) return true;
        if(dp[index]!=-1) return dp[index]==1;
        if(index<=nums.length-2&&nums[index]==nums[index+1]&&process(index+2,nums)){
            dp[index]=1;
            return true;
        }
        if(index<=nums.length-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]&&process(index+3,nums)){
            dp[index]=1;
            return true;
        }
        if(index<=nums.length-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]&&process(index+3,nums)){
            dp[index]=1;
            return true;
        }
        dp[index]=0;
        return false;
    }
}

實(shí)現(xiàn)方式2:

class Solution {
    int[] dp;
    public boolean validPartition(int[] nums) {
        int n=nums.length;
        dp=new int[n];
        Arrays.fill(dp,-1);
        return process(0,nums);
    }

    public boolean process(int index,int[] nums){
        if(index>=nums.length) return true;
        if(dp[index]!=-1) return dp[index]==1;
        boolean flag=false;
        if(index<=nums.length-2&&nums[index]==nums[index+1]){
            flag|=process(index+2,nums);
        }
        if(index<=nums.length-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){
            flag|=process(index+3,nums);
        }
        if(index<=nums.length-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){
            flag|=process(index+3,nums);
        }
        dp[index]=flag?1:0;
        return flag;
    }
}

?? 運(yùn)行結(jié)果

? 動態(tài)規(guī)劃

?? 求解思路

1. 按照我們之前遞歸和記憶化搜索的思路，通過動態(tài)規(guī)劃實(shí)現(xiàn)出來。

?? 實(shí)現(xiàn)代碼

注意:代碼可以繼續(xù)優(yōu)化，可以省去一些沒有用的，或者將所有的條件都放到一個(gè)邏輯判斷中，這些點(diǎn)也很重要，但是我們更加關(guān)注的是狀態(tài)的轉(zhuǎn)移。

class Solution {
    boolean[] dp;
    public boolean validPartition(int[] nums) {
        int n=nums.length;
        dp=new boolean[n+1];
        dp[n]=true;
        for(int index=n-1;index>=0;index--){
            boolean flag=false;
            if(index<=n-2&&nums[index]==nums[index+1]){
                flag|=dp[index+2];
            }
            if(index<=n-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){
                flag|=dp[index+3];
            }
            if(index<=n-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){
                flag|=dp[index+3];
            }
            dp[index]=flag;
        }
        return dp[0];
    }
}

?? 運(yùn)行結(jié)果

?? 共勉

文章來源地址http://www.zghlxwxcb.cn/news/detail-418532.html

到了這里，關(guān)于【LeetCode: 2369. 檢查數(shù)組是否存在有效劃分 | 暴力遞歸=＞記憶化搜索=＞動態(tài)規(guī)劃 | 線性dp】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！