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];
    }

Leetcode -- 5. Longest Palindromic Substring(Strategy)

5. Longest Palindromic Substring
medium
https://leetcode.com/problems/longest-palindromic-substring/#/description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思路： - iterate string, keep finding longer palindrome(curLen)
                  check if str[i-curlen-1, i]: curLen+=2
                  else if str[i-curlen, i]: curLen+=1

Complexity: Time O(n^2) for "aaaa..a" Space O(1)

public String longestPalindrome(String s) {
        //if ...*axxa (a), we check if *axxaa isPalindrome
        // else axxa(a)
        //else palindrome disconnect here
        //keep tracking current len to set begin, cuz if < current len, not longest, skip
        if(s.length() < 2)return s;
        String res = "";
        int curLen = 0;//watch index boundary
        for(int i = 1; i < s.length(); i++){
            if(isPalindrome(s, i-curLen-1, i)){
                res = s.substring(i-curLen-1, i+1);//susbstring
                curLen += 2; 
            }else if(isPalindrome(s, i-curLen, i)){
                res = s.substring(i-curLen,i+1);
                curLen += 1;
            }
        }
        return res;
    }
    public boolean isPalindrome(String s, int begin, int end){
        if(begin < 0)return false;
        while(begin < end){
            if(s.charAt(begin) == s.charAt(end)){
                begin++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }

Leetcode - 328. Odd Even Linked List

 328. Odd Even Linked List

easy

https://leetcode.com/problems/odd-even-linked-list/#/description 

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input. 
The first node is considered odd, the second node even and so on ...

思路： - use double pointer, to maintain 2 list: regular & evenlist
           - pointer: even, odd modify current node. evenHead(2 in this case) always point the start of evenlist
           - travel the list to adjust nodes until reach end of evenlist
Complexity: Time O(N) Space O(1)

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null)
            return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
            odd.next = evenHead;
        }
        return head;
    }
}

思路2： - use double pointer, to maintain 2 list:odd& evenlist
              - Traverse the list till end
              - Then connect odd & even list
Complexity: Time O(N) Space O(1)

  Preview (hint: you can copy and paste the preview into Microsoft Word):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        oddStart = ListNode(0)
        evenStart = ListNode(0)
        oddN = oddStart
        evenN = evenStart
        counter = 1
        while(head != None):
            if(counter % 2 != 0):
                oddN.next = head
                oddN = oddN.next
            else:
                evenN.next = head
                evenN = evenN.next
            head = head.next
            counter += 1
            
        evenN.next = None
        oddN.next = evenStart.next
        
        return oddStart.next

Leetcode -- 227. Basic Calculator II (Stack)

227. Basic Calculator II(Stack)
medium
https://leetcode.com/problems/basic-calculator-ii/

mplement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

思路： - use stack to store number after operation. initialize sign as '+'
           - calculating current val = val * 10 + char
           - when meet next sign, perform operation of last sign on current number(+,-*,/)
           - finally sum up number in stack
eg: 2+33*2
            (here) sign = +, val = 33, then sign = *

Complexity: Time O(N) Space O(N)

public int calculate(String s) {
        if(s == null || s.length() == 0) return 0;
        Stack<Integer> st = new Stack();
        char sign = '+';
        int val = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                val = val*10 + (c -'0');
            }
            if((!Character.isDigit(c) && c != ' ') || i == s.length() - 1){
                if(sign == '+'){
                    st.push(val);
                }
                if(sign == '-'){
                    st.push(-val);
                }
                if(sign == '*'){
                    st.push(st.pop()*val);
                }
                if(sign == '/'){
                    st.push(st.pop()/val);
                }
                sign = c;
                val = 0;
            }
        }
        
        int res = 0;
        for(Integer i: st){
            res += i;
        }
        return res;
    }