240426 leetcode exercises-EW帮帮网

240426 leetcode exercises

@jarringslee

文章目录

240426 leetcode exercises

1669. 合并两个链表

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

示例 1：
输入：list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[10,1,13,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

还是一道练增删改查基本功的题。让你把第一个链表从某两点断开并删除中间节点，并拼上新的链表。用正常的思路就能解决：

找断点
断链表1
接链表2
拼剩余的链表1

🔁基础版保存断点，先拼再补

我们首先找到结点a和的具体位置并保存。

? 为什么不能先找a,把a拼在list2上,再找b并拼接?

我们在找a并把它拼到list2的时候已经修改了list1的结点了。所以在根据b来找结点肯定找不着。所以要提前找好节点方便后续操作。

因为要从第a个结点开始删除。所以我们让指针走向第a - 1个结点。

b的话因为我们后面会直接拼上b节点的next指针，即第b + 1个结点。所以正常遍历就好。

接下来让保存好的a + 1结点接上list2。

我这里新定义了一个节点preA来便利链表二，这样比较严谨。其实可以直接让刚才拼到list2的那个指针去遍历的。

最后让让遍历到list2的尾结点的指针拼上刚才找到结点b的指针。

返回list1。

struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2) {
    // 找到第 a-1 个节点
    struct ListNode* preA = list1;
    a -= 1;
    while (a-- > 0) {
        preA = preA->next;
    }

    // 找到第 b 个节点
    struct ListNode* bNode = list1;
    while (b-- > 0) {
        bNode = bNode->next;
    }

    // preA 后接 list2
    preA->next = list2;

    // 找到 list2 的尾节点
    struct ListNode* tail = list2;
    while (tail->next) {
        tail = tail->next;
    }

    // list2 尾接 afterB
    tail->next = bNode->next;

    return list1;
}

🔁进阶版一遍到位，直接拼接

preA 一开始指向 list1，负责走到第 a-1 个节点。
bNode 同时指向 list1，负责走到第 b 个节点。
两个 while循环独立，分别移动到准确位置。

连接阶段一：

直接把 preA->next = list2;，也就是a-1 节点后面接上整个 list2。

连接阶段二：

继续用 list2（注意！此时 list2 是指向 list2 的头结点）一路往后遍历到 list2 的最后一个节点。

连接阶段三：

把 list2 的尾节点 list2->next 指向原链表的 bNode->next，也就是第 b+1 个节点。

最后 return list1。

struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2) {
    struct ListNode *preA = list1, *bNode = list1;
    a -= 1;
    while (a-- > 0) preA = preA->next;
    while (b-- > 0) bNode = bNode->next;
    preA->next = list2;
    while (list2->next) list2 = list2->next;
    list2->next = bNode->next;

    return list1;
}

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0

这道题看似需要从头到尾找一遍。我首先想到的思路是正常遍历，快慢指针按顺序走，通过对比前后元素的方式找到并记录无序的地方并返回长度。但是如果从结果来看，我们只需要找到无序的部分。那你倒过来想，其他地方都是有序的，我们如果找有序的地方，无序的子数组就是剩下的地方。会不会简单一点？

🔁排序 + 双指针遍历

复制一份原数组，对其进行尊贵的快排，然后进入比对：

找左右边界

我们把排序好的数组分别从两头开始遍历。从左向右，找到第一个使得 nums[l] != sorted[l] 的位置停止。从右向左也是一样。

计算长度

如果整个数组已经有序，那么上述过程可能找不到任何不等的位置，此时 l 会跑到 n，r 会跑到 -1，或者在两指针相遇时都没发现不等。此时直接返回 0。否则，我们需要的整数n就是左右两指针之间无序子数组的长度，即 r - l + 1。


int cmp(const void *a, const void *b) {
    return (*(int*)a) - (*(int*)b);
}

int findUnsortedSubarray(int* nums, int numsSize){
    if (numsSize < 2) return 0;
    // 排序
    int *sorted = malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++)
        sorted[i] = nums[i];
    qsort(sorted, numsSize, sizeof(int), cmp);

    // 找左右边界
    int l = 0, r = numsSize - 1;
    while (l < numsSize && nums[l] == sorted[l]) l++;
    while (r >= 0 && nums[r] == sorted[r]) r--;

    free(sorted);
    // 3计算并返回
    return (l < r) ? (r - l + 1) : 0;
}

240426 leetcode exercises