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 operationc和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;
}