Leetcode - Medium - 15. 3Sum - Javascript

Leetcode - Medium - 15. 3Sum - Javascript

   清晨6:07       Rain Lin

---

15. 3Sum

Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

 

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

 

解題方向：

1. 需要先由小到大排序 array

2. 這題要透過 two point 方式解, 所以除了 a 是原點外, 要增加a左邊一個的 b, 與最右邊的 c

3. 當 array 小於 3 時就不需要比較

4. 如果排序後第一位大於 0, 也代表後面排序的數字不可能相加等於 0, 可跳過這一輪的 a

5. 如果 a 這一輪的數字與前一輪比過的數字一樣, 也可以跳過這一輪的 a

6. 相加 nums[a], nums[b], nums[c] 等於 0 就紀錄到 result, 並讓 b, c 往中間移動, 需注意 b與c下一個如果與前一個相同數字則跳過, 因為已經計算過

7. 如 nums[a], nums[b], nums[c] 不等於 0, 則判斷  nums[b] + nums[c] 是否大於或小於 -nums[a], 如果是就讓 b or c 指標往中間移動繼續下一個判斷

程式碼 ：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let result = [];
    const numsLen = nums.length;
    
    if (numsLen < 3) { return result; }
    
    nums.sort((a,b) => a-b);

    for (let a = 0; a < numsLen; a++) {
        if(nums[a] > 0){    
           break;
        }
        
        if (a > 0 && nums[a] === nums[a-1]) {
            continue;
        }
        
        let b = a + 1;
        let c = numsLen - 1;
        const temp = -(nums[a]);
        
        while (b < c) {
            if (nums[a] + nums[b] + nums[c] === 0) {
                result.push([nums[a], nums[b], nums[c]]);
            
                while(b < c && nums[b] === nums[b+1]) b++;
                while(b < c && nums[c] === nums[c-1]) c--;
                b++;
                c--;
            }
            
            const twoPointSum = nums[b] + nums[c];
            
            if (twoPointSum > temp) {
                c--;
            } else if (twoPointSum < temp) {
                b++;
            }
        }
    }
    
    
    return result;
};

執行成果：

Read More

Leetcode - Medium - 12. Integer to Roman - Javascript

Leetcode - Medium - 12. Integer to Roman - Javascript

   晚上9:27       Rain Lin

---

12. Integer to Roman

Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

 

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 

Constraints:

• 1 <= num <= 3999

 

解題方向：

1. 這邊主要是要搞懂 Roman 規則, 再擬定羅馬與數字對照表

    a. 1 ~ 3 是用 I 表示

    b. 4 ~ 8 是與 V 相關

    c. 9 ~ 10 是和 ‘X’ 相關

程式碼 ：

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    if (num < 1 || num > 3999) { return ''; }
    
    const romanList = {
        1000: "M", 
        900: "CM", 
        500: "D", 
        400: "CD", 
        100: "C", 
        90: "XC", 
        50: "L", 
        40: "XL", 
        10: "X", 
        9: "IX", 
        5: "V", 
        4: "IV", 
        1: "I"
    }
    
    const numList = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let index = 0;
    let result = '';
    let leastNum = num;
    
    while(index < numList.length) {
        const numMod = numList[index];
        index++;
        
        const repeatNum = parseInt(leastNum / numMod);
        
        if (repeatNum === 0) { continue;}
        
        leastNum = leastNum - (repeatNum * numMod);
        result += romanList[numMod].repeat(repeatNum);
        
    }
    
    return result;
};

執行成果：

Read More

Leetcode - Medium - 11. Container With Most Water - Javascript

Leetcode - Medium - 11. Container With Most Water - Javascript

   凌晨12:54       Rain Lin

---

11. Container With Most Water

Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

解題方向：

程式碼 ：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  const heightLen = height.length;
  let leftIndex = 0;
  let rightIndex = heightLen - 1;

  let maxCount = 0;

  while (leftIndex !== rightIndex) {
    const dist = rightIndex - leftIndex;
    let leftLine = height[leftIndex];
    let rightLine = height[rightIndex];
    
    let minHeight;
    if (leftLine < rightLine) {
        minHeight = leftLine;
        leftIndex++;
    } else {
        minHeight = rightLine;
        rightIndex--
    }
      
    const _curentNum  = minHeight * dist;

    if (maxCount < _curentNum) {
      maxCount = _curentNum;
    }
  }

  return maxCount;
};

執行成果：

Read More

Leetcode - Medium - 8. String to Integer (atoi) - Javascript

Leetcode - Medium - 8. String to Integer (atoi) - Javascript

   清晨6:40       Rain Lin

---

8. String to Integer (atoi)

Medium

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

 

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

解題方向：

1. 一開始以為是單純的文字移除空白和文字後再轉成 int 的函式, 但詳細了解後並非這麼簡單

2. 這邊有分成兩階段共三步驟方式處理

- 第一階段: 累計數字

    step 1. 先利用 isPositive 紀錄是否開頭為 '-', '+', '0-9' 如果在這個步驟遇到空白外的文字即立刻回傳 0

    step 2. 當紀錄 isPositive 後就開始累計 '0-9', 遇到其他文字立即中斷 while 迴圈, 結束累計

- 第二階段 處理回傳值

    step 3. 透過文字個別轉成數字時判斷是否落在 minLimit 與 maxLimit 之間, 如不是即立刻回傳對應的上下限值即可

程式碼 ：

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    let index = 0;
    let isPositive = 0;
    let resultString = '';
    const digiArray = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0'];
    
    while(index < s.length) {
        const letter = s[index];
        index++;
        
        if (isPositive === 0) {
            if (letter === ' ') {
                continue;
            } else if (letter === '-') {
                isPositive = '-1';
                continue;
            } else if (letter === '+') {
                isPositive = '1';
                continue;
            } else if (digiArray.includes(letter)) {
                isPositive = '1';
                resultString += letter;
            } else {
                return 0;
            }
            
        } else {
            if (!digiArray.includes(letter)) {
                break;
            } else {
                resultString += letter;
            }
        }        
    }
    
    
    const minLimit = -2147483648;
    const maxLimit = 2147483647;
    let result = 0;
    
    for (let i in resultString) {
        result = result * 10 + isPositive * parseInt(resultString[i]);
        
        if (result < minLimit) { return minLimit};
        if (result > maxLimit) { return maxLimit};
    }
    
    return result;
};

執行成果：

Read More

Leetcode - Medium - 7. Reverse Integer - Javascript

Leetcode - Medium - 7. Reverse Integer - Javascript

   清晨5:49       Rain Lin

---

 7. Reverse Integer

Medium

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

 

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

 

Constraints:

• -231 <= x <= 231 - 1

解題方向：

1. 這題是要反轉數字後保留正負數符號

2. 先轉成字串, 在檢查第一個文字是不是 '-1' 是的話就記錄負數

3. 再反轉紀錄文字, 最後再轉成數字和疊加正負數符號

4. 結果沒落在  -231 <= x <= 231 - 1  就要回傳 0

程式碼 ：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    
    
    const stringX = x.toString();
    
    let index = 0;
    let revertStringX = '';
    let isPositive = true;
    while (index < stringX.length) {
        const letter = stringX[index];
        
        if (index === 0 && letter === '-') {
            isPositive = false;
        } else {
            revertStringX = letter + revertStringX;
        }
        
        index++;
    }
    
    let result = 0;
    
    if (isPositive) {
        result = parseInt(revertStringX); 
    } else {
        result = -(parseInt(revertStringX));
    }
    
    if (result < -2147483648 || result > 2147483649) { return 0;} 
    return result;
};

執行成果：

Read More