Count Univalue Subtrees

Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

Solution:

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1];
    isUnivalSubtrees(root, count);
    return count[0];
}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {
    if (root == null) {
        return false;
    }
    boolean left = isUnivalSubtrees(root.left, count);
    boolean right = isUnivalSubtrees(root.right, count);
    if (!left && !right) {
        if (root.left == null && root.right == null) {
            count[0]++;
            return true;
        }
    } else if (left && right) {
        if (root.left.val == root.val && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (left && !right) {
        if (root.right == null && root.left.val == root.val) {
            count[0]++;
            return true;
        }
    } else if (!left && right) {
        if (root.left == null && root.right.val == root.val) {
            count[0]++;
            return true;
        }
    }
    return false;
}
FacebookTwitterGoogle+Share

Combination Sum

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Example

given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Note

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

Solution: Subsets 变种题 DFS

O(2^n) time

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (candidates == null) {
        return result;
    }
    Arrays.sort(candidates);
    combinationSumHelper(new ArrayList<Integer>(), 0, candidates, target, result);

    return result;
}

public void combinationSumHelper(ArrayList<Integer> curr, int index, int[] candidates, int target, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(curr));
        return;
    }
    if (index >= candidates.length) {
        return;
    }
    for (int i = index; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            curr.add(candidates[i]);
            combinationSumHelper(curr, i, candidates, target - candidates[i], result);
            curr.remove(curr.size() - 1);
        }
    }
}

Palindrome Partitioning

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

N-Queens I &&II

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

k Sum II

k Sum II

Given n unique integers, number k (1<=k<=n)  and target. Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k=2, target=5, [1,4] and [2,3] are possible solutions

Solutions: DFS

Time Complexity?

    public ArrayList < ArrayList < Integer >> kSumII(int A[], int k, int target) {
    	ArrayList < ArrayList < Integer >> result = new ArrayList < > ();
    	if (A == null) {
    		return result;
    	}
    	kSumIIHelper(new ArrayList < Integer > (), 0, A, k, target, result);
    	return result;
    }

    public void kSumIIHelper(ArrayList < Integer > curr, int index, int A[], int k,
    int target, ArrayList < ArrayList < Integer >> result) {
    	if (curr.size() == k) {
    		if (target == 0) {
    			result.add(new ArrayList < > (curr));
    		}
    		return;
    	}
    	for (int i = index; i < A.length; i++) {
    		curr.add(A[i]);
    		kSumIIHelper(curr, i + 1, A, k, target - A[i], result);
    		curr.remove(curr.size() - 1);
    	}
    }

 

Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

Solution:

1. 找到midNode,这个就是root node

2. 两边建树 分别加到这个root的left, right

注意左右字数可能为null的情况 以及midNode可能为head的情况

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode mid = findMiddle(head);
    TreeNode root = new TreeNode(mid.val);
    ListNode midPost = mid.next;
    if (mid != head) {
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(midPost);

    return root;

}

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    //Remember to set pre.next = null
    if (pre != null) {
        pre.next = null;
    }
    return slow;
}