算法练习02——双指针

目录 283. 移动零11. 盛最多水的容器15. 三数之和42. 接雨水*(暴力，双指针优化暴力，单调栈)27. 移除元素344. 反转字符串54. 替换数字（第八期模拟笔试）151. 反转字符串中的单词206. 反转链表19. 删除链表的倒数第 N 个结点.面试题 02.07. 链表相交142. 环形链表 II

283. 移动零

https://leetcode.cn/problems/move-zeroes/

class Solution { //方法一：简单覆盖 //非零的从下标0添加，数组剩下位置都填0 // public void moveZeroes(int[] nums) { // int len=nums.length; // int k=0; // for(int i=0;i<len;i++){ // if(nums[i]!=0){ // nums[k++]=nums[i]; // } // } // while(k<len){ // nums[k++]=0; // } // } //方法二：双指针 //解释一下：如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换； //如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换。 public void moveZeroes(int[] nums) { int len=nums.length; int left=0; int right=0; while(right<len){ if(nums[right]!=0){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; } right++; } } } 11. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/

class Solution { public int maxArea(int[] height) { //若向内 移动短板 ，水槽可能变大，因此下个水槽的面积 可能增大 。 //若向内 移动长板 ，下个水槽的面积 可能会变小（或者不变） int left=0; int right=height.length-1; int res=0; while(left<right){ int area= Math.min(height[left],height[right])*(right-left); res=Math.max(res,area); if(height[right]>=height[left]){ left++; }else{ right--; } } return res; } } 15. 三数之和

https://leetcode.cn/problems/3sum/

class Solution { public List<List<Integer>> threeSum(int[] nums) { int len=nums.length; Arrays.sort(nums);//先排序 List<List<Integer>> res=new ArrayList<>(); for(int i=0;i<len;i++){ if(nums[i]>0){ return res; } if(i>0 && nums[i]==nums[i-1]){ continue;//去重 } int left=i+1; int right=len-1; while(right>left){ int sum=nums[i]+nums[left]+nums[right]; if(sum<0){ left++; }else if(sum>0){ right--; }else{ res.add(Arrays.asList(nums[i],nums[left],nums[right])); left++; right--; while(right>left && nums[left]==nums[left-1]){ left++; } while(right>left && nums[right]==nums[right+1]){ right--; } } } } return res; } } 42. 接雨水*(暴力，双指针优化暴力，单调栈)

https://leetcode.cn/problems/trapping-rain-water/

class Solution { public int trap(int[] height) { //3.单调栈 int len=height.length; if (len <= 2) return 0; int res=0; Stack<Integer> s=new Stack<>(); s.push(0); for(int i=1;i<len;i++){ int top=s.peek(); if(height[top]>height[i]){ s.push(i); }else if(height[top]>height[i]){ s.pop(); s.push(i); }else{ int curHigh=height[i];//目前节点的高度 while(!s.isEmpty() && (curHigh>height[s.peek()])){ int mid=s.pop(); if(!s.isEmpty()){ int left=s.peek(); int h=Math.min(height[left],curHigh)-height[mid]; int w=i-left-1; int area=h*w; if(area>0){ res+=area; } } } s.push(i); } } return res; //2.双指针 /* 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍， 这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft[]） 右边最高高度记录在一个数组上（maxRight[]），这样就避免了重复计算。 */ int len=height.length; if (len <= 2) return 0; int res=0; int maxLeft[]=new int[len]; int maxRight[]=new int[len]; // 记录每个柱子左边柱子最大高度 maxLeft[0]=height[0]; for(int i=1;i<len;i++){ maxLeft[i]=Math.max(maxLeft[i-1],height[i]); } // 记录每个柱子右边柱子最大高度 maxRight[len-1]=height[len-1]; for(int i=len-2;i>=0;i--){ maxRight[i]=Math.max(maxRight[i+1],height[i]); } for(int i=0;i<len;i++){ if(i==0 || i==len-1){ continue; } int h=Math.min(maxLeft[i],maxRight[i])-height[i]; res+=h; } return res; //1.暴力解法 //每一列雨水的高度，取决于该列左侧最高的柱子和右侧最高的柱子中最矮的 //那个柱子的高度减去当前列的高度h=Math.min(maxLeft,maxRight)-height[i] int len=height.length; int res=0; for(int i=0;i<len;i++){ if(i==0 || i==len-1){ continue; } int maxLeft=0; int maxRight=0; for(int j=i;j<len;j++){ maxRight=Math.max(maxRight,height[j]); } for(int j=i;j>=0;j--){ maxLeft=Math.max(maxLeft,height[j]); } int h=Math.min(maxLeft,maxRight)-height[i]; res+=h; } return res; } } 27. 移除元素

https://leetcode.cn/problems/remove-element/description/

class Solution { public int removeElement(int[] nums, int val) { //1.快慢指针 int slow=0; for(int fast=0;fast<nums.length;fast++){ if(nums[fast]!=val){ nums[slow++]=nums[fast]; } } return slow; //2.相向双指针 int leftIndex = 0; int rightIndex = nums.length - 1; while (leftIndex <= rightIndex) { // 找左边等于val的元素 while (leftIndex <= rightIndex && nums[leftIndex] != val){ ++leftIndex; } // 找右边不等于val的元素 while (leftIndex <= rightIndex && nums[rightIndex] == val) { -- rightIndex; } // 将右边不等于val的元素覆盖左边等于val的元素 if (leftIndex < rightIndex) { nums[leftIndex++] = nums[rightIndex--]; } } return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素 } } 344. 反转字符串

https://leetcode.cn/problems/reverse-string/description/

class Solution { public void reverseString(char[] s) { int len=s.length; int left=0; int rigtht=len-1; while(left<rigtht){ char t=s[left]; s[left++]=s[rigtht]; s[rigtht--]=t; } } } 54. 替换数字（第八期模拟笔试）

https://kamacoder.com/problempage.php?pid=1064

import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.nextLine(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (Character.isDigit(s.charAt(i))) { sb.append("number"); }else sb.append(s.charAt(i)); } System.out.println(sb); } } 151. 反转字符串中的单词

https://leetcode.cn/problems/reverse-words-in-a-string/description/

class Solution { public String reverseWords(String s) { //去掉字符串中的多余空格 StringBuilder sb=clearSpace(s); //对整个字符串进行翻转 reverseAll(sb,0,sb.length()-1); //对每个单词进行翻转 reverseStr(sb); return sb.toString(); } //去掉字符串中的多余空格 public StringBuilder clearSpace(String s){ int len=s.length(); int start=0; int end=len-1; while(s.charAt(start)==' ')start++; while(s.charAt(end)==' ')end--; StringBuilder sb=new StringBuilder(); while(start<=end){ char c=s.charAt(start); if(c!=' ' || sb.charAt(sb.length()-1)!=' '){ sb.append(c); } start++; } return sb; } //对整个字符串进行翻转 public void reverseAll(StringBuilder sb,int start,int end){ while(start<end){ char temp=sb.charAt(start); sb.setCharAt(start++,sb.charAt(end)); sb.setCharAt(end--,temp); } } //对每个单词进行翻转 public void reverseStr(StringBuilder sb){ int start = 0; int end = 1; int n = sb.length(); while (start < n) { while (end < n && sb.charAt(end) != ' ') { end++; } reverseAll(sb, start, end - 1); start = end + 1; end = start + 1; } } } 206. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

/** * 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 cur=head; ListNode pre=null; ListNode temp=null; while(cur!=null){ temp=cur.next; cur.next=pre; pre=cur; cur=temp; } return pre; } } 19. 删除链表的倒数第 N 个结点.

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

/** * 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) { //2.双指针，快慢指针 //如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动， //fast和slow中间永远差n个节点，直到fast指向链表末尾。 //删掉slow所指向的节点就可以了。 ListNode preHead=new ListNode(0); preHead.next=head; ListNode slow=preHead; ListNode fast=preHead; while(n>0){ fast=fast.next; n--; } fast=fast.next; while(fast!=null){ fast=fast.next; slow=slow.next; } slow.next=slow.next.next; return preHead.next; //1.普通方法 ListNode cur=head; int size=0; while(cur!=null){ cur=cur.next; size++; } if(n==size){ head=head.next; return head; } cur=head; for(int i=0;i<size-n-1;i++){ cur=cur.next; } if(cur.next!=null) cur.next=cur.next.next; return head; } } 面试题 02.07. 链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

交点不是数值相等，而是指针相等

/** * 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) { ListNode pA=headA; ListNode pB=headB; int lenA=0; int lenB=0; while(pA!=null){ pA=pA.next; lenA++; } while(pB!=null){ pB=pB.next; lenB++; } pA=headA; pB=headB; if(lenA>lenB){ int gap=lenA-lenB; while(gap>0){ pA=pA.next; gap--; } while(pA!=null){ if(pA==pB){ return pA; } pA=pA.next; pB=pB.next; } }else{ int gap=lenB-lenA; while(gap>0){ pB=pB.next; gap--; } while(pA!=null){ if(pA==pB){ return pA; } pA=pA.next; pB=pB.next; } } return null; } } 142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow=head; ListNode fast=head; while(fast!=null && fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ ListNode index01=head; ListNode index02=fast; while(index01!=index02){ index01=index01.next; index02=index02.next; } return index01; } } return null; } }