Leetcode刷题笔记8.12-8.16

Leetcode刷题笔记8.12-8.16

19.删除倒数第n个链表结点(8.12)

• 一个巧妙删除倒数第n个结点的trick
  该方法克制了对链表的一次全面扫描来获得总长度
  

1. // 返回链表的倒数第 k 个节点
2. ListNode findFromEnd(ListNode head, int k) {
3.     ListNode p1 = head;
4.     // p1 先走 k 步
5.     for (int i = 0; i < k; i++) {
6.         p1 = p1.next;
7.     }// 注意这里是向后处理k次
8.     ListNode p2 = head;
9.     // p1 和 p2 同时走 n - k 步
10.     while (p1 != null) {
11.         p2 = p2.next;
12.         p1 = p1.next;
13.     }
14.     // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
15.     return p2;
16. }

复制代码

• 在这个真题的处理上，建立了虚拟结点来处理边界问题
  为了防止出现空指针的情况，好比说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。但有了我们虚拟节点 dummy 的存在，就克制了这个问题，可以大概对这种情况举行正确的删除。
  

26. 删除有序数组中的重复项(8.14)

• 双指针技巧：用于在链表或数组中原地索引或修改，这类过程一样平常必要数组中元素自身作比较，使用双指针（可以是差异步移动、同步移动）
  左右指针是两个指针相向而行大概相背而行；快慢指针是两个指针同向而行，一快一慢。
  对于单链表来说，大部分技巧都属于快慢指针，因为无法直接定位到链表的末尾。单链表的六大解题套路 都涵盖了，好比链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
  
• 【原地修改】：
  如果不是原地修改的话，直接new int[]，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。但是原地删除，不允许new新数组，只能在原数组上使用，然后返回一个长度，如许就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。
  所以该题无所谓去重后剩余空间中的数字，无需思量剩余空间的处理。
  3.接纳快慢指针计谋：让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 进步一步。如许，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
  

1. class Solution {
2.     public int removeDuplicates(int[] nums) {
3.         if (nums.length == 0) {
4.             return 0;
5.         }
6.         int slow = 0, fast = 0;
7.         while (fast < nums.length) {
8.             if (nums[fast] != nums[slow]) {
9.                 slow++;
10.                 // 维护 nums[0..slow] 无重复
11.                 nums[slow] = nums[fast];
12.             }
13.             fast++;
14.         }
15.         // 数组长度为索引 + 1
16.         return slow + 1;
17.     }
18. }

复制代码

27.移除元素(8.16）

• 这道题和上一道思路很像，通过fast指针遍历后移来扫描元素，在满足条件时更换(赋值)slow指针，本质上是删除重复/不必要的元素，同时缩短整个数组
  把nums中全部值为val的元素原地删除，依然必要使用快慢指针技巧：
  如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 进步一步
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。