Pretty Sure

LeetCode - Count Complete Tree Nodes

Question Definition

Given a complete binary tree, count the number of nodes.

Java Solution

public int countNodes(TreeNode root) {
    int leftDepth = leftDepth(root);
    int rightDepth = rightDepth(root);

    if (leftDepth == rightDepth)
        return (1 << leftDepth) - 1;
    else
        return 1+countNodes(root.left) + countNodes(root.right);
}

private int rightDepth(TreeNode root) {
    int dep = 0;
    while (root != null) {
        root = root.right;
        dep++;
    }
    return dep;
}

private int leftDepth(TreeNode root) {
    int dep = 0;
    while (root != null) {
        root = root.left;
        dep++;
    }
    return dep;
}

LeetCode - Cheapest Flights Within K Stops

Question Definition

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

LeetCode - Beautiful Arrangement

Question Definition

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position. Now given N, how many beautiful arrangements can you construct?

LeetCode - Search a 2D Matrix II

Question Definition

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

LeetCode - Find Right Interval

Question Definition

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.