Add Digits leetcode

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

public class Solution {
    public int addDigits(int num) {
        while (num > 9) {
            int newnum = 0;
            while (num > 0) {
                newnum += num % 10;
                num = num / 10;
            }
            num = newnum;
        }
        return num;
    }
}

public class Solution {
    public int addDigits(int num) {
        return  (num - 1) % 9 + 1;
    }
}

Binary Tree Paths leetcode

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if (root == null) {
            return res;
        }
        String str = root.val +"";
        helper(res, root, str);
        return res;
    }
    public void helper(List<String> res, TreeNode root, String str) {
        if (root.left == null && root.right == null) {
            res.add(str);
            return;
        }
        if (root.left != null) {
            helper(res, root.left, str + "->" + root.left.val);
        }
        if (root.right != null) {
            helper(res, root.right, str +"->" + root.right.val);
        }
    }
}

Paint House leetcode

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

public class Solution {
    public int minCost(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int n = costs.length;
        int[][] dp = new int[n][3];
        for (int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }
        for (int j = 1; j < costs.length; j++) {
            dp[j][0] = costs[j][0] + Math.min(dp[j - 1][1], dp[j - 1][2]);
            dp[j][1] = costs[j][1] + Math.min(dp[j - 1][0], dp[j - 1][2]);
            dp[j][2] = costs[j][2] + Math.min(dp[j - 1][1], dp[j - 1][0]);
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));

    }
}

Verify Preorder Sequence in Binary Search Tree leetcode

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return helper(preorder, 0, preorder.length - 1);
    }
    public boolean helper(int[] preorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int i = left + 1;
        while (i <= right && preorder[i] < preorder[left]) {
            i++;
        }
        int j = i;
        while (j <= right) {
            if (preorder[j] > preorder[left]) {
                j++;
            } else {
                return false;
            }
        }
        
        return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
        
    }
}

Factor Combinations leetcode

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

用dfs方法,

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (n <= 2) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        helper(res, tem,n,2);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> tem, int m,int div) {
        if (m <= 1) {
            if (tem.size() > 1) {
                res.add(new ArrayList<Integer>(tem));
            }
            return;
        }
        for (int i = div; i <= m; i++) {
            if (m % i == 0) {
                tem.add(i);
                helper(res, tem,m / i, i);
                tem.remove(tem.size() - 1);
            }
            
        }
    }
}

Meeting Rooms leetcode

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Comparator com = new Comparator() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        };
        Arrays.sort(intervals, com);
        Interval tem = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            Interval next = intervals[i];
            if (next.start < tem.end) {
                return false;
            }
            tem = next;
        }
        return true;
    }
}

Count Univalue Subtrees leetcode

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.

就是对一个树找子树值和root相同的个数, 对于例子中 三个叶节点5都算, 另外一个是root的右儿子 因为它left child为空 right child值跟本身相等

public class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] res = new int[1];
        if (root == null) {
            return 0;
        }
        helper(root, res);
        return res[0];
    }
    public boolean helper(TreeNode root, int[] res) {
        if (root.left == null && root.right == null) {
            res[0]++;
            return true;
        } else if (root.left == null && root.right != null) {
            if (helper(root.right, res) && root.val == root.right.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        } else if (root.right == null && root.left != null) {
            if (helper(root.left, res) && root.left.val == root.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        } else {
            boolean l = helper(root.left, res);//必须单独列出来因为如果root.left = false 仍要递归root.right以对res进行操作
            boolean r = helper(root.right, res);
            if (l && r && root.val == root.left.val && root.val == root.right.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        }
    }
}