shuangzhi双指针可以将时间复杂度从O(n*n)到o(n)
而在双指针的概念中，我们可以将双指针分为两种类型：快慢指针、相向指针，同向指针。
左右指针中间夹，快慢指针走到头，后序指针往回走.
快慢指针
快慢指针，顾名思义就是在使用时朝相同方向移动，一个指针的移动速度慢而另一个指针移动速度快，通过两个指针之间的移动所带来的差值，从而确定应用指针所在的数据结构中的某些数据或规律。
142.找出环型链表的入口处
判断是否有环。
- 准备两个指针，快指针一次走两步，慢指针一次走一步。
- 假如链表中有环的话，那么两个指针一定会相遇。
寻找入口处。
因为快指针一次两步，慢指针一次一步，所以快指针走的距离始终是慢指针的两倍。fast = 2*slow
即：
$$
2(F+a) = F+n(a+b)+a,n为快指针跑了多少圈
$$
即：
$$
F = (n-1)(a+b)+b
$$
因为a+b就是一圈环，所以，我们直接就可以看作F = b，即从头节点到入口处 = 第一次相遇点到入口处。
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
|
public ListNode (ListNode head){
if(head==null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(fast==slow){
return fast;
}
}
return null;
}
public ListNode detectCycle(ListNode head) {
ListNode interact = getInteract(head);
if(interact==null){
return null;
}
ListNode start = head;
while(start!=interact){
start=start.next;
interact=interact.next;
}
return start;
}
|
参考：环型链表官方题解
头尾指针
有序数组的 Two Sum
题目描述：在有序数组中找出两个数，使它们的和为 target。
通过头尾指针来解决。
当头指针+尾指针>value，尾指针–；
当头指针+尾指针<value，头指针++；
两者相等，返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public int[] calTwoSum(int[] numbers, int target) {
int head = 0;
int tail = numbers.length-1;
int[] result ;
while(head<tail){
if(numbers[head]+numbers[tail]<target)
head++;
else if(numbers[head]+numbers[tail]>target)
tail--;
else
return new int[]{head,tail};
}
return null;
}
|
两数平方和
题目描述：判断一个非负整数是否为两个整数的平方和。
可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public boolean judgeSquareSum(int c) {
if(c<0){
return false;
}
int head = 0;
int tail = (int)Math.sqrt(c);
while(head<=tail){
if(head*head+tail*tail<c)
head++;
else if(head*head+tail*tail>c)
tail--;
else
return true;
}
return false;
}
|
回文字符串
题目描述：可以删除一个字符，判断是否能构成回文字符串。
所谓的回文字符串，是指具有左右对称特点的字符串，例如 “abcba” 就是一个回文字符串。
使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。
本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
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
|
public boolean validPalindrome(String s) {
int head = 0;
int tail = s.length()-1;
while(head<tail){
if(s.charAt(head)==s.charAt(tail)){
head++;
tail--;
}else{
return (isPalindrome(s,head+1,tail)||isPalindrome(s,head,tail-1));
}
}
return true;
}
public boolean isPalindrome(String s,int start,int end){
while (start<end){
if(s.charAt(start)==s.charAt(end)){
start++;
end--;
}else{
return false;
}
}
return true;
}
|
两个头指针
最长子序列(524)
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
|
public String findLongestWord(String s, List<String> d) {
String result = "";
if(s.equals("")){
return "";
}
for(String ele:d){
if(ele!=null&&!(ele.equals(""))&&isSub(s,ele)){
if(ele.length()>result.length()){
result=ele;
}else if(ele.length()==result.length()){
if(ele.compareTo(result)<0){
result = ele;
}
}
}
}
return result;
}
public boolean subLength(String s ,String ele){
int sHead = 0;
int eleHead = 0;
int length = 0;
while(eleHead<ele.length()&&sHead<s.length()){
if(s.charAt(sHead)==ele.charAt(eleHead)){
length++;
sHead++;
eleHead++;
}else{
sHead++;
}
}
return ele.length()==length;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int removeDuplicates(int[] nums) {
if(nums.length<=1){
return nums.length;
}
int first = 0;
int second = 1;
while(second<nums.length){
if(nums[first]==nums[second]){
second++;
}else{
first++;
nums[first] = nums[second];
second++;
index++;
}
}
return first+1;
}
|
- 基础技巧：分治、二分、贪心
- 排序算法：快速排序、归并排序、计数排序
- 搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
- 图论：最短路径、最小生成树
- 动态规划：背包问题、最长子序列
数据结构，主要有如下几种：
- 数组与链表：单 / 双向链表
- 栈与队列
- 哈希表
- 堆：最大堆 ／ 最小堆
- 树与图：最近公共祖先、并查集
- 字符串：前缀树（字典树） ／ 后缀树
近期评论