1. 天际线问题

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。

每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

lefti 是第 i 座建筑物左边缘的 x 坐标。

righti 是第 i 座建筑物右边缘的 x 坐标。

heighti 是第 i 座建筑物的高度。

天际线应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标进行排序。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

示例 1：

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

解释：

图 A 显示输入的所有建筑物的位置和高度，

图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。

示例 2：

输入：buildings = [[0,2,3],[2,5,3]]

输出：[[0,3],[5,0]]

提示：

1 <= buildings.length <= 104

0 <= lefti < righti <= 2^31 - 1

1 <= heighti <= 2^31 - 1

buildings 按 lefti 非递减排序

出处：

https://edu.csdn.net/practice/26559306

代码：

import java.util.*;
class getSkyline {
    public static class Solution {
        public List<List<Integer>> getSkyline(int[][] buildings) {
            int n = buildings.length, m = n << 1;
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            int[] boundaries = new int[m];
            for (int i = 0; i < n; i++) {
                boundaries[i << 1] = buildings[i][0];
                boundaries[(i << 1) + 1] = buildings[i][1];
            }
            Arrays.sort(boundaries);
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
            int building = 0;
            for (int i = 0; i < m; i++) {
                if (i > 0 && boundaries[i - 1] == boundaries[i])
                    continue;
                while (building < n && buildings[building][0] <= boundaries[i])
                    pq.offer(new int[] { buildings[building][1], buildings[building++][2] });
                while (!pq.isEmpty() && pq.peek()[0] <= boundaries[i])
                    pq.poll();
                int height = (pq.isEmpty()) ? 0 : pq.peek()[1];
                if (ans.size() == 0 || height != ans.get(ans.size() - 1).get(1))
                    ans.add(Arrays.asList(boundaries[i], height));
            }
            return ans;
        }
    }
    public static String ListToString(List<Integer> list) {
        String res = "[";
        for (int i = 0; i < list.size(); ++i) {
            res += String.valueOf(list.get(i));
            if (i+1 < list.size()) {
                res += ",";
            }
        }
        return res + "]";
    }
    public static void printList2D(List<List<Integer>> list) {
        System.out.print("[");
        for (int i = 0; i < list.size(); ++i) {
            System.out.print(ListToString(list.get(i)));
            if (i+1 < list.size()) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }
        public static void main(String[] args) {
        Solution s = new Solution();
        int[][] buildings = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        printList2D(s.getSkyline(buildings));
        int[][] buildings2 = {{0,2,3},{2,5,3}};
        printList2D(s.getSkyline(buildings2));
    }
}

输出：

[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

[[0,3],[5,0]]

2. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1

输出：true

解释：20 = 1

示例 2：

输入：n = 16

输出：true

解释：24 = 16

示例 3：

输入：n = 3

输出：false

示例 4：

输入：n = 4

输出：true

示例 5：

输入：n = 5

输出：false

提示：

-2^31 <= n <= 2^31 - 1

进阶：你能够不使用循环/递归解决此问题吗？

出处：

https://edu.csdn.net/practice/26559307

代码：

import java.util.*;
class isPowerOfTwo {
    public static class Solution {
        public boolean isPowerOfTwo(int n) {
            if (n <= 0)
                return false;
            return countBit(n) == 1;
        }
        public int countBit(int num) {
            int count = 0;
            while (num != 0) {
                count += (num & 1);
                num >>= 1;
            }
            return count;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isPowerOfTwo(1));
        System.out.println(s.isPowerOfTwo(16));
        System.out.println(s.isPowerOfTwo(3));
        System.out.println(s.isPowerOfTwo(4));
        System.out.println(s.isPowerOfTwo(5));
    }
}

输出：

true

false

true

false

进阶：不使用循环/递归

原理：任意2的n次幂，其二进制表达式只有最高位是1，必有 (n & (n - 1)) == 0

bin(16) = 0b10000

bin(15) = 0b01111

==> 16&15 == 0

import java.util.*;
class isPowerOfTwo {
    public static class Solution {
        public boolean isPowerOfTwo(int n) {
            if (n <= 0) {
                return false;
            }
            return (n & (n - 1)) == 0;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isPowerOfTwo(1));
        System.out.println(s.isPowerOfTwo(16));
        System.out.println(s.isPowerOfTwo(3));
        System.out.println(s.isPowerOfTwo(4));
        System.out.println(s.isPowerOfTwo(5));
    }
}

3. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

/ \

2 2

/ \ / \

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

/ \

2 2

\ \

3 3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

出处：

https://edu.csdn.net/practice/26559308

代码1：递归

import java.util.*;
public class isSymmetric {
    public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public static class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        public boolean isSymmetric(TreeNode n1, TreeNode n2) {
            if (n1 == null || n2 == null) {
                return n1 == n2;
            }
            if (n1.val != n2.val) {
                return false;
            }
            return isSymmetric(n1.left, n2.right) && isSymmetric(n1.right, n2.left);
        }
    }
    public static TreeNode createBinaryTree(Vector<Integer> vec) {
        if (vec == null || vec.size() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(vec.get(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = queue.poll();
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.left = new TreeNode(vec.get(i));
                    queue.offer(node.left);
                }
                i++;
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.right = new TreeNode(vec.get(i));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        Integer[] nums = {1,2,2,3,4,4,3};
        Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums));
        TreeNode root = createBinaryTree(vec);
        System.out.println(s.isSymmetric(root));
        Integer[] nums2 = {1,2,2,NULL,3,NULL,3};
        vec = new Vector<Integer>(Arrays.asList(nums2));
        root = createBinaryTree(vec);
        System.out.println(s.isSymmetric(root));
    }
}

代码2： 迭代

import java.util.*;
public class isSymmetric {
    public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public static class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root.left);
            queue.offer(root.right);
            while (!queue.isEmpty()) {
                TreeNode n1 = queue.poll();
                TreeNode n2 = queue.poll();
                if (n1 == null && n2 == null) {
                    continue;
                }
                if (n1 == null || n2 == null || n1.val != n2.val) {
                    return false;
                }
                queue.offer(n1.left);
                queue.offer(n2.right);
                queue.offer(n1.right);
                queue.offer(n2.left);
            }
            return true;
        }
    }
    public static TreeNode createBinaryTree(Vector<Integer> vec) {
        if (vec == null || vec.size() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(vec.get(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = queue.poll();
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.left = new TreeNode(vec.get(i));
                    queue.offer(node.left);
                }
                i++;
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.right = new TreeNode(vec.get(i));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        Integer[] nums = {1,2,2,3,4,4,3};
        Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums));
        TreeNode root = createBinaryTree(vec);
        System.out.println(s.isSymmetric(root));
        Integer[] nums2 = {1,2,2,NULL,3,NULL,3};
        vec = new Vector<Integer>(Arrays.asList(nums2));
        root = createBinaryTree(vec);
        System.out.println(s.isSymmetric(root));
    }
}