Facebook脸家 - Lexicographical path

Lexicographical path

        5
       / \
      3   2
     / \   \
    2   4   4
             \
              1

FB 面经，自底向上的 path 有【1,4,2,5】，【4,3,5】，【2,3,5】，要求按自底向上的 lexicographical order 返回排序的 path，比如在这里是 【1,4,2,5】, 【2,3,5】,【4,3,5】

Analysis: Post order, for each node keep left & right paths, merge 2 into one single path.
Complexity: O(nlgn), each node has at most lgn node in the path.

var binaryTreePaths = function(root) {
 var res = [];
 console.log(dfs(root, res));
 
 return res
};
function dfs(root, path){
    if(root === null){
 return [];
  }
  if(root.left === null && root.right === null){
      return [[root.val]];
  }
  var left = dfs(root.left, path);
  var right = dfs(root.right, path);
  var path = [];
  for(var key in left){
     left[key].push(root.val);
  }
  for(var key in right){
     right[key].push(root.val);
  }
  path = left.concat(right);
  return path;
}

Leetcode - 214. Shortest Palindrome

214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Analysis:
  S#S' will make a valid palindrome. Key is to use KMP algo to find existing repeating part from the half, which is S
 ex1:   aa#aa
KMP: 01012  -> so we will have s.substring(2).reverse + s = '' + 'aa' = 'aa'
ex2:   bba#abb
KMP: 0100012 -> so we will have s.substring(1).reverse +  s = 'a.reverse' + 'bba' = abba

Complexity: O(N)

var shortestPalindrome = function(s) {
    if(s.length < 1){return s;}
    var pali = s+"#"+s.split("").reverse().join("");//s#s'
   //storing next entry pos for comparision
    var kmp = getKMP(pali);
    console.log(kmp)
    var length = kmp[kmp.length-1];
    return s.substring(length).split("").reverse().join("") + s;
};

function getKMP(s){
    var j = 0;
    var table = [];
    table[0] = 0;
    for(var i = 1; i < s.length; i++){
        while(s[i] !== s[j] && j > 0){
            j = table[j-1];
        }
        if(s[i] === s[j]){
            table[i] = j+1;
            j++;
        }else{
            table[i] = 0;
        }
    }
    return table;
}

Leetcode - Permutation Palindrome ii (javascript)

 267. Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Analysis:
1. start from i, first figure out if s is valid for palindrome by checking if have > 1 odd # letter. Use a map to record key-count.
2. If valid, reduce all even count/=2. If find the odd one, reduce to 0, and save odd letter.
3. DFS the left half till reach s.length/2, append to res with odd + reverse right half.

Complexity:
Time O(N!)

var s = "aasbb";
var map = {};
var res = [];
var odd = "";
if (helper(s, map)) {
    for (var key in map) {
        if (map[key] === 1) {
            odd = key;
            delete map[key];
        }
        if (map[key] % 2 === 0) {
            map[key] /= 2;
        }
    }
    dfs(map, [], res, parseInt(s.length / 2), odd);
}
console.log(res);//["absba", "basab"]

function dfs(map, path, res, len, odd) {;
    if (path.length === len) {
        res.push(path.join("") + odd + path.reverse().join(""));
        return;
    }
    for (var key in map) {
        if (map[key] === 0) {
            continue;
        }
        path.push(key);
        map[key]--;
        dfs(map, path, res, len, odd);
        path.pop();
        map[key]++;
    }
}

function helper(s, map) {
    var count = 0;
    for (var i = 0; i < s.length; i++) {
        if (map[s[i]] === undefined) {
            map[s[i]] = 0;
        }
        map[s[i]]++;
    }
    for (var key in map) {
        if (map[key] % 2 !== 0) {
            count++;
        }
        if (count > 1) {
            return false
        }
    }
    return true;
}

Leetcode -- 105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

思路：
pre: 1,2,3,4 //pre+1 can be left child, find its position 'rindex' in inorder
in:   4,2,1,3//[inStart, inEnd] is the range for left/right child
                     [inStart, rindex-1] - left child
                     [rindex+1, inEnd] - right child
                    **rindex+1 is right child, convert its position in preorder: preStart+rindex-inStart+1

Complexity:  Time O(n^2) Space O(1)
or use HashMap to improve find:  Time O(N) Space O(N)

var buildTree = function(preorder, inorder) {
    return helper(preorder, inorder, 0, inorder.length - 1, 0);
};
function helper(preorder, inorder, inStart, inEnd, preStart){
    if(preStart > inorder.length-1 || inStart > inEnd)
        return null;
    var root = new TreeNode(preorder[preStart]);
    var rindex = 0;
    for(var i = inStart; i <= inEnd; i++){
        if(inorder[i] === preorder[preStart]){
            rindex = i;
            break;
        }
    }
    root.left = helper(preorder, inorder, inStart, rindex-1, preStart+1);
    root.right = helper(preorder, inorder, rindex+1, inEnd,  preStart+rindex-inStart+1);
    return root;
}

Leetcode - 61. Rotate List(linkedlist)

61. Rotate List
medium
https://leetcode.com/problems/rotate-list/#/submissions/1

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

思路： - find out how many times to rotate: k%len
           - each time, do rotate operation by moving last node in list to the new head
           - edge case: len = 1

Complexity: Time O(k%len*N) ~ O(N) Space O(1)

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null)return head;
        //find size
        int len = 0;
        ListNode cur = head;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        int times = k % len;//len 5 6times, actually rotate once!
        ListNode nHead = head;
        for(int i = 0; i < times; i++){
            nHead = doRotation(nHead);
        }
        return nHead;
    }
    
    public ListNode doRotation(ListNode head){
        ListNode cur = head;
        while(cur.next != null && cur.next.next != null){
            cur = cur.next;
        }
        ListNode nHead = cur.next;
        cur.next = cur.next.next;
        nHead.next = head;
        return nHead;
    }
}

Leetcode -- 547. Friend Circles(dfs)

547. Friend Circles(dfs)
medium
https://leetcode.com/problems/friend-circles/#/description

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

思路：- define visited array for each person, mark all ppl in one cycle visited using dfs
           - traverse the he specific row, if get 1, traverse the corresponding row of that column #
             since 2's friend is considered indirect friend of 1
           - once finishing visit a 1 cycle, increment circle res

Complexity: Time O(N^2) -- n cycle  Space O(1)

public class Solution {
    public int findCircleNum(int[][] M) {
        boolean visited[] = new boolean[M.length];
        int cycle = 0;
        for(int i = 0; i < M.length; i ++){
            if(!visited[i]){
                cycle++;
                visited[i] = true;
                dfs(M, visited, i);//dfs to mark all ppl in the cycle visited
            }
        }
        return cycle;
    }
    public void dfs(int[][] M, boolean[] visited, int i){
        for(int j = 0; j < M[0].length; j++){//no return case here!!
            if(!visited[j] && M[i][j] == 1){
                visited[j] = true;
                dfs(M, visited, j);
            }
        }
    }
}

Leetcode -- 322. Coin Change(DP)

322. Coin Change(DP)
Medium
https://leetcode.com/problems/coin-change/#/description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

思路：-  use dp bottom up, memoization method
          - we know each solution is formed by at least 1 existing coin, so we check if dp[i-coin] exists.
          - keep filling dp[i] with the min
Complexity: Time O(m*n) -  m is amount, n is len of coins,  Space O(m) - dp array

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];//0,1,2,..,amount
        for(int i = 1; i <= amount; i++){
            int count = -1;
            //key is min count, all solutions must be generated from existing coin
            for(int coin : coins) {
             if(i >= coin && dp[i-coin]!=-1) {//skip non-existing solution
              int cur = dp[i-coin]+1;
              if(count < 0)
                  count  = cur;
              else if(cur < count)
                  count = cur;
             }
         }
         dp[i] = count;
        }
        return dp[amount];
    }