liumingzhang

/* bitwise and: do and in all numbers between [m,n]
我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110
return 11000
直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果

liumingzhang

 /*
 层次遍历法。遍历到每层最后一个节点时，把其放到结果集中。
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

liumingzhang

/*
一个只包含字符0和1的二维数组，找出里面不相邻的只包含1的块的个数。

思路：DFS、BFS。只要遍历一遍，碰到一个1，就把它周围所有相连的1都标记为非1，这样整个遍历过程中碰到的1的个数就是所求解。
*/
public class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int res = 0;

liumingzhang

/*
这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。那么我们对于这类求极值的问题首先考虑动态规划Dynamic Programming来解，我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和，经过分析，我们可以得到递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 由此看出我们需要初始化dp[0]和dp[1]，其中dp[0]即为num[0]，dp[1]此时应该为max(num[0], num[1])

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int[] dp = new int[nums.length];
        if(nums.length <= 1){
            return nums[0];

liumingzhang

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++){
            res = (res << 1) | (n & 1);
            n = n >> 1;
        }
        return res;
    }

liumingzhang

/*
首先先把整个array进行reverse，然后分段reverse
*/
public class Solution {
    public void rotate(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 0)
            return;
        int len = nums.length;
        k = k % len;
        reverse(nums, 0, len - 1);

liumingzhang

/*
首先考虑将ACGT进行二进制编码

A -> 00

C -> 01

G -> 10

T -> 11

liumingzhang

/*http://www.cnblogs.com/yuzhangcmu/p/4235285.html
贪心思路：对于两个备选数字a和b，如果str(a) + str(b) > str(b) + str(a)，则a在b之前，否则b在a之前

按照此原则对原数组从大到小排序即可

时间复杂度O（nlogn）

易错样例：

Input:     [0,0]

liumingzhang

/*
乍一看，这个问题和"Maximum/Minimum Path Sum"问题很相似。然而，具有全局最大HP（生命值）收益的路径并不一定可以保证最小的初始HP，因为题目中具有限制条件：HP不能≤0。例如，考虑下面的两条路径：0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。这两条路径的净HP收益分别是-300 + 310 = 10 与 -1 + 2 = 1。第一条路径的净收益更高，但是它所需的初始HP至少是301，才能抵消第二个房间的-300HP损失，而第二条路径只需要初始HP为2就可以了。

幸运的是，这个问题可以通过“table-filling”（表格填充）动态规划算法解决，与其他"grid walking"（格子行走）问题类似：

首先，我们应该维护一个2维数组D，与地牢数组的大小相同，其中D[i][j]代表可以保证骑士在进入房间(i,j)之前，探索其余地牢时能够存活下来的最小HP。显然D[0][0]就是我们随后需要的最终答案。因此，对于这个问题，我们需要从右下角到左上角填充表格。

然后，我们来计算离开房间(i,j)时的最小HP。从这一点出发只有两条路径可选：(i + 1, j)和(i, j + 1)。当然我们会选择拥有更小D值的那个房间，换言之，骑士完成剩下的旅途所需的较小HP。因此我们有：

  min_HP_on_exit = min(D[i+1][j], D[i][j+1])

liumingzhang

/*
维护一个栈，从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。

调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。
*/
public class BSTIterator {
    private Stack<TreeNode> stack;
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();