Java

Answers To Questions of Java

Java趣题集锦答案。（部分题目为本人答案，有纰漏之处望指正）

1, 答案是1。（&）按位与运算符，参加运算的两个数据，按二进制位进行“与”运算。两位同时为“1”，结果才为“1”，否则为0。0&0=0; 0&1=0; 1&0=0; 1&1=1;
引申，(i & 1) != 0 是判断奇偶的高效方式，另外注意不要使用 i % 2 == 1 来判断是否是奇数，因为i为负奇数时不成立，请使用 i % 2 != 0 来判断是否是奇数。例如，对Java而言，-3 % 2 = -1，当取余操作返回一个非零的结果时，它与左操作数具有相同的正负符号。但是注意，在Python中，-3 % 2 = 1，非负，与Java不一样。(参考：Modulo operation，c和python负数取余)

2, 整数分解质因数。这个题目用递归即可，但很容易被返回值List绕进去，一时想不明白出口。

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> getPrimeFactorization(int n){
    List<Integer> result = new ArrayList<>();
    for(int i = 2; i <= Math.sqrt(n); i++){
        if (n % i == 0){
            result.add(i);
            result.addAll(getPrimeFactorization(n/i));
            return result;
        }
    }
    result.add(n);
    return result;
}

上机测试通过，例如255255可被分解为[3, 5, 7, 11, 13, 17].
又例，使用递归从尾到头输出单链表：

1
2
3
4
5
6
public void printListReversely(Node pListHead) {
    if (PListHead != null) {
        printListReversely(pListHead.next);
        System.out.println(pListHead.data);
    }
}

每访问到一个结点，先递归输出它后面的结点，再输出结点自身。

3, 答案是5。 Java计算b得到86400000，正确，但计算a却得到500654080，错误，所以最后结果500654080/86400000得到5.
这里发生了溢出，尽管a为long，有足够的空间，但是算式实际计算时完全是以 int 运算来执行的，并且只有在运算完成之后，其结果才被提升到long，而此时已经太迟了：计算已经溢出了。从int提升到long是一种拓宽原始类型转换（widening primitive conversion），
它保留了（不正确的）数值。那么为什么计算会是以 int 运算来执行的呢？因为所有乘在一起的因子都是 int 数值。当你将两个 int 数值相乘时，你将得到另一个 int 数值。Java 不具有目标确定类型的特性，这是一种语言特性，其含义是指存储结果的变量的类型会影响到计算所使用的类型。（编者按：我觉得这明显就是Java语言的BUG，Python直接运算本题就没这么多破事。）规避办法：final long a = 24L * 60 * 60 * 1000 * 1000; 运算一开始就提到long即可。
那么为什么会得到错误的500654080？预期结果应该是86400000000，看看它们对应的二进制，很明显，被截断了。

1
2
1010000011101110101110110000000000000
        11101110101110110000000000000

java int类型属于”有符号”的类型，长度是32位，这个符号用来区分是正数还是负数的，对应到二进制上就是二进制的首位。首位是0表示是正数，1表示负数。取值范围是 -2^31 ~ 2^31-1, 对应的二进制也就是：10000000000000000000000000000000 ~ 01111111111111111111111111111111。

4, 答案是0.8999999999999999，

5, 

1
2
3
4
5
6
7
8
9
public Node searchMid(Node head) {
    Node p = this.head;
    Node q = this.head;
    while(p!=null && p.next!=null && p.next.next!=null) {
        p = p.next.next;
        q = q.next;
    } 
    return q;
}

很容易想到先遍历一遍单链表，获取长度length，然后再遍历 length/2，但这需要遍历两遍。如果是双链表，可以分别从首尾同时向中间遍历直到相遇。对于单链表也有只遍历一遍的办法，如上所示。两个指针从头开始，快指针速度是慢指针2倍，当快指针跑到末尾，慢指针正好是中间。（链表长度为奇数，慢指针正好指向中间元素。链表长度偶数，慢指针指向的结点和该结点的下一个结点都是链表的中间结点）

6, (1)定义快慢两个指针，快指针速度是慢指针2倍，同时向前移动，快指针每次移动2步，慢指针每次移动1步。快指针每移动一次都要跟慢指针比较，直到相等，证明带环，否则无环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isLoop(Node head) {
    Node fast = head;
    Node slow = head;
    if (fast == null) {
        return false;
    }
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow){
            return true;
        }
    }
    return !(fast == null || fast.next == null)
}

(2)如果单链表有环，快指针与慢指针相遇时，慢指针肯定没有遍历完，而快指针已经在环内循环了n圈(n>=1)。假设慢指针走了s步，则快指针走了2s步（快指针是慢指针速度2倍），也等于s+在环上多转的n圈，设环长r，则
2s = s + nr，故 s = nr
设整个链表长L，环入口点与相遇点距离为x，起点到环入口点距离为a，则
a + x = nr
=> a + x = (n - 1)r + r = (n - 1)r + L - a
=> a = (n - 1)r + (L - a - x)
(L - a - x) 为相遇点到环入口点的距离，从链表头部到环入口点等于(n - 1)循环内环 + 相遇点到环入口点，从而，在链表头部和相遇点分布设一个指针，每次各走1步，必相遇，该点即环入口点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Node findLoopPort(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null)
        return null;
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}