LeetCode 191, 173, 210

191. 位1的个数

题目链接

191. 位1的个数

标签

位运算 分治

思路

这里可以使用一个结论：n & (n - 1) 可以将 n 的二进制数的最后一个 1 变成 0。例如：n = 10，那么 n 的二进制数为 1010，n - 1 的二进制数为 1001，n & (n - 1) = 1000。

利用这个特性，只要 n 不等于 0（即每一位都是 0），就一直进行 n &= n - 1 的操作。记录这个操作的次数，操作次数即为 n 的二进制数中 1 的个数。

代码

class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n &= n - 1;
            res++;
        }
        return res;
    }
}

Integer.bitCount()

在 Java 中，Integer.bitCount() 静态方法可以完美地处理这个问题，不过它的源码很抽象。

173. 二叉搜索树迭代器

题目链接

173. 二叉搜索树迭代器

标签

栈 树 设计 二叉搜索树 二叉树 迭代器

思路

本题想要实现一个能够返回二叉树的中序遍历的数据结构，中序遍历并不难，可以使用 递归 和 迭代 两种方式，可以看看这道题 94. 二叉树的中序遍历 来学习这两种方式。

递归

先不考虑时间复杂度和空间复杂度，可以在创建本数据结构时，中序遍历传入的二叉树，将结果放到一个链表中，此时，本数据结构就是一个链表。

• 对于 int next() 方法，就像普通链表的 next()，先获取本节点的值，然后让指针指向下一个节点。
• 对于 boolean hasNext() 方法，就像普通链表的 hasNext()，判断下一个节点是否为 null。

以上是传统的 LinkedList（真正的链表）的实现方式，不过，在此处直接使用 ArrayList（更像能够扩容的数组 Vector）更快一点，不仅是从编写代码的角度看，还是从运行的角度看。

• 对于 int next() 方法，先获取本节点的值，然后让指向元素的索引指向下一个元素。
• 对于 boolean hasNext() 方法，判断 指向当前元素的索引 是否小于 链表的长度。

class BSTIterator {
    private int idx = 0; // 指向中序遍历结果链表的索引
    private List<Integer> list = new ArrayList<>(); // 存放中序遍历的结果

    public BSTIterator(TreeNode root) {
        inorderTraversal(root);
    }
    
    public int next() { // 获取当前节点的值，并指向下一个节点
        return list.get(idx++);
    }
    
    public boolean hasNext() { // 返回当前索引是否小于链表长度
        return idx < list.size();
    }

    private void inorderTraversal(TreeNode curr) { // 中序遍历获取二叉树的所有值
        if (curr == null) {
            return;
        }
        inorderTraversal(curr.left);
        list.add(curr.val);
        inorderTraversal(curr.right);
    }
}

迭代

在递归的方法中，next(), hasNext() 的时间复杂度都是 $O(1)$，不过使用了 $O(n)$ 内存，这里的 n 是二叉树的节点个数，明显比二叉树的高度大，所以需要想一种方法来降低空间复杂度。

复习一下中序遍历的思想：先遍历左子树，再处理本节点（在本题中是获取本节点的值并返回），最后遍历右子树。这点在代码中会体现到。

这里就想到了中序遍历的迭代实现方式——使用栈：

• 使用 TreeNode curr 记录当前遍历到的节点。
• 使用 LinkedList<TreeNode> stack 储存未被处理的节点。
• 在 int next() 方法中，先遍历 curr 的左子树，直到无法再遍历；此时 stack 的栈顶节点就是本次遍历的节点，取出它；最后让 curr 指向本节点的右子节点，准备遍历右子树。
• 在 boolean hasNext() 方法中，对 当前遍历到的节点 和 储存未被处理的节点的栈 做判断，如果 当前遍历的节点是 null，并且 栈为空，则本二叉树被遍历完了。

看看这种方法的复杂度：

• 时间复杂度：
  • next()：使用 n 次该方法后，总的时间复杂度是 $O(n)$，平均时间复杂度为 $O(1)$。
  • hasNext()：该方法的时间复杂度一直为 $O(1)$。
• 空间复杂度：栈最多储存的节点数就是二叉树的层数，即为题目所要求的 $O(h)$，其中，h 是二叉树的高度。

class BSTIterator {
    private TreeNode curr; // 当前节点
    private LinkedList<TreeNode> stack = new LinkedList<>(); // 储存节点的栈

    public BSTIterator(TreeNode root) {
        curr = root;
    }
    
    public int next() { // 获取当前节点的值，并指向下一个节点
    	// 先遍历左子树
        while (curr != null) { // 从 curr 开始，一直向左子节点方向遍历，直到 curr 为 null
            stack.push(curr);
            curr = curr.left;
        }
        
        // 再处理本节点
        curr = stack.pop(); // 取出栈中的最后一个节点，这个节点就是本次遍历的节点
        int res = curr.val; // 获取节点的值
        
        // 最后遍历右子树
        curr = curr.right; // 指向下一个“节点”：处理完左子节点，该处理右子节点了
        return res;
    }
    
    public boolean hasNext() { // 只有 栈为空 且 curr 为 null 的情况才算没有下一个节点
        return !stack.isEmpty() || curr != null;
    }
}

210. 课程表 II

题目链接

210. 课程表 II

标签

深度优先搜索 广度优先搜索 图 拓扑排序

思路

本题是 207. 课程表 的加强版，但没有加强多少，核心还是 图的拓扑排序：入度越小，越靠前。如果对图这个结构不理解，请务必先看 207 题的题解。

拓扑排序的具体步骤为：

1. 在排序之前，先将所有入度为 0 的结点加入 队列。
2. 将队列中的结点（入度为 0）移出队列。
3. 把该结点所指向的结点的入度减一。
4. 当某个结点的入度被减到 0 时，将它加入队列。
5. 重复第二步到第四步，直到队列为空。

如果需要返回拓扑排序的结果，则在将结点移出队列时，将节点的值加入到结果链表中即可。这也是本题的加强之处。

本题和 207 题一样，难点还在于 如何构建图，思想就是 将图看作 一堆节点 连接的 一堆节点，这里就不做赘述了，看 207 题的题解就行了。

代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化存储图的数据结构
        List<List<Integer>> graph = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 统计每个结点的入度，并构建图
        int[] inDegree = new int[numCourses]; // 存储每个结点的入度
        for (int[] pair : prerequisites) {
            int start = pair[1]; // 始点
            int end = pair[0]; // 终点
            List<Integer> toList = graph.get(start); // 获取 始点的 指向结点集合
            toList.add(end); // 将 终点 加入 始点的 指向结点集合 中
            inDegree[end]++; // 让终点的入度加一
        }

        // 寻找入度为 0 的结点，初始化队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) { // 如果索引为 i 的结点的入度为0
                queue.offer(i); // 则将索引 i 放入队列
            }
        }

        // 拓扑排序
        int[] res = new int[numCourses]; // 储存结果的数组
        
        int cnt = 0; // 结点的索引
        while (!queue.isEmpty()) { // 直到队列为空才退出循环
            int start = queue.poll(); // 将结点移出队列，获取始点在graph中的索引

            res[cnt++] = start; // 将入度为 0 的结点放入结果数组中

            List<Integer> toList = graph.get(start); // 获取始点指向的所有终点的索引
            for (int end : toList) { // 将始点指向的所有终点的入度减一
                if (--inDegree[end] == 0) { // 当终点的入度减到0时
                    queue.offer(end); // 将其加入队列
                }
            }
        }

        if (cnt != numCourses) { // 如果 移出队列的结点数 不等于 结点总数
            return new int[0]; // 说明无法学习到全部课程，返回空数组
        }
        
        return res;
    }
}