3 开在初夏-命名忧伤

尚未进行身份认证

cs在读研究僧

等级
TA的排名 13w+

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串""。示例1:输入: ["flower","flow","flight"]输出: "fl"示例2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。说明:所有输入只包含小写字母a-z。思路:这题思路不难,但在具体的实现中有...

2019-03-19 09:48:18

13. 罗马数字转整数

罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符 数值I 1V 5X 10L 50C 100D 500M 1000例如, 罗马数字 2 写做II,即为两个并列的 1...

2019-03-04 15:46:16

9. 回文数

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。示例 1:输入: 121输出: true示例 2:输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3:输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文...

2019-01-14 10:54:16

7. 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。示例 1:输入: 123输出: 321 示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21注意:假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。...

2019-01-09 14:47:56

1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]三种解法:...

2019-01-04 17:19:10

部分背包问题(贪心算法)

部分背包问题是基于贪心法的基本思想。何谓贪心法,只要你够贪心,就能领略贪心算法之精髓。部分背包问题和0/1背包问题的区别就是:部分背包问题中的单个物品,可以取一部分装入背包。而0/1背包问题则是要么全部拿走,要么一无所有(这里引用了LOL卡牌大师的台词)。那么作为一个sogreed的你,肯定应该知道按照什么顺序拿物品的把。没错,看着值钱的先抢!这里所说的值钱,指的是单位重量所产生的价...

2018-11-09 20:59:23

7-11 关键活动

7-11 关键活动 (30 分)假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如英语和C程序设计,它们没有必须先修哪门的约束;有些课程则不可...

2018-10-09 19:10:18

7-10 公路村村通

7-10 公路村村通 (30 分)现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。输出格式:...

2018-10-05 15:47:46

7-9 旅游规划

7-9 旅游规划 (25 分)有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。输入格式:输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是...

2018-10-04 09:40:26

7-8 哈利·波特的考试

7-8 哈利·波特的考试 (25 分)哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。现...

2018-09-30 15:48:24

7-7 六度空间

7-7 六度空间 (30 分)“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。图1 六度空间示意图“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许...

2018-09-30 09:16:33

7-6 列出连通集

7-6 列出连通集 (25 分)给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。输入格式:输入第1行给出2个整数N(0<N≤10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。输出格式:按照"{...

2018-09-29 10:49:47

排序算法之基数排序

基数排序(Radix Sort)是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。对于一般的基数排序有通常有两种排序算法:主位优先算法(Most Significant Digit...

2018-09-26 15:42:47

排序之桶排序

如果已知N个关键字的取值范围在0到M-1之间,而M比N小的多,则桶排序则为关键字的每个可能取值建立一个桶,即建立M个桶;在扫描N个关键字时,将每个关键字放入到相应的桶中,然后按照桶的顺序收集一遍就自然有序了。所以桶排序的效率比一般的排序算法效率高-------当然需要的额外条件是已知关键字的范围,并且关键字在此范围内是可列的,个数还不能超过内存空间所能承受的程度。代码如下:/******...

2018-09-26 15:32:36

拓扑排序

概述:在现实生活中,某些事物可以用有向无环图(Directed Acyclic Graph,DAG)表述。这种有向无环图通常也称作“流程图”,比如,施工流程图、生产流程图、图中每个顶点可以代表一个具体的工序,每条有向边则反映了两个工序的前后次序。拓扑序:如果图中从V到W有一条有向路径,则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序。获得一个拓扑序的过程就是拓扑排序AOV如果...

2018-09-17 08:35:35

最小生成树之克鲁斯卡尔算法(Kruskal)

prim算法中的最小生成树是,采用的是从一个顶点开始,让一棵小树逐渐长成最小生成树,而kruskal算法,采用的是每次选择权值最小的一条边作为生成树,采用将每一棵生成树合并一棵最小生成树方法。也就是将树合成为森林。有一点需要注意:就是将新边加入到最小生成树中时,要判断是否构成回路,如果构成回路的话,则不能加入。那么问题来了,如何判断构成回路呢?一种是采用深度优先搜索来判断两个顶点是否连通,另一种是...

2018-09-14 17:32:49

最小生成树之Prim算法-使用邻接矩阵实现

最小生成树的算法,网上有详细的介绍,这里简单谈一下关键的几个步骤:1:prim算法和单源最短路径中的迪杰斯特拉算法很相识,也在其中借鉴了部分算法。总的来说将图上的顶点分成两部分。一部分   为树顶点(已被选入生成树的顶点)和非树顶点(还未被选入生成树的顶点)。首先选择任意一个顶点加入生成树,然后从剩   下的非树顶点中选择一个距离生成树最近的顶点加入到生成树中,并且更新其它非...

2018-09-13 15:28:20

弗洛伊德(Floyd)算法(多源最短路径)

弗洛伊德算法比较适合稠密图,形式上比较优雅,核心代码只有五行。for (k = 1; k <= g.v; k++) for (i = 1; i <= g.v; i++) for(j = 1; j <= g.v; j++) if (g.matrix[i][j] > g.matrix[i][k] + ...

2018-09-08 16:06:09

单源最短路径-迪杰斯塔拉(Dijkstra)算法的实现

/************************************************************************** 文件名:7.1.1.cpp** 文件描述:Dijkstra算法的实现(好久没写代码了,看来我还是适合codeing不适合paper)** 创建人: fdk* 时 间: 2018-09-03** 版本号:1.0** 修...

2018-09-04 19:57:45

图的存储结构—-邻接矩阵和邻接表的代码实现

图的存储结构一般有两种:一、邻接矩阵:用矩阵表示图中各顶点之间的邻接关系和权值。(一般把带权值的图叫做网)邻接矩阵适合稠密图的存储。二、邻接表:是图的一种顺序存储于链式存储结合的存储方法。领接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点Vi,将所有的邻接于Vi的顶点Vj链接成一个单链表,这个单链表就称做顶点Vi的邻接表,再将所有点的邻接表表头放到一个数组中,就构成了图的邻接表...

2018-08-20 10:25:02

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!