gcrfelix

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount < 1 || coins == null || coins.length == 0) return 0;
        int[] dp = new int[amount+1];
        int sum = 1;
        Arrays.sort(coins);
        while(sum <= amount) {
            int min = -1;
            for(int coin : coins) {
                if(sum < coin) break;

gcrfelix

/*
time complexity O(m * n ^ 2) where m is the length of the list and the n is the length of the word.

There are several cases to be considered that isPalindrome(s1 + s2):

Case1: If s1 is a blank string, then for any string that is palindrome s2, s1+s2 and s2+s1 are palindrome.

Case 2: If s2 is the reversing string of s1, then s1+s2 and s2+s1 are palindrome.

gcrfelix

/*
Forget about two jugs pouring between each other, which may make you confused.
Let's make it simple: assuming we have one big enough bucket and two cups with volume x and y, respectively. 
Now we want to perform a series of operation -- pouring water in and out only by those two cups.
Somehow, there will be only z water left in this big bucket eventually. Then the equation will be:

z = m * x + n * y

m means using cup-x m times. If m is positive, it means pouring in. Otherwise, it's pouring out.

gcrfelix

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points == null || points.length == 0 || points[0].length == 0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] a, int [] b) {
                if(a[0] == b[0]) return a[1] - b[1];
                else return a[0] - b[0];
            }
        });
        

gcrfelix

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

gcrfelix

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

gcrfelix

Going over all cells, we can count only those that are the "first" cell of the battleship. 
First cell will be defined as the most top-left cell. We can check for first cells by only counting cells that do not have an 'X' 
to the left and do not have an 'X' above them.

public class Solution {
    public int countBattleships(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return 0;
        int count = 0;
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {

gcrfelix

public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num <= 0) return false;
        int left = 0, right = num;
        while(left <= right) {
            long mid = left + (right-left)/2;
            if(mid * mid == num) {
                return true;
            } else if(mid * mid > num) {
                right = (int)mid - 1;

gcrfelix

/*
The main idea is the following:

Traverse the matrix. For each building, use BFS to compute the shortest distance from each '0' to
this building. After we do this for all the buildings, we can get the sum of shortest distance
from every '0' to all reachable buildings. This value is stored in 'distance[][]'. 
For example, if grid[2][2] == 0, distance[2][2] is the sum of shortest distance from this block to all reachable buildings.
Time complexity: O(number of 1)O(number of 0) ~ O(m^2n^2)

We also count how many building each '0' can be reached. It is stored in reach[][]. 

gcrfelix

public class Solution {
    public boolean isReflected(int[][] points) {
		if(points == null || points.length == 0 || points[0].length == 0) {
			return true;
		}
		HashSet<String> set = new HashSet<String>();
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for(int[] p : points) {
			max = Math.max(max, p[0]);