当前位置：首页 > 编程日记 > 正文

leetcode-23 合并K个排序链表

编程日记 2024-04-15 01:00:00

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

方法一：
使用vector数组存多个链表的所有节点，进行从小到大的排序，完成后再进行元素的指向，从第一个元素指向最后一个元素

bool cmp(ListNode *l1, ListNode *l2) {return l1 -> val < l2 -> val;
}ListNode* mergeKLists(vector<ListNode*>& lists) {vector<ListNode *> node_vec;for (int i = 0;i < lists.size();   i) {while(lists[i]){node_vec.push_back(lists[i]);lists[i] = lists[i] -> next;}}if (node_vec.size() == 0) {return NULL;}//从小到大排序std::sort(node_vec.begin(), node_vec.end(), cmp);for(int i = 1;i < node_vec.size();   i) {node_vec[i-1] -> next = node_vec[i];}//将最后一个元素的next指针指向空node_vec[node_vec.size() - 1] -> next = NULL;return node_vec[0];
}

时间复杂度：
设有k个链表，平均每个链表有n个节点
kNlogkN kN = O(kNlogkN)

方法二：
分治法，即将所有链表分治合并为两个链表，再将两个链表合并为一个有序链表
实现如下:

//合并两个链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode new_head(0);ListNode *pre_new = &new_head;while(l1 && l2) {if (l1 -> val < l2 -> val) {pre_new -> next = l1;l1 = l1 -> next;} else {pre_new -> next = l2;l2 = l2 -> next;}pre_new = pre_new -> next;}if (l1) {pre_new -> next = l1;} if (l2) {pre_new -> next = l2;}return new_head.next;
}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size() == 0) return NULL;if (lists.size() == 1) return lists[0];if (lists.size() == 2) {return mergeTwoLists(lists[0],lists[1]);}int mid = lists.size() / 2;vector<ListNode *> sub_list1;vector<ListNode *> sub_list2;for (int i = 0;i < mid; i  ) {sub_list1.push_back(lists[i]);}for (int i = mid;i < lists.size();   i) {sub_list2.push_back(lists[i]);}/*分治链表节点，两两合并*/ListNode *l1 = mergeKLists(sub_list1);ListNode *l2 = mergeKLists(sub_list2);return mergeTwoLists(l1,l2);
}

时间复杂度：
设有k个链表，平均每个链表有n个节点
第1轮，进行k/2次，每次处理2n个数字;
第2轮，进行k/4次，每次处理4n个数字;…;
最后一次，进行k/(2^{logk)次，每次处理2}logk*N个值。

2N*k/2 4N * k/4 8N * k/8 … 2^logk * N * k/(2^logk) =Nk Nk … Nk = O(kNlogk)

方法三：
使用队列，将K个链表插入队列，两两合并后放入队尾，直到队列中只有一个元素
实现如下:

ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size() == 0) {return NULL;}if (lists.size() == 1) {return lists[0];}//将vector转为队列queue<ListNode*> waiting(deque<ListNode*>(lists.begin(), lists.end()));while(waiting.size() > 1) {ListNode *l1 = waiting.front();waiting.pop();ListNode *l2 = waiting.front();waiting.pop();ListNode *p = mergeTwoLists(l1,l2);//见如方法二中的实现waiting.push(p);}return waiting.front();
}

时间复杂度：
(k-1)*n (k - 2)*n … n = n(k-1)*k/2
O(nk^2)

https://www.dkcj.cn/info/4691.html

Access应用日志一

今天在确认实习生不能帮忙搭建数据库后，自己根据业务需求尝试搭了一个小型access数据库。主要目的：储存历史月度数据，避免每次从公司数据库下载数据的麻烦，节省数据拉取时间。搭建了以acct id为主键的两种数据。 1）客…

编程日记2024/04/15 00:30:00

mongodb检查点_mongodb 监控命令mongostat

mongodb 监控命令mongostat2016/03/07 15:11 于数据分析mongostat实用工具提供了mongoDB一个实例快速概述和当前运行的状态。mongostat功能类似于UNIX / Linux文件系统实用vmstat,mongostat只不过是提供 mongodb 的数据。监控包含的数据：服务器状态数据副本状态数据…

编程日记2024/04/15 00:00:00

RunnableException与CheckedException

Checked Exception 编译时异常编译的时候检查你的代码可能在运行的时候抛出异常，这通常在编译的时候要去处理的。 RunnableException 运行时异常，可以编译通过，但如果不处理运行时会导致崩溃，需要对其进行try....catch...处理。 …

编程日记2024/04/14 23:30:00

Educational Codeforces Round 59 (Rated for Div. 2)

A.Digits Sequence Dividing 题意：给你一个1-9的数字字符串，把它划分成若干段（>2）段，使其大小递增。错误：当长度为2的时候没考虑 #include<cstdio> #include<cmath> #include<cstring&g…

编程日记2024/04/14 23:00:01

leetcode-225 队列实现栈

使用队列实现栈的下列操作： push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空队列的特点：先入先出栈的特点：后入先出即我们每次添加元素到队列时，想要达到栈的效果，…

编程日记2024/04/14 22:30:00

详解Java Math类的toDegrees()方法：将参数从弧度转换为角度

Java Math 类的 toDegrees() 方法是将一个角度的弧度表示转换为其度表示，返回值为double类型，表示从弧度数转换而来的角度数。这就是Java Math 类的 toDegrees() 方法的攻略。我们已经了解了该方法的基本概念、语法、注意事项以及两个示例。希望这篇攻略对你有所帮助。

编程日记2024/04/14 22:00:02

python语音合成标贝_tacotronV2 + wavernn 实现中文语音合成(Tensorflow + pytorch)

TacotronV2 WaveRNN开源中文语音数据集标贝(女声)训练中文TacotronV2，实现中文到声学特征(Mel)转换的声学模型。在GTA模式下，利用训练好的TacotronV2合成标贝语音数据集中中文对应的Mel特征，作为声码器WaveRNN的训练数据。在合成阶段&#x…

编程日记2024/04/14 22:00:00

作为一名老码农，在开发后端Java业务系统，包括各种管理后台和小程序等。在这些项目中，我设计过单/多租户体系系统，对接过许多开放平台，也搞过消息中心这类较为复杂的应用，但幸运的是，我至今还没有遇到过线上系统由于代码崩溃导致资损的情况。这其中的原因有三点：一是业务系统本身并不复杂；二是我一直遵循某大厂代码规约，在开发过程中尽可能按规约编写代码；三是经过多年的开发经验积累，我成为了一名熟练工，掌握了一些实用的技巧。啥是防抖所谓防抖，一是防用户手抖，二是防网络抖动。

编程日记2024/04/14 21:30:02

OC语言基础笔记

OC方面的基础笔记:1.类的基本用法#import <Foundation/Foundation.h>// 大体上就是include, 用于包含头文件, 但是即使头文件中, 没有ifndef defined endif, 仍然能够踢除重复包含的头文件// ----interface section----// OC中声明和实现是分离的, 两个都必须有.interfac…

编程日记2024/04/14 21:30:00

Docker 数据卷之进阶篇

Docker 数据卷之进阶篇原文:Docker 数据卷之进阶篇笔者在《Docker 基础 : 数据管理》一文中介绍了 docker 数据卷(volume) 的基本用法。随着使用的深入，笔者对 docker 数据卷的理解与认识也在不断的增强。本文将在前文的基础上介绍 docker 数据卷的原理及一些高级用…

编程日记2024/04/14 21:00:01

leetcode-232 用栈实现队列

使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。pop() – 从队列首部移除元素。peek() – 返回队列首部的元素。empty() – 返回队列是否为空栈的特点：后入先出队列的特点：先入先出使用一个数据栈，一个辅…

编程日记2024/04/14 20:30:00

sparkcore分区_Spark学习：Spark源码和调优简介 Spark Core (二）

本文基于 Spark 2.4.4 版本的源码，试图分析其 Core 模块的部分实现原理，其中如有错误，请指正。为了简化论述，将部分细节放到了源码中作为注释，因此正文中是主要内容。第一部分内容见：Spark学习：…

编程日记2024/04/14 20:00:01

Tips——IndexSearcher自动更新

情景描述为了调高效率，创建全局变量IndexReader取代每次查询新建IndexReader所带来的效率问题。当时每天会更新一边索引8.23号部署的Index服务，Search服务，结果index都更新到了8.25，查询结果还是8.23的 Tips分享先来看一下Inde…

编程日记2024/04/14 19:30:00

公司运作 - 利润率、周转率

公司一般由市场部、研发部、财务部、人力资源部及其他辅助部门组成。分成了几个层面，如下： 宏观层面：业务范围、业务定位、专业化、多元化部门层面：各部门绩效、部门职责主体层面：跨部门事务，如产品研发涉及…

编程日记2024/04/14 19:00:00

测试用例设计方法基础理论知识

一、什么是测试用例测试用例设计：将软件测试的行为活动，作为一个科学化的组织归纳。测试用例：设计一个情况，软件程序在这种情况下，必须能够正常运行并且达到程序所设计的执行结果。因为我们不可能进行穷举测试&…

编程日记2024/04/14 18:30:00

leetcode-155 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。示例： MinStack minStack new Mi…

编程日记2024/04/14 18:00:00

legend位置 pyecharts_可视化入门 | pyecharts全局配置项详解

更多文章，请见：http://mp.weixin.qq.com/mp/homepage?__bizMzIxODczMDUwOA&hid2&sn7928727456d49032f08ef1fcf0ee719e&scene18#wechat_redirectmp.weixin.qq.com大家好，我是你们的机房老哥！ 计算机绘图是老哥很早就…

编程日记2024/04/14 17:30:00

查询Master下的系统表和系统视图获取数据库的信息和简单的渗透测试

在SQL中可以通过查询Master下的系统表（sys）和系统视图（information_schema）获取数据库的信息。SQL2000和SQL2005的结构略有不同。系统表结构参考系统表详细说明。系统信息结构图参考：http://dev.mysql.com/doc/refma…

编程日记2024/04/14 17:00:01

cocos2d-x android 移植问题

为什么80%的码农都做不了架构师？>>> 由于android系统目前没有将boost加入，这里面使用了大量的STL及C的一些语言特性，导致编译出现令人非常头痛的问题。 1、出现类似的异常函数错误 boost/exception/detail/exception_ptr.hpp:382…

编程日记2024/04/14 16:30:00

python插入排序演示源码

工作闲暇时间，把写内容过程较好的内容段做个备份，下面的内容内容是关于python插入排序演示的内容，应该能对各朋友也有用处。 def insert_sort(t): for i in xrange(len(t)): key t[i] j i - 1 while j>-1 and t[j]>key:#如果当前值比…

编程日记2024/04/14 16:00:01

leetcode-215 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: [3,2,1,5,6,4] 和 k 2 输出: 5 该题比较简洁的解法，我们使用堆来完成最小堆：即堆顶为所…

编程日记2024/04/14 15:30:00

c++ double 只输出五位_c 语言第四章在控制台上数据的输入和输出

1 数据输出我们之前已经使用过printf()函数来实现数据在控制台上输出#include<stdio.h> int main(){printf("hello world");return 0; }具体的用法是printf("数据模板",数据1,数据2,...)// 数据模板表示输出数据的形式,里面包含占位符,打印的时候使用…

编程日记2024/04/14 15:00:00

pyQt 每日一练习 -- 登录框

#codingutf-8#第一个练习，登录框import sys from PyQt4 import QtGui,QtCore#登录框 class LoginBox(QtGui.QWidget):def __init__(self):super(LoginBox, self).__init__()self.initUI()def initUI(self):vBoxLayout QtGui.QVBoxLayout()hBoxLayout_1 QtGui.QHBo…

编程日记2024/04/14 14:30:00

photoshop CS5 Dreamweaver CS5序列号及完美破解方法

adobe photoshop CS5 的序列号（任选一个）1330-1440-1602-3671-9749-78971330-1191-2998-6712-2520-54241330-1367-4285-4928-0630-31071330-1570-9599-9499-8092-82371330-1028-1662-3206-1688-51141330-1631-5733-5042-4138-6389 Adobe Dreamweaver CS…

编程日记2024/04/14 14:00:00

[原创]Android Monkey 在线日志分析工具开发

[原创]Android Monkey 在线日志分析工具开发在移动App测试过程中,Monkey测试是我们发现潜在问题的一种非常有效手段，但是Android原生的Monkey有其天然的不足，数据不能有效的去解读，同时也不能提供非常清晰的信息，所以针对这个问题…

编程日记2024/04/14 13:30:00

leetcode-295 数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 3) / 2 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数…

编程日记2024/04/14 13:00:00

Servlet开发入门

Servlet是sun公司提供的一门用于开发动态web资源的技术。 Sun公司在其API中提供了一个servlet接口，用户若想开发一个动态web资源(即开发一个Java程序向浏览器输出数据)，需要完成以下2个步骤： 编写一个Java类，实现servlet接口。把开…

编程日记2024/04/14 12:30:00

#串口通信超时处理_简单通信协议

用C语言做物联网网关开发时，经常需要通过串口、485接口等从一些传感器读取数据，由于网关设备和传感器所处的环境复杂多样，电磁干扰等常常会破坏传输的数据，为了确保传输数据的可靠性，通常会采取一些策略，常…

编程日记2024/04/14 12:00:00

在cmd的方式下，简化mysql的输入的方法

2019独角兽企业重金招聘Python工程师标准>>> 在我的电脑，高级系统设置，环境变量，path 添加运行的mysql.exe的路径。转载于:https://my.oschina.net/u/779687/blog/140411

编程日记2024/04/14 11:30:00

Parser Generator Tips翻译(中英对译) by Joshua Xu

You can use the ParserWizard command from the Project menu to help you create initial YACC and Lex skeleton source files.如果需要生成初始的YACC & Lex骨架源文件，可以在系统菜单中，选取Project->ParserWizard。Use the Parser Generato…

编程日记2024/04/14 11:00:00