[Algorithm][综合训练][合并k个已排序的链表][dd爱旋转][小红取数]详细讲解

目录

  • 1.合并k个已排序的链表
    • 1.题目链接
    • 2.算法原理讲解 && 代码实现
  • 2.dd爱旋转
    • 1.题目链接
    • 2.算法原理详解 && 代码详解
  • 3.小红取数
    • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.合并k个已排序的链表

1.题目链接

  • 合并k个已排序的链表

2.算法原理讲解 && 代码实现

  • 自己的解法:堆 -> 将全部节点丢入堆中
    class Solution 
    {typedef pair<int, ListNode*> PIL;
    public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<PIL, vector<PIL>, greater<>> heap;for(const auto& list : lists){ListNode* cur = list;while(cur){heap.push({cur->val, cur});cur = cur->next;}}ListNode* newHead = new ListNode(0);ListNode* tail = newHead;while(heap.size()){ListNode* node = heap.top().second;heap.pop();tail->next = node;tail = tail->next;}tail->next = nullptr;tail = newHead->next;delete newHead;return tail;}
    };
    
  • 优化解法:堆 -> 只存入每个链表的头结点,出堆时,再压入下一个节点
    • 对自己的版本进行了时间上和空间上的优化
    • 并且对堆排序时的比较方法进行了优化
    class Solution 
    {struct CMP{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};
    public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, CMP> heap;for(auto head : lists){if(head != nullptr){heap.push(head);}}ListNode* newHead = new ListNode(0);ListNode* tail = newHead;while(heap.size()){ListNode* tmp = heap.top();heap.pop();tail = tail->next = tmp;if(tmp->next != nullptr){heap.push(tmp->next);}}tail = newHead->next;delete newHead;return tail;}
    };
    

2.dd爱旋转

1.题目链接

  • dd爱旋转

2.算法原理详解 && 代码详解

  • 解法:模拟 + 优化
    • 180° --> 一次行对称 + 一次列对称
    • 行列的顺序无所谓
    • 如果为偶数次,则无需变换
    #include <iostream>
    #include <vector>
    using namespace std;int n = 0;
    vector<vector<int>> matrix;void SwapRol() // 行对称
    {for(int i = 0; i < n / 2; i++){for(int j = 0; j < n; j++){swap(matrix[i][j], matrix[n - 1 - i][j]);}}
    }void SwapCol() // 列对称
    {for(int j = 0; j < n / 2; j++){for(int i = 0; i < n; i++){swap(matrix[i][j], matrix[i][n - 1 - j]);}}
    }int main()
    {cin >> n;matrix.resize(n, vector<int>(n, 0));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> matrix[i][j];}}int q = 0, x = 0;cin >> q;int row = 0, col = 0;while(q--){cin >> x;if(x == 1){row++, col++;}else{row++;}}if(row %= 2){SwapRol();}if(col %= 2){SwapCol();}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << matrix[i][j] << " ";}cout << endl;}return 0;
    }
    

3.小红取数

1.题目链接

  • 小红取数

2.算法原理详解 && 代码实现

  • 解法:01背包 + 同余(倍数问题可以转换为余数问题)
    • 同余定理
      请添加图片描述

    • 状态表示dp[i][j]:从前i个数中挑选,总和%k等于j时,最大和是多少

    • 状态转移方程
      请添加图片描述

    • 初始化
      请添加图片描述

    • 返回值dp[n][0] --> 因为k的倍数的余数为0

    #include <iostream>
    #include <vector>
    #include <climits>
    using namespace std;int main()
    {int n = 0, k = 0;cin >> n >> k;vector<long long> nums(n + 1, 0);for(int i = 1; i <= n ; i++){cin >> nums[i];}vector<vector<long long>> dp(n + 1, vector<long long>(k, LLONG_MIN));dp[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < k; j++){dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i] % k + k) % k] + nums[i]);}}cout << (dp[n][0] <= 0 ? -1 : dp[n][0]) << endl;return 0;
    }
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/413084.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

centos换源安装升级gcc

使用devtools升级安装的时候&#xff0c;由于此库已经停止更新 了&#xff0c;因此需要切换阿里源 SCLDevtoolset 安装与使用笔记-腾讯云开发者社区-腾讯云 (tencent.com)https://cloud.tencent.com/developer/article/1889181 1 yum 安装 yum install centos-release-scl c…

前后端交互的路径怎么来的?后端解决cors问题的一种方法

背景&#xff1a;后端使用node.js搭建&#xff0c;用的是express 前端请求的路径baseURL怎么来的 &#xff1f; 前后端都在同一台电脑上运行&#xff0c;后端的域名就是localhost&#xff0c;如果使用的是http协议&#xff0c;后端监听的端口号为3000&#xff0c;那么前端请求…

Qt 调用MFC dll,动态库中有界面

一、创建MFC 动态库工程 下一步 创建 点击确定 二、创建接口 这个是系统创建的&#xff0c;改成自己的接口。 头文件&#xff1a; #ifndef __WEB_ENGINE__ #define __WEB_ENGINE__#ifdef __cplusplus extern "C" { #endif__declspec(dllexport) bool __stdcall Loa…

10款必备的电脑监控软件推荐,实用又方便!顶尖产品一网打尽!2024纯干货

电脑监控软件目前是企业管理不可或缺的一部分&#xff0c;它们不仅能够帮助企业提升工作效率&#xff0c;还能有效保障信息安全。本文将为您推荐10款2024年必备的电脑监控软件&#xff0c;这些顶尖产品以其强大的功能和便捷的操作&#xff0c;赢得了市场的广泛认可。 接下来&am…

【Python实战因果推断】73_图因果模型8

目录 Adjusting for Selection Bias Conditioning on a Mediator Adjusting for Selection Bias 不幸的是&#xff0c;纠正选择偏倚绝非易事。在我们一直在讨论的例子中&#xff0c;即使有随机对照试验&#xff0c;ATE也无法识别&#xff0c;仅仅是因为你无法在对那些回应了…

前端性能优化--元素类型和dom层级

展示相同布局&#xff0c;使用控制变量法&#xff0c;对比性能差距 1. 结论&#xff1a;用块级元素模拟行内元素时&#xff0c;会有性能浪费&#xff0c;所以能用行内元素的&#xff0c;就不要使用块元素(能用span就不用div) 2. 结论&#xff1a;行内元素模拟块级元素时&…

Feign的原理及概念

1.什么是Feign Feign是Netflix开发的声明式、模板化的HTTP客户端&#xff0c;Feign可帮助我们更加便捷、优雅地调用HTTP API。Feign可以做到使用HTTP请求远程服务时就像调用本地方法一样的体验&#xff0c;开发者完全感知不到这是远程方法&#xff0c;更感知不到这是个HTTP请求…

3.美食推荐系统(Java项目springboot和vue)

目录 0.系统的受众说明 1 绪论 1.1研究背景 1.2研究现状 1.3研究内容 2 系统关键技术 2.1 Springboot框架 2.2 JAVA技术 2.3 MYSQL数据库 2.4 B/S结构 3 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2经济可行性 3.1.3操作可行性 3.2 系统性能分析 3.3 系统功能分析 3.4系统…

c#笔记5 详解事件的内置类型EventHandler、windows事件在winform中的运用

为什么要研究这一问题&#xff1f; 事件和委托可以说是息息相关。 前面先解释了什么是委托&#xff0c;怎么定义一个委托以及怎么使用匿名方法来内联地新建委托。 事实上事件这一机制在c#的程序开发中展很重要的地位&#xff0c;尤其是接触了winform软件开发的同学们应该都知…

基于django的在线音乐网站设计/基于python的音乐播放系统

Django在线音乐网站设计 摘要&#xff1a;计算机网络如果结合使用信息管理系统&#xff0c;能够提高管理员管理的效率&#xff0c;改善服务质量。优秀的在线音乐网站设计能够更有效管理音乐资讯规范&#xff0c;帮助管理者更加有效管理音乐网站&#xff0c;可以帮助提高克服人工…

Linux驱动(一):环境搭建及介绍

目录 前言一、硬件配置及SDK包1.硬件核心芯片2.瑞芯微原厂SDK包 二、环境镜像文件的获取1.镜像文件的组成及启动流程2.获取环境所需的镜像文件2.1 uboot.img2.2 boot.img2.3 rootfs.img2.4 整体编译 三、镜像文件烧录 前言 自用自用自用&#xff0c;晚上睡觉前复盘用。当然&…

8个平面设计必备素材网站,免费下载。

平面设计师应该去哪里找免费可商用素材网站&#xff1f;我推荐这8个&#xff0c;赶紧收藏好。 1、菜鸟图库 菜鸟图库-免费设计素材下载 菜鸟图库是一个非常大的素材库&#xff0c;站内包含设计、办公、自媒体、图片、电商等各行业素材。网站还为新手设计师提供免费的素材&…

查看显卡cuda版本

1.命令行窗口 打开cmd&#xff0c;输入下列语句 nvidia-smi 如下图红框所示&#xff1a; 2.查看cuda版本&#xff0c;打开英伟达控制面板&#xff0c;桌面右键或者系统右下角&#xff0c;然后点击系统信息&#xff0c;之后点击组件

获取当前计算机的处理器架构platform.machine()

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 获取当前计算机的处理器架构 platform.machine() 选择题 关于以下代码的输出结果说法正确的是&#xff1f; import platform print("【执行】print(platform.machine())") prin…

成都高温限电:当电动汽车「无电可充」

8月末的成都&#xff0c;因为高温限电了。 近几日&#xff0c;成都市气象台连续发布了高温红色预警信号。据新华社报道&#xff0c;8月21日&#xff0c;四川电网用电负荷两次创下历史新高&#xff0c;最高达6797万千瓦&#xff0c;较去年最大用电负荷增长近13%&#xff0c;电力…

代码随想录day1数组/字符串总结

二分法 按左闭右闭的区间处理 适合已经完成排序的&#xff0c;找target数——减少暴力遍历 元素移动类题目 两种方法&#xff1a; 1、双指针 移动规则不同&#xff1a; 移动条件不同\fast一次跳两步&#xff0c;slow一次一步 适合解决元素移动/排序/查找 链表中找环 f…

打手机检测算法源码样本展示打手机检测算法实际应用场景介绍

打手机检测算法是一种利用计算机视觉技术来监测和识别人们在特定区域如驾驶舱、考场或其他敏感区域非法使用手机的行为。这种算法对于提高安全性和确保规则的遵守具有重要意义。以下是关于打手机检测算法源码及其实际应用的详细阐述&#xff1a; 1. 算法实现 - 深度学习框架&a…

【北森-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

力扣134-加油站(java题解)

题目链接&#xff1a;134. 加油站 - 力扣&#xff08;LeetCode&#xff09; 前情提要&#xff1a; 因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。 贪心方法&#xff1a;局部最优推出全局最优。 如果一个题你觉得可以用局部最优推出全局最优&#xff0c;并…

源代码编译,Apache DolphinScheduler前后端分离部署解决方案

转载自神龙大侠 生产环境部署方案 在企业线上生产环境中&#xff0c;普遍的做法是至少实施两套环境。 测试环境线上环境 测试环境用于验证代码的正确性&#xff0c;当测试环境验证ok后才会部署线上环境。 鉴于CI/CD应用的普遍性&#xff0c;源代码一键部署是必要的。 本文…