Daily Archives: June 3, 2015

Palindrome Partitioning

Posted on by
Reply

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    partitionHelper(s, new ArrayList<String>(), result);
    return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
    if (s.length() == 0) {
        result.add(new ArrayList<String>(curr));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        String currString = s.substring(0, i + 1);
        if (isPalindrome(currString)) {
            curr.add(currString);
            partitionHelper(s.substring(i + 1), curr, result);
            curr.remove(curr.size() - 1); //important
        }
    }
}

public boolean isPalindrome(String s) {
    int start = 0;
    int end = s.length() - 1;
    while (start <= end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}
FacebookTwitterGoogle+Share

N-Queens I &&II

Posted on by
Reply

N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[“.Q..”, // Solution 1

“…Q”,

“Q…”,

“..Q.”],

[“..Q.”, // Solution 2

“Q…”,

“…Q”,

“.Q..”]

]

Solution1: Recursion DFS, Permutation模板，判断条件换一下

ArrayList<ArrayList<String>> solveNQueens(int n) {
    ArrayList<ArrayList<String>> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result;
}

//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
    if (row == chessBoard.length) {
        result.add(toStringList(chessBoard));
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

public ArrayList<String> toStringList(int[][] chessBoard) {
    ArrayList<String> result = new ArrayList<>();
    for (int i = 0; i < chessBoard.length; i++) {
        StringBuilder row = new StringBuilder();
        for (int j = 0; j < chessBoard[i].length; j++) {
            if (chessBoard[i][j] == 0) {
                row.append('.');
            } else {
                row.append('Q');
            }
        }
        result.add(row.toString());
    }
    return result;
}

Solution 2. Non-Recursive

 

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

这里要注意的是 因为java的int和Integer类型都是传值不传reference，所以不能直接把int传进递归方法里，还是需要用一个链表, 或者用一个static variable

Solution 1. Recursive

public int totalNQueens(int n) {
    ArrayList<Integer> result = new ArrayList<>();
    if (n <= 0) {
        return 0;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result.size();
}

public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
    if (row == chessBoard.length) {
        result.add(result.size() + 1);
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

Solution 2. Non-Recursive

Clone Graph

Posted on by
Reply

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ’s undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
O(n) time complexity, O(n) space

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
        return null;
    }
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    queue.offer(node);
    UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
    map.put(node, copyRoot);
    while (!queue.isEmpty()) {
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, currCopy);
                }
            }
        }
    }
    for (UndirectedGraphNode originalNode : map.keySet()) {
        for (UndirectedGraphNode neighbor : originalNode.neighbors) {
            map.get(originalNode).neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}