wumuzi-CSDN博客

原创单链表的快速排序

单链表的特点是：单向。设头结点位head，则最后一个节点的next指向NULL。如果只知道头结点head，请问怎么将该链表排序？设结点结构为 struct Node{ int key; Node* next; }; 那么一般人见到这种题目，立马就会想到

2012-10-16 19:00:26 23637 9

原创求正整数n所有可能的和式的组合

求正整数n所有可能的和式的组合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2）首先说一下，群里面很多人在问这个东东怎么去打印，当然如果是只求组合个数的话，他就是一个完全背包的问题，如果要打印的话，那还真的费一番功夫。我们可以将这题想为一个找零钱问题，以前找零钱问题是，我们有1元、2元、5元、10元面值的纸币，现在我有20元钱，问有多少种找法。这个找零钱如果

2012-10-07 22:03:49 14948 9

原创和为 n 连续正数序列

题目：输入一个正数 n，输出所有和为 n连续正数序列。例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6和 7-8。方法一:首先判断n最多能由几个连续数的和得到，假设最多由M个连续数和得到，那么M(M+1)/2=n这样很容易求得M=(sqrt(8n+1)-1)/2。由题义可知，n至少需要由两个连续数和得来，所以

2012-10-07 21:14:27 4511 2

原创左旋转字符串新思路

题目描述：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。ps:该题目来自July的程序员编程艺术第一章、左旋转字符串章节，但该题的解法有新颖之处。在July的博客的思路一中，提到三次

2012-08-31 13:15:47 1605 2

原创将整数nSum拆分成num个数的和的形式——阿里巴巴笔试题

将一个整数nSum分解成num个整数和的形式，如nSum=6，num=3那么，nSum就可以分解成为1 1 4；1 2 3；222。请编程实现！方法解析：采用递归的算法，分解时，层次（nDepth，基于0）每深一层，其层所对应的值就应该不比上一层的值小，所以循环体中变量i应从上一层的值开始，直到nSum/num时截止，因为最后一组最大情况应都为nSum/num。其中nDepth+nu

2012-08-07 23:33:11 4968

原创给定数组a[N]构造数组b [N]——腾讯笔试

给定一个数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：要求O（1）空间复杂度和O（n）的时间复杂度；除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）解析：设b[0]=1由b[i]=b[i-1]*a[i-1]可得b[1] = a[0]b[

2012-08-07 23:07:17 5585 2

原创老鼠喝药问题

我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分？解析：为了方便分析，我们先以三只老鼠为例来导出一般式。首先，我们给每个瓶子进行从1~n编号，给每个老鼠从0~k进行编号（这里k=3-1

2012-08-07 21:22:21 2921

原创五猴偷桃之数学解法及问题拓展

有五只猴子摘了一些桃子，打算隔天早上起来分了吃。晚上的时候，第一只猴子偷偷起来把桃子分成五堆，还多了一个，就把多了的那个吃掉，并拿走了一堆。第二只猴子也偷偷起来将桃子分成了五堆，还是又多了一个，同样吃掉了这一颗桃子，并拿走了其中一堆。第三只、第四只、第五只猴子都做了同样的事情。请问这堆桃子最少有多少个？解：设桃子一共有m个，F[i]表示第i个猴子偷完后剩余的桃子的个数F[0] = m

2012-08-07 13:55:28 4322

原创找零钱递归实现

题目：现有1元、2元、5元、10元、20元面值不等的钞票，问需要20元钱有多少种找钱方案，打印所有的结果！分析：此题如果没要求打印结果，只要求打印出一共有多少种方案，那么可以直接用动态规划，参考背包问题——“01背包”及“完全背包”装满背包的方案总数分析及实现如果要求打印所有结果，那递归是再好不过的了。 #include #include using namespac

2012-08-06 22:59:12 11567 1

转载设计模式：简单工厂、工厂方法、抽象工厂之小结与区别

简单工厂，工厂方法，抽象工厂都属于设计模式中的创建型模式。其主要功能都是帮助我们把对象的实例化部分抽取了出来，优化了系统的架构，并且增强了系统的扩展性。本文是本人对这三种模式学习后的一个小结以及对他们之间的区别的理解。简单工厂简单工厂模式的工厂类一般是使用静态方法，通过接收的参数的不同来返回不同的对象实例。不修改代码的话，是无法扩展的。工厂方法工厂方法是针对每一

2012-07-25 20:12:48 1500

原创动态规划——通配符匹配算法

-----Edit by ZhuSenlin HDU设计通配符匹配算法，其中*号可以匹配任意多个字符，？号可以匹配任意一个字符。例如12345和12*、12*？以及12*4？等都匹配。函数原型为：bool match(const char* str, const char* strpattern); 分析：利用动态规划来解决。此题类似与LCS问题。假设字符串A[i]代表前i+1

2012-03-21 15:56:12 8493 5

原创动态规划——数组中最长递减子序列

-----Edit by ZhuSenlin HDU求一个数组的最长递减子序列比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}分析：典型的动态规划题目，对每一个数计算由它开始的最大递减子序列的个数，并存放到一张映射表中。例如对数组a[n]有……然后利用求得的映射表及最大子序列个数获取原数组中的元素。对于{9,4,3,2,5,4,3,2}我们

2012-03-21 15:42:19 13824 5

原创动态规划——最长公共子序列（LCS）

-----Edit by ZhuSenlin HDU求最长公共子序列。给定两个序列和，希望找出X和Y的最大公共子序列。1）确定LCS最优子结构。设为X和Y的任意一个LCS，则如果xm=yn,那么zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS；如果xm!=yn,那么zk!=xm蕴含Z是Xm-1和Y的一个LCS；如果xm!=yn,那么zk!=yn蕴含Z是X和Yn-

2012-03-21 15:27:57 1603 1

原创单例模式的设计分析（自动释放实例内存）

-----Edit by ZhuSenlin HDU方法一：利用私有静态成员变量static Singleton m_Instance实现1）因为只有一个实例，所以我们不能把构造函数借口暴露给用户（否则用户可以创建很多个）。所以采用一个静态成员函数static Singleton* GetInstance();来获取实例。2）因为只有一个实例，我们不想让用户随便删除，所以我们需要把

2011-12-11 22:20:44 4596

原创《编程之美》2.18——数组分割新思路（包含分类后数组的输出）

-----Edit by ZhuSenlin HDU本文说是《编程之美》2.18新思路，其实也是July的《微软等公司面试100题》上的32题的解法。两个序列大小均为n，序列元素的值为任一整数，无序；要求通过交换两个序列的元素，使序列a元素之和与序列b的元素之和的差最小（可能存在很多种组合，要求找出其中一种即可）。如序列：1 5 7 8 9和序列6 3 1

2011-11-30 21:01:24 8213 2

原创利用牛顿迭代法自己写平方根函数sqrt

-----Edit by ZhuSenlin HDU 给定一个正数a，不用库函数求其平方根。设其平方根为x，则有x2=a，即x2-a=0。设函数f(x)= x2-a,则可得图示红色的函数曲线。在曲线上任取一点(x0,f(x0))，其中x0≠0那么曲线上该点的切线方程为 (1-1) 求该切线

2011-11-30 13:16:41 12861 4

原创背包问题——“01背包”及“完全背包”装满背包的方案总数分析及实现

-----Edit by ZhuSenlin HDU 本人博文《背包问题——“01背包”最优方案总数分析及实现》及《背包问题——“完全背包”最优方案总数分析及实现》中分别谈过“01背包”和“完全背包”实现最大价值的方案总数，这里我们再讨论一下这两种背包被物品刚好装满的方案总数。网上各大公司经常出题目：假设现在有1元、2元、5元的纸币很多张，现在需要20块钱，你

2011-11-28 22:18:51 24042 9

原创背包问题——“完全背包”最优方案总数分析及实现

-----Edit by ZhuSenlin HDU 本人博文《背包问题——“完全背包”详解及实现（包含背包具体物品的求解）》中已详细谈过完全背包问题，同时在博文《背包问题——“01背包”最优方案总数分析及实现》中也总结过01背包的最优方案总数的实现。这里我们模仿01背包最优方案总数方法给出完全背包的最优方案求解方法。重写完全背包的动态规划的状态及

2011-11-28 15:09:28 7275 2

原创背包问题——“01背包”最优方案总数分析及实现

-----Edit by ZhuSenlin HDU本人博文>中已谈过01背包，这里再重写一下01背包的动态规划状态及状态方程：设背包容量为V，一共N件物品，每件物品体积为C[i]，每件物品的价值为W[i]1）子问题定义：F[i][j]表示前i件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。2）根据第i件物品放或不放进行决策

2011-11-28 13:25:11 10193 2

原创背包问题——“完全背包”详解及实现（包含背包具体物品的求解）

-----Edit by ZhuSenlin HDU 完全背包是在N种物品中选取若干件（同一种物品可多次选取）放在空间为V的背包里，每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解怎么装物品可使背包里物品总价值最大。动态规划（DP）： 1）子问题定义：F[i][j]表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能

2011-11-26 16:23:43 64499 8

原创背包问题——“01背包”详解及实现（包含背包中具体物品的求解）

-----Edit by ZhuSenlin HDU 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解将那些物品装入背包可使总价值最大。动态规划（DP）： 1）子问题定义：F[i][j]表示前i件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大

2011-11-26 14:41:26 54518 20

wumuzi520的专栏