11. Container With Most Water

解題程式碼

var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let area = 0;
  while (left < right) {
    const temp = (right - left) * Math.min(height[left], height[right]);
    area = Math.max(temp, area);

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return area;
};

解題思路、演算法

這題可以使用 two pointer 去處理，分別指向陣列的第一個和最後一個元素，然後比對當前指針指向的值的大小，若左指針指向的值比較小，就往右移一位，去尋找更大的值才能裝更多的水。

反之若右指針指向的值比較小，就往左移一位，兩數相同時，移哪個都沒差，直到兩個指針都重疊時，就停止比較。

然後移動的過程中，不斷的去比較新移動後的容量和當前記錄的容量，把較大的記錄起來。

解法的時間、空間複雜度

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

參考資料

Container with Most Water - Leetcode 11 - Python

252. Meeting Rooms

題目說明

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Example 1:

Input: [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: [[7,10],[2,4]]
Output: true

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

解題程式碼

const canAttendMeetings = (intervals) => {
  if (intervals.length < 2) return true;
  
  intervals.sort((a, b) => a[0] - b[0]);

  let end = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (end > intervals[i][0]) return false;
    if (end < intervals[i][1]) end = intervals[i][1];
  }
  return true;
}

解題思路、演算法

將所有會議的時間做排序，那前一場結束的時間一定要小於下一場開始的時間才不會有重疊，如果符合這個條件就去更新前一場結束的時間，改為下一場結束的時間，然後繼續跑迴圈下去。

解法的時間、空間複雜度

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

參考資料

134. Gas Station

解題程式碼

var canCompleteCircuit = function (gas, cost) {
  let total = 0;
  let startIndex = 0;
  let curSum = 0;

  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    curSum += gas[i] - cost[i];

    if (curSum < 0) {
      curSum = 0;
      startIndex = i + 1;
    }
  }

  if (total < 0) return -1;
  return startIndex;
};

解題思路、演算法

要判斷有沒有解的話，把兩個陣列元素全部加起來，然後用 gas 的總和去減 cost 的總和，如果比 0 小，就代表沒有解了，回傳 -1。

至於要找到起始的索引值，可以從頭開始遍歷陣列，範例 gas = [1,2,3,4,5], cost = [3,4,5,1,2] 中，前三站一定不可能是起始點，所以從 index 3 開始即為起始點，若是更多元素，可以用以下方式思考:

以下陣列是 gas 和 cost 各相同索引值的元素值相加後所組成的陣列，用 O 符號代表當前的加總是正數，X 代表負數。

[O, O, O, X, O, O, O, O, X, X, X, O]
 i           i                    i

因為已經判定過 gas 的總和去減 cost 的總和會 >= 0 了，所以在加總的幾個位置中，會有其中一個值為起點時，繞一圈後結果還是 >= 0。

解法的時間、空間複雜度

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

參考資料

LeetCode - 134. Gas Station　解題心得