求按从小到大的顺序的第N个丑数

2017年02月05日 37 阅读

求按从小到大的顺序的第N个丑数2015-09-12题目描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。输入：输入包括一个整数N（1<=N<=1500）。输出：可能有多组测试数据，对于每组数据，输出第N个丑数。样例输入：3样例输出：3思路：最简单的方法就是先通过将一个数不断除以2，3，5来判定该数是不是丑数，而后在...

求整数中1出现的次数

2017年02月05日 38 阅读

求整数中1出现的次数2015-09-12题目描述：亲们！！我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的...

异或去重的例子

2017年02月05日 37 阅读

异或去重的例子2015-09-12这篇文章没有代码，介绍的是纯理论的思路。异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。异或的性质：1、交换律：a^b = b^a；2、结合律：（a^b）^c = a^（b^c）；3、对于任意的a：a^a=0，a^0=a，a^（-1）=~a。了解了上面这些，来看看这...

输入n个整数并找出其中的最小k个数

2017年02月05日 40 阅读

输入n个整数并找出其中的最小k个数2015-09-14题目: 输入n个整数, 找出其中的最小k个数.使用快速排序（Quick Sort）的方法求解, 把索引值（index）指向前k个数.代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <stdlib.h>int Rand...

大整数乘法：给定两个长度不超过10000的整数并返回乘法的结果

2017年02月05日 36 阅读

大整数乘法：给定两个长度不超过10000的整数并返回乘法的结果2015-09-14题目:大整数乘法, 给定两个长度不超过10000的整数, 返回乘法的结果.char* multi（char* number_a, char* number_b）代码:/** test.cpp**Created on: 2014.04.24*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <iostream>#in...

Word Search -- LeetCode

2017年02月05日 40 阅读

Word Search -- LeetCode2015-09-14 csdn博客 Code_Ganker原题链接: http://oj.leetcode.com/problems/word-search/ 这道题很容易感觉出来是图的题目，其实本质上还是做深度优先搜索。基本思路就是从某一个元素出发，往上下左右深度搜索是否有相等于word的字符串。这里注意每次从一个元素出发时要重置访问标记（也就是说虽然单次搜索字符不能重复使用，但是每次从一个新的元素出发，字符...

求一个字符串编辑成为另一个字符串的最少操作数

2017年02月05日 36 阅读

求一个字符串编辑成为另一个字符串的最少操作数2015-09-14原题链接: http://oj.leetcode.com/problems/edit-distance/这道题求一个字符串编辑成为另一个字符串的最少操作数，操作包括添加，删除或者替换一个字符。这道题难度是比较大的，用常规思路出来的方法一般都是brute force，而且还不一定正确。这其实是一道二维动态规划的题目，模型上确实不容易看出来，下面我们来说说递推式。我们维护的变量res[i][j]表...

Distinct Subsequences -- LeetCode

2017年02月05日 38 阅读

Distinct Subsequences -- LeetCode2015-09-14原题链接: http://oj.leetcode.com/problems/distinct-subsequences/这道题应该很容易感觉到是动态规划的题目。还是老套路，先考虑我们要维护什么量。这里我们维护res[i][j]，对应的值是S的前i个字符和T的前j个字符有多少个可行的序列（注意这道题是序列，不是子串，也就是只要字符按照顺序出现即可，不需要连续出现）。下面来看...

华为上机练习题：按位取反操作

2017年02月05日 39 阅读

华为上机练习题：按位取反操作2015-09-16题目：求指定位取反后的结果（用异或来进行指定位数的取反）* 输入：0x1234 3* 输出：0x123c分析：从网上看到这道题发现蛮有意思的， 记得当时学C语言的时候就有过这种的操作，只不过时间久了就有些健忘， 经过努力追忆后终于想起些些， 现在做出如下总结：* AND--> & --> AND指令主要用于使操作数若干位不变， 而使某些位为"0"的场合* OR --> | -...

华为上机练习题：压缩字符串

2017年02月05日 41 阅读

华为上机练习题：压缩字符串2015-09-16题目：通过键盘输入一串小写字母（a~z）组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。压缩规则：1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz&qu...

图的存储形式：邻接矩阵（数组）

2017年02月05日 37 阅读

图的存储形式：邻接矩阵（数组）2015-09-16邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。比如考虑下面这个有向图：如果用邻接矩阵存储可以表示为：1.顶点数组：2.邻接矩阵：图的遍历：深度优先（DFS）：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾访问过，则深度优先搜索可从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有...

图的存储形式：邻接表

2017年02月05日 36 阅读

图的存储形式：邻接表2015-09-16邻接表：邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点有三个域组成，其中邻接点域指示与顶点vi邻接的点在途中的位置，链域指示下一条边或者弧的结点；数据域存储和边或者弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设置链域指向链表第一个结点之外，还设置有存储顶点vi的名。如下所示：实现：/...

字符串转整数的问题

2017年02月05日 40 阅读

字符串转整数的问题2015-09-18要点：要考虑到各种非法参数。实现：/********************************** 字符串转整数 by Rowandjj 2014/7/15 ***********************************/#include<iostream>#include<stdlib.h>//不加这个头文件在九度oj上会编译错误using namespace std;int s...

最小生成树之Prim算法

2017年02月05日 33 阅读

最小生成树之Prim算法2015-09-18Prim算法：假设N = （V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0属于V），TE={}开始，重复执行下述操作：在所有u属于U，v属于V-U的边（u,v）属于E中找到一条代价最小的边（u0,v0）并入集合TE,同时v0并入U，直至U=V为止，此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树.为实现这个算法，需附设一个辅助数组closedge,以记录从U到V-U...

剑指offer：栈的压入弹出序列

2017年02月05日 37 阅读

剑指offer：栈的压入弹出序列2015-09-18剑指offer上的第22题，九度OJ上AC。题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。输入：每个测试案例包括3行：第一行为1个整数n（1<=n<=100000），表...

有向图的十字链表存储形式

2017年02月05日 41 阅读

有向图的十字链表存储形式2015-09-18十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表（只考虑入度）结合起来得到的一种链表。在十字链表中，对应于有向图中每一个顶点有一个节点，每一条弧也有一个结点。顶点之间是数组顺序存储，而弧是链式存储。弧结点结构：顶点结点结构：十字链表形态：...

HashTable的相关操作

2017年02月05日 35 阅读

HashTable的相关操作2015-09-20前言学过Java的人肯定对Hash这个词非常之熟悉,HashTable、HashSet、HashMap等都是对哈希表的封装或改进。这次我们来看下哈希表用C语言表示的封装实现。哈希表哈希表又叫散列表，是实现字典操作的一种有效数据结构。哈希表的查询效率极高，在没有冲突（后面会介绍）的情况下不需经过任何比较，一次存取便能得到所查记录，因此理想情况下，查找一个元素的平均时间为O（1）。哈希表就是描述key&mdash...

KMP模式匹配算法概述

2017年02月05日 36 阅读

KMP模式匹配算法概述2015-09-20我们经常会遇到一种情况是匹配两个字符串，看strPar中是否含有str子串，如果有则返回子串在父串strPar中的位置，如果不存在则返回false.很明显，我们可以通过暴力求解的方式解决该问题。即从strPar第一个字符和子串进行比较，若成功则返回第一个0，若不成功，再第二个字符开始比较，这样的时间复杂度为O（M*N）.可以看出，这个复杂度是相当高的，那么我们有没有一种复杂度会降低呢？显然，有一种叫做KMP算法可以...

求数组中只出现一次的数字的算法

2017年02月05日 38 阅读

求数组中只出现一次的数字的算法2015-09-20题目: 一个整型数组里除了两个数字以外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字.如果从头到尾依次异或数组中的每一个数字, 那么最终的结果刚好是那个只出现一次的数字.根据结果数组二进制某一位为1, 以此分组, 为1的一组, 为0的一组, 再重新进行异或. 最后得出两个结果.时间复杂度O（n）.代码:/** main.cpp**Created on: 2014.6.12*Author: ...

线性递归和尾递归概述

2017年02月05日 39 阅读

线性递归和尾递归概述2015-09-20今天一直在研究尾递归，看了些博文，记下点笔记，供以后复习用线性递归：也即是普通递归，单向递归，线性递归函数的最后一步操作不是递归操作，而是其他的操作。当数据量很大的时候，会造成栈溢出，这是因为，在每次递归调用时，递归函数中的参数，局部变量等都要保存在栈中，如果数据量很大的话，便可能会溢出。尾递归：也即是线性迭代，尾递归函数的最后一步操作是递归，也即在进行递归之前，把全部的操作先执行完，这样的好处是，不用花费大量的栈空...