之前开过一个坑 Leetcode 刷题笔记,总结了许多 Leetcode 上的好题。然而,这些题还是比较乱的,不利于我们备考和面试。因此,我选择新开一个坑,专门记录 Leetcode 上的各种模板题,从而帮助我们更好地复习。
1. 链表题
1.1 第160题.相交链表
参考题解:官方题解
题目:
标签:
- 哈希表。
- 双指针。
思路:
- 这道题的挑战在于,如何将时间复杂度降到 O(n),空间复杂度降到 O(1)。
- 看到时间复杂度 O(n) 基本就明白了,方法被限制在了:哈希表、双指针、位运算。这个敏感性还是需要具备的。
- 用哈希表求解可以实现 O(n) 的空间复杂度。
- 用双指针求解才是最优解。而这个思路还有一些特别,需要记住:指针 A 扫描到 A 串末尾后,需要跳到 B 串。B 到末尾也要跳到 A 串。比较指针指向的节点是否相等,不能光判断 val,还需要判断 next,因此可以直接判断指向的节点是否相等(==)。
题解:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode val1 = headA, val2 = headB;
if (val1 == null || val2 == null) {
return null;
}
while (true) {
if (val1 == null && val2 == null) {
return null;
}
if (val1 == null) {
val1 = headB;
}
if (val2 == null) {
val2 = headA;
}
if (val1 == val2) {
return val1;
}
val1 = val1.next;
val2 = val2.next;
}
}
}
2. 其他题
2.1 第401题. 二进制手表
参考题解:官方题解
题目:
标签:
- 意想不到。
- 位运算。
思路:
- 这道题是一道简单题,只需要枚举就可以解决。
- 然而,必须要知道这是一道枚举题。否则可能会想歪。
- 枚举所有数字,用 bitCount 计算对应的比特数,保留符合要求的组合,并生成符合格式要求的题解。
题解:
class Solution {
public List<String> readBinaryWatch(int turnedOn) {
List<String> ans = new ArrayList<String>();
for (int h = 0; h < 12; ++h) {
for (int m = 0; m < 60; ++m) {
if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
ans.add(h + ":" + (m < 10 ? "0" : "") + m);
}
}
}
return ans;
}
}
Comments | NOTHING