二维数组中的查找概述

2017年02月05日 36 阅读

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

剑指offer：包含min函数的栈

2017年02月05日 36 阅读

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

剑指offer：顺时针打印矩阵

2017年02月05日 39 阅读

剑指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&...

如何判断二叉树是否平衡

2017年02月05日 35 阅读

如何判断二叉树是否平衡2015-09-22题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。注：这里不考虑该二叉树是否是二叉排序树解决要点：1.后序遍历二叉树；2.递归。核心算法：bool isBalanced（pTree pT,int *depth）{if（！pT）//参数判断{*depth = 0;return true;}//后序遍历int left,right;if...

Geeks 面试题之Optimal Binary Search Tree

2017年02月05日 39 阅读

Geeks 面试题之Optimal Binary Search Tree2015-09-24Dynamic Programming | Set 24 （Optimal Binary Search Tree）Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number o...

基本数据结构：队列的顺序表示

2017年02月05日 38 阅读

基本数据结构：队列的顺序表示2015-09-24以下为操作队列的算法，该队列为静态队列，用循环数组实现。给该队列分配的内存长度为len+1，但实际只用了len个内存空间来保存数据，这样做是为了更方便判断队列的满与空。队列中front位置中存放的是队首的数据，rear位置的前一个位置中存放队尾的数据，而rear位置中则没有数据存放，这样做的目的是为了在入队和出队时方便对队列的操作，而不用考虑特殊情况操作系统：ubuntu编译软件：gcc结果截图：...

如何实现图的BFS和DFS

2017年02月05日 36 阅读

如何实现图的BFS和DFS2015-09-24图的存储结构本文的重点在于图的深度优先搜索（DFS）和广度优先搜索（BFS），因此不再对图的基本概念做过多的介绍，但是要先大致了解下图的几种常见的存储结构。邻接矩阵邻接矩阵既可以用来存储无向图，也可以用来存储有向图。该结构实际上就是用一个二维数组（邻接矩阵）来存储顶点的信息和顶点之间的关系（有向图的弧或无向图的边）。其描述形式如下：//图的邻接矩阵存储表示#define MAX_NUM 20 // 最大顶点个数...

模式匹配：从BF算法到KMP算法

2017年02月05日 38 阅读

模式匹配：从BF算法到KMP算法2015-09-24模式匹配子串的定位操作通常称为串的模式匹配。模式匹配的应用很常见，比如在文字处理软件中经常用到的查找功能。我们用如下函数来表示对字串位置的定位：int index（const string &Tag,const string &Ptn,int pos）其中，Tag为主串，Ptn为子串（模式串），如果在主串Tag的第pos个位置后存在与子串Ptn相同的子串，返回它在主串Tag中第pos个字符...

4Sum：LeetCode

2017年02月05日 36 阅读

4Sum：LeetCode2015-09-26这道题要求跟3Sum差不多，只是需求扩展到四个的数字的和了。我们还是可以按照3Sum中的解法，只是在外面套一层循环，相当于求n次3Sum。我们知道3Sum的时间复杂度是O（n^2），所以如果这样解的总时间复杂度是O（n^3）。代码如下：public ArrayList<ArrayList<Integer>> fourSum（int[] num, int target） {ArrayLis...

Geeks 面试题之Ugly Numbers

2017年02月05日 42 阅读

Geeks 面试题之Ugly Numbers2015-09-26Ugly NumbersUgly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …shows the first 11 ugly numbers. By convention, 1 is included.Wri...

Vijos1028. 魔族密码

2017年02月05日 39 阅读

Vijos1028. 魔族密码2015-09-26题目概述风之子刚走进他的考场, 就……花花: 当当当当~~偶是魅力女皇——花花！！^^（华丽出场, 礼炮, 鲜花）风之子: 我呕……（杀死人的眼神）快说题目！否则……-_-###花花: ……咦~~好冷~~我们现在要解决的是魔族的密码问题（自我陶醉: 搞不好魔族里面还会有人用...

基本数据结构：栈的链式表示

2017年02月05日 38 阅读

基本数据结构：栈的链式表示2015-09-26以下为操作栈的算法，该栈为动态栈。在该栈中，pTop指向的节点中存放该栈的栈顶数据,pBottom指向的节点的上一个节点存放该栈的栈底数据，pBottom指向的节点中不存放有效数据，这样做的目的是为了在进行入栈和出栈时方便对栈的操作，而不用考虑特殊情况操作系统：ubuntu编译软件：gcc结果截图：...

Algorithms：Counter计数器详解

2017年02月05日 36 阅读

Algorithms：Counter计数器详解2015-09-28Counter计数器, 在算法中, 有很重要的应用, 包含一个名称（name-String）, 一个计数器（count-int）;可以递增（increment）, 返回计数值（tally）, 可以默认打印（toString）;代码如下:public class Counter {private final String name;private int count;public Counte...

Geeks 面试题之Maximum size square sub-matrix with all 1s

2017年02月05日 36 阅读

Geeks 面试题之Maximum size square sub-matrix with all 1s2015-09-28Maximum size square sub-matrix with all 1sGiven a binary matrix, find out the maximum size square sub-matrix with all 1s.For example, consider the below binary matrix.0...

Simplify Path：LeetCode

2017年02月05日 40 阅读

Simplify Path：LeetCode2015-09-28原题链接: http://oj.leetcode.com/problems/simplify-path/这道题目是Linux内核中比较常见的一个操作，就是对一个输入的文件路径进行简化。思路比较明确，就是维护一个栈，对于每一个块（以‘/’作为分界）进行分析，如果遇到‘../’则表示要上一层，那么就是进行出栈操作，如果遇到‘./&rsqu...

用非常规方法求1+2+···+n

2017年02月05日 35 阅读

用非常规方法求1+2+···+n2015-09-28今天在《剑指offer》里看到了下面这样一个简单且有趣的题，考察程序员的发散思维能力，前提是你对C++相关知识点熟悉，否则是想不出来方案的，分享给大家。题目：求1+2+···+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A？B:C）。点评：这个问题本身没有太多的实际意义，因为在软件开发中不可能有这么苛刻...

Geeks 面试题之Fibonacci numbers优化为lgn效率

2017年02月05日 38 阅读

Geeks 面试题之Fibonacci numbers优化为lgn效率2015-09-30The Fibonacci numbers are the numbers in the following integer sequence.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..In mathematical terms, the sequence Fn of Fibonac...

Restore IP Addresses：LeetCode

2017年02月05日 35 阅读

Restore IP Addresses：LeetCode2015-09-30原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/这道题的解法非常接近于NP问题，也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP...

关于字符串操作的算法题目

2017年02月05日 37 阅读

关于字符串操作的算法题目2015-09-30原题链接: http://oj.leetcode.com/problems/interleaving-string/这是一道关于字符串操作的题目，要求是判断一个字符串能不能由两个字符串按照他们自己的顺序，每次挑取两个串中的一个字符来构造出来。像这种判断能否按照某种规则来完成求是否或者某个量的题目，很容易会想到用动态规划来实现。先说说维护量，res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表...

折半查找（binary search） 算法示例

2017年02月05日 37 阅读

折半查找（binary search） 算法示例2015-09-30折半查找, 又称二分查找（binary search）, 需要数组有序（sort）, 通过比较数组的中间数据（中心偏向较小的方法）, 确定查找值的范围;直到中值等于查找值, 则查找成功; 如果未成功, 则重置数据, 判断首尾位置的大小, 再进行中值比较; 判断失败, 则数据不存在;注意:1. Eclipse无法重定向（redirect）输入文件（file）, 只能读入数据;2. 使用cmd...