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

2016年07月27日 35 阅读

输入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的整数并返回乘法的结果

2016年07月27日 38 阅读

大整数乘法：给定两个长度不超过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

2016年07月27日 36 阅读

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

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

2016年07月27日 33 阅读

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

Distinct Subsequences -- LeetCode

2016年07月27日 36 阅读

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

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

2016年07月27日 36 阅读

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

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

2016年07月27日 35 阅读

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

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

2016年07月27日 33 阅读

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

图的存储形式：邻接表

2016年07月27日 38 阅读

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

字符串转整数的问题

2016年07月27日 34 阅读

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

最小生成树之Prim算法

2016年07月27日 32 阅读

最小生成树之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：栈的压入弹出序列

2016年07月27日 30 阅读

剑指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），表...

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

2016年07月27日 39 阅读

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

HashTable的相关操作

2016年07月27日 39 阅读

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

KMP模式匹配算法概述

2016年07月27日 38 阅读

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

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

2016年07月27日 32 阅读

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

线性递归和尾递归概述

2016年07月27日 34 阅读

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

二维数组中的查找概述

2016年07月27日 34 阅读

二维数组中的查找概述2015-09-22这一题给跪，c++死活超时。。。后来main函数改成用c就好了。。。算法：/* 题目描述： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 输入： 输入可能包含多个测试样例，对于每个测试案例， 输入的第一行为两个整数m和n（1<=m,n<=1000）：代表将要输入的矩阵的行数和列数。 输...

剑指offer：包含min函数的栈

2016年07月27日 37 阅读

剑指offer：包含min函数的栈2015-09-22剑指offer上的第21题，之前在Cracking the Coding interview上做过，思路参考这里，这次写了测试函数，在九度OJ上测试通过。题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。输入：输入可能包含多个测试样例，输入以EOF结束。对于每个测试案例，输入的第一行为一个整数n（1<=n<=1000000）， n代表将要输入的操作的步骤数。接下...

剑指offer：顺时针打印矩阵

2016年07月27日 34 阅读

剑指offer：顺时针打印矩阵2015-09-22剑指offer上的第20题，九度OJ上测试通过。题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：1 2 3 45 6 7 89 10 11 1213 14 15 16则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.输入：输入可能包含多个测试样例，对于每个测试案例，输入的第一行包括两个整数m和n（1<=m,n&...