专栏原创出处:github-源笔记文件 ,github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。
[toc]
拿到题目,开始考虑暴力解法,借助暴力方法我们可以在过程上继续优化,循序渐进的优化复杂度。
-
寻找关键字
提取题目关键字,比如给定一个「二叉树」与给定一个「完美二叉树」解题思路可能完全不一样。案例 力扣 116 / 力扣 117
-
画图分析
许多问题依靠大脑不能很好的立马想出方案,尤其涉及链表相关问题。推荐采用画图模式分析解题过程,这样在转换代码时更为流畅。
-
注意边界、重复、溢出问题
一定考虑数据边界问题,尤其是
>= > < <= null 空头、空尾...
之类的问题,很多 BUG 都是因为边界处理不周全导致的。注意递归重复计算问题,返回值溢出问题。 -
优先考虑原地算法
先不考虑借助外部数据结构尝试原地算法 ,当然如果本身数据不允许修改本身时只能借助外部数据临时存储。
-
借助外部数据结构
分析题目过程中的一些特点,是否执行替换操作、当前操作是否依赖历史数据、过程数据的流向。 一般情况,如果涉及替换、反转类操作考虑指针(双指针)。如果涉及历史数据时考虑指针记录是否满足,不满足时使用数据结构。比如先进后出、先进先出、KV 映射哈希表。 在使用数据结构时,尽量减少空间复杂度。比如我们的一个数组,可以记录一个下标,前半部分用于删除后半部分用于修改。
一个指针从始端开始,而另一个指针从末端开始。
关键词:反转字符串、排序数组、原地算法、首尾替换
// 案例:将输入的字符串反转过来
// 输入:["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;
}
}
}
使用两个指针,两个指针保持一定的窗口距离进行迭代。
关键词:删除倒数第 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;
}
使用两个指针,一个快指针和一个慢指针。指针的移动策略取决于条件本身。
关键词:原地删除、寻找环形链表环形入口点(环形链表 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;
}
我们在移除单链表的元素时,如果移除的是中间的元素,直接使用「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; // 移除哨兵节点返回真实的头节点
}
求和问题需要考虑进位问题,最终结果考虑是否加 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
更多相关专栏内容汇总: