導(dǎo)讀: 數(shù)據(jù)是最基本的數(shù)據(jù)結(jié)構(gòu)眉枕，能解決很多問(wèn)題，比如常見(jiàn)的,求解,使用數(shù)組來(lái)解決重復(fù)遞歸過(guò)程，動(dòng)態(tài)規(guī)劃使用數(shù)組記錄最近解過(guò)程中的各個(gè)步驟的解录别。今天我們用幾個(gè)常見(jiàn)的面試題來(lái)談一談算法——數(shù)據(jù)結(jié)構(gòu)【數(shù)組】那些事

背景

數(shù)組是最常見(jiàn)的也是經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu),大多數(shù)語(yǔ)言的封裝類型（List/Map）都含有數(shù)組的身影。我們知道數(shù)組時(shí)一塊連續(xù)的內(nèi)存區(qū)域邻吞，訪問(wèn)某個(gè)數(shù)據(jù)時(shí)用數(shù)組下標(biāo)訪問(wèn)组题，當(dāng)擴(kuò)容和刪除時(shí)略顯麻煩.

那我們?cè)趺床拍苡煤脭?shù)組呢？怎么能快速使用數(shù)組這種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)來(lái)解決復(fù)雜的問(wèn)題呢抱冷？

下面我們從一到題來(lái)引入講解數(shù)組解一些常見(jiàn)的算法題.

給定一個(gè)整數(shù)數(shù)組 nums 崔列，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和旺遮。

示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大赵讯，為 6。

最大子序列求和的解法

在我的思維里耿眉，如果一個(gè)問(wèn)題边翼，你之前沒(méi)做過(guò)，沒(méi)有系統(tǒng)的學(xué)習(xí)過(guò)此類通用算法解決鸣剪，那么暴力就是能想到的第一種解法思路组底。

下面我們來(lái)看一下暴力解題法丈积，怎么去做？首先我們可以想到

列舉 數(shù)組中的所有可能的連續(xù)區(qū)間/子集斤寇？然后把連續(xù)區(qū)間相加桶癣，求和，判斷最大.

解法一： 時(shí)間復(fù)雜度

    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        //使用兩個(gè)for循環(huán)來(lái)列舉出所有的連續(xù)區(qū)間/子集
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                sum = 0;
                //列舉出來(lái)的子集娘锁，在通過(guò)一個(gè)for循環(huán)相加
                for (int k = i; k <= j; k++) {
                    sum += nums[k];
                }
                if (sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }

解法二： 時(shí)間復(fù)雜度

其實(shí)我們?cè)诹信e的過(guò)程中就可以把和相加起來(lái)牙寞，進(jìn)行判斷，所有有了解法二

    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
            //列舉子序列求和的過(guò)程中解決此問(wèn)題
                sum += nums[j];
                if (sum > max)
                    max = sum;
            }
        }
        return max;
    }

解法三：動(dòng)態(tài)規(guī)劃 時(shí)間復(fù)雜度

看了上述的暴力解題法莫秆，我們發(fā)現(xiàn)一些可以優(yōu)化的東西间雀，因?yàn)樗兄貜?fù)的子結(jié)構(gòu)性質(zhì)财松，那就是每次相加都從開(kāi)始的那個(gè)元素去相加辕羽，那我們可以從動(dòng)態(tài)規(guī)劃的角度想一下這個(gè)問(wèn)題。

設(shè)sum[i]為以第i個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組气筋，那我們可以把上述問(wèn)題描述為這樣的一個(gè)公式

把公式化解一下就是這樣的.

那么算法可以描述為

  public int maxSubArray(int[] nums) {
        int sums[] = new int[nums.length];
        sums[0] = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (sums[i-1] > 0) sums[i] += nums[i];
            else sums[i] = nums[i];
            if (max < sums[i]) max = sums[i];
        }
        return max;
    }

這樣算法的空間復(fù)雜度為缝驳，如果原數(shù)據(jù)數(shù)組nums可以被更改连锯，那么我們的sums數(shù)組可以省略.

public int maxSubArray(int[] nums) {
        int currnetValue = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (currnetValue > 0) currnetValue += nums[i];
            else currnetValue = nums[i];
            if (max < currnetValue) max = currnetValue;
        }
        return max;
    }

n層for循環(huán)求解

排列問(wèn)題和組合問(wèn)題很相似（經(jīng)典問(wèn)題有全排列）,這里列舉一道 相關(guān)的題

給定一個(gè)無(wú)重復(fù)元素的數(shù)組candidates和一個(gè)目標(biāo)數(shù)target，找出candidates中所有可以使數(shù)字和為target的組合用狱。
candidates中的數(shù)字可以無(wú)限制重復(fù)被選取运怖。

說(shuō)明：
所有數(shù)字（包括target）都是正整數(shù)。
解集不能包含重復(fù)的組合夏伊。
示例1: 輸入: candidates = [2,3,6,7], target = 7, 所求解集為:
[
[7],
[2,2,3]
]

示例2:
輸入: candidates = [2,3,5], target = 8,
所求解集為:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

解法

按我的思路來(lái)摇展，第一就去想暴力解法，然后再去想辦法優(yōu)化（如果你之前做過(guò)這題溺忧，或者直接能想到什么動(dòng)態(tài)規(guī)劃算法咏连，可以直接使用，不要在暴力鲁森。）

想講一個(gè)暴力通用解法模型祟滴，就是本節(jié)所說(shuō)的n層for循環(huán)求解 .
這可以解決很多與組合相關(guān)的問(wèn)題，如密碼暴力破解等.

給你一個(gè)字符串歌溉，列舉里面所有可能的三位密碼踱启，（字符串里面字母都不相同，不考慮密碼順序）

這樣我們能很簡(jiǎn)單的想到一個(gè)算法

    int len = str.length();
    for(int i = 0;i < len - 2;i++){
        for(int j = i +1;j<len - 1;j++){
            for(int k = j+1;k<len;k++){
                String password = ""+ str.charAt(i) + str.charAt(j) + str.charAt(k);
            }
        }
    }

那要是現(xiàn)在列舉100位密碼呢研底？不可能寫(xiě)這樣的循環(huán)了吧?

一般解法埠偿，是使用遞歸來(lái)替代n層for循環(huán)，一般解法模型,偽代碼如下

void find(int start,int count,int passwordLen,int array[]){
    if(count == passwordLen){
        //得到結(jié)果
        return;
    }
    for(int i = start;i<array.length;i++){
        find(i + 1,count+1,passwordLen,array);
    }
}

那么上面那道題榜晦，使用這個(gè)模型來(lái)解決代碼如下:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listAll = new ArrayList<>();
        List<Integer> currentList = new ArrayList<>();
        Arrays.sort(candidates);
        find(listAll,currentList,candidates,target,0);
        return listAll;
    }
    
    
    private void find(List<List<Integer>> listAll,List<Integer> currentList,int[] candidates,int target,int currentIndex) {
        if(target < 0) return;
        if(target == 0){
            listAll.add(currentList);
        }else{
            for(int i = currentIndex;i<candidates.length && candidates[i]<=target;i++){
                List<Integer> list=new ArrayList<>(currentList);
                list.add(candidates[i]);
                find(listAll,list,candidates,target - candidates[i],i);
                //currentList.remove(currentList.size()-1);
            }
        }
    }
}

爬樓梯

假設(shè)你正在爬樓梯冠蒋。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階乾胶。你有多少種不同的方法可以爬到樓頂呢抖剿？

如果你之前見(jiàn)過(guò)這題朽寞，那應(yīng)該知道這是一個(gè)斐波那契數(shù)列（相似的問(wèn)題還有很多，如兔子繁殖問(wèn)題等都是斐波那契數(shù)列）斩郎，可以描述為

那么求這個(gè)公式怎么解呢脑融？我們可以想到一個(gè)遞歸過(guò)程，如下

 public int fib(int n) {
    if(n <= 2) return 1;
    else{
        return fib(n-1) + fib(n-2);
    }
}

我們知道遞歸過(guò)程中會(huì)有很多重復(fù)計(jì)算缩宜，這里列舉一張法f(5）的計(jì)算過(guò)程肘迎，如下

image

那我們?cè)趺唇鉀Q這個(gè)問(wèn)題呢，使用一個(gè)數(shù)組來(lái)保存結(jié)果锻煌，避免重復(fù)計(jì)算,(也被成為備忘錄法則)妓布，這里其實(shí)已經(jīng)是動(dòng)態(tài)規(guī)劃了。

public int fib(int n) {
        if(n <= 2) return 1;
        if(save[n] > 0){
            return save[n];
        }else{
            save[n] = save[n-1]+save[n-2];
            return save[n];
        }
}

我們知道遞歸有一個(gè)函數(shù)棧的調(diào)用過(guò)程宋梧，那我們可以嘗試把遞歸去了

public int fib(int n) {
        save[0] = 1;
        save[1] = 1;
        for(int i = 2;i < n;i++){
            save[i] = save[i-1]+ save[i-2];
        }
        return save[n-1];
    }
}

其實(shí)這個(gè)如果只是一次計(jì)算f(n)的結(jié)果匣沼，不用使用數(shù)組，可以優(yōu)化為

    int v1 = 1,v2=1;
        for(int i = 2;i < n;i++){
            int temp = v1 + v2;
            v1 = v2;
            v2 = temp;
        }
        return v2;
    }

拓展：看完上述內(nèi)容捂龄，你應(yīng)該能輕松解決释涛，如果樓梯不是一次只能上1或者2層，他能上任意層倦沧，怎么解決這個(gè)問(wèn)題呢唇撬？歡迎留言區(qū)評(píng)論

關(guān)于二維數(shù)組

二維數(shù)組是在一維數(shù)組的基礎(chǔ)上，增加了縱向刀脏。那二維數(shù)組一般的暴力解法和一維數(shù)組基本類似局荚。常見(jiàn)的二維數(shù)組經(jīng)典題目有 【n皇后問(wèn)題】【走迷宮】 對(duì)應(yīng)的回溯算法超凳，也是暴力算法的一種愈污，有一個(gè)剪枝，優(yōu)化過(guò)程轮傍。 在這里舉一個(gè)二維數(shù)組例子暂雹。

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。

機(jī)器人每次只能向下或者向右移動(dòng)一步创夜。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）杭跪。
問(wèn)總共有多少條不同的路徑？

image

有了上面的暴力解題思路過(guò)程驰吓，并且此題也有一些重疊子問(wèn)題涧尿，那我們這題，直接考慮動(dòng)態(tài)規(guī)劃解決. 可以想到遞歸函數(shù)為

根據(jù)遞歸公式代碼檬贰，也能輕松寫(xiě)出

class Solution {
    public int uniquePaths(int m, int n) {
        int sum[][] = new int[m][n];
        for(int i = 0;i<m;i++){
            sum[i][0] = 1;
        }
         for(int i = 0;i<n;i++){
            sum[0][i] = 1;
        }
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                sum[i][j] = sum[i-1][j] + sum[i][j-1];
            }
        }
        return sum[m-1][n-1];
    }
}

總結(jié)

本文主要介紹了一些數(shù)組的算法姑廉，一些解題思路，從問(wèn)題的暴力解法開(kāi)始（通用的暴力解法：兩個(gè)for循環(huán)列舉翁涤，n層for循環(huán)等)桥言，逐步優(yōu)化萌踱，一些能想到的優(yōu)化方式，節(jié)省空間号阿，時(shí)間并鸵。到后面一些可以用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，（此處沒(méi)有列舉一些回溯常見(jiàn)解法扔涧，但是思路都是從暴力解法開(kāi)始园担，逐步剪枝，優(yōu)化的過(guò)程）

文末

因?yàn)楸救思夹g(shù)有限扰柠，文中如有錯(cuò)誤之處粉铐，還請(qǐng)大佬指教，感謝.

文中題目來(lái)源 LeetCode
如果你正在準(zhǔn)備面試卤档，或者你喜歡算法蝙泼，刷題推薦LeetCode，挺不錯(cuò)的網(wǎng)站.

如果你對(duì)圖片,Canvas感興趣劝枣，推薦閱讀

Android：讓你的“女神”逆襲汤踏，代碼擼彩妝（畫(huà)妝）
Flutter PIP（畫(huà)中畫(huà)）效果的實(shí)現(xiàn)