Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]

Explanation:

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var findDiagonalOrder = function(matrix) {
  let M = matrix.length;
  if (!M) return [];
  let N = matrix[0].length;

  let res = [];

  // first row
  for (let i = 0; i < N; i++) {
    let x = 0
      , y = i
      , tmp = [];

    while (true) {
      tmp.push(matrix[x][y]);
      x++;
      y--;

      if (x < 0 || x >= M || y < 0 || y >= N)
        break;
    }

    res.push(tmp);
  }

  // last column
  for (let i = 1; i < M; i++) {
    let x = i
      , y = N - 1
      , tmp = [];

    while (true) {
      tmp.push(matrix[x][y]);
      x++;
      y--;

      if (x < 0 || x >= M || y < 0 || y >= N)
        break;
    }

    res.push(tmp);
  }

  let ans = [];
  res.forEach(function(item, index) {
    if (!(index & 1)) {
      ans.push(...item.reverse());
    } else {
      ans.push(...item);
    }
  });

  return ans;
};

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree

    1
   / \
  2   3
 / \     
4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        

        def getHeight(node, depth):
            if node == None:
                return -1
            else:
                left = getHeight(node.left, depth) + 1
                right = getHeight(node.right, depth) + 1
                getHeight.ans = max(getHeight.ans, left + right)
                return max(left, right)

        getHeight.ans = 0
        getHeight(root, 0)
        
        return getHeight.ans

Differrent Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:
Input: "2-1-1"

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2:
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

/**
 * @param {string} input
 * @return {number[]}
 */
var diffWaysToCompute = function(input) {
  var ans = [];

  // 暴力递归求解
  dfs([], [], 0, 0, input);

  return ans;

  function dfs(numStack, symStack, num, index, input) {
    if (index === input.length) {
      numStack.push(num);

      while (symStack.length) {
        var b = numStack.pop();
        var a = numStack.pop();
        var sym = symStack.pop();

        numStack.push(eval('(' + a + ')' + sym + '(' + b + ')' ));
      }

      ans.push(numStack[0]);
      return;
    }

    var item = input[index];

    if ('-+*'.indexOf(item) !== -1) {

      // 不处理
      var _numStack = numStack.concat();
      var _symStack = symStack.concat();
      _numStack.push(num);
      _symStack.push(item);
      dfs(_numStack, _symStack, 0, index + 1, input);

      // 处理
      _numStack = numStack.concat();
      _numStack.push(num);
      _symStack = symStack.concat();
      while (_symStack.length) {
        var b = _numStack.pop();
        var a = _numStack.pop();
        var sym = _symStack.pop();

        _numStack.push(eval('(' + a + ')' + sym + '(' + b + ')' ));

        var newNumStack = _numStack.concat();
        var newSymStack = _symStack.concat();
        newSymStack.push(item);
        dfs(newNumStack, newSymStack, 0, index + 1, input);
      }
    } else {
      dfs(numStack.concat(), symStack.concat(), num * 10 + +item, index + 1, input);
    }
  }
};

/**
 * @param {string} input
 * @return {number[]}
 */
var diffWaysToCompute = function(input) {
  // save the possible values from the string input
  var ans = [];
  for (var i = 0, len = input.length; i < len; i++) {
    var item = input[i];
    if (~'+-*'.indexOf(item)) {
      var left = diffWaysToCompute(input.substring(0, i));
      var right = diffWaysToCompute(input.substring(i + 1));
      left.forEach(function(a) {
        right.forEach(function(b) {
          ans.push(eval('(' + a + ')' + item + '(' + b + ')'));
        });
      });
    }
  }

  !ans.length && ans.push(+input);
  return ans;
};

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
  var MAX_POSITIVE_INT = ~(1 << 31);
  var MAX_NEGATIVE_INT = (1 << 31);

  var ans = Math.floor(dividend / divisor);

  if (ans < MAX_NEGATIVE_INT)
    ans = MAX_NEGATIVE_INT;

  if (ans > MAX_POSITIVE_INT)
    ans = MAX_POSITIVE_INT;

  return ans;
};

Encode and Decode TinyURL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

let [p, index] = [new Map(), 0];

var base62 = (n) => {
  let str = '0123456789abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ';
  let len = str.length;
  let ret = '';

  do {
    ret += str[n % len];
    n = ~~(n / len);
  } while (n);

  return ret;
};

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
  let shortUrl = base62(index++);
  p.set(shortUrl, longUrl);
  return shortUrl;
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
  return p.get(shortUrl);
};