LeetCode快速入門① ——陣列系列上（面試常問，建議收藏）

首先我在這里先介紹下演算法對于我們個人的意義，在實際專案中，演算法的使用場景有很多，如“Java8中Hashmap使用紅黑樹來實作”、“Redis底層使用LRU來進做淘汰策略”、“大資料領域很多問題都基于TopK”、“JS原型鏈里使了類似鏈表的成環檢測”、“特別復雜的業務邏輯經常涉及到DAG”、“MySql為什么索引要用B+樹”、“Oracle里的開窗函式如何實作” 等等等等，總之，正是因為演算法題目中只保留了必備的要素，舍棄了其他無關緊要的部分，所以可以對每一位做題人都構建一個學習解決問題的最佳環境，而在這個環境中的成長與提高，將對一個軟體工程師的生涯產生深遠影響，乃至一世，所以，請大家能有一顆匠心，你可以選擇不去了解學習掌握演算法，但是請不要耽誤他人進步，山高水長，江湖路遠，珍重萬千，有緣再見！

一、LeetCode 350題 求兩個集合中的差值

1.1 題目分析

我們先來看一道題目： 第350題：兩個陣列的交集
需求：給定兩個陣列，撰寫一個函式來計算它們的交集，
實體代碼

輸入: nums1 = [1,2,2,1], nums2 = [2,2]

輸出: [2,2]

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

輸出: [4,9]

根據實體代碼分析：

1. 輸出的結果應該與給定的兩個集合共同出現的次數是相同的，
2. 我們這里不考了排序的問題
3. 首先拿著這個題目的時候，我們首先應該想到使用map的方式進行映射，為什么可以這樣看那，因為我們需要找出兩個陣列中交集的元素，同時應與兩個陣列中出現的次數一直，這樣導致我們需要制每個值串的次數，所以映射關系就成了<元素，元素出現的次數>

1.2 題目講解

根據分析，假設我們有兩個陣列分別為； nums1=[1,2,2,2] ， nums2=[2,2]

首先我們定義一個map用來存其中一個陣列中的資料，進行回圈向陣列中輸入資料

第一次map中沒有這個元素所以value為1

第二、三次map中如有這個元素value+1后面依次類推，就像使用map計算wordCount

首先我們需要進行判斷map中是否這個資料，如果有則進行相加(后面的邏輯就是一樣的了)

第二階段

首先定義一個空的陣列，我們現在獲取到了map之后，map中就存盤了我們每個元素及他們出現的個數，接下來我們在遍歷nums2這個陣列，拿著每個元素去map中get資料如果get到了資料value次數減1,將這個key復制給空的陣列，

1.3 代碼分析

public static int[] intersect(int[] nums1, int[] nums2) {
        // 判空操作
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        //1.定義一個map用來存盤一個陣列中的出現的值 value存盤出現的個數
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            Integer integer = map.get(nums1[i]);
            if (integer == null) {
                map.put(nums1[i], 1);
            } else {
                map.put(nums1[i], integer + 1);
            }
        }
        int k = 0;
        for (int i = 0; i < nums2.length; i++) {
            Integer integer = map.get(nums2[i]);
            if (integer != null) {
                if (integer > 0) {
                    nums2[k] = nums2[i];
                    map.put(nums2[i], integer - 1);
                    k++;
                }
            }
        }
        return Arrays.copyOfRange(nums2, 0, k);
    }

1.4 題目進階（優化）

前提:我們首先我們需要將兩個陣列進行排序

如果給定的陣列已經排好序呢？你將如何優化你的演算法？我們分析一下，假如兩個陣列都是有序的，分別為： nums1=[1,2,2,2] ， nums2=[2,2]

解題步驟：
<1>如果兩個指標的元素不相同，我們將小的指標往后一然后在進行判斷

<2>如果兩個元素相同，則兩個指標同時后移

<3> 直到任意一個陣列終止，

1.5 代碼分析

 public static int[] intersect2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        int i = 0, j = 0, k = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                nums2[k] = nums1[i];
                i++;
                j++;
                k++;
            }
        }
        return Arrays.copyOfRange(nums2, 0, k);
    }

二、LeetCode 14 最長公共前綴

2.1 題目分析

我們先來看一道題目： 第14: 最長公共前綴
需求：撰寫一個函式來查找字串陣列中的最長公共前綴，如果不存在公共前綴，則回傳""
實體代碼

輸入: ["flower","flow","flight"]
輸出: "fl"

輸入: ["dog","racecar","car"]
輸出: ""

題目分析：

我們要想尋找最長的公共前綴，那么首先這個前綴是公共的，我們可以從任意一個元素中找到他，假定我們現在就從一個陣列中尋找最長公共前綴，那么首先，我們可以將第一個元素設定為基準元素x0，假如陣列為[“flow”,“flower”,“flight”]，flow就是我們的基準元素x0，

然后我們只需要依次將基準元素和后面的元素進行比較（假定后面的元素依次為x1,x2,x3…），不斷更新基準元素，直到基準元素和所有元素都滿足最長公共前綴的條件，就可以得到最長公共前綴，

對比流程：

• 如果strs[i].indexOf(x0,x) == 0，則直接跳過（因為此時x就是x1的最長公共前綴），對比下一個元素，（如flower和flow進行比較）
• 如果strs[i].indexOf(x0,x) != 0, 則截取掉基準元素x的最后一個元素，再次和x1進行比較，直至滿足strs[i].indexOf(x0,x) == 0，此時截取后的x為x和x1的最長公共前綴，（如flight和flow進行比較，依次截取出flow-flo-fl，直到fl被截取出，此時fl為flight和flow的最長公共前綴）

2.2 圖解分析

2.3 代碼分析

public static String longestCommonPrefix(String[] strs) {
        if (strs.length==0 || strs[0].length()==0){
            return "";
        }
        String mondel = strs[0].substring(0, strs[0].length() - 1);
        for (int i = 0; i < strs.length; i++) {
            if (mondel.length()==0){
                return "";
            }
            if (strs[i].indexOf(mondel)!=0){
                while (true){
                    mondel=mondel.substring(0,mondel.length()-1);
                    if (mondel.length()==0){
                        break;
                    }
                    if (strs[i].indexOf(mondel)==0){
                        break;
                    }
                }
            }
        }
        return mondel==null? "":mondel;
    }

三、LeetCode 買賣股票的最佳時機（I、II）

面試時出現的頻率非常的高，稍微改一改條件，就讓我們防不勝防，那我們如何攻克這一類的問題那？我們從最賤的一道開始看起，

3.1 121題 買賣股票的最佳時機 I

3.1.1 題目分析

我們先來看一道題目： 第121題：買賣股票的最佳時機 I

需求：給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤，

注意：你不能在買入股票前賣出股票，
示例1：

輸入: [7,1,5,3,6,4]
輸出:  5 

解釋： 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
注意：注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票，
示例 2:

輸入: [7,6,4,3,1]
輸出: 0

解釋： 在這種情況下, 沒有交易完成, 所以最大利潤為 0，

3.2.2 圖解分析

假設我們是第二天買入，在收益在多的那一天賣出

執行流程

第二次執行

第三次執行… 以此類推，當我們整個回圈遍歷完成后maxV就獲取到了整個陣列中的最大收益，

3.1.3 代碼分析

 public static int maxProfit(int[] prices) {
        int maxProfit = 0, fi = 0, maxV = 0;
        for (int i = 1; i < prices.length; i++) {
            fi = Math.max(maxProfit + prices[i] - prices[i - 1], 0);
            maxV = Math.max(fi, maxV);
            maxProfit = fi; 
        }
        return maxV;
    }

3.2 122題 買賣股票的最佳時機 II

3.2.1 題目分析

我們先來看一道題目： 第122題：買賣股票的最佳時機 II

需求：給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，

設計一個演算法來計算你所能獲取的最大利潤，你可以盡可能地完成更多的交易（多次買賣一支股票），

注意： 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
示例1

輸入: [7,1,5,3,6,4]
輸出: 7

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 ，
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 ，
示例 2:

輸入: [1,2,3,4,5]
輸出: 4

解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 ，
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出，
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票，

示例三

輸入: [7,6,4,3,1]
輸出: 0

解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0，

3.2.2 圖解分析

假設我們的資料是：[7, 1, 5, 3, 6, 4]

從上圖中，我們可以觀察到 A+B+C的和等于差值 DD 所對應的連續峰和谷的高度之差，

3.2.3 代碼分析

    public int maxProfit(int[] prices) {
        int maxProfit=0;
        for (int i = 1; i < prices.length ; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        } 
        return maxProfit;
    }

四、LeetCode 189 旋轉陣列

4.1 題目分析

我們先來看一道題目： 第189 題：旋轉陣列
需求：給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數
示例 1:

輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]

解釋:

向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]

示例 2:

輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]

解釋:

向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]

注意：
盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題，
要求使用空間復雜度為 O(1) 的 原地 演算法，

4.2 圖解分析

假設我們的陣列為[1,2,3,4,5,6],I=6 且 k=3

通過觀察我們可以得到，我們要得到最終的結果，我們只需要將所有元素反轉，然后反轉前 k 個元素，再反轉后面l-k個元素，就能得到想要的結果，

4.3代碼分析

 public static void rotate(int[] nums, int k) {
        revers(nums, 0, nums.length);
        revers(nums, 0, k % nums.length);
        revers(nums, k % nums.length, nums.length);
    }

    public static void revers(int[] nums, int start, int end) {
        int length = end - start;
        for (int i = 0; i < length / 2; i++) {
            int num = nums[start + i];
            nums[start + i] = nums[start + length - i - 1];
            nums[start + length - i - 1] = num;
        }
        System.out.println(Arrays.toString(nums));
    }