11 wuzhekai1985

尚未进行身份认证

暂无相关简介

等级
TA的排名 3k+

解题笔记(40)——第1-39篇合集

2011年7月至今,解题笔记系列已有39篇文章,本文做一个归纳及索引,方便网友阅读参考。其中的题目多出自两个博客,一个是JULY的,另一个是何海涛的。上面有题目,也有解题思路及代码。      JULY的博客  http://blog.csdn.net/v_JULY_v/ar

2011-10-07 11:09:06

解题笔记(39)——过河问题

问题描述:在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那

2011-10-06 16:05:29

解题笔记(38)——大整数阶乘计算

问题描述:求一个整数 n 的阶乘,0      比如n = 50,结果为30414093201713378043612608166064768844377641568960512000000000000     思路:从阶乘的定义出发,n! = n * (n-

2011-10-05 22:36:03

解题笔记(37)——Catalan数计算及应用

问题描述:卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。输入一个整数n,计算h(n)。其递归式如下:h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2,h(0) = h(1) = 1)    该递推关

2011-09-10 09:17:11

解题笔记(36)——最大公约数问题

问题描述:求两个正整数的最大公约数。     思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法。通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。根据通式写出算法不难,这里

2011-09-05 20:37:39

一些字符串及内存操作的函数

本文给出了一些字符串及内存操作的函数的实现:memcpy、memset、memmove、strcpy、strcmp、strlen、strstr、strcat,为了与标准区分,所有函数名前加了下划线。下面给出这些函数的实现。如果错误,还请读者指正。//函数功能: 拷贝不重叠

2011-09-03 14:31:54

解题笔记(35)——旋转数组中的最小元素

问题描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。      思路:这道题最直观的解

2011-08-30 21:58:51

解题笔记(34)——求最长单调递减子序列

问题描述:求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}。      思路:这是很经典的一个问题,用动态规划解决。假设源数组为A,定义一个辅助数组为B,B[i]表示以A[i]结尾的最长递减序列的长度。举个简单

2011-08-30 19:41:02

解题笔记(33)——按层次遍历二元树

问题描述:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。          例如输入   8  / / 6 10/ / / /5 7 9 11输出8 6 10 5 7 9 11。

2011-08-29 19:13:07

解题笔记(32)——输入一颗二元查找树,将该树转换为它的镜像

问题描述:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。          例如输入:  8  / /  6 10 //

2011-08-29 14:37:29

解题笔记(31)——从数列1,2...n中随意取几个数,使其和等于m

问题描述:输入两个整数n和m,从数列1,2.......n中随意取几个数,使其和等于m,要求将其中所有的可能组合列出来。      思路:这个问题其实背包问题的变形,本文给出两种解法。      解法一:用递归,效率可能低了点。假设问题的解为F(n, m)

2011-08-29 11:37:21

有点意思的C/C++问题及解答:21-25

问题21:判断C编译器是否支持嵌套注释。       解法:嵌套注释是指在/* */ 中出现/* ... */,定义这个式子: /*/*/0*/**/1  。如果编译器不支持嵌套注释,那么这个式子为0*1。如果支持嵌套注释,那么这个式子为1。摘自《C陷阱与缺陷》。

2011-08-28 15:26:46

解题笔记(30)——找含单链表的环入口点(转网上某位高手的解法)

原文出处 http://hi.baidu.com/iwitggwg/blog/index/1  很不错。        问题1:如何判断单链表中是否存在环(即下图中从结点E到结点R组成的环)?        设一快一慢两个指针(Node *fast, *low)同时从

2011-08-27 20:22:37

解题笔记(30)——找含单链表的环入口点

问题描述:有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。如果链表存在环,找到环的入口点?      思路:这道题的原型可能来自《C专家编程》一书,题目为”怎样才能检测到链表中存在循环“,书中给出的最终算

2011-08-27 16:17:20

解题笔记(29)——珠子问题

问题描述:一串首尾相连的珠子(n个),有N种颜色(N      思路:可以利用一种计数的方法。定义两个指针p1和p2,主要有三个步骤:     (1)p1向前移动,如果p1所指的珠子颜色编号为 i ,则增加 i 的出现次数。当出现的颜色种数为N时,p1停止

2011-08-27 12:43:30

解题笔记(28)——寻找捣乱分子对

问题描述:多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176, 178, 180, 170, 171      这些捣乱

2011-08-25 14:25:55

解题笔记(27)——找数组中的特定元素

问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。      思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i

2011-08-24 21:19:44

解题笔记(26)——排队问题

问题描述:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?        思路:可以用递归来解决。假设已按高矮顺序编号从0到11,即0号最矮、11号最高,(i, j)表示某个人在队列中的位置。对于0号只能排在(0, 0

2011-08-23 21:45:29

解题笔记(25)——把数组排成最小的数

问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32,  321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。      思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依

2011-08-21 10:40:51

解题笔记(24)——找出数组中两个只出现一次的数字(数组)

问题描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。     思路:如果只有一个数字只出现一次,而其他都出现两次,则直接将所有数字做一次异或运算即可,因为相等的数字异或一下结果为

2011-08-20 18:57:03

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!