Press "Enter" to skip to content

JS Tech Road

LeetCode 43. Multiply Strings (javascript)

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Solution:

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    let len1 = num1.length;
    let len2 = num2.length;
    let carry = 0;
    let val = 0;
    let index = 0;
    let res = Array(len1 + len2).fill(0);
    
    for (let i = len1 - 1; i >= 0; i--) {
        carry = 0;
        for (let j = len2 - 1; j >= 0; j--) {
            // calucate from the right position and store in result array from index 0
            // reverse it later
            index = len1 + len2 - 2 - i - j;
            // basic math calculation
            val = (num1[i] * num2[j]) + res[index] + carry;
            carry = Math.floor(val / 10);
            res[index] = val % 10;
        }
        // check if has carry 1
        if (carry) res[index + 1] = carry;
    }
    
    // before reverse, remove the begining 0
    while (res.length > 1 && res[res.length - 1] === 0) res.pop();
    return res.reverse().join("");
};

LeetCode 9. Palindrome Number (javascript)

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 palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

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.

Example 4:

Input: x = -101
Output: false

Constraints:

  • -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    // negative number is not a Palindrome Number
    if (x < 0) return false;
    let y = x;
    let reverse = 0;
    while (y > 0) {
        let lastDigit = y % 10;
        reverse = reverse * 10 + lastDigit;
        y = parseInt(y / 10);
    }
    return reverse === x ;
};

LeetCode 8. String to Integer (atoi) Javascript solution

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 charcter 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.

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
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.

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

Example 4:

Input: s = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
         ^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
         ^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 0.

Example 5:

Input: s = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
         ^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
          ^
Step 3: "-91283472332" ("91283472332" is read in)
                     ^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ''+''-', and '.'.

Solution 1:

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
  const len = s.length;
  let max = 2147483647;
  let min = -2147483648;
  let numberMatch = /^[\d ()+-]+$/;

  for (let i = 0, j = i; i < len; i++) {
    let current = s[i];

    if (current != " " && !current.match(numberMatch)) {
        return 0;
    } else if (current != " " && current.match(numberMatch)) {
      let result = "";

      while (j < len && current.match(numberMatch)) {
        result += s[j];
        j++;
      }
      let output = parseInt(result);
      if (isNaN(output)) return 0;
      else if (output > max) return max;
      else if (output < min) return min;
      else return output;
    }
  }
  return 0;
};

Solution 2:

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
  let i = 0;
  let sign = 1;
  let res = 0;
  let len = s.length;
  let INT_MAX = 2147483647;
  let INT_MIN = - INT_MAX - 1;

  // skip all space
  while (s[i] === ' ') i++;

  // check sign
  if (s[i] === '+' || s[i] === '-') {
    sign = s[i] === '+' ? 1 : -1;
    i++;
  }

  while (s[i] >= '0' && s[i] <= '9') {
    res = (res * 10) + (s[i] - 0);
    if (sign === 1 && res > INT_MAX) return INT_MAX;
    if (sign === -1 && res > INT_MAX + 1) return INT_MIN;
    i++;
  }

  return res * sign;
};

LeetCode 7. Reverse Integer (javascript)

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

Example 4:

Input: x = 0
Output: 0

Constraints:

  • -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {number}
 */

var reverse = function(x) {
    const str      = "" + Math.abs(x);   // convert absolute value to string
    const reversed = str.split("")       // get array of digit characters
                   .reverse()            // reverse it
                   .join("");            // join into string again;
    const num      = parseInt(reversed); // convert to integer
    const revNum = Math.sign(x) * num;   // multiple the sign
    // if out of range return 0
    if (revNum < Math.pow(-2, 31) || revNum > Math.pow(2, 31) - 1) return 0;
    return revNum;
}

LeetCode 763. Partition Labels (javascript)

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

  • S will have length in range [1, 500].
  • S will consist of lowercase English letters ('a' to 'z') only.

Idea:

  • Create hash table to track the last index of the letter
  • use start and end variable to decide the partition letters
  • when end reach to the last index of the letter :
    • store the length of the partition letters (end – start + 1)
    • reset start => end + 1

Solution:

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let last_index = new Map();
    for (let i = 0; i < S.length; i++) {
        last_index.set(S[i],  i);
    }
    let res = [];
    let start = 0;
    let end = 0;
    for (let i = 0; i < S.length; i++) {
        end = Math.max(end, last_index.get(S[i]));
        if (i === end) {
            res.push(end - start + 1);
            start = end + 1;
        }
    }
    return res;
};

LeetCode 14. Longest Common Prefix (javascript)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

Idea:

  • Use first string for comparison
  • loop through each string:
    • store the common letter if match
    • or return the answer if no match

Solution:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let ans = "";
    for (let i = 0; i < strs[0].length; i++) {
        for (let s of strs) {
            if (s.length <= i || s[i] !== strs[0][i]) return ans;
        }   
        ans += strs[0][i];
    }
        
    return ans;
};

LeetCode 6. ZigZag Conversion (javascript)

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"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Idea:

  • Treat this as an elevator
  • The letter trend is from the top to the bottom, and then from the bottom to the top as the elevator, so only need to build n(numRows) level strings elevator, each string represents a layer(level)
  • every time to visit a layer(level) while loop through the String s, store that letter into visiting layer(level)
  • merge all the layers to get the final answer

Solution:

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) return s;
        
    let levels = [];
    for (let i = 0; i < numRows; i++) {
        levels[i] = [];
    }
    let down = true;
    const n = s.length;
    let index = 0;
    for (let i =  0; i < n; i++) {
        if (down) {
            let end = index >= numRows - 1;
            if (end) down = false;
            levels[index].push(s[i]);
            index = end ? index - 1: index + 1;
        } else {
            let top = index <= 0;
            if (top) down = true;
            levels[index].push(s[i]);
            index = top ? index + 1: index - 1;
        }
    }
    let res = "";
    for (let i = 0; i < numRows; i++) {
        res += levels[i].join('');
    }
    return res;
};

LeetCode 56. Merge Intervals (javascript)

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Idea:

  • First step (Important): sort the intervals by the first number
  • Use result array to store the first interval
  • Compare the last interval of the result array vs. new coming interval
    • new interval > last interval of the result array : store the new interval into result array
    • new interval < last interval of the result array : store the interval that has longer range

Solution:

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort(([a, b], [c, d]) => a - c);
    let res = [];
    for (let interval of intervals) {
        if (res.length === 0 || interval[0] > res[res.length - 1][1]) {
            res.push(interval.concat());
        } else {
            res[res.length - 1][1] = Math.max(interval[1], res[res.length - 1][1]);
        }
    }
    return res;
};

LeetCode 876. Middle of the Linked List (javascript)

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

Idea:

Use fast and slow pointers traversal

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    
    while(fast) {
        if (!fast.next) break;
        fast = fast.next.next;
        slow = slow.next;
    }
    
    return slow;
};

LeetCode 202. Happy Number (javascript)

Write an algorithm to determine if a number n is happy.

happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 231 - 1

Idea:

create a function to calculate the sum of the squares of its digits.

use fast and slow pointers traversal concept (the other one execute function twice) to check if they can reach 1 (means it is happy number)

Solution:

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    let slow = n;
    let fast = n;
    
    do {
        slow = squareSum(slow);
        fast = squareSum(squareSum(fast));
    } while (slow !== fast);
    
    return fast === 1;
};

var squareSum = function(n) {
    let sum = 0;
    while(n) {
        sum += (n % 10) * (n % 10);
        n = parseInt(n / 10);
    }
    return sum;
};