#190 Reverse Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

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

思路，

这题是位运算操作。对输入参数n做右移操作，右移之后和1进行与操作，对返回结果不断左移。

Java代码，

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++, n >>= 1) {
        result = (result << 1) + (n & 1);
    }
    return result;
}

Python代码，

def reverseBits(self, n):
    result = 0
    for i in xrange(32):
        result = (result << 1) + (n & 1)
        n >>= 1
    return result

#191 Number of 1 Bits

Number of 1 Bits

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.

思路，

这题是位运算。n & (n - 1)这个操作可以消去最低位的1，多次执行这个操作可以统计出1的个数。这个题目在很多地方出现过，Beautiful Code其中一章对此做出了比较详尽的解答。从实现难度和效率两方面考虑，下面这个实现应该是比较合适的。

Java代码，

public int hammingWeight(int n) {
    int result = 0;
    for (; n != 0; result++) {
        n &= n - 1;
    }
    return result;
}

Python代码，

def hammingWeight(self, n):
    result = 0
    while n:
        n &= n - 1
        result += 1
    return result

#198 House Robber

Hourse Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

思路，

这是一道DP题，递推公式，dp[i] = max(nums[i] + dp[i-1], nums[i] + dp[i-2])。

Java代码，

public int rob(int[] nums) {
    int[] dp = Arrays.copyOf(nums, nums.length);
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i - 2; j >= 0 && j >= j - 3; j--) {
            dp[i] = Math.max(dp[i], nums[i] + dp[j]);
        }
        result = Math.max(dp[i], result);
    }
    return result;
}

Python代码，

def rob(self, nums):
    p = list(nums)
    for i in xrange(len(nums)):
        for j in xrange(max(0, i - 3), i - 1):
            p[i] = max(p[i], nums[i] + p[j])
    return max(p) if p else 0

#199 Binary Tree Right Side View

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

思路，

这题需要返回二叉树每一层最右边的节点值，

可以用BFS层次遍历二叉树的方法来做，层次遍历下每一层的最后一个元素就是需要返回的结果。

为了编码方便实际用了DFS方法对二叉树进行中序遍历，在遍历的过程中记录当前访问的层数，记录更新当前访问的值。因为中序访问的顺序，右节点会在左节点访问之后才被访问到。

Java代码，

public List<Integer> rightSideView(TreeNode root) {
    Map<Integer, Integer> map = new TreeMap<>();
    dfs(root, 0, map);
    return new ArrayList<>(map.values());
}

private void dfs(TreeNode root, int level, Map<Integer, Integer> map) {
    if (root == null) {
        return;
    }
    dfs(root.left, level + 1, map);
    map.put(level, root.val);
    dfs(root.right, level + 1, map);
}

Python代码，

def rightSideView(self, root):
    record = {}
    self.dfs(root, 0, record)
    return [record[i] for i in xrange(len(record))]

def dfs(self, root, level, record):
    if not root:
        return
    self.dfs(root.left, level + 1, record)
    record[level] = root.val
    self.dfs(root.right, level + 1, record)