121. Best Time to Buy and Sell Stock

解題程式碼

var maxProfit = function (prices) {
  let maxProfit = 0;
  let currentDayPrice = prices[0];
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] - currentDayPrice > maxProfit) {
      maxProfit = prices[i] - currentDayPrice;
    }
    if (currentDayPrice > prices[i]) {
      currentDayPrice = prices[i];
    }
  }
  return maxProfit;
};

解題思路、演算法

這題用 maxProfit 去記錄最大收益，用 currentDayPrice 紀錄買進日的價格，然後把整個 prices 遍歷一次

如果發現賣出日減 currentDayPrice 大於當前的 maxProfit，就去更新 maxProfit

而如果遍歷過程發現有買進更低的價格，就將 currentDayPrice 更新成更低的價格

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

【leetcode 121】想學會DP這題一定要會！Best Time to Buy and Sell Stock 買賣股票的最佳時機

57. Insert Interval

解題程式碼

var insert = function (intervals, newInterval) {
  const result = [];
  intervals.forEach((ele) => {
    if (ele[1] < newInterval[0]) {
      result.push(ele);
    } else if (ele[0] > newInterval[1]) {
      result.push(newInterval);
      newInterval = ele;
    } else {
      newInterval = [Math.min(ele[0], newInterval[0]), Math.max(ele[1], newInterval[1])];
    }
  });
  result.push(newInterval);

  return result;
};

// result = [], newInterval = [2, 5]
// result = [], newInterval = [1, 5] (forEach index = 0)
// result = [[1, 5]], newInterval = [6,9] (forEach index = 1)

// result = [], newInterval = [4, 8]
// result = [[1, 2]], newInterval = [4, 8] (forEach index = 0)
// result = [[1, 2]], newInterval = [3, 8] (forEach index = 1)
// result = [[1, 2]], newInterval = [3, 8] (forEach index = 2)
// result = [[1, 2]], newInterval = [3, 10] (forEach index = 3)
// result = [[1, 2], [3, 10]], newInterval = [12, 16] (forEach index = 4)

解題思路、演算法

這題題目分成幾個 case 處理:

1. 當前 intervals 的元素陣列 ele 值都比 newInterval 小，就直接將 ele 加入到結果陣列
2. 當前 intervals 的元素陣列 ele 值都比 newInterval 大，就代表沒有合併動作，直接將 newInterval 加入到結果陣列，並將 ele 取代為 newInterval
3. 以上條件都不符合，就需要做合併，各取 ele 和 newInterval 的第一個元素最小值和第二個元素最大值當作 newInterval

最後將 newInterval(迴圈完後會是整個陣列的最大值) 加入 result 陣列。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

Insert Interval - Leetcode 57 - Python

15. 3Sum

解題程式碼

var threeSum = function (nums) {
  nums = nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    let l = i + 1;
    let r = nums.length - 1;
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 連續兩個數相同，ex: [-4, -1, -1, 0, 1, 2] 的 -1

    while (l < r) {
      let total = nums[i] + nums[l] + nums[r];
      if (total > 0) {
        r--;
      } else if (total < 0) {
        l++;
      } else {
        result.push([nums[i], nums[l], nums[r]]);
        while (nums[l] === nums[l + 1]) l++;
        while (nums[r] === nums[r - 1]) r--;
        l++;
        r--;
      }
    }
  }

  return result;
};

解題思路、演算法

這題先做排序會比較好處理，所以先排序。

接著遍歷整個陣列，先選擇一個數 nums[i] 當作當前遍歷到的值，然後用左右指標 l、r 做紀錄，然後根據三個數 nums[i] + nums[l] + nums[r] 的總合去判斷要怎麼移動兩個指標。

• 若 nums[i] 和前一個數 nums[i - 1] 相同，則跳過這次循環，避免將重複結果加入最終結果陣列內
• 若 total > 0，r 須右移(nums[r] 變更小)，這樣之後三個數相加會比較有可能更接近 0 或等於 0
• 若 total < 0，l 須右移(nums[l] 變更大)，這樣之後三個數相加會比較有可能更接近 0 或等於 0
• 若 total === 0，加入最終結果陣列內，l 右移一次，r 左移一次，然後若 l、r 碰到相同的數就再移一次避免重複

思路範例

total = (-3) + (-1) + 2 < 0，l 向左移 =>

total = (-3) + (-1) + 2 < 0，l 向左移 =>

total = (-3) + 0 + 2 < 0，l 向左移 =>

total = (-3) + 1 + 2 === 0，所以將 [-3, 1, 2] 加入到 result 陣列。

解法的時間、空間複雜度

時間複雜度: O(n^2)
空間複雜度: O(n)

參考資料

3Sum - Leetcode 15 - Python

LeetCode 15. 3Sum