18. Subsets II

public class Solution {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
       
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            if (i != start && nums[i]==nums[i-1]) {
                continue;
            }
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
            // [1,2] -> [1]  回溯
            cur.remove(cur.size() - 1);
        }
    }
   
   
   
}

17. Subsets

Given a set of distinct integers, return all possible subsets.

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets

根据第一条
ex:
S = [1, 2, 3]

1:
1
12
13
123

2:
2
23

3:
3

想法：
List<List<Integer>> res  = new List<List<Integer>()
for(int i = 0; i<S.size; i++) {
     List<Integer> prev = new ArrayList<>();
     prev.add(i);
     helper(
}

helper(List<Integer> prev, i, n, res) {
    if(i == n) {
        return;
    } else {
       
       for(int i = 0; i<S.size; i++) {
          List<Integer> cur = new ArrayList<>(prev);
          cur.add(i);
          res.add(cur);
          helper(cur, i+1, n, res)
       }
    }
}


Code（WA）

input：[1,2]

output：
[[],[1],[1,2],[2],[2,2]]


 

  public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        rst.add(prev);
       
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> prev, int i, int[] nums, List<List<Integer>> rst) {
        if(i == nums.length) {
            return;
        } else {
            for(int k = i; k < nums.length; k++) {
                List<Integer> cur = new LinkedList<>(prev);
                cur.add(nums[k]);
                rst.add(cur);
                helper(cur, i+1, nums, rst);
               
            }
        }
造成这个问题的原因是没有回溯
当找到【1，2】开头的结果后 没有remove 2
导致要找【1，3】开头的结果就会变成找【1，2，3】开头的结果   


Answer
public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
           

// [1,2] -> [1]  回溯

            cur.remove(cur.size() - 1);
        }
    }

33. N-Queens

N-Queues
国际象棋的皇后是可以向8个方向走的
所以在同一列（1）， 同一行（2），同一条斜线（3）上是不能出现两个皇后的
因为我们在同一列（1）不会出现两个皇后
所以我们可以通过一个一位数组纪录每一列的Q在哪一行
下标（index）为第几列，值为第几行
这也是一个DFS在我们放下第一个Q后
我们需要以第一个Q的位置为依据判断下一个Q的摆放位置

Is it a Valid Queen
判断依据 即另外两个条件：

1. 不在 同一行（2）（新的Q的值（数）不会与之前数组内的值（列数）相同）
2. 不在 同一条斜线（3）（新的Q的值与列数差（斜线）不会与之前数组内的相同）

public class Solution {
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    public List<List<String>> solveNQueens(int n) {
        // write your code here
        List<List<String>> res = new ArrayList<>();
       
        helper(n, 0, new int[n], res);
        return res;
    }
   
    private void helper(int n, int row, int[] columnForRow, List<List<String>> res) 
    { 
        if(row == n) 
        { 
            List<String> item = new ArrayList<>();; 
            for(int i=0;i<n;i++) 
            { 
                StringBuilder strRow = new StringBuilder(); 
                for(int j=0;j<n;j++) 
                { 
                    if(columnForRow[i]==j) 
                        strRow.append('Q'); 
                    else 
                        strRow.append('.'); 
                } 
                item.add(strRow.toString()); 
            } 
            res.add(item); 
            return; 
        } 
        for(int i=0;i<n;i++) 
        { 
            columnForRow[row] = i; 
            if(check(row,columnForRow)) 
            { 
                helper(n,row+1,columnForRow,res); 
            } 
        } 
    } 
    private boolean check(int row, int[] columnForRow) 
    { 
        for(int i=0;i<row;i++) 
        { 
            if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==row-i) 
                return false; 
        } 
        return true; 
    } 
}

120. Word Ladder （Self， WA）

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Thinking:
分为

1. 记录transformation的过程（记录如何变化的）
1. helper function 用来判断是否还剩一步就能变化成功，即与目标单词之差一个letter 
2. dfs
3. 如果在一次dfs中已经变化过那就可以从set去除了
2. 比较得到最短的tranformation
1. 设立rst为Integer.MAX_VALUE;

Leetcode discussion

1. It’s much faster than one-end search indeed as explained in wiki.
2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.

 unsolved:
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Set<String> reached = new HashSet<String>();
        reached.add(beginWord);
        wordDict.add(endWord);
        int distance = 1;
        while (!reached.contains(endWord)) {
            Set<String> toAdd = new HashSet<String>();
            for (String each : reached) {
                for (int i = 0; i < each.length(); i++) {
                    char[] chars = each.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String word = new String(chars);
                        if (wordDict.contains(word)) {
                            toAdd.add(word);
                            wordDict.remove(word);
                        }
                    }
                }
            }
            distance++;
            if (toAdd.size() == 0) return 0;
            reached = toAdd;
        }
        return distance;

127. Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A -> B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

思考：
BFS (??)
使用queue

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        if (graph == null || graph.size() == 0) {
            return graph;
        }
       
        ArrayList<DirectedGraphNode> rst = new ArrayList<>();
       
       
        // keep track of all neighbors in HashMap
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 找到所有被directed的点并记录被directed多少次
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                int key = neighbor.label;
                if (map.containsKey(key)) {
                    map.put(key, map.get(key) + 1);
                } else {
                    map.put(key, 1);
                }
            }
        }
       
        // find all the root which never be directed and cannot be found in map
        Queue<DirectedGraphNode> queue = new LinkedList<> ();
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node.label)) {
                queue.offer(node);
                rst.add(node);
            }
        }
       
       
        // BFS: according the node in queue to proccess
        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode neighbor : node.neighbors) {
                int key = neighbor.label;
                map.put(key, map.get(key)-1);
                if(map.get(key) == 0) {
                    queue.offer(neighbor);
                    rst.add(neighbor);
                }
            }
        }
        return rst;
       
    }
   
}

Combination Question and DFS

Most of Combination questions connect to DFS, following structure is common:

private void dfs(int[] nums, int pos, int gap, List<Integer> list, List<List<Integer>> result) {
       
        // 一个合法的解
        if (gap == 0) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
       
        for (int i = pos; i < nums.length; i++) { //扩展状态           
            // 剪枝
            if (gap < nums[i]) {
                return;
            }
           
            list.add(nums[i]); // 扩展动作
            dfs(nums, i, gap-candidates[i], list, result);
            // backtrack 撤销动作
            list.remove(list.size() - 1);
           
        }
    }

Wikipedia上的讲解是：“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. 
One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible 
along each branch before backtracking.”

深度优先主要思想是：

1. 设置几个方法，有顺序
1. 方法： 1，2，3.....
2. 按照方法1 去执行直到方法一执行不能，尝试方法2
3. 若所有方法都不发执行，退回到上一个步骤执行方法2（因为方法1 已经执行过了）（backtracking)
4. 在执行方法的每一步中要检测是否到达目的地或目标

// recursive  

void dfs()  
{  
    // 判断是否到达终点
    if() {
        return;
    }

    // 尝试每一个可走方向（右下左上） 
    for(i=0; i<n; i++){ 
        // 判断是否可走,可走调用递归尝试下一步，不可走则尝试该点的其他方向
        if () {
            // 继续下一步  
            dfs();  
        }
    }  
}  

non-recursive
procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
            v ← S.pop()
            if v is not labeled as discovered:
                label v as discovered
                for all edges from v to w in G.adjacentEdges(v) do
                    S.push(w)

7. Binary Tree Serialization

Thinking:

1. binary Tree 和 Stringbuilder 的联合题
2. 对Stringbuilder 和StringTokenizer的使用方法的考验

public String serialize(TreeNode root) {
        // write your code here
        StringBuilder result = new StringBuilder();
        if (root == null) return result.toString();
       
        serialHelper(root, result);
        return result.substring(0, result.length() - 1);
    }
   
    private void serialHelper(TreeNode root, StringBuilder result) {
        if (root == null) {
            result.append("#,");
        } else {
            result.append(root.val).append(",");
            serialHelper(root.left, result);
            serialHelper(root.right, result);
        }
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        if (data == null || data.length() == 0) return null;

        StringTokenizer st = new StringTokenizer(data, ",");
        return deseriaHelper(st);
    }
   
    private TreeNode deseriaHelper(StringTokenizer st) {
        if (!st.hasMoreTokens()) return null;

        String val = st.nextToken();
        if (val.equals("#")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deseriaHelper(st);
        root.right = deseriaHelper(st);

        return root;
    }