算法刷题系列：

• 算法刷题：链表题（持续更）

力扣链接：
删除有序数组中的重复项
删除排序链表中的重复元素
移除元素
移除链表元素
两数之和
反转字符串
反转链表
验证回文串
验证回文串 II

快速排序

原理

（自己懒得做图，图片来自别的博客）
下面序列：

把第一位57作为基准位，用变量把它存起来，因为一会就没了

• 把所有比57小的数放在57的左面，把比57大的数放在57的右面
• 两边同时进行，左边找大的，右边找小的，把小的放左边，大的放右边，具体操作如下：

第一趟：从指针j开始，24小于57，放到左边，把57覆盖掉

之后：指针i右移，指向68，68>57，放到右边

之后：指针j左移指向33，33<57，放到左边

之后：指针i右移指向59，59>57，放右边

之后：指针j左移指向96，96>57，j再左移指向28，28<57，放左边

之后：指针i右移指向52，52<57,i继续右移指向72，72>57,放右边

之后：指针j左移，与指针i重合指向NULL，这时放入57

这时发现左边的数都比57小，右边都比57大

然后再对57左边的数，即：0到i-1进行快速排序（同样操作，把24作为基准，左边小，右边大），对57右边的数，即：i+1到n进行快速排序（以72位基准，左边小，右边大）直到不能再进行排序为止；

代码实现

优化：扰动

int pvt = nums[mid];
swap(nums, left, mid);

static void quickSort(int[] nums, int left, int right){
if(left > right) return;

int mid = (left + right) >>> 1;
int l = left;
int r = right;
int pvt = nums[mid]; // 基准元素

swap(nums, left, mid);
while(l < r){
while(l < r && nums[r] >= pvt) r--;
if(l < r) nums[l++] = nums[r]; // l 指向空位

while(l < r && nums[l] < pvt) l++;
if(l < r) nums[r--] = nums[l]; // r 指向空位
} nums[l] = pvt; // 基准元素放入 lr 指向的空位

quickSort(nums, left, l - 1);
quickSort(nums, l + 1, right);
}

快慢指针

快慢指针sf：
同向移动：

• 同步移动：

1. 速度倍数：
2. 相对速度：
3. 相邻先后 (pcn)：
4. 齐头并进：是否需要齐头，之后再并进

• 异步移动：

1. 慢指针符合条件再动

异向移动：

• 左右指针
• 边向中
• 中向边

指针指向：

• 空位（快速排序）
• 处理点

注意事项

if(str.charAt(l) != str.charAt(r)){

不如

char lval = str.charAt(l);
char rval = str.charAt(r);
if(lval != rval){

的效率高

异步移动

删除有序数组的重复项

代码实现

public int removeDuplicates(int [] nums){
int slow = 0;
for(int fast = 0; fast < nums.length; ++fast){
if(nums[fast] != nums[slow]){
nums[++slow] = nums[fast];
}
}
return slow + 1;
}

对比链表的删除重复项代码

很类似：

public ListNode deleteDuplicates(ListNode head){
if(head == null) return null;

ListNode slow = head;
for(ListNode fast = head; fast != null; fast = fast.next){
if(fast.val != slow.val){
slow.next = fast;
slow = slow.next;
}
}
slow.next = null;
return head;
}

移除元素

代码实现

int removeElement(int [] nums, int val){
int sl = 0;
for(int fa = 0; fa < nums.length; ++fa){
if(nums[fa] != val){
nums[sl] = nums[fa];
sl++;
}
}
return sl;
}

对比移除链表元素

ListNode removeElements(ListNode head, int val){
ListNode dummy = new ListNode();

ListNode sl = dummy;
for(ListNode fa = head; fa != null; fa = fa.next){
if(fa.val != val){
sl.next = fa;
sl = sl.next;
}
}
return dummy.next;
}

异向而行

两数之和

暴力解法（\(O(N^2)\)，56ms）

class Solution {
public int[] twoSum(int[] nums, int target) {
int [] res = new int [2];
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
int sum = nums[i] + nums[j];
if(sum == target) {
res[0] = i;
res[1] = j;
return res;
}
}
}
return res;
}
}

快排 + 左右指针（\(O(NlogN)\)，2ms）

但是排序之后，索引位置会发生变化
所以需要保存排序之前的数组

class Solution {
public int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;

int [] src = new int [nums.length]; // 保存源数组
for(int i = 0; i < nums.length; i++){
src[i] = nums[i];
}
quickSort(nums, 0, right); // 排序

int [] res = new int [2];

int sum = 0;
while(left < right){
sum = nums[left] + nums[right];
if(sum < target){
left ++;
} else if(sum > target){
right --;
} else {
int i = 0;
int lval = nums[left];
int rval = nums[right];
while(true){
if(src[i] == lval){
res[0] = i;
break;
} i++;
} i = 0;
while(true){
if(src[i] == rval){
if(i == res[0]){
i++;
continue;
}
res[1] = i;
break;
} i++;
}
break;
}
}
return res;
}
}

哈希表空间换时间（\(O(N)\)）

单向遍历解法（2ms）

将两个变量中的一个变量，用空间（哈希表）转化成常量，空间换时间

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int l = 0; l < nums.length; l++){
int rval = target - nums[l];
if(map.containsKey(rval)){
return new int []{map.get(rval), l};
}
map.put(nums[l], l);
}
// return new int []{0, 0};
return new int [2];
}
}

优化：边向中左右指针（0ms）

类似快速排序的左右指针从边界向中间迭代：

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int l = 0, r = nums.length - 1; l <= r; l++, r--){
int rval = target - nums[l];
if(map.containsKey(rval)){
return new int []{map.get(rval), l};
}
map.put(nums[l], l);

int lval = target - nums[r];
if(map.containsKey(lval)){
return new int []{map.get(lval), r};
}
map.put(nums[r], r);
}
// return new int []{0, 0};
return new int [2];
}
}

反转字符串（\(O(N)\)）

代码实现

void reverseString(char [] s){
int left = 0;
int right = s.length - 1;
while(left < right){
swap(s, left, right);
left++;
right--;
}
}

对比反转链表

ListNode reverse(ListNode head){
if(head == null && head.next == null){
return head;
}
ListNode pre = null; // 处理完成
ListNode cur = head; // cur 是待处理的点
ListNode nxt = null;
while(cur != null){ // 没有需要处理的
nxt = cur.next;

cur.next = pre; // 处理内容：反转

pre = cur; // 跟随
cur = nxt;
}
return pre;
}

验证回文串（\(O(N)\)，1ms击败100%）

这个本质也是相向而行，但是在相向而行中多处理了很多步骤

class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while(left < right){
// 大写转换为小写
char lval = castChar(s.charAt(left));
char rval = castChar(s.charAt(right));
// 是否是小写字母 或数字
if(lval > 'z' || lval < 'a' ){
if(lval > '9' || lval < '0'){
left ++;
continue;
}
}
if(rval > 'z' || rval < 'a' ){
if(rval > '9' || rval < '0'){
right --;
continue;
}
}
// 判断是否回文串
if(lval != rval){
return false;
}
// 迭代
left ++;
right --;
}
return true;
}
char castChar(char c){ // 将大写字母转换为小写字母
if(c >= 'A' && c <= 'Z'){
return (char)((int)c - ('A' - 'a'));
}
return c;
}
}

验证回文串 II（\(O(N)\)，4ms击败100%）

全是英文小写字母，重点是可以有一次机会修改，这个可以理解为左右指针指向了不一致的值可以删除左指针值或者右指针值，再看看是不是回文串

class Solution {
public boolean validPalindrome(String s) {
int l = 0;
int r = s.length() - 1;
while(l < r){
char lval = s.charAt(l);
char rval = s.charAt(r);
if(lval != rval){
boolean lok = palindrome(s, l + 1, r);
if(lok) break;
boolean rok = palindrome(s, l, r - 1);
if(rok) break;
return false;
}
l++; r--;
}
return true;
}
public boolean palindrome(String s, int l, int r){
while(l < r){
char lval = s.charAt(l);
char rval = s.charAt(r);
if(lval != rval){
return false;
}
l++; r--;
}
return true;
}
}