数组

列举一些数组常见的处理手段，供发散思维，寻找解题切入点：

  • 排序：排序之后更容量对数组进行遍历与查找，比如使用二分算法。
  • map<int, int> count：使用map记录每个数字出现的次数。
  • map<int, int> index：针对无重复元素的数组，使用map记录下标，方便索引。
  • 前缀和：用于快速求区间和，参考 前缀和。
  • 双指针：用于滑动窗算法，参考 双指针&滑动窗口。
  • 栈，队列，最大最小堆等。


一些数组操作技巧：

  • 数组元素循环右移n位：先反转开头的n个元素，再反转剩下的元素，再反转整个数组。

链表

链表相关的解题技巧与示例应用。

链表定义

// 单向链表
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 双向链表
struct Node {
    int val;
    Node *prev;
    Node *next;
};

链表需要一个链表头用于遍历整个链表，实际使用时，可以直接将链表的第一个结点作为链表头，也可以为链表单独设置一个链表头结点，这个头结点不存储数据，数据从头结点的下一个结点开始存储。

带独立头结点的链表在插入和删除时操作相对简单，因为不需要考虑插入前或删除后链表为空的情况。

哨兵节点

在插入或删除链表节点时，如果链表没有单独的头结点，则需要处理边界条件，也就是插入前链表为空，或是删除的是头结点的情况，为了简化问题，可以在头部加入一个哨兵节点，以简化操作，如下：

链表插入：

// 在头结点为head的链表结尾插入新结点val
ListNode* append(ListNode *head, int val) {
    ListNode dummy;
    dummy.next = head;
    ListNode *node = &dummy;
    while(node->next != nullptr) {
        node = node->next;
    }
    node->next = new ListNode(val);
    return dummy.next;
}

链表删除：

// 删除链表中值为val的结点
ListNode *remove(ListNode *head, int val) {
    ListNode dummy;
    dummy.next = head;
    ListNode *node = &dummy;
    while(node->next != nullptr) {
        if(node->next->val == val) {
            node->next = node->next->next;
            break;
        }
        node = node->next;
    }
    return dummy.next;
}

快慢指针

使用快慢指针可以轻松解决以下这类的问题：

  • 定位到链表的中间结点
  • 定位到链表的倒数第k个结点
  • 找到链表中环的入口节点

对于定位链表中间结点，我们可设置两个指针p1和p2，初始时都指向链表头，然后p1一次走一步，p2一次走两步，当p2到达链表尾部时，p1所指的位置必然是链表的中间结点：

ListNode *middleNode(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


对于定位到链表的倒数第k个结点，同样是使用快慢指针p1和p2，让p2先走k步，再p1、p2一起走，这样，当p2到达链表尾部时，p1指向的就是链表的倒数第k个结点：

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode *slow = head;
    ListNode *fast = head;
    while(k--) {
        fast = fast->next;
    }
    while(fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}


对于寻找链表中环的入口节点，

问题示例


  • O(1)时间删除单链表指定结点：

    node->val = node->next->val;
node->next = node->next->next;

    缺陷：只能应用于除尾结点之外的结点，如果删除的是尾结点，则只能从头遍历。



  • 无标签