算法题

14亿个数乱序，从中抽取一个数字，如何知道抽取的是哪个数字？

将抽取一个数字后的数组中的每个元素依次进行异或运算，结果再与1到14亿依次进行异或运算，得到的结果就是抽取的数字。
例：1~10，抽取9

System.out.println(1^2^3^4^5^6^7^8^10^1^2^3^4^5^6^7^8^9^10); 9

10亿个数取TopN

维护一个长度为N的数组arr；
先读取N个数，放入数组中，对其进行快排；
之后每次读取一个数，如果该数字小于等于arr[N-1]，则丢弃；
如果该数字大于arr[N-1]，则进行二分查找，数组移动，并插入。

上台阶问题

一共有n级台阶，有两种走法：一次上一层，一次上两层，问上到第n级台阶有几种上法。
假设上到第n级台阶有W(n)中上法。
W(n) = 上到第n-1级台阶，然后一次走一层 + 上到第n-2级台阶，然后一次走两层
W(n) = W(n-1) + W(n-2)

W(1) = 1
W(2) = 2
W(3) = W(1)+W(2)
W(4) = …
…
W(n) = W(n-1) + W(n-2)
获得一个长度为n+1的数组int[] W，W(n)表示上n级台阶有多少种上法。

合并两个有序链表

类似于归并排序的并过程
其中为新链表的头结点设计一个rootPre节点，可以避免判断if(root == null)。

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(5);
        node1.next.next = new Node(23);
        Node node2 = new Node(3);
        node2.next = new Node(4);
        node2.next.next = new Node(5);
        Node root = merge(node1, node2);
        while (root != null) {
            System.out.print(root.value + " ");
            root = root.next;
        }
    }
    private static Node merge(Node node1, Node node2) {
        if (node1 == null) return node2;
        if (node2 == null) return node1;
        Node rootPre = new Node(Integer.MIN_VALUE);
        Node currentNode = rootPre;
        while (node1 != null && node2 != null) {
            if (node1.value <= node2.value) {
                currentNode.next = node1;
                currentNode = node1;
                node1 = node1.next;
            } else {
                currentNode.next = node2;
                currentNode = node2;
                node2 = node2.next;
            }
        }
        if (node1 == null) currentNode.next = node2;
        else currentNode.next = node1;
        return rootPre.next;
    }
}
class Node {
    int value;
    Node next;
    public Node(int value) {
        this.value = value;
    }
}