2022年1月16日 星期日

Leetcode - Easy - 9. Palindrome Number - Javascript


9. Palindrome Number

Easy

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

  • For example, 121 is a palindrome while 123 is not.

 

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

 

Constraints:

  • -231 <= x <= 231 - 1



解題方向:
1. 這題主要是要找對稱的數字, 所以要先排除大於 231 與小於 0
2. 再透過 leftIndex 與 rightIndex 從中心點個別往左右找是否數字相同

程式碼 :
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x > 2147483647 || x < 0) { return false; }
    
    const stringX = x.toString();
    const stringXLen = stringX.length;
    
    const center =  parseInt(stringXLen/2);
    
    let leftIndex = center - 1;
    let rightIndex = center;
    
    if (stringXLen % 2) {
        rightIndex = center + 1;
    }
    
    let result = true;
    
    while(leftIndex >= 0 && rightIndex <= stringXLen) {
        if (stringX[leftIndex] !== stringX[rightIndex]) {
            result = false;
            break;
        }
        
        leftIndex--;
        rightIndex++;
    }
        
    return result;
};




執行成果:


2022年1月15日 星期六

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


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;
};



執行成果:





Leetcode - Medium - 7. Reverse Integer - Javascript


 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;
};


執行成果:


2022年1月13日 星期四

Leetcode - Medium - 6. Zigzag Conversion - Javascript


6. Zigzag Conversion

Medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"



解題方向:
1. 這題的關鍵是要透過 mod 方式找出倒 N 型規則
2. 要排除 mod 是 0 or 1 的情況, 直接回傳 s
3. 倒 N 的 mod 數是 (numRow -1)x2
4. mod 後計算出的值如果大於 numRow -1, 就是反轉順序
5. 反轉順序的 mod 為 numRow -1
6. 反轉順序的 index 為 反轉mod - (第一次mod值 % 反轉mod)
7. 時間複雜度為 O(n)

程式碼 :
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    const stringList = [];
    const stringLen = s.length;
    const modNum = (numRows - 1) * 2;
    const revertModNum = numRows - 1;
    
    if (modNum <= 1) { return s;};
    
    for (let i = 0; i < stringLen; i++) {
        const index = i % modNum;
        let arrayIndex;
        
        if (index > revertModNum) {
            arrayIndex = revertModNum - (index%revertModNum);
        } else {
            arrayIndex = index;
        }
        stringList[arrayIndex] = stringList[arrayIndex] ? stringList[arrayIndex] + s[i] : s[i];
    }
    
    return stringList.join('');
};



執行成果:



高手解題:
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if(numRows === 1) {
        return s;
    }
    const result = new Array(numRows).fill('');
    let i = 0;
    let count = 0;
    let dir = false;
    while(i < s.length) {
        if(i % (numRows-1) === 0) dir = !dir
        result[count] += s[i];
        dir ? count++ : count--
        i++;
    }
    
    return result.join('');
};


透過取餘數為零時反轉 dir 指標

並針對對應的 couter 寫入對應的 array string

減少 mod 計算數量與複雜度

2022年1月12日 星期三

Leetcode - Medium - 5. Longest Palindromic Substring - Javascript


 5. Longest Palindromic Substring

Medium

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"


解題方向:
1. 這題是要找翻轉後也長相同的 substring, 所以在判斷時會有分 odd 與 even 兩種情況
2. 透過往左右的方式找尋 palindrome,  並回傳最大的 substring



程式碼 (1):

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    
    function getLongestPalindrome(string, leftIndex, rightIndex) {
      while (leftIndex >= 0 && rightIndex < string.length) {
        if (string[leftIndex] != string[rightIndex]) break;
        rightIndex++;
        leftIndex--;
      }
      return [leftIndex + 1, rightIndex];
    }
    
    let currentLongest = [0, 1];
    for (let i = 1; i < s.length; i++) {
        const odd = getLongestPalindrome(s, i - 1, i + 1);
        const even = getLongestPalindrome(s, i - 1, i);
        const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even;
        currentLongest = currentLongest[1] - currentLongest[0] > longest[1] - longest[0] ? currentLongest : longest;
      }
    return s.slice(currentLongest[0], currentLongest[1]);
};



執行成果:




程式碼 (2):

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  var longest = '', c;
  for (c=0; c<s.length; c++) {
    if ((s.length-c)*2 <= longest.length) break;  // exit early if remaining can't surpass largest found

    longest = scanOutward(s, longest, c, c);   // odd length "ata"
    longest = scanOutward(s, longest, c+1, c); // even length "atta"
  }
  return longest;
};

function scanOutward(s, longest, left, right) {
  if (left > 0 && right < s.length && s[left-1] === s[right+1]) {
    return scanOutward(s, longest, left-1, right+1);
  } else {
    return (right-left+1 >= longest.length) ? s.substring(left, right+1) : longest;
  }
}