leetcode solutions

00-a!.leetcode.js

/*everything about leetcode*/

add-binary.ts

/*
67
https://leetcode.com/problems/add-binary/
*/

function addBinary(a: string, b: string): string {
  let result = "";
  let isCarrying = false;

  for (let i = 1; i <= Math.max(a.length, b.length); ++i) {
    // check each digit one by one from the end
    // "0" is 48, "1" is 49 as charcode
    const aNum = (a.charCodeAt(a.length - i) || 48) - 48;
    const bNum = (b.charCodeAt(b.length - i) || 48) - 48;

    // reverse bit twice to cast boolean into 0 or 1
    const union: number = aNum + bNum + (isCarrying ? 1 : 0);

    // union is possibly 0, 1, 2, 3
    isCarrying = union >= 2;

    // 1 and 3 -> 1, 0 or 2 -> 0
    result = (union % 2) + result;
  }

  return isCarrying ? "1" + result : result;
}

add-two-numbers.js

/*
2
https://leetcode.com/problems/two-sum/
*/

var addTwoNumbers = function (l1, l2) {
    // Head of the new linked list - this is the head of the resultant list
    let head = null;
    // Reference of head which is null at this point
    let temp = null;
    // Carry
    let carry = 0;
    // Loop for the two lists
    while (l1 !== null || l2 !== null) {
        // At the start of each iteration, we should add carry from the last iteration
        let sum = carry;
        // Since the lengths of the lists may be unequal, we are checking if the
        // current node is null for one of the lists
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        // At this point, we will add the total sum % 10 to the new node
        // in the resultant list
        let node = new ListNode(Math.floor(sum) % 10);
        // Carry to be added in the next iteration
        carry = Math.floor(sum / 10);
        // If this is the first node or head
        if (temp == null) {
            temp = head = node;
        }
        // For any other node
        else {
            temp.next = node;
            temp = temp.next;
        }
    }
    // After the last iteration, we will check if there is carry left
    // If it's left then we will create a new node and add it
    if (carry > 0) {
        temp.next = new ListNode(carry);
    }
    return head;
};

backspace-string-compare.ts

/*
844
https://leetcode.com/problems/backspace-string-compare/
*/

function backspaceCompare(S: string, T: string): boolean {
  let s = S;
  let t = T;

  while (s.includes("#")) {   
    s = s.replace(/([^#]#|^#+)/g, "");
  }

  while (t.includes("#")) {
    t = t.replace(/([^#]#|^#+)/g, "");
  }

  return s === t;
}

best-time-to-buy-and-sell-stock.ts

/*
121
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
*/

function maxProfit(prices: number[]): number {
  let maxProfit = 0;
  let minPrice = Number.MAX_SAFE_INTEGER;

  for (let i = 0; i < prices.length; ++i) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (maxProfit < prices[i] - minPrice) {
      maxProfit = prices[i] - minPrice;
    }
  }

  return maxProfit;
}

four-sum.js

/*
18
https://leetcode.com/problems/4sum/
*/


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
const fourSum = function(nums, target) {
  let result = [];
  let length = nums.length;
  if (length < 4) return result; 
  nums = nums.sort((a, b) => a - b );
for (let i = 0; i < length - 3; i++) {
    if (nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < length - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let k = j + 1;
      let l = length - 1;
while (k < l) {
        const sum = nums[i] + nums[j] + nums[k] + nums[l];
if (sum === target) {
          result.push([nums[i], nums[j], nums[k], nums[l]])
        }
if (sum <= target) {
          k += 1;
          while (nums[k] === nums[k - 1]) {
            k += 1;
          }
        }
if (sum >= target) {
          l -= 1;
          while (nums[l] === nums[l + 1]) {
            l -= 1;
          }
        }
      }
    }
  }
return result;
};

integer-to-english-words.js

/*
273
https://leetcode.com/problems/integer-to-english-words/
*/

/**
 * @param {number} num
 * @return {string}
 */
const numberToWords = function(num) {
  let result = toHundreds(num % 1000);
  const bigNumbers = ["Thousand", "Million", "Billion"];
  
  for (let i = 0; i < 3; ++i) {
    num = Math.trunc(num / 1000);
    result = num % 1000 !== 0 ? [toHundreds(num % 1000), bigNumbers[i], result].filter(Boolean).join(" ") : result;
  }
  
  return result.length === 0 ? "Zero" : result;
}

function toHundreds(num) {
  const numbers = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
    "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"];
  const tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
  const result = Array(3).fill("");
  let a = Math.trunc(num / 100), b = num % 100, c = num % 10;
  result[0] = a > 0 && `${numbers[a]} Hundred`;
  result[1] = b < 20 ? numbers[b] : tens[Math.trunc(b / 10)]
  result[2] = b >= 20 && `${numbers[c]}`;
  return result.filter(Boolean).join(" ");
}

longest-valid-parentheses.js

/*
32
https://leetcode.com/problems/longest-valid-parentheses/
*/

/**
 * @param {string} s
 * @return {number}
 */
const longestValidParentheses = function(S) {
  let stack = [-1], ans = 0;
  for (let i = 0; i < S.length; i++)
    if (S[i] === '(') stack.push(i)
    else if (stack.length === 1) stack[0] = i
    else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1])
  return ans
};

median-of-two-sorted-arrays.js

/*
4
https://leetcode.com/problems/median-of-two-sorted-arrays/
*/


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = (nums1, nums2) => {
  const merge = (xs1, xs2) => {
    if (!xs1 || !xs1.length) {
      return xs2
    }
    if (!xs2 || !xs2.length) {
      return xs1
    }
    const [hd1, ...rest1] = xs1
    const [hd2, ...rest2] = xs2
    return hd1 <= hd2 ? [hd1, ...merge(rest1, xs2)] : [hd2, ...merge(xs1, rest2)]
  }
  const nums = merge(nums1, nums2)
  const middle = Math.floor((nums.length-1) / 2)

  return (middle * 2 === (nums.length-1)) ?  nums[middle] : ((nums[middle] + nums[middle + 1]) / 2) 
}

min-cost-to-connect-all-points.js

/*
1584
https://leetcode.com/problems/min-cost-to-connect-all-points/
*/

/**
 * @param {number[][]} points
 * @return {number}
 */
const minCostConnectPoints = function (points) {
  const distance = (p1, p2) => Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1])
  const arr = []
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const d = distance(points[i], points[j])
      arr.push([i, j, d])
    }
  }
  arr.sort((a, b) => a[2] - b[2])
  const parents = points.map((x, index) => index)
  const root = (a) => {
    while (parents[a] !== parents[parents[a]]) {
      parents[a] = parents[parents[a]]
    }
    return parents[a]
  }
  const isConnected = (a, b) => root(a) === root(b)
  const union = (a, b) => {
    const rootA = root(a)
    const rootB = root(b)
    parents[rootA] = rootB
  }
  let result = 0
  for (const [a, b, cost] of arr) {
    if (!isConnected(a, b)) {
      result += cost
      union(a, b)
    }
  }
  return result
}

missing-number.js

/*
268
https://leetcode.com/problems/missing-number/
*/

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
let expectedSum = nums.length*(nums.length + 1)/2
    let actualSum = nums.reduce((a, b) => a + b, 0)
    let missingNumber = expectedSum - actualSum

    return missingNumber 
};

permutation-in-string.js

/*
567
https://leetcode.com/problems/permutation-in-string/
*/

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
const checkInclusion = function(s1, s2) {
  const len1 = s1.length, len2 = s2.length;
  if (len1 > len2) return false;
const count = Array(26).fill(0);
  for (let i = 0; i < len1; i++) {
      count[s1.charCodeAt(i)-97]++;
      count[s2.charCodeAt(i)-97]--;
  }
  if (!count.some(e => e !== 0)) return true;
for (let i = len1; i < len2; i++) {
      count[s2.charCodeAt(i)-97]--;
      count[s2.charCodeAt(i-len1)-97]++;
      if (!count.some(e => e !== 0)) return true;
  }
  return false;
};

permutations.js

/*
46
https://leetcode.com/problems/permutations/
*/

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = function(nums) {
    let results = [];
let go = (current) => {
      if (current.length === nums.length){
        results.push(current);
        return;
      }
      nums.forEach(n => {
        if (!current.includes(n)){
          go([...current, n]);
        }
      });
    }
    go([]);
    return results;
};

ransom-note.js

/*
383
https://leetcode.com/problems/ransom-note/
*/

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const map = {}
    for(let c of magazine) {
        map[c] = (map[c] || 0) + 1
    }
    
    const map2 = {}
    for(let c of ransomNote) {
        map2[c] = (map2[c] || 0) + 1
        if(map2[c] > (map[c] || 0)) {
            return false
        }
    }
    return true
};

reverse-integer.js

/*
7
https://leetcode.com/problems/reverse-integer/
*/

/**
 * @param {number} x
 * @return {number}
 */
const reverse = function(num) {
    let result = 0;
    while (num !== 0) {
      result = result * 10 + num % 10;
      num = Math.trunc(num / 10);
    }
if (result > 2**31 || result < -(2**31)) return 0;
    return result;
};

shortest-palindrome.js

/*
214
https://leetcode.com/problems/shortest-palindrome/
*/

/**
 * @param {string} s
 * @return {string}
 */

const shortestPalindrome = function(s) {
  let index = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === s[index]) index++;
  }
  if (index === s.length) return s;
  let remainingRev = s.substring(index, s.length);
  console.log(remainingRev);
  remainingRev = reverse(remainingRev);
return remainingRev + shortestPalindrome(s.substring(0, index)) + s.substring(index);
};
function reverse(string) {
  let myString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    myString = myString + string[i];
  }
  return myString;
};

smallest-string-with.swap.js

/*
1202
https://leetcode.com/problems/smallest-string-with-swaps/
*/

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}
/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
const smallestStringWithSwaps = function (s, pairs) {
  const result = []
  const uf = new UnionFind(s.length)
  pairs.forEach(([index1, index2]) => {
    uf.union(index1, index2)
  })
  const groups = {

  }

  for (let i = 0; i < s.length; i++) {
    const currentRoot = uf.root(i)
    if (groups[currentRoot]) {
      groups[currentRoot].add(i)
    } else {
      groups[currentRoot] = new Set([i])
    }
  }
  // leetcode 的JS环境是 10.15.0
  Object.values(groups).forEach((indexSet) => {
    const indexes = [...indexSet]
    const str = indexes.map(index => s[index])
    // NOTE node 12.12.0  竟然可以这样写 str.sort(([a, b]) => a.localeCompare(b))
    str.sort((a, b) => a.localeCompare(b))
    str.forEach((item, index) => {
      const realIndex = indexes[index]
      result[realIndex] = item
    })
  })
  return result.join('')
}

string-multiplication.js

/*
43
https://leetcode.com/problems/multiply-strings/
*/

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
const multiply = function(num1, num2) {
    return String(BigInt(num1) * BigInt(num2));
};

two-sum.js

/*
1
https://leetcode.com/problems/two-sum/
*/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // Array to store the result
    result = [];
    // Map to store the difference and its index
    index_map = new Map();
    // Loop for each element in the array
    for (let i = 0; i < nums.length; i++) {
        let difference = target - nums[i];
        if (index_map.has(difference)) {
            result[0] = i;
            result[1] = index_map.get(difference);
            break;
        } else {
            index_map.set(nums[i], i);
        }
    }
    return result;
};