LeetCode 191-200

191. 位1的个数

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

196. 删除重复的电子邮箱

delete p1 from Person p1,Person p2 
where p1.email = p2.email and p1.id > p2.id

197. 上升的温度

datediff函数可以比较日期：
DATEDIFF('2007-12-31','2007-12-30'); # 1
DATEDIFF('2010-12-30','2010-12-31'); # -1

select b.id from Weather a,Weather b 
where b.temperature > a.temperature
and datediff(a.RecordDate,b.RecordDate) = -1

198. 打家劫舍

简单dp题。
时间复杂度On，空间复杂度On。

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], (i - 2 >= 0 ? dp[i - 2] : 0) + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

滚动数组优化，空间复杂度降到O1：

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int p = 0, q = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(q, p + nums[i]);
            p = q;
            q = res;
        }
        return res;
    }
}

199. 二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode front = q.poll();
                if (front.left != null) {
                    q.offer(front.left);
                }
                if (front.right != null) {
                    q.offer(front.right);
                }
                if (i == size - 1) {
                    res.add(front.val);
                }
            }
        }
        return res;
    }
}

200. 岛屿数量

用二维数组标记每个格子是否访问过，对每一个未访问的1进行深度优先搜索，每一次搜索的过程中把所有的1都置为已访问，搜索完之后，岛屿数量加1。
时间复杂度O(mn)，空间复杂度O(mn)。

class Solution {
    boolean[][] isVisit;
    int res = 0;
    int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};

    public void dfs(int i, int j, char[][] grid) {
        for (int k = 0; k < 4; k++) {
            int newI = i + X[k], newJ = j + Y[k];
            if (newI >= 0 && newI < grid.length && newJ >= 0 && newJ < grid[0].length && grid[newI][newJ] == '1' && isVisit[newI][newJ] == false) {
                isVisit[newI][newJ] = true;
                dfs(newI, newJ, grid);
            }
        }
    }

    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        isVisit = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1' && isVisit[i][j] == false) {
                    res++;
                    dfs(i, j, grid);
                }
            }
        }
        return res;
    }
}