LeetCode 刷题笔记

19. 删除链表的倒数第 N 个结点

题源：2009年408题源
要求：使用一趟扫描完成

思路一：快慢指针(高效)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;   // 快指针，永远比slow快n个
        ListNode* slow = head;   // 慢指针，最终指向待删除节点的前驱节点

        // 将快指针向后移动n个(题目已确保数据合法)
        for(int i = 0; i < n; i ++)
            fast = fast -> next;
        
        // 在快指针未到末尾的条件下将快慢指针同时向后移动直到快指针抵达末尾
        while(fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next;
        }

        // 此时快指针抵达末尾节点
        if(fast) {
            // 此时n<sz
            slow -> next = slow -> next -> next;
            return head;
        } else {
            // 此时n=sz
            return head -> next;
        }            
    }
};

189. 轮转数组

题源：2010年408题源
要求：使用原地算法(即空间复杂度为O(1))解决此题
注意：C语言的 memcpy 函数不可处理源内存片和目标内存片有重合的情况，否则属于未定义行为。而其升级版 memmove 函数已经不再是原地算法。

思路一：使用类似于冒泡排序的思想，每次操作只转动一次数组，直到转动(k%size)次

时间复杂度：$$O(k\times Size)\approx O(Size^2)$$
空间复杂度：$$O(1)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void rotate(int* nums, int numsSize, int k) {
    //每次将队尾元素"冒泡"至队头，其他元素相对位置不变。
    k %= numsSize;                        //对numsSize取余
    int tail = 0;                         //本变量用于存储每次"冒泡"的队尾元素
    for(int t = 0; t < k; t++)
    {
        tail = *(nums + numsSize - 1);    //取队尾元素
        for(int i = numsSize - 1; i > 0; i--)
        {
            *(nums + i) = *(nums + i - 1);
        }
        *nums = tail;
    }
}

运行结果：超时(但是算法应该正确)

思路二：直接使用C标准库

时间复杂度：$$O(1)$$
空间复杂度：$$O(Size)$$

1
2
3
4
5
6
7
8
void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    int* temp = malloc(sizeof(int) * numsSize);
    memcpy(temp, nums + (numsSize - k), k * sizeof(int));
    memcpy(temp + k, nums, (numsSize - k) * sizeof(int));
    memcpy(nums, temp, numsSize * sizeof(int));
    free(temp);
}

运行通过。

思路三：数组二次翻转

参考题解：https://leetcode.cn/problems/rotate-array/solutions/683855/shu-zu-fan-zhuan-xuan-zhuan-shu-zu-by-de-5937
时间复杂度：$$O(2n)$$
空间复杂度：$$O(1)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void reverse(int *nums, int numsSize) {
    for(int i = 0; i < numsSize / 2; i++)
    {
        int temp = *(nums + i);
        *(nums + i) = *(nums + numsSize - i - 1);
        *(nums + numsSize - i - 1) = temp;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    //第一次翻转
    reverse(nums, numsSize);
    //分别翻转[0, k], [k+1, numSize]两个子数组
    reverse(nums, k);
    reverse(nums + k, numsSize - k);
}