N-Queens II

Q: https://leetcode.com/problems/n-queens-ii/editorial/

Use backtracking to try all chance.

class Solution {
    private int result = 0;
    public int totalNQueens(int n) {
        int[][] board = new int[n][n];
        helper(0, n, board);
        return result;
    }

    public void helper(int col, int n, int[][] board) {
        if (col == n) {
            return;
        }
        for(int row = 0;row < n;row++) {
            if (col == n - 1 && board[row][col] == 0) {
                result++;
                return;
            }
            if (board[row][col] == 0) {
                board[row][col] = col + 1;
                for (int j = 0; j < n; j++) {
                    if (board[j][col] == 0) {
                        board[j][col] = col + 1;
                    }
                }
                for (int j = col; j < n;j++) {
                    if (board[row][j] == 0) {
                        board[row][j] = col + 1;
                    }
                }
                int x = col;
                int y = row;
                while (x < n && y < n) {
                    if(board[y][x] == 0) {
                        board[y][x] = col + 1;
                    };
                    x++;
                    y++;
                }
                x = col;
                y = row;
                while (x >= 0 && y >= 0) {
                    if(board[y][x] == 0) {
                        board[y][x] = col + 1;
                    };
                    x--;
                    y--;
                }
                x = col;
                y = row;
                while (x < n && y >= 0) {
                    if(board[y][x] == 0) {
                        board[y][x] = col + 1;
                    };
                    x++;
                    y--;
                }
                x = col;
                y = row;
                while (x >= 0 && y < 0) {
                    if(board[y][x] == 0) {
                        board[y][x] = col + 1;
                    };
                    x--;
                    y++;
                }
                helper(col+1, n , board);
                for (int r = 0;r < n;r++) {
                    for (int c = 0;c < n;c++) {
                        if (board[r][c] == col+1) {
                            board[r][c] = 0;
                        }
                    }
                }
            }
        }
    }
}

Word Break II

Q: https://leetcode.com/problems/word-break-ii/description/
use backtrack to try all chance of words

class Solution {
    protected Set<String> wordSet;
    private List<String> result = new ArrayList<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        wordSet = new HashSet<>();
        for (String word : wordDict) {
            wordSet.add(word);
        }
        LinkedList<String> words = new LinkedList<>();
        backtrack(s, 0, words);
        return result;
    }

    private void backtrack(String s, int start, LinkedList<String> words) {
        if (start == s.length()) {
            result.add(String.join(" ", words));
        } else {
            for (int i = start;i <= s.length();i++) {
                if (wordSet.contains(s.substring(start, i))) {
                    words.addLast(s.substring(start, i));
                    backtrack(s, i, words);
                    words.removeLast();
                }
            }
        }
    }
}

Subsets

Q: https://leetcode.com/problems/subsets/description/

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        helper(result, new ArrayList<>(), nums, 0);
        return result;
    }
    private void helper(List<List<Integer>> result, List<Integer> subSet, int[] nums, int start) {
        result.add(new ArrayList<>(subSet));
        if (start < nums.length) {
            for (int i = start;i < nums.length;i++) {
                subSet.add(nums[i]);
                helper(result, subSet, nums, i+1);
                subSet.remove(subSet.size() - 1);
            }
        }
    }
}

群組今日討論到的演算法

Binary Lifting

Q: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/

solution:
use array to restore parent and find the k ancstor

class TreeAncestor {
    private int n;
    private int[] parent;
 
    public TreeAncestor(int n, int[] parent) {
        this.n=n;
        this.parent = parent;
    }
    
    public int getKthAncestor(int node, int k) {
        int ancestor = parent[node];
        for(int i=1;i<k&&ancestor!=-1;i++){
            ancestor = parent[ancestor];
        }
        return ancestor;
    }
}

init array: log(n)
find ancestor: log(n)

use binary search logic, save ancestor 2^xth list in array, when I want to find k ancstor, i just need to find, 2^0 x k0 + 2^1 x k1 + ..... = k

import java.util.Arrays;
 
public class TreeAncestor {
    private int[][] dp;
 
    public TreeAncestor(int n, int[] parent) {
 
        dp = new int[n][16];
        for (int[] a : dp) {
            Arrays.fill(a, -1);
        }
        for (int i = 0; i < n; i++) {
            dp[i][0] = parent[i];
        }
        for (int j = 1; j < 16; j++) {
            for (int i = 0; i < n; i++) {
                if (dp[i][j - 1] != -1) {
                    dp[i][j] = dp[dp[i][j - 1]][j - 1];
                }
            }
        }
 
    }
 
    public int getKthAncestor(int node, int k) {
        for (int i = 0; i < 16; i++) {
            if (((1 << i) & k) != 0) {
                node = dp[node][i];
            }
            if (node == -1) {
                break;
            }
        }
        return node;
    }
}