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. 数据流的中位数
难度在于插入后排序,取出中位数定位。