双指针法¶
双指针用法的总结，一定要自己AC
1. 移除元素¶
题目重点：原地修改
思路：快慢指针
- 慢指针指向新的数组的索引
- 快指针寻找原数组中满足条件的元素
2. 反转字符串¶
题目重点：原地修改
思路：双向指针
注意：需要在循环中让两个指针进行移动
3. 替换数字¶
思路：Java比较容易实现，因为Java的字符串不能够修改，只能使用辅助空间
本次用C++实现，不需要辅助空间 1. 首先确定字符串中的数字的个数，从而确定把数组换为 “number” 后的字符串长度 2. 使用双指针，从后向前移动，其中 一个指针指向原数组的最后位置，另一个指针指向新数组的最后位置 3. 从后向前遍历原数组，非数字字符直接加入新数组，数字字符则将 “number” 反转后加入新数组
#include <iostream>
using namespace std;
int main(){
string s;
cin >> s;
int oldSize = s.size();
// cnt 用来记录字符串中的数字的个数
int cnt=0;
for (int i=0; i<s.size();i++){
if (s[i] >= '0' && s[i] <='9') cnt += 1;
}
// 新数组大小
int newSize = s.size()+cnt*5;
// 扩充数组
s.resize(newSize);
// 使用双指针
int oldIndex = oldSize-1, newIndex = newSize-1;
// 从后向前遍历原数组
while(oldIndex >= 0){
if (s[oldIndex] >= '0' && s[oldIndex] <= '9'){
s[newIndex] = 'r';
s[newIndex-1] = 'e';
s[newIndex-2] = 'b';
s[newIndex-3] = 'm';
s[newIndex-4] = 'u';
s[newIndex-5] = 'n';
newIndex = newIndex-6;
oldIndex--;
}else{
s[newIndex] = s[oldIndex];
newIndex--;
oldIndex--;
}
}
cout << s << endl;
}
4. 反转字符串里的单词¶
link: LeetCode 151
思路： 1. 首先去除字符串中的多余空格（此处因为对字符串的长度进行了更改，因此需要返回新的字符串） 2. 翻转整个字符串（此时传入的 start 和 end 是新的字符串的 start 和 end） 3. 翻转每个单词（需要遍历字符串，使用双指针找到每个单词的起始位置和终止位置，然后将单词进行翻转）
有很多细节
class Solution {
public String reverseWords(String s) {
// 1. 去除多余的空格
StringBuilder sb = reverseSpace(s);
// 2. 翻转整个字符串
reverseString(sb, 0, sb.length()-1);
// 3. 遍历字符串, 翻转每一个单词
reverseEachWord(sb);
return sb.toString();
}
// 1. 去除多余的空格
public StringBuilder reverseSpace(String s){
StringBuilder resBuilder = new StringBuilder();
// 首先去除开头和结尾的空格
int start = 0, end = s.length()-1;
while(s.charAt(start) == ' ') start++;
while(s.charAt(end) == ' ') end--;
// 遍历整个字符串, 去除多余的空格
while(start <= end){
if (s.charAt(start) != ' ' || s.charAt(start-1) != ' '){
resBuilder.append(s.charAt(start));
}
start++;
}
return resBuilder;
}
// 2. 翻转整个字符串 左闭右闭
public void reverseString(StringBuilder sb, int start, int end){
while(start < end){
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
// 3. 遍历字符串, 翻转每一个单词
public void reverseEachWord(StringBuilder sb){
// left: 单词的开头 right：单词的结尾
int left=0,right=1, len=sb.length();
while(left < len){
// 寻找到单词后面的空格的索引
while(right < len && sb.charAt(right) != ' ') right++;
// 进行翻转
reverseString(sb, left, right-1);
// 更新新的单词在开头
left = right+1;
right = left+1;
}
}
}
5. 翻转链表¶
思路：
- 使用双指针，pre 指向当前节点前面的节点，cur 指向当前节点，并用 temp 保存当前节点后面的节点
- 改变当前节点与前面节点的指针指向后，pre 和 cur 都向前移动一位，直到 cur=null
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 定义双指针
ListNode preNode = null;
ListNode curNode = head;
while(curNode != null){
ListNode tempNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = tempNode;
}
return preNode;
}
}
6. 删除链表的倒数第N个节点¶
思路： 1. 使用虚拟节点，从而保证删除头节点和删除其他节点的逻辑一致 2. 使用双指针，fast指针先向前走N步，然后 slow 和fast 同时向前走，当fast指针走到最后一个节点的时候，slow指针正好指向要删除节点的前面的节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode virtualHead = new ListNode(-1, head);
ListNode slow = virtualHead;
ListNode fast = virtualHead;
while(n-- > 0) fast = fast.next;
while(fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// 找到要删除节点的前面的节点
slow.next = slow.next.next;
return virtualHead.next;
}
}
7. 链表相交¶
link: LeetCode
思路： 1. 首先遍历两个链表，确定两个链表的长度差 gap 2. 使用双指针，一个指向短链表，一个指向长链表，指向长链表的指针先移动 gap 步，然后两个指针一块移动，直到指向的节点相等或者到链表末尾为null
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode cntA = headA;
ListNode cntB = headB;
while(cntA != null) { lenA++; cntA = cntA.next;}
while(cntB != null) { lenB++; cntB = cntB.next;}
// 保证A一直是长链表
if (lenA < lenB){
int temp = lenA;
lenA = lenB;
lenB = temp;
ListNode tempNode = headA;
headA = headB;
headB = tempNode;
}
// 计算两个链表的长度差
int gap = lenA - lenB;
// 定义两个指针分别指向两个链表
ListNode indexA = headA;
ListNode indexB = headB;
while(gap-- > 0){
indexA = indexA.next;
}
while(indexA != null){
if (indexA == indexB) return indexA;
else{
indexA = indexA.next;
indexB = indexB.next;
}
}
return null;
}
}
8. 环形链表¶
link: LeetCode 142
思路：
-
首先通过快慢双指针确定两个指针在链表中相遇的位置，其中快指针每次走两步，慢指针每次都一步，因此快指针相对于慢指针每次多走了一步，因此如果有环，必定相遇（并且是在慢指针进入环的第一圈相遇）
-
寻找环的入口，再次定义两个指针，分别指向头节点
headIndex和 相遇的节点metIndex
根据第一步的快慢指针可以得到等式：\(2(x+y) = x + n(y+z) + y\), 经过化简得到 $$ x = n(y+z) - y = (n-1)(y+z) + z $$
因此在第二步定义的两个指针同时开始走，必定会在 环的入口处相遇
9. 三数之和¶
link: LeetCode 15
注意：题目要求返回的是三元组，即满足条件的元素，不是下标；并且三元组不能重复
思路：
- 首先将数组按照从小到大的顺序排序
- 使用 \(i\) 遍历整个数组
- 然后定义双指针，
left=i+1, rigth=nums.length-1, 当三元组的和小于target，则left向右移动，如果三元组的和 大于 target, 则right向左移动(临界条件left < right) - 去重
- 首先需要对三元组的第一个数
a = nums[i]进行去重, 因为如果nums[i]=nums[i-1], 之前已经对nums[i-1]进行了处理, 对nums[i]进行处理的结果是 对nums[i-1]处理结果的子集，因为要求三元组不能重复, 因此需要去重 - 当 满足题目条件后, 如果
nums[left] = nums[left-1], 则left继续向右移动; 如果nums[right] = nums[right+1], right继续向左移动
10. 四数之和¶
link: LeetCode 18
思路： 在三数之和的基础上，再套上一层 for 循环 - 每一层for循环都需要去重
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> resList = new ArrayList<>();
// 将数组排序
Arrays.sort(nums);
if (nums.length < 4) return resList;
for (int i=0; i<nums.length-3; i++){
if (nums[i] > 0 && nums[i] > target) break;
// 去重
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j=i+1; j<nums.length-2;j++){
// 去重
if (j > i+1 && nums[j] == nums[j-1]) continue;
int left = j+1, right = nums.length-1;
while(left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target){
resList.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
}
else if (sum > target) right--;
else if (sum < target) left++;
}
}
}
return resList;
}
}