The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police.

Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. Solution: public class Solution { public int maxSubArray(int[] nums) { int pre = -1; int max = Integer.MIN_VALUE; for(int i=0; i<nums.length; i++){ if(pre>0){ pre += nums[i]; } else { pre = nums[i]; } max = Math.max(max, pre);

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. Solution: public class Solution { public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE; int cur = 1; for(int i=0; i<nums.length; i++){ cur *= nums[i]; max = Math.max(max, cur); if(cur==0) cur = 1; } cur = 1;

Count the number of prime numbers less than a non-negative number, n. Solution: public class Solution { public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for(int i=2; i<n; i++) isPrime[i]=true; for(int i=2; i*i<n; i++){ if(!isPrime[i]) continue; for(int j=i*i; j<n; j+=i){ isPrime[j]=false; } } int num = 0; for(int i=2; i<n; i++) if(isPrime[i]) num++; return num; } }

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9. public class Solution { public int numSquares(int n) { int[] ans = new int[n+1]; for(int i=1; i<=n; i++)

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels. Format The graph contains n nodes which are labeled from 0 to n - 1.

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]] There are a total of 2 courses to take.

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them.