LeetCode第21~25题解

这篇具有很好参考价值的文章主要介绍了LeetCode第21~25题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 21. 合并两个有序链表(简单)

【题目描述】

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

【示例1】

LeetCode第21~25题解,leetcode,算法,职场和发展,学习,c++

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

【示例2】

输入:l1 = [], l2 = []
输出:[]

【示例3】

输入:l1 = [], l2 = [0]
输出:[0]

【提示】

两个链表的节点数目范围是 [0, 50]
− 100 ≤ N o d e . v a l ≤ 100 -100\le Node.val\le 100 100Node.val100
l1l2 均按非递减顺序排列

【分析】


直接模拟即可,每次取两个链表中较小的结点,接到新链表的后面,如果其中一个链表空了,则直接将另一个链表接到新链表的后面。


【代码】文章来源地址https://www.toymoban.com/news/detail-681505.html

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        auto dummy = new ListNode(-1), cur = dummy;  // 用auto才能并排写
        while (list1 && list2)
            if (list1->val < list2->val) cur = cur->next = list1, list1 = list1->next;
            else cur = cur->next = list2, list2 = list2->next;
        if (list1) cur->next = list1;
        else if (list2) cur->next = list2;
        return dummy->next;
    }
};

LeetCode 22. 括号生成(中等)

【题目描述】

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。

【示例1】

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

【示例2】

输入:n = 1
输出:["()"]

【提示】

1 ≤ n ≤ 8 1\le n\le 8 1n8

【分析】


本题只有小括号,对于这类问题,判断一个括号序列是否合法有一些很重要的推论:

  • 任意前缀中,( 数量一定大于等于 ) 数量(最重要);
  • () 的数量相等。

我们可以使用 DFS 搜索方案,对于每个位置,只要当前 ( 的数量小于 n n n 就可以填入,而填入 ) 需要满足当前 ) 的数量小于 n n n 且小于 ( 的数量。


【代码】

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return res;
    }

    void dfs(int n, int lc, int rc, string now)  // lc和rc分别表示左右括号的数量
    {
        if (lc == n && rc == n) { res.push_back(now); return; }
        if (lc < n) dfs(n, lc + 1, rc, now + '(');
        if (rc < n && rc < lc) dfs(n, lc, rc + 1, now + ')');
    }
};

LeetCode 23. 合并K个升序链表(困难)

【题目描述】

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。

【示例1】

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

【示例2】

输入:lists = []
输出:[]

【示例3】

输入:lists = [[]]
输出:[]

【提示】

k = = l i s t s . l e n g t h k == lists.length k==lists.length
0 ≤ k ≤ 1 0 4 0\le k\le 10^4 0k104
0 ≤ l i s t s [ i ] . l e n g t h ≤ 500 0\le lists[i].length\le 500 0lists[i].length500
− 1 0 4 ≤ l i s t s [ i ] [ j ] ≤ 1 0 4 -10^4\le lists[i][j]\le 10^4 104lists[i][j]104
lists[i]升序排列
lists[i].length 的总和不超过 1 0 4 10^4 104

【分析】


和第21题差不多,我们每次从这 K K K 个链表中找出最小的结点,将其接到新链表的后面,可以使用一个小根堆(优先队列 priority_queue 来维护最小值)。需要注意的是我们需要写一个排序算法,C++ 中优先队列的排序算法不是传入一个函数,而是重载了 () 的结构体,具体实现方式见代码部分。


【代码】

/**
 * 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:
    struct Cmp
    {
        // 默认是大根堆,因此用大于号翻转为小根堆,注意一定要有{}
        bool operator() (ListNode*& a, ListNode*& b) { return a->val > b->val; } 
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto dummy = new ListNode(-1), cur = dummy;
        priority_queue<ListNode*, vector<ListNode*>, Cmp> Q;  // 传入比较结构体
        for (auto list: lists)
            if (list) Q.push(list);  // 判断是否为空
        while (Q.size())
        {
            auto t = Q.top(); Q.pop();
            cur = cur->next = t;
            if (t->next) Q.push(t->next);
        }
        return dummy->next;
    }
};

LeetCode 24. 两两交换链表中的节点(中等)

【题目描述】

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

【示例1】

LeetCode第21~25题解,leetcode,算法,职场和发展,学习,c++

输入:head = [1,2,3,4]
输出:[2,1,4,3]

【示例2】

输入:head = [1,2,3,4]
输出:[2,1,4,3]

【示例3】

输入:head = [1]
输出:[1]

【提示】

链表中节点的数目在范围 [0, 100]
0 ≤ N o d e . v a l ≤ 100 0\le Node.val\le 100 0Node.val100

【分析】


我们通过画图可以更加直观地分析:

LeetCode第21~25题解,leetcode,算法,职场和发展,学习,c++

具体步骤如下:

  1. P->nextP->next->next 存在时,将其分别记为 AB
  2. P->next = B
  3. A->next = B->next
  4. B->next = A
  5. P = A

【代码】

/**
 * 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* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1), cur = dummy;
        dummy->next = head;
        while (cur->next && cur->next->next)
        {
            auto a = cur->next, b = cur->next->next;
            cur->next = b, a->next = b->next, b->next = a, cur = a;
        }
        return dummy->next;
    }
};

LeetCode 25. K 个一组翻转链表(困难)

【题目描述】

给你链表的头节点 head,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

【示例1】

LeetCode第21~25题解,leetcode,算法,职场和发展,学习,c++

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

【示例2】

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

【提示】

链表中的节点数目为 n n n
1 ≤ k ≤ n ≤ 5000 1\le k\le n\le 5000 1kn5000
0 ≤ N o d e . v a l ≤ 1000 0\le Node.val\le 1000 0Node.val1000

【分析】


和上一题的分析类似,我们先画出示意图:

LeetCode第21~25题解,leetcode,算法,职场和发展,学习,c++

具体步骤如下:

  1. 先遍历一次看看 P 后面是否存在 K 个结点,若不存在直接返回结果,若存在则记最后一个结点为 V
  2. 分别将 P->nextP->next->next 记为 AB
  3. P->next = V
  4. A->next = V->next
  5. P = A
  6. B->next 记为 C
  7. B->next = A
  8. A = B, B = C
  9. 重复6~8共 K − 1 K-1 K1 次。

【代码】

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1), cur = dummy;
        dummy->next = head;
        while (true)
        {
            auto v = cur;
            for (int i = 0; i < k; i++)
                if (v->next == nullptr) return dummy->next;
                else v = v->next;
            auto a = cur->next, b = cur->next->next;
            cur->next = v, a->next = v->next, cur = a;
            for (int i = 0; i < k - 1; i++)
            {
                auto c = b->next;
                b->next = a, a = b, b = c;
            }
        }
        return dummy->next;  // 此行避免报错,不会执行
    }
};

到了这里,关于LeetCode第21~25题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode算法系列题解】第46~50题

    【题目描述】 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以按 任意顺序 返回答案。 【示例1】 【示例2】 【示例3】 【提示】 1 ≤ n u m s . l e n g t h ≤ 6 1le nums.lengthle 6 1 ≤ n u m s . l e n g t h ≤ 6 − 10 ≤ n u m s [ i ] ≤ 10 -10le nums[i]le 10 − 10 ≤ n u

    2024年02月10日
    浏览(35)
  • 【LeetCode算法系列题解】第26~30题

    【题目描述】 给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以

    2024年02月10日
    浏览(40)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(42)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(53)
  • LeetCode算法题解(回溯)|39. 组合总和、40. 组合总和 II、131. 分割回文串

    题目链接:39. 组合总和 题目描述: 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数

    2024年02月05日
    浏览(62)
  • python - leetcode - 424. 替换后的最长重复字符【经典题解 - 贪心滑动窗口算法】

    描述: 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回包含相同字母的最长子字符串的长度。 示例 1: 示例 2: 提示: 1 = s.length = 105 s 仅由大写英文字母组成 0 =

    2024年02月16日
    浏览(48)
  • 学习平台助力职场发展与提升

    近年来,随着互联网技术的发展, 学习平台 逐渐成为了职场发展和提升的必备工具。学习平台通过提供丰富的课程内容、灵活的学习时间和个性化的学习路径,帮助职场人士更好地提升自己的技能和知识储备,为职场发展打下坚实的基础。 学习平台的优势在于提供了丰富多

    2024年02月11日
    浏览(51)
  • LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)

    参考前文 参考文章: LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和) LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II) LeetCode链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 首先 sor

    2024年02月09日
    浏览(46)
  • LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​

    题目链接:669. 修剪二叉搜索树 题目描述: 给你二叉搜索树的根节点  root  ,同时给定最小边界 low  和最大边界  high 。通过修剪二叉搜索树,使得所有节点的值在 [low, high] 中。修剪树  不应该  改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关

    2024年02月06日
    浏览(37)
  • 【LeetCode】剑指 Offer(25)

    目录 题目:剑指 Offer 49. 丑数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 丑数这道题用到一点动态规划的思想, 具体思路如下: 根据题意: 如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数, 那么我们发现,之后的丑数: 都是前

    2023年04月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包