Interesting Leetcode Problems

BT_max_sum_path.js

/**
 * 
 * -10
   / \
  9  20
    /  \
   15   7
 * 
 * 
    
 *          
 * 
 * 
 * (-10, 9, 42)
   /         \
  (9, 0, 0)   (20, 15, 7)
             /           \
            (15, 0, 0)   (7, 0, 0)
 * 
 * 
 * 
 */

 // https://leetcode.com/problems/binary-tree-maximum-path-sum/submissions/

var maxPathSum = function(root) {
    let max = -Infinity;
    
    function traverse(root) {
        if (!root) return -Infinity;
        if (!root.left && !root.right) {
            max = Math.max(max, root.val);
            return root.val;
        }
        let left = -Infinity, right = -Infinity
        if (root.left) left = traverse(root.left);
        if (root.right) right = traverse(root.right);

        lmax = Math.max(
            left + root.val,
            right + root.val,
            root.val
        );

        max = Math.max(
            max, 
            lmax,
            left + right + root.val,
        );

        return lmax
    }
    
    traverse(root);
    
    return max;
};

merge_k_sorted_liinked_lists.js

// https://leetcode.com/problems/merge-k-sorted-lists/submissions/

function Heap() {
  const store = [];
  let length = 0;

  const parent = (x) => parseInt(Math.floor((x - 1) / 2));
  const leftChild = (x) => 2 * x + 1;
  const rightChild = (x) => 2 * x + 2;

  const swap = (a, x, y) => {
    let t = a[x];
    a[x] = a[y];
    a[y] = t;
  };

  const heapify_up = () => {
    let current = length;
    length++;
    while (current > 0) {
      let p = parent(current);
      if (store[current].val < store[p].val) {
        swap(store, current, p);
        current = p;
      } else {
        break;
      }
    }
  };

  const heapify_down = () => {
    store[0] = store[length - 1];
    length--;
    let current = 0;
    while (current < length) {
      let left = store[leftChild(current)] && store[leftChild(current)].val;
      let right = store[rightChild(current)] && store[rightChild(current)].val;
      if (
        leftChild(current) < length &&
        store[current].val > left &&
        left <= right
      ) {
        swap(store, current, leftChild(current));
        current = leftChild(current);
      } else if (
        rightChild(current) < length &&
        store[current].val > right &&
        right < left
      ) {
        swap(store, current, rightChild(current));
        current = rightChild(current);
      } else {
        break;
      }
    }
  };

  return {
    add(x) {
      store[length] = x;
      heapify_up();
    },
    remove() {
      if (length <= 0) return null;
      let p = store[0];
      heapify_down();
      return p;
    },
  };
}

function mergeKLists(xs) {
  let len = xs.length;
  let heap = new Heap();
  let sorted_hd = null,
    sorted_tl = null;

  for (let i = 0; i < len; i++) {
    while (xs[i]) {
      heap.add(xs[i]);
      xs[i] = xs[i].next;
    }
  }

  let h = heap.remove();
  while (h !== null) {
    if (sorted_hd === null && sorted_tl === null) {
      sorted_hd = h;
      sorted_tl = sorted_hd;
    } else {
      sorted_tl.next = h;
      sorted_tl = sorted_tl.next;
    }
    h = heap.remove();
  }

  sorted_tl && (sorted_tl.next = null);

  return sorted_hd;
}

//[[-2,-1,-1,-1],[]]

function Node(val, next) {
  return {
    val,
    next: next || null,
  };
}

let ll1 = Node(-2, Node(-1, Node(-1, Node(-1))));
let ll2 = null;
let xs = [null];

let sorted = mergeKLists(xs);

let s = [];
while (sorted) {
  s.push(sorted.val);
  sorted = sorted.next;
}

console.log(s.join(", "));

roman_numerals.js

// https://leetcode.com/problems/integer-to-roman/submissions/
function intToRoman(n) {
  if (n <= 0) return '';    
  if (n >= 1 && n <= 3) return 'I' + intToRoman(n - 1);
  if (n === 4) return 'IV';
  if (n >= 5 && n <= 8) return 'V' + intToRoman(n - 5);
  if (n === 9) return 'IX';
  if (n >= 10 && n <= 39) return 'X' + intToRoman(n - 10);
  if (n >= 40 && n <= 49) return 'XL' + intToRoman(n - 40);
  if (n >= 50 && n <= 89) return 'L' + intToRoman(n - 50);
  if (n >= 90 && n <= 99) return 'XC' + intToRoman(n - 90);
  if (n >= 100 && n <= 399) return 'C' + intToRoman(n - 100);
  if (n >= 400 && n <= 499) return 'CD' + intToRoman(n - 400);
  if (n >= 500 && n <= 899) return 'D' + intToRoman(n - 500);
  if (n >= 900 && n <= 999) return 'CM' + intToRoman(n - 900);
  if (n >= 1000 && n <= 3999) return 'M' + intToRoman(n - 1000);
}

intToRoman(1000) === 'M'

roman_to_integer.js

const lookup = {
  'I': 1,
  'IV': 4,
  'V': 5,
  'IX': 9,
  'X': 10,
  'XL': 40,
  'L': 50,
  'XC': 90,
  'C': 100,
  'CD': 400,
  'D': 500,
  'CM': 900,
  'M': 1000
}
function romanToInt(rs) {
  let head = 0, end = rs.length, answer = 0;
  while (head < end) {
    if (((head+1) < end) && (!!lookup[rs[head] + rs[head + 1]])) {
      answer += lookup[rs[head] + rs[head + 1]]
      head += 2
    } else if (!!lookup[rs[head]]) {
      answer += lookup[rs[head]]
      head++
    }
  }
  return answer
}

romanToInt('MCMXCIV')

rotate_reverse.js

function reverse(a, s = 0, e = a.length - 1) {
  let temp;
  for (let i = s; i < e / 2; i++) {
    temp = a[i];
    a[i] = a[e - i];
    a[e - i] = temp;
  }
}

function left_rotate_better(a, k = 0) {
  let n = a.length - 1;
  reverse(a)
  reverse(a, 0, n - k)
  reverse(a, n - k + 1, n)
}

function left_rotate(a, k) {
  while (k--) {
    let start = a[0];
    for (let i=1;i<a.length;i++) {
      a[i-1] = a[i];
    }
    a[a.length-1] = start;
  }
}

a = [1, 2, 3, 4, 5];
left_rotate(a, 3)
a;

b = [1, 2, 3, 4, 5];
left_rotate_better(b, 3)
b;