力扣每日一練之數組下篇Day3

🍕前面的話🥞

大家好！本篇文章将介紹2周搞定資料結構的題，來自力扣的35,兩個數組的交集和121.買賣股票的最佳時機，本文将以這兩道題作為背景，介紹經典的數組排序以及線性查找，展示語言為java（部落客學習語言為java)。今天呢，是部落客開始刷力扣的第三天，如果有想要開始準備自己的算法面試的同學，可以跟着我的腳步一起，共同進步。大家都是并肩作戰的夥伴，一起努力奮力前行，路漫漫其修遠兮，吾将上下而求索，相信我們一定都可以拿到自己期望的offer，沖沖沖！

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創

😘系列專欄：java學習

💻首發時間：🎞2022年5月1日🎠

🎨你做三四月的事，八九月就會有答案，一起加油吧

🔏參考線上程式設計網站：🎧力扣

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🏓導航小助手📻

文章目錄

力扣每日一練之數組下篇Day3

@[toc]

🏸LeetCode350 兩個數組的交集
👝解題思路

方法一：哈希表
方法二：排序加雙指針

🎳121 買賣股票的最佳時間
方法一：暴力解法
方法二：動态規劃
🌌總結

覺得文章寫的不錯的親親，點贊評論關注走一波，愛你們哦🛴

🏸LeetCode350 兩個數組的交集

給你兩個整數數組 nums1 和 nums2 ，請你以數組形式傳回兩數組的交集。傳回結果中每個元素出現的次數，應與元素在兩個數組中都出現的次數一緻（如果出現次數不一緻，則考慮取較小值）。可以不考慮輸出結果的順序。

> 示例 1：

>

> 輸入：nums1 = [1,2,2,1], nums2 = [2,2]

> 輸出：[2,2]

> 示例 2:

>

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

> 輸出：[4,9]

👝解題思路

方法一：哈希表

由于同一個數字在兩個數組中都可能出現多次，是以需要用哈希表存儲每個數字出現的次數。對于一個數字，其在交集中出現的次數等于該數字在兩個數組中出現次數的最小值。

首先周遊第一個數組，并在哈希表中記錄第一個數組中的每個數字以及對應出現的次數，然後周遊第二個數組，對于第二個數組中的每個數字，如果在哈希表中存在這個數字，則将該數字添加到答案，并減少哈希表中該數字出現的次數。

為了降低空間複雜度，首先周遊較短的數組并在哈希表中記錄每個數字以及對應出現的次數，然後周遊較長的數組得到交集。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

方法二：排序加雙指針

如果兩個數組是有序的，則可以使用雙指針的方法得到兩個數組的交集。

首先對兩個數組進行排序，然後使用兩個指針周遊兩個數組。

初始時，兩個指針分别指向兩個數組的頭部。每次比較兩個指針指向的兩個數組中的數字，如果兩個數字不相等，則将指向較小數字的指針右移一位，如果兩個數字相等，将該數字添加到答案，并将兩個指針都右移一位。當至少有一個指針超出數組範圍時，周遊結束。

部落客采用的是方法二，下面我們來看怎麼寫代碼，第一步，對兩個數組進行重新排序。之後定義出來數組的長度，以及數組的最小值和角标初始化。完成這些基本操作後，我們就用循環開始計算了，首先用while循環，定義出角标的長度。

然後采用if else語句，在不同的情況下，增加角标大小，向後周遊，最後傳回重合的角标

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

🎳121 買賣股票的最佳時間

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你隻能選擇某一天買入這隻股票，并選擇在未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能擷取的最大利潤。

傳回你可以從這筆交易中擷取的最大利潤。如果你不能擷取任何利潤，傳回 0 。

示例 1：

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

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 是以最大利潤為 0。

方法一：暴力解法

思路：枚舉所有發生一次交易的股價差。

public class Solution {
public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len < 2) {
        return 0;
    }

    // 有可能不發生交易，是以結果集的初始值設定為 0
    int res = 0;

    // 枚舉所有發生一次交易的股價差
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            res = Math.max(res, prices[j] - prices[i]);
        }
    }
    return res;
}
}

方法二：動态規劃

思路：題目隻問最大利潤，沒有問這幾天具體哪一天買、哪一天賣，是以可以考慮使用動态規劃的方法來解決。

買賣股票有限制，根據題目意思，有以下兩個限制條件：

條件 1：你不能在買入股票前賣出股票；

條件 2：最多隻允許完成一筆交易。

是以當天是否持股是一個很重要的因素，而目前是否持股和昨天是否持股有關系，為此我們需要把是否持股設計到狀态數組中。

狀态定義：

dp[i][j]：下标為 i 這一天結束的時候，手上持股狀态為 j 時，我們持有的現金數。換種說法：dp[i][j] 表示天數 [0, i] 區間裡，下标 i 這一天狀态為 j 的時候能夠獲得的最大利潤。其中：

j = 0，表示目前不持股；

j = 1，表示目前持股。

注意：下标為 i 的這一天的計算結果包含了區間 [0, i] 所有的資訊，是以最後輸出 dp[len - 1][0]。

說明：

使用「現金數」這個說法主要是為了展現買入股票手上的現金數減少，賣出股票手上的現金數增加這個事實；

「現金數」等價于題目中說的「利潤」，即先買入這隻股票，後買入這隻股票的差價；

是以在剛開始的時候，我們的手上肯定是有一定現金數能夠買入這隻股票，即剛開始的時候現金數肯定不為 00，但是寫代碼的時候可以設定為 0。極端情況下（股價數組為 [5, 4, 3, 2, 1]），此時不發生交易是最好的（這一點是補充說明，限于我的表達，希望不要給大家造成迷惑）。

推導狀态轉移方程：

dp[i][0]：規定了今天不持股，有以下兩種情況：

昨天不持股，今天什麼都不做；

昨天持股，今天賣出股票（現金數增加），

dp[i][1]：規定了今天持股，有以下兩種情況：

昨天持股，今天什麼都不做（現金數與昨天一樣）；

昨天不持股，今天買入股票（注意：隻允許交易一次，是以手上的現金數就是當天的股價的相反數）。

狀态轉移方程請見參考代碼 2。

知識點：

多階段決策問題：動态規劃常常用于求解多階段決策問題；

無後效性：每一天是否持股設計成狀态變量的一維。狀态設定具體，推導狀态轉移方程友善。

public class Solution {
public int maxProfit(int[] prices) {
    int len = prices.length;
    // 特殊判斷
    if (len < 2) {
        return 0;
    }
    int[][] dp = new int[len][2];

    // dp[i][0] 下标為 i 這天結束的時候，不持股，手上擁有的現金數
    // dp[i][1] 下标為 i 這天結束的時候，持股，手上擁有的現金數

    // 初始化：不持股顯然為 0，持股就需要減去第 1 天（下标為 0）的股價
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 從第 2 天開始周遊
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    }
    return dp[len - 1][0];
}
}

力扣每日一練之數組下篇Day3