初級算法學習記錄(第一天)

初級算法

題目1

題幹：
給你一個 升序排列 的數組 nums ，請你 原地 删除重複出現的元素，使每個元素 隻出現一次 ，傳回删除後數組的新長度。元素的 相對順序 應該保持 一緻 。
由于在某些語言中不能改變數組的長度，是以必須将結果放在數組nums的第一部分。更規範地說，
如果在删除重複項之後有 k 個元素，num的前 k 個元素應該儲存最終結果。
将最終結果插入num的前 k 個位置後傳回 k 。
不要使用額外的空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。
    
    
示例1
輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數應該傳回新的長度 2 ，并且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度後面的元素。

示例2
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該傳回新的長度 5 ， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度後面的元素。
 
提示
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
           

思路1

• 方法

  雙指針

• 核心内容

  1.去除異常條件
  2.使用雙指針，左右指針分别從0和1開始
  3.周遊數組
  4.如果f[i] != f[j] 将f[j]指派給f[i+1]，然後i++
  5.傳回i+1
             

針對思路1優化

• 方法

  雙指針

• 核心内容

  1.目前每次比較的時候，需要進行原地的指派，其實是沒有意義的
  2.小優化：隻有當左右指針的差距大于1，才需要進行指派
             

代碼：

思路1
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] != nums[j]) {
                nums[i + 1] = nums[j];
                i++;
            }
            j++;
        }
        return i + 1;
    }
}

優化思路
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] != nums[j]) {
                if (j - i > 1) {
                    nums[i + 1] = nums[j];
                }
                i++;
            }
            j++;
        }
        return i + 1;
    }
}
           

題目2

給你一個整數數組 prices ，其中prices[i] 表示某支股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候最多隻能持有一股股票。你也可以先購買，然後在同一天出售。
傳回你能獲得的最大利潤。
  
    
示例1
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。
随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 。總利潤為 4 + 3 = 7 。
    
    
示例2
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。總利潤為 4 。
    

示例3
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無法獲得正利潤，是以不參與交易可以獲得最大利潤，最大利潤為0。
    
  
提示
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
           

思路1

• 方法

  動态規劃(二維數組)

• 核心内容

  數組定義：
  f[i][0]表示第i天沒有持有股票的最大利潤，f[i][1]表示第i天持有股票的最大利潤
  
  有兩種情況(轉移方程)：
  1.如果目前賣出股票的最大值：f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i])
  2.如果當天買入股票的最大值：f[i][1] = max(f[i - 1][1], f[i - 1][0]- prices[i])
  
  初始條件：
  f[0][0] = 0
  f[0][1] = -prices[i]
      
  結果：
  最後一天一定沒持有股票才能擷取最大利潤：f[prices.length][0]
             

思路2(優化思路1)

• 方法

  動态規劃(變量)

• 核心内容

  第一種方式使用的二維數組，優化為變量維護
  
  empty表示沒有持有股票的最大利潤，contain表示持有股票的最大利潤
  
  有兩種情況(轉移方程):
  1.如果目前賣出股票的最大值：empty = max(empty, contain + prices[i])
  2.如果當天買入股票的最大值：contain = max(contain, empty - prices[i])
  
  初始條件:
  empty = 0
  contain = -prices[i]
  
  結果:
  最後一天一定沒持有股票才能擷取最大利潤：empty
             

思路3

• 方法

  貪心算法

• 核心内容

  如果f[i] <= f[i + 1]，此時進行累計計算即可
             

代碼：

思路1
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int[][] f = new int[prices.length][2];
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }
        return f[prices.length - 1][0];
    }
}


class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int empty = 0;
        int contain = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            empty = Math.max(empty, contain + prices[i]);
            contain = Math.max(contain, empty - prices[i]);
        }
        return empty;
    }
}

思路3
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

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