双指针问题:
一道快慢指针类问题:
1
2
3
4
5
6
7
8
9
10
| public int removeElement(int[] nums, int val) {
int slowindex = 0, fastindex = 0;
for (; fastindex < nums.length; fastindex++) {
if (nums[fastindex] != val) {
nums[slowindex] = nums[fastindex];
slowindex++;
}
}
return slowindex;
}
JAVA
|
一道简单的双指针问题，判断子序列，只贴代码，不给解释:
1
2
3
4
5
6
7
8
9
10
11
12
| public static boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else if (j < t.length()) j++;
}
if (i == s.length()) return true;
return false;
}
JAVA
|
方法1: 先遍历数组，再二分查找寻找另一个数 O(nlogn):
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
| public static int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
int num = 0;
for (int i = 0; i < numbers.length; i++) {
num = target - numbers[i];
int index = find(numbers, num, i + 1, numbers.length - 1);
if (index != -1) {
result[0] = i + 1;
result[1] = index + 1;
break;
}
}
return result;
}
private static int find(int[] numbers, int num, int begin, int end) {
int l = begin, r = end;
int m = (l + r) / 2;
while (l <= r) {
m = (l + r) / 2;
if (numbers[m] == num) return m;
else if (numbers[m] > num) {
r = m - 1;
}else {
l = m + 1;
}
}
return -1;
}
JAVA
|
双指针法(头尾夹) O(n):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
int sum = 0;
int[] ints = new int[2];
while (i < j) {
sum = numbers[i] + numbers[j];
if (sum == target) {
ints[0] = i + 1;
ints[1] = j + 1;
break;
} else if (sum < target) {
i++;
continue;
} else {
j--;
continue;
}
}
return ints;
}
JAVA
|
简单的双指针问题:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int maxArea = 0;
int length = 0, width = 0;
while (i < j) {
length = j - i;
width = Math.min(height[i], height[j]);
maxArea = Math.max(maxArea, length * width);
while (i < j && height[j] <= width) {
j--;
}
while (i < j && height[i] <= width) {
i++;
}
}
return maxArea;
}
JAVA
|
排序＋双指针，核心问题还是定一求二
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
| public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int i = 1, j = nums.length - 1;
int sum = 0, sum1 = 0;
int index = 0;
for (int k = 0; k < nums.length - 2; ) {
i = k + 1;
j = nums.length - 1;
while (i < j) {
sum = -nums[k];
sum1 = nums[i] + nums[j];
if (sum1 == sum) {
list.add(List.of(nums[k], nums[i], nums[j]));
while (i < j && nums[i] == nums[++i]) ;
while (i < j && nums[j] == nums[--j]) ;
continue;
} else if (sum1 < sum) {
while (i < j && nums[i] == nums[++i]) ;
continue;
} else {
while (i < j && nums[j] == nums[--j]) ;
continue;
}
}
while (k < nums.length - 1 && nums[k] == nums[++k]) ;
}
return list;
}
JAVA
|
滑动窗口问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static int minSubArrayLen(int target, int[] nums) {
int i = 0, j = 0;
int len = Integer.MAX_VALUE;
int sum = nums[0];
while (i <= j && j < nums.length) {
if (sum >= target) {
len = Math.min(j - i + 1, len);
sum -= nums[i];
sum = sum;
i++;
continue;
} else if (sum < target) {
j++;
if (j < nums.length) sum += nums[j];
continue;
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
JAVA
|
滑动窗口:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static int lengthOfLongestSubstring(String s) {
int i = 0, j = 0;
int len = 0;
String s1 = "";
HashMap<Character, Integer> hashMap = new HashMap<>();
while (i <= j && j < s.length()) {
if (!s1.contains(Character.toString(s.charAt(j)))) {
s1 = s.substring(i, j + 1);
len = Math.max(len, j - i + 1);
} else {
i = hashMap.get(s.charAt(j)) + 1;
s1 = s.substring(i, j + 1);
}
hashMap.put(s.charAt(j), j);
j++;
}
return len;
}
JAVA
|
非常痛苦的一道双指针问题
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
45
46
47
48
49
50
51
52
53
| public static String minWindow(String s, String t) {
HashMap<Character, Integer> hp = new HashMap<>();
HashMap<Character, Integer> hp1 = new HashMap<>();
int i = 0, j = 0;
int min = s.length(), max = 0;
int len = Integer.MAX_VALUE, curlen = 0;
Character ch = null;
for (int k = 0; k < t.length(); k++) {
if (!hp.containsKey(t.charAt(k))) {
hp.put(t.charAt(k), 1);
} else {
hp.put(t.charAt(k), 1 + hp.get(t.charAt(k)));
}
}
while (i <= j && j < s.length()) {
ch = s.charAt(j);
if (hp.containsKey(ch)) {
if (hp1.containsKey(ch)) {
hp1.put(ch, hp1.get(ch) + 1);
} else {
hp1.put(ch, 1);
}
}
if (check(hp, hp1)) {
while (check(hp, hp1)) {
curlen = j - i + 1;
if (curlen < len) {
len = curlen;
min = i;
max = j;
}
if (hp1.containsKey(s.charAt(i))) {
hp1.put(s.charAt(i), hp1.get(s.charAt(i)) - 1);
}
i++;
}
}
j++;
}
return len == Integer.MAX_VALUE ? "" : s.substring(min, max + 1);
}
private static boolean check(HashMap<Character, Integer> hp, HashMap<Character, Integer> hp1) {
Set<Map.Entry<Character, Integer>> entries = hp.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
if (!hp1.containsKey(entry.getKey()) || hp1.get(entry.getKey()) < entry.getValue()) return false;
}
return true;
}
JAVA
|
哈希表(Map Set)
只操作一个map:
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
| public boolean isAnagram(String s, String t) {
HashMap<Character, Long> hp = new HashMap<>();
Character ch = null;
if (s.length() != t.length()) return false;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (hp.containsKey(ch)) {
hp.put(ch, hp.get(ch) + 1);
} else {
hp.put(ch, 1L);
}
}
for (int i = 0; i < t.length(); i++) {
ch = t.charAt(i);
if (hp.containsKey(ch)) {
hp.put(ch, hp.get(ch) - 1);
if (hp.get(ch) == 0) {
hp.remove(ch);
}
} else {
return false;
}
}
return hp.isEmpty();
}
JAVA
|
我是先排序在处理 因为排序复杂度为O(nlogn)，所有总复杂度为O(n):
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
| public static int[] twoSum(int[] nums, int target) {
int[] ints = new int[2];
int[] nums1 = Arrays.copyOf(nums, nums.length);
int i = 0, j = nums1.length - 1;
int sum = 0;
Arrays.sort(nums1);
while (i < j) {
sum = nums1[i] + nums1[j];
if (sum == target) {
ints[0] = nums1[i];
ints[1] = nums1[j];
break;
} else if (sum > target) {
j--;
} else {
i++;
}
}
return find(nums, ints[0], ints[1]);
}
private static int[] find(int[] nums, int target1, int target2) {
int[] ints = new int[2];
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target1) {
ints[0] = i;
break;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target2 && i != ints[0]) {
ints[1] = i;
break;
}
}
return ints;
}
JAVA
|
但是 实际上，利用hash表有O(n)的算法：
1
2
3
4
5
6
7
8
9
10
11
| public static int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
} else {
map.put(nums[i], i);
}
}
throw new RuntimeException("No two sum");
}
JAVA
|
理论上可以用哈希表存储路径上的每一个数字，因为最终循环长度不会超过720，所以是可行的:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static boolean isHappy(int n) {
HashSet<Integer> hs = new HashSet<>();
int bit = 0;
int sum = 0;
while (!hs.contains(sum)) {
hs.add(sum);
sum = 0;
while (n != 0) {
bit = n % 10;
sum += bit * bit;
n /= 10;
}
if (sum == 1) {
return true;
} else {
n = sum;
}
}
return false;
}
JAVA
|
但是实际上，最好还是使用快慢指针，这个空间复杂度会更低:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static boolean isHappy(int n) {
int slow = n, fast = n;
do {
slow = bitsquarenum(slow);
fast = bitsquarenum(fast);
fast = bitsquarenum(fast);
} while (slow != fast);
return slow == 1;
}
private static int bitsquarenum(int n) {
int bit = 0, sum = 0;
while (n != 0) {
bit = n % 10;
sum += bit * bit;
n /= 10;
}
return sum;
}
JAVA
|
此题目难度较大，注意map的主键为排序后的字符串，因为对于字母异位词，排序后结果相同，值为List:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> hp = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String s = new String(charArray);
if (hp.containsKey(s)) {
List<String> list1 = hp.get(s);
list1.add(str);
hp.put(s,list1);
} else {
List<String> newList = new ArrayList<>();
newList.add(str);
hp.put(s, newList);
}
}
return new ArrayList<>(hp.values());
}
JAVA
|
利用java8的新特性Collectors.groupBy进行解答(膜拜大佬):
1
2
3
4
5
6
7
8
9
10
| public static List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays
.stream(strs)
.collect(Collectors
.groupingBy(str->{
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
return new String(charArray);
})).values());
}
JAVA
|
哈希表 但是用到了数组，时间和空间存在一定浪费:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static int longestConsecutive(int[] nums) {
TreeSet<Integer> ts = new TreeSet<>();
int max = 1;
int count = 1;
for (int num : nums) {
ts.add(num);
}
Integer[] array = Arrays.copyOf(ts.toArray(), ts.size(), Integer[].class);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] == array[i] + 1) {
count++;
max = Math.max(count, max);
} else {
max = Math.max(count, max);
count = 1;
}
}
return (nums.length == 0) ? 0 : max;
}
JAVA
|
直接迭代，但是迭代器的时间消耗比数组还要高。。。:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static int longestConsecutive(int[] nums) {
TreeSet<Integer> ts = new TreeSet<>();
int max = 1;
int count = 1;
for (int num : nums) {
ts.add(num);
}
for (Integer t : ts) {
if (ts.contains(t + 1)) {
count++;
} else {
max = Math.max(max, count);
count = 1;
}
}
max = Math.max(max, count);
return (nums.length == 0) ? 0 : max;
}
JAVA
|
链表
链表双指针(快慢指针经典问题)
1
2
3
4
5
6
7
8
9
10
| public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (true) {
if (fast == null || fast.next == null) return false;
fast = fast.next.next;
slow = slow.next;
if (slow == fast) break;
}
return true;
}
JAVA
|
核心问题在于 s = s.next
这里要注意链表是一条链，所有s.next = list1的操作实际上是继承了整条链
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
|
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
int num1 = 0, num2 = 0;
ListNode r = new ListNode();
ListNode s = r;
while (list1 != null && list2 != null) {
num1 = list1.val;
num2 = list2.val;
if (num1 < num2) {
s.next = list1;
list1 = list1.next;
} else {
s.next = list2;
list2 = list2.next;
}
s = s.next;
}
while (list1 != null) {
s.next = list1;
list1 = list1.next;
}
while (list2 != null) {
s.next = list2;
list2 = list2.next;
}
return r.next;
}
JAVA
|
递归法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
JAVA
|
迭代法:
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
| public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode r = new ListNode();
ListNode s = r;
int num = 0, carrybit = 0;
while (true) {
num = l1.val + l2.val + carrybit;
s.val = num % 10;
carrybit = num / 10;
l1 = l1.next;
l2 = l2.next;
if (l1 == null || l2 == null) break;
s.next = new ListNode();
s = s.next;
}
while (l1 != null) {
s.next = new ListNode();
s = s.next;
num = l1.val + carrybit;
s.val = num % 10;
carrybit = num / 10;
l1 = l1.next;
}
while (l2 != null) {
s.next = new ListNode();
s = s.next;
num = l2.val + carrybit;
s.val = num % 10;
carrybit = num / 10;
l2 = l2.next;
}
if (carrybit != 0) {
s.next = new ListNode(1);
}
return r;
}
JAVA
|
迭代法:
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
| public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
int len = right - left + 1;
dummyNode.next = head;
ListNode pre = dummyNode;
left--;
while (left > 0) {
pre = pre.next;
left--;
}
ListNode leftNode = pre;
ListNode start = leftNode.next;
while (len > 0) {
pre = pre.next;
len--;
}
ListNode end = pre;
ListNode rightNode = end.next;
end.next = null;
leftNode.next = null;
reverseLinkedList(start);
leftNode.next = end;
start.next = rightNode;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
reverse(null, head);
}
private void reverse(ListNode pre, ListNode cur) {
if (cur == null) return;
ListNode tmp = cur.next;
cur.next = pre;
reverse(cur, tmp);
}
JAVA
|
善用虚拟头节点:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public ListNode deleteDuplicates(ListNode head) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode prev = dummyNode;
ListNode cur = prev.next;
ListNode tmp = null;
while (cur != null) {
tmp = cur.next;
if (tmp == null || cur.val != tmp.val) {
prev = cur;
cur = tmp;
} else {
while (tmp != null && cur.val == tmp.val) {
tmp = tmp.next;
}
prev.next = tmp;
cur = tmp;
}
}
return dummyNode.next;
}
JAVA
|