Reverse Bits leetcode

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++, n >>= 1) {
            res = res << 1 | (n & 1);//给res的最后一位置为(n最右一位)
        }
        return res;
    }
}

//方法2
public int reverseBits(int n) {
        int res = 0;
        int[] tem = new int[32];
        for (int i = 0; i < 32; i++) {
            tem[i] = n >> i & 1;
        }
        for (int i = 31; i >= 0; i--) {
            res += tem[i] << (31 - i);
        }
        return res;
    }

Power of Two leetcode

Given an integer, write a function to determine if it is a power of two.

public class Solution {
    public boolean isPowerOfTwo(int n) {
         if (n <= 0) {
             return false;
         }
         return (n & (n - 1)) == 0;
        
    }
}

Number of 1 Bits leetcode

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

解法1: 把每一位都 & 1, 计算所有1的个数
解法2: 因为n & (n - 1)就可以消除掉最右边的一个1, 比如110，减去1得101，相与得100，消去了最右边的1。这样一直消除到没有, 可以计算出1得个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

3Sum Smaller leetcode

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

用3Sum的方法 a=num[i] + num[l] + num[r]
当a < target时候 left++, 但是注意此时对于num[i] + num[l] + num[l + 1 ---> r] 都满足<target
所以这个时候指针右移 count+ right - left;

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        } 
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    count+= right - left;
                    left++;
                }
                if (nums[i] + nums[left] + nums[right] >= target) {
                    right--;
                }
            }
        }
        return count;
    }
}

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