LeetCode 热题 HOT 100
两数之和
暴力枚举
- 思路：两层循环，找出相加之和为target的两个下标
- 代码
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{};
}
}
哈希表
- 思路
- 用HashMap的Key存储当前num，Value存储下标。我们遍历数组时，只需要判断当前HashMap中，是否已经存在
target - num。如果存在，当前num与target - num之和就是target（我在说什么废话），将二者的Value（因为Value存的是下标）封装成数组作为结果返回即可。 - 暴力枚举的时间复杂度高是因为要定位
target - num的下标在哪儿，而使用哈希表，我们可以存储每个num的下标，直接将O(N)的复杂度降至O(1)，空间换时间。
- 用HashMap的Key存储当前num，Value存储下标。我们遍历数组时，只需要判断当前HashMap中，是否已经存在
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public int[] twoSum(int[] nums, int target) {
// 创建哈希表的时候尽量指定好其容量
HashMap<Integer, Integer> map = new HashMap<>(nums.length - 1);
map.put(nums[0], 0);
for (int i = 1; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{i, map.get(target - nums[i])};
}
map.put(nums[i], i);
}
return new int[]{};
}
}
两数相加
模拟
- 这里说明一下示例3中的进位情况，这个示例3比较误导人，反正我是读了半天题目才读懂（
鬼看得出来你这一堆9是逆序的还是正序的啊）
| 9 | 9 | 9 | 9 | 9 | 9 | 9 | |
|---|---|---|---|---|---|---|---|
| 9 | 9 | 9 | 9 | 0 | 0 | 0 | |
| 8 | 9 | 9 | 9 | 0 | 0 | 0 | 1 |
- 但是换成
987 + 23，就容易理解的多，数字是逆序存储的，同时遍历两条链表，高位补0，再用一个carry变量来存储进位
| 7 | 8 | 9 | |||
|---|---|---|---|---|---|
| 3 | 2 | 0 | |||
| pre↑ | 0 | 1 | 0 | 1 | |
| cur↑ |
思路就是模拟
- 同时遍历两条链表，定义一个pre指向链表头，cur指向pre，pre不动，cur往后走，最终返回pre.next就是结果，
cur.next.val = (carry + l1.val + l2.val) % 10
- 同时遍历两条链表，定义一个pre指向链表头，cur指向pre，pre不动，cur往后走，最终返回pre.next就是结果，
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
//存储进位
int carry = 0;
//只要一条链表没走完就继续
while (l1 != null || l2 != null) {
//高位补0
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
//计算结果
int sum = x + y + carry;
//计算进位
carry = sum / 10;
//对当前结果取模，保留个位数
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
//判断能否继续往下走
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
//两个个位数相加，最高进位只可能为1，看看会不会想987 + 23一样，由3位数变成4位数
if (carry == 1)
cur.next = new ListNode(carry);
return pre.next;
}
}
无重复字符的最长子串
滑动窗口
- 首先我们需要明白一点：如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！
1
2
3
4
5以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb； - 原因也很容易理解，仅看前两个例子，以a开始的最长无重复子串为abc，那么以b开始的最长无重复子串，保底就得是bc，如果bc后面没出现重复字符，那么以b开始的最长无重复子串的终点坐标，必然是大于等于以a开始的最长无重复子串的终点坐标
- 那我们这里就可以使用滑动窗口来解决这个问题了，左指针代表子串的起点，右指针代表子串的终点
- 在每一步的操作中，我们会将左指针向右移动一格，表示我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；在枚举结束后，我们找到的最长的子串的长度即为答案。
- 其中，在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> hashSet = new HashSet<>();
int n = s.length();
int res = 0, right = 0;
//left++代表左指针右移
for (int left = 0; left < n; left++) {
if (left != 0){
//左指针每次右移时，从滑动窗口中移除左指针之前所指元素
hashSet.remove(s.charAt(left - 1));
}
while (right < n && !hashSet.contains(s.charAt(right))){
hashSet.add(s.charAt(right));
right++;
}
res = Math.max(res,right - left);
}
return res;
}
}
寻找两个正序数组的中位数
暴力解法
- 前天刚好学了stream流，暴力做法就直接将两个数组合并到同一个集合中，然后判断集合里的元素是奇数个还是偶数个，然后根据奇偶的情况，来返回结果，奇数直接返回最中间的数，偶数返回中间两个数的平均值。
- 具体做法就是用stream流排序，然后跳过一半的元素，再获取第一个元素
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
ArrayList<Integer> list = new ArrayList<>();
for (int num : nums1)
list.add(num);
for (int num : nums2)
list.add(num);
return list.size() % 2 == 0 ? (list.stream().sorted().skip(list.size() / 2).findFirst().get().doubleValue() +
list.stream().sorted().skip(list.size() / 2 - 1).findFirst().get().doubleValue()) / 2
: list.stream().sorted().skip(list.size() / 2).findFirst().get().doubleValue();
}
}
优化
最长回文子串
评论
