春招冲刺百题计划|双指针

Java基础复习

Java数组的声明与初始化
Java ArrayList
Java HashMap
Java String 类
Java LinkedList
Java Deque继承LinkedList
Java Set
Java 队列
优先队列:第二题用到了
Java数组划分
Java数组转ArrayList
String 转数字
String

这一部分，代码随想录写得超级好！（快慢指针）

第一题：26. 删除有序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {// 快慢指针：慢指针负责确定位置，快指针负责寻找元素int slow = 0;for(int fast=0; fast<nums.length; fast++){if(nums[slow]!=nums[fast]){nums[++slow] = nums[fast];}}return slow+1;}
}

第二题：31. 下一个排列

这题解出来，全凭能不能琢磨出来规律。个人觉得还是很复杂的。
给定一个数组，除非是降序的（最大的排列了），就直接反转。
其他情况，要按照以下步骤来执行：
1.从尾部开始查找，找到第一个下降的点a[i]
2.从尾部开始查找，找到最后一个满足a[j]>a[i]的点a[j]，交换两者。
3.翻转a[i+1:n-1]。

class Solution {public void nextPermutation(int[] nums) {int n = nums.length, k = n - 1;while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;if (k == 0) {reverse(nums, 0, n - 1);} else {int u = k;while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;swap(nums, k - 1, u);reverse(nums, k, n - 1);}}void reverse(int[] nums, int a, int b) {int l = a, r = b;while (l < r) swap(nums, l++, r--);}void swap(int[] nums, int a, int b) {int c = nums[a];nums[a] = nums[b];nums[b] = c;}
}

但是，这题和双指针有什么关系呢？

第三题：88. 合并两个有序数组

在这里插入图片描述

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {if(n==0){return;}if(m==0){for(int i=m; i<n+m; i++){nums1[i] = nums2[i-m];}}int p1=m-1, p2=n-1, p3=n+m-1;while(p1>=0&&p2>=0){if(nums1[p1]>nums2[p2]){nums1[p3--] = nums1[p1--];}else{nums1[p3--] = nums2[p2--];}}if(p1>=0){for(int i=p3; i>=0; i--){nums1[i] = nums1[p1--];}}else{for(int i=p3; i>=0; i--){nums1[i] = nums2[p2--];}}}
}

从后往前。如果从前往后会遇到nums1的元素被覆盖的问题，要是再来一个数组存储的话，还不如直接建一个sorted数组。因此，从后往前，保证nums1的元素不被覆盖。

第四题：189. 轮转数组

在这里插入图片描述
有一个额外的数组来辅助是最简单的，难点就在于如何原地轮转。
以下是额外数组的做法：

class Solution {public void rotate(int[] nums, int k) {//最简单就是额外来一个数组，就非常简单。int[] results = new int[nums.length];k = k%nums.length;for(int i=0; i<nums.length; i++){results[(i+k)%nums.length] = nums[i];//向右k，就是向左n-k。}for(int i=0; i<nums.length; i++){nums[i] = results[i];}}
}

翻转一下！（这一题，还有一个推导的解法用到了指针的概念，但是！你怎么能放在双指针章节迷惑人！！！）
在这里插入图片描述

class Solution {//官方题解：找规律，能够环状替换，要数学推导，不管了。//官方题解2：数组翻转（好像经常遇到。）public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}}

第五题：165. 比较版本号

在这里插入图片描述

class Solution {public int compareVersion(String version1, String version2) {//先划分开来String[] v1 = version1.split("\\.");String[] v2 = version2.split("\\.");//转成数字，并对齐长度ArrayList<Integer> al1 = new ArrayList<>();ArrayList<Integer> al2 = new ArrayList<>();for(int i=0; i<v1.length; i++){al1.add(Integer.parseInt(v1[i]));}for(int i=0; i<v2.length; i++){al2.add(Integer.parseInt(v2[i]));//String 如何转数字}int n = Math.max(v1.length, v2.length);while(al1.size()<n) al1.add(0);while(al2.size()<n) al2.add(0);//比较for(int i=0; i<n; i++){if(al1.get(i)>al2.get(i)){return 1;}if(al1.get(i)<al2.get(i)){return -1;}}return 0;//Arrays.toString(v1)}
}

双指针的目的是为了节省空间。个人觉得题解的代码很优雅！

class Solution {public int compareVersion(String version1, String version2) {int n = version1.length(), m = version2.length();int i = 0, j = 0;while (i < n || j < m) {int x = 0;for (; i < n && version1.charAt(i) != '.'; ++i) {x = x * 10 + version1.charAt(i) - '0';}++i; // 跳过点号int y = 0;for (; j < m && version2.charAt(j) != '.'; ++j) {y = y * 10 + version2.charAt(j) - '0';}++j; // 跳过点号if (x != y) {return x > y ? 1 : -1;}}return 0;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/compare-version-numbers/solutions/970416/bi-jiao-ban-ben-hao-by-leetcode-solution-k6wi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第六题：125. 验证回文串

算是超经典题目了。
在这里插入图片描述

class Solution {public boolean isPalindrome(String s) {if(s.length()==0){return true;}//还要先处理。s = s.toLowerCase();int l=0, r=s.length()-1;while(l<s.length()&&(s.charAt(l)>'z'||s.charAt(l)<'a')&&(s.charAt(l)>'9'||s.charAt(l)<'0')) l++;while(r>=0&&(s.charAt(r)>'z'||s.charAt(r)<'a')&&(s.charAt(r)>'9'||s.charAt(r)<'0')) r--;while(l<r){System.out.println(s.charAt(l) + " " + s.charAt(r));if(s.charAt(l)!=s.charAt(r)){return false;}l++;r--;while(l<s.length()&&(s.charAt(l)>'z'||s.charAt(l)<'a')&&(s.charAt(l)>'9'||s.charAt(l)<'0')) l++;while(r>=0&&(s.charAt(r)>'z'||s.charAt(r)<'a')&&(s.charAt(r)>'9'||s.charAt(r)<'0')) r--;}return true;}
}

第七题：295. 数据流的中位数

在这里插入图片描述
难度在于插入后排序，取出中位数定位。