[TOC]
合并两个有序数组
题目描述:
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
1 | 输入: |
解题思路：
跟堆排序中的合并两个有序数组的方法类似。
从尾部进行遍历，比较两个数组的最大值，放入到第一个数组中的末尾。
1 | public void merge(int[] nums1, int m, int[] nums2, int n) { |
移除元素
题目描述:
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
1 | 给定 nums = [3,2,2,3], val = 3, |
解题思路:
使用双指针, i 是慢指针, j 是快指针, 原地置换元素, 最后返回新数组的长度.(由于 nums 数组是传参引用, 所以在方法内部修改后, 外部调用时是修改后的数组内容)
1 | public int removeElement(int[] nums, int val) { |
无重复字符的最长子串
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
1 | 输入: "abcabcbb" |
解答思路：
使用滑动窗口，双指针进行左闭右开[i, j)，每次遍历刷新下标，保证set中不重复，取最长的ans，
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
// 有重复的情况下，去掉最左边
set.remove(s.charAt(i++));
}
}
return ans;
}
进阶版
解答思路：
遇到重复的字符，将滑动窗口的左边直接滑到第一个重复的字符下标。如果 s[j] 在 [i, j) 范围内有与 j’ 相同的字符, 可以直接跳过 [i, j’]范围内的所有元素, 将 i 下标置为 j’ + 1. 使用 HashMap 来存储字符对应的下标.
1 | public static int lengthOfLongestSubstring(String s) { |
串联所有单词的子串
题目描述:
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
1 | 输入： |
解题思路:
使用两个 HashMap 保存出现的字符和次数
遍历给定字符(直到总长度 totalLen减去单个待查找字符的长度wordLen), 在内部循环中, 以 wordLen 作为长度切分给定的字符。如果连续子字符中包含查询字符，继续找；如果不包含查询字符，调成内层循环，从下一个字符开始查询。最后内层循环结束后，判断查找次数是否一致，如果是，保存起始下标到结果集中。
代码: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
32
33
34
35
36
37
38
39public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
int wordSize = words.length;
if (wordSize == 0) {
return result;
}
// words 数组中每个字符的长度都一致, 取第一个
int wordLength = words[0].length();
// 字符数组有可能有重复的, 使用 allWordMap 存放每个 word 出现的次数
HashMap<String, Integer> allWordMap = new HashMap<>();
for (String word : words) {
allWordMap.put(word, allWordMap.getOrDefault(word, 0) + 1);
}
for (int i = 0; i < s.length() - wordSize * wordLength + 1; i++) {
HashMap<String, Integer> hashMap = new HashMap<>();
// 单趟循环中, 成功匹配的次数
int num = 0;
while (num < wordSize) {
// 根据查找字符的长度进行截断
String word = s.substring(i + num * wordLength, i + (num + 1) * wordLength);
if (allWordMap.containsKey(word)) {
hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
// 还有可能超过 words 中原来的数量
if (hashMap.get(word) > allWordMap.get(word)) {
break;
}
} else {
// 如果没有查询到, 跳过这次循环, 查找下一个字符
break;
}
num++;
}
if (num == wordSize) {
result.add(i);
}
}
return result;
}
旋转链表
题目描述：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
1 | 输入: 1->2->3->4->5->NULL, k = 2 |
解题思路
①：遍历链表，获得链表长度和最后一个节点的地址。
②：计算得到需要移动的次数（k % length）
③：移动，以示例作为例子，k = 2，表示右移两次，可以认为是做了以下三步操作：
- 末尾节点指向了头部节点：5 -> 1
- 第三个节点变成了头部节点：head = 3
- 第二个节点变成了末尾节点：2.next -> null
代码：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
32public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) {
return head;
}
int length = 1;
ListNode tempNode = head;
ListNode endNode = null;
while (tempNode.next != null) {
length++;
tempNode = tempNode.next;
}
endNode = tempNode;
// 得到需要移动的次数
int moveNum = k % length;
if (moveNum == 0) {
return head;
}
// 找到待替换的下标
int findIndex = 1, index = length - moveNum + 1;
tempNode = head;
while (tempNode.next != null) {
findIndex++;
if (findIndex == index) {
endNode.next = head;
head = tempNode.next;
tempNode.next = null;
break;
}
tempNode = tempNode.next;
}
return head;
}
最小覆盖子串
题目描述：(原题描述不完整，还有很多隐含条件，在评论区找出来的）
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
1 | 示例： |
隐含条件:1
2
3
4
5
6
7
8①
输入:
s='a'
t='aa'
输出：
''
②
参数的全集是大写字母和小写字母
解题思路，参考这篇文章
1 | 1. 注意到题目的关键："所有字母的最小子串"，也就是说两个串都只能是字母。 |
代码实现(解答答案中耗时最少的回答）：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
32
33
34
35
36
37
38
39
40
41
42
43
44
45public String minWindow(String s, String t) {
int lenS = s.length(), lenT = t.length();
if(lenS < lenT){
return "";
}
int[] tCount = new int[256];
for(int i=0;i<lenT;i++){
tCount[t.charAt(i)] ++;
}
int[] sCount = new int[256];
int left = 0, right = 0;
//保存窗口中等于字符串t的字符的数量，当count等于lenT时，说明找到一个子串
int count = 0;
int minLen = lenS + 1, start = -1;
while(left < lenS){
if(right < lenS && count < lenT){
//right右滑一格
char charRight = s.charAt(right);
sCount[charRight] ++;
if(sCount[charRight] <= tCount[charRight]){
count ++;
}
right ++;
}else{
char charLeft = s.charAt(left);
//更新最小字串的长度和起始索引
if(count == lenT && right - left < minLen){
minLen = right - left;
start = left;
}
//left右滑一格
sCount[charLeft] --;
// 这里只会在 sCount 中，被去掉要查询的字符，才会减少窗口中的总数；
// 如果被去掉是其它无关字符，只需要 left 移动，总量 count 不需要改变
if(sCount[charLeft] < tCount[charLeft]){
count --;
}
left ++;
}
}
if(start != -1){
return s.substring(start, start + minLen);
}
return "";
}
数组中的 k-diff 数对
题目描述：
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
1 | 示例 1: |
解题思路：
使用 map 保存给定的数组，每个数字出现的次数。根据 k 值判断两个数字间的差值是否符合条件。
代码：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
30public int findPairs(int[] nums, int k) {
int ans = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
if (k == 0) {
for (int key : map.keySet()) {
if (map.get(key) > 1) {
ans++;
}
}
} else if (k > 0) {
for (int key : map.keySet()) {
if (map.containsKey(key + k)) {
ans++;
}
}
} else {
for (int key : map.keySet()) {
if (key >= 0) {
continue;
}
if (map.containsKey(key - k)) {
ans++;
}
}
}
return ans;
}
进阶版
将数组排好序之后进行比较：
1 | public int findPairs(int[] nums, int k) { |
字符串的排列
题目描述：
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
1 | 输入: s1 = "ab" s2 = "eidbaooo" |
解题思路：
由于只包含小写字母，可以使用数组保存待匹配的字符出现的次数。然后通过两个指针的移动，匹配到 s1 长度的 s2 子串。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public boolean checkInclusion(String s1, String s2) {
int[] count = new int[26];
char[] pattern = s1.toCharArray();
char[] str = s2.toCharArray();
for (int i = 0; i < pattern.length; i++) {
count[pattern[i] - 'a']++;
}
int left = 0, right = 0;
while (right < str.length){
if (count[str[right] - 'a'] != 0) {
count[str[right] - 'a']--;
right++;
if (right - left == pattern.length) {
return true;
}
} else if (left == right) {
left++;
right++;
} else {
count[str[left] - 'a']++;
left++;
}
}
return false;
}