如何判断二叉树是否平衡

2016年07月27日 37 阅读

如何判断二叉树是否平衡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

2016年07月27日 42 阅读

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...

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

2016年07月27日 36 阅读

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

如何实现图的BFS和DFS

2016年07月27日 35 阅读

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

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

2016年07月27日 39 阅读

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

4Sum：LeetCode

2016年07月27日 35 阅读

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

2016年07月27日 38 阅读

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. 魔族密码

2016年07月27日 38 阅读

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

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

2016年07月27日 38 阅读

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

Algorithms：Counter计数器详解

2016年07月27日 43 阅读

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

2016年07月27日 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

2016年07月27日 37 阅读

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

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

2016年07月27日 43 阅读

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

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

2016年07月27日 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

2016年07月27日 37 阅读

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

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

2016年07月27日 37 阅读

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

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

2016年07月27日 38 阅读

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

Geeks面试题： Closest Pair of Points及O（nlogn） Implementati

2016年07月27日 38 阅读

Geeks面试题： Closest Pair of Points及O（nlogn） Implementati2015-10-02Closest Pair of Points | O（nlogn） ImplementationWe are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array...

LeetCode总结之二分查找篇

2016年07月27日 35 阅读

LeetCode总结之二分查找篇2015-10-02二分查找算法虽然简单，但面试中也比较常见，经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有：Search Insert PositionSearch for a RangeSqrt（x）Search a 2D MatrixSearch in Rotated Sorted ArraySearch in Rotated Sorted Array II这类题目基本可以分为如下四种...

剑指offer之和为定值的两个数

2016年07月27日 37 阅读

剑指offer之和为定值的两个数2015-10-02题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输入：每个测试案例包括两行：第一行包含一个整数n和k，n表示数组中的元素个数，k表示两数之和。其中1 <= n <= 10^6，k为int第二行包含n个整数，每个数组均为int类型。输出：对应每个测试案例，输出两个数，小的先输出。如果找不到，则输出&ldqu...