Skip to content

Latest commit

 

History

History
168 lines (134 loc) · 7.55 KB

算法技巧总结.md

File metadata and controls

168 lines (134 loc) · 7.55 KB
Raw

专栏原创出处：github-源笔记文件 ，github-源码 ，欢迎 Star，转载请附上原文出处链接和本声明。

[toc]

1. 解题思路

拿到题目，开始考虑暴力解法，借助暴力方法我们可以在过程上继续优化，循序渐进的优化复杂度。

  • 寻找关键字

    提取题目关键字，比如给定一个「二叉树」与给定一个「完美二叉树」解题思路可能完全不一样。案例 力扣 116 / 力扣 117

  • 画图分析

    许多问题依靠大脑不能很好的立马想出方案，尤其涉及链表相关问题。推荐采用画图模式分析解题过程，这样在转换代码时更为流畅。

  • 注意边界、重复、溢出问题

    一定考虑数据边界问题，尤其是 >= > < <= null 空头、空尾... 之类的问题，很多 BUG 都是因为边界处理不周全导致的。注意递归重复计算问题，返回值溢出问题。

  • 优先考虑原地算法

    先不考虑借助外部数据结构尝试原地算法 ，当然如果本身数据不允许修改本身时只能借助外部数据临时存储。

  • 借助外部数据结构

    分析题目过程中的一些特点，是否执行替换操作、当前操作是否依赖历史数据、过程数据的流向。 一般情况，如果涉及替换、反转类操作考虑指针（双指针）。如果涉及历史数据时考虑指针记录是否满足，不满足时使用数据结构。比如先进后出、先进先出、KV 映射哈希表。 在使用数据结构时，尽量减少空间复杂度。比如我们的一个数组，可以记录一个下标，前半部分用于删除后半部分用于修改。

2. 双指针技巧

2.1 对撞指针-两个指针从两端向中间迭代

一个指针从始端开始，而另一个指针从末端开始。

关键词：反转字符串、排序数组、原地算法、首尾替换

// 案例：将输入的字符串反转过来
// 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
class Solution {
    public void reverseString(char[] s) {
        int min = 0; // 开始位置
        int max = s.length - 1; // 末尾位置
        while (min < max) { // 向中间迭代
            char minVal = s[min];
            s[min++] = s[max];
            s[max--] = minVal;
        }
    }
}

2.2 窗口指针-两个指针保持一定距离

使用两个指针，两个指针保持一定的窗口距离进行迭代。

关键词：删除倒数第 N 个问题

// 案例：删除链表的倒数第 N 个节点
// 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
public ListNode removeNthFromEnd(ListNode head, int n) {
   ListNode sentinel = new ListNode(0); // 哨兵节点,避免头节点 null 问题
   sentinel.next = head;

   ListNode first = sentinel; // 第一个指针
   ListNode second = sentinel;// 第二个指针

   // 第二个指针先前进 n 步
   for (int i = 0; i < n; i++) second = second.next;
   
   while (second.next != null) { // 同步向后迭代，第二个指针到末尾即寻找结束
       first = first.next;
       second = second.next;
   }
   first.next = first.next.next; // 第一个指针指向的节点，即为移除节点
   return sentinel.next;
}

2.3 快慢指针

使用两个指针，一个快指针和一个慢指针。指针的移动策略取决于条件本身。

关键词：原地删除、寻找环形链表环形入口点（环形链表 II）、两个单链表相交的起始节点（相交链表）

// 案例：移除元素
// 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
public int removeElement(int[] nums, int val) {
    int i = 0; // 快指针
    int k = nums.length - 1; // 慢指针
    while (i <= k) {
        if (nums[i] == val) { // 不相等时将值交换到末尾
            nums[i] = nums[k--];
        } else {
            i++;
        }
    }
    return k + 1;
}

// 案例：判断单链表是否是环形链表（链表中有一个环，其尾部连接到前面的节点。）
// 双指针,每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。
// 如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环 N 周，并赶上慢指针。
 public boolean hasCycle(ListNode head) {
     ListNode slow = head; // 慢指针
     ListNode fast = slow; // 快指针
     do {
         if (fast == null || fast.next == null) {
             return false;
         }
         slow = slow.next;
         fast = fast.next.next;
     } while (fast != slow);
     return true;
}

3. 哨兵节点（哑节点、伪节点）-避免空问题

我们在移除单链表的元素时，如果移除的是中间的元素，直接使用「curr」「prev」两个指针来处理。 但是如果移除的是头部节点时，「prev」为空。使用了哨兵节点后我们避免对 「null」 处理。

哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。

// 案例：删除链表中等于给定值 val 的所有节点。
public ListNode removeElements1(ListNode head, int val) {
    ListNode sentinel = new ListNode(0); // 哨兵节点
    sentinel.next = head; // 本身的头节点挂在到哨兵节点
    
    ListNode curr = head; // 当前节点
    ListNode prev = sentinel; // 当前节点的上一个节点，默认为哨兵节点
    
    while (curr != null) {
        if (curr.val == val) { // 相等，移除当前节点 curr
            // 上一个节点直接指向下下一个节点。如果不用哨兵节点需要判断 null 重置头节点
            prev.next = curr.next; 
        } else prev = curr; // 不能移除时，当前节点更新为上一个节点
        curr = curr.next; // 继续寻找下一个节点
    }
    return sentinel.next; // 移除哨兵节点返回真实的头节点
}

4. 求和（进位、最终进位）

求和问题需要考虑进位问题，最终结果考虑是否加 1 。

$99 + 1$ 运算，通常我们会考虑进位问题，有时也会忽略了处理最终进位时错误的输出 00，百位的 1 可能丢失。

// 案例：两数相加 https://leetcode-cn.com/problems/add-two-numbers/
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

输入：(9 -> 9 -> 9) + (1)
输出：1 -> 0 -> 0 -> 0
原因：999 + 1 = 1000

参考

更多相关专栏内容汇总：