最近在复盘前面学的东西，然后顺便刷刷题，总之不能闲着…
想读书，想学嵌入式，想一个人出去旅行，想一个人去看电影，想做的事情都好多，可时间真的好少，而且放在当下时间节点的优先级也不算高
两数之和
暴力枚举
- 思路：两层循环，找出相加之和为target的两个下标
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
| class 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)，空间换时间。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class 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
-
代码
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
31
| class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while (l1 != null || l2 != null) {
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;
}
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
22
| import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> hashSet = new HashSet<>();
int n = s.length();
int res = 0, right = 0;
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
12
| class 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();
}
}
|
优化
最长回文子串
