算法题技巧速记

备注

持续更新

思路

  • 如果数组已经排序,可以考虑二分,时间复杂度O(log2n)。
  • 如果空间要求O(1),需要确认原始数组能否修改,可以考虑原址排序,利用数组读写的时间复杂度均O(1)的性质。
  • 指针访问成员操作,都需要判断非NULL。
  • dfs/bfs入栈时,即刻修改条件。
  • 容器size返回unsigned int,需要处理后加入int运算。

贪心

  • 复杂度O(n)

双指针

142. Linked List Cycle II (Medium)

题干

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改链表。

题解

简单的说,这道题的意思就是,如果链表里有环,那找环的起点。那么,很明显这题有两个目标,第一是判断链表是否有环,第二是判断环起点位置。

if (有环()) {
    return 获取环位置();
} else {
    return -1;
}

对于链表有环的判断,可以使用快慢指针同时从起点出发,如果没环,快指针一定能到链表终点。但是如果有环的话,我们的循环要停下来,需要停止条件
如果快指针和慢指针停在了相同的位置,就意味着他们一定出现了快指针在慢指针后面,追逐慢指针的情况,导致这个情况的原因就是链表有环,把本该走在前面的快指针传送到慢指针的后面。由此,我们得到了链表环判断的方法。

bool HasCycle(ListNode *head) { // 是否有环
    if (head == nullptr) {return false;} // 注意判空
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr) {
        slow = slow->next;
        if (fast->next == nullptr) {
            return false; // 快指针抵达终点,无环
        }
        fast = fast->next->next;
        if (fast == slow) { // 停止条件
            return true;
        }
    }
    return false; // 快指针抵达终点,无环
}

接下来我们要计算环的起点。很明显,当前快慢指针汇聚的位置作为我们已知的信息,非常重要。我们以这个为突破口,可以倒推环的起点。

如图,若链表未成环的长度为a,环起点到汇合点长度为b,汇合点回到环起点长度为c,设快指针在环内走了n圈可得
2(a+b)=a+(n+1)b+nc
简化可得
a=(n-1)b+nc=n(b+c)-b
可以理解为,a的长度等价于在环中走n圈,再向回退b的长度,而此时,已经有先前的快慢指针指向了b的位置,可以简单的让当前的慢指针向前走a的长度,就会回到环的起点。
如何让慢指针走a的长度呢?我们只需要再安排一个新指针同时从头开始走,当新指针走到a的长度时,位于环起点,慢指针此时也走了a的长度,位于环起点,则只需要判断两个指针相遇,他们处于的位置即是环起点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode * detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr) {
        slow = slow->next;
        if (fast->next == nullptr) {
            return nullptr;
        }
        fast = fast->next->next;
        if (fast == slow) { // 以下是获取起点的代码
            fast = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
    return nullptr;
}