学习记录算法数组算法技巧
TONG HUI左右指针和快慢指针
快慢指针技巧
有序数组去重
用到快慢指针技巧：我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int removeDuplicates(int[] nums){
if(nums.length == 0){
return 0;
}
int slow = 0,fast = 0;
while(fast < nums.length){
if(nums[fast] != nums[slow]){
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow+1;
}
|
算法执行过程：
删除排序链表中的重复元素
1
2
3
4
5
6
7
8
9
10
11
12
13
| ListNode deleteDuplicates(ListNode head){
if(head == null) return null;
ListNode slow = head,fast = head;
while(fast != null){
if(fast.val != slow.val){
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
slow.next = null;
return head;
}
|
算法执行过程:
有序数组/链表中去重
把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow前进一步。
1
2
3
4
5
6
7
8
9
10
11
12
|
int removeElement(int[] nums,int val){
int fast =0,slow =0;
while(fast < nums.length){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
|
将数组中的所有值为 0 的元素移到数组末尾
1
2
3
4
5
6
7
8
| void moveZeroes(int[] nums){
int p = removeElement(nums,0);
for(;p<nums.length;p++){
nums[p] =0;
}
}
|
滑动窗口算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void slidingWindow(string s,string t){
unordered_map<char,int> nedd,window;
for(char c: t){
need[c]++;
}
int left=0,right=0;
int valid =0;
while(right < s.size()){
char c = s[right];
right++;
while(window needs shrink){
char d = s[left];
left++;
}
}
}
|
左右指针的常用算法
二分查找
最简单的二分算法，旨在突出它的双指针特性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int binarySearch(int[] nums,int target){
int left = 0,right = nums.length-1;
while(left <= right){
int mid = (right + left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid +1;
}else if(nums[mid] > target){
right = mid + 1;
}
}
return -1;
}
|
两数之和
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int[] twoSum(int[] nums,int target){
int left = 0,right =nums.length -1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum == target){
return nwe int[]{left+1,right+1};
}else if(sum < target){
left++;
}else if(sum > target){
right--;
}
}
}
|
反转数组
1
2
3
4
5
6
7
8
9
10
11
12
| void reverseString(char[] s){
int left = 0,right = s.length-1;
while(left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
|
回文串判断
1
2
3
4
5
6
7
8
9
10
11
12
| boolean isPalindrome(String s){
int left =0,right = s.length()-1;
while(left < right){
if(s.charAt(left) != s.charAt(right)){
return fasle;
}
left++;
right--;
}
return true;
}
|
找出最长的回文串
核心是从中心向两端扩散的双指针技巧
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
1
2
3
4
5
6
7
8
9
10
11
|
String palindrome(String s,int l,int r){
while(l>=0 && r < s.lenth() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
return s.substring(l+1,r);
}
|
最长回文串的问题，解法的大致思路就是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| for 0 <= i < len(s):
找到以 s[i] 为中心的回文串
找到以 s[i] 和 s[i+1] 为中心的回文串
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
|
用到快慢指针技巧：
