overstack的专栏

作者:Dong | 可以转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明网址:http://dongxicheng.org/structure/segment-tree/1、概述线段树，也叫区间树，是一个完全二叉树，它在各个节点保存一条线段（即“子数组”），因而常用于解决数列维护问题，它基本能保证每个操作的复杂度为O(lgN)。2、线段树基本操作

今天看算法分析是，看到一个这样的问题，就是在一堆数据中查找到第k个大的值。      名称是：设计一组N个数，确定其中第k个最大值，这是一个选择问题，当然，解决这个问题的方法很多，本人在网上搜索了一番，查找到以下的方式，决定很好，推荐给大家。      所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。      解

卡特兰数：规定h(0)＝1，而h(1)＝1，h(2)＝2，h(3)＝5，h(4)＝14，h(5)＝42，h(6)＝132，h(7)＝429，h(8)＝1430，h(9)＝4862，h(10)＝16796，h(11)＝58786，h(12)＝208012，h(13)＝742900，h(14)＝2674440，h(15)＝9694845·····················通项公式为：

问题描述： 给定一个序列 An = a1 ,a2 ,  ... , an ，找出最长的子序列使得对所有 i j ，ai aj 。显然，暴力算法的时间复杂度是 O(2n ) ，因为搜索空间呈指数级增长。对于这种问题，如果要找复杂度为多项式时间的算法，自然而然地会想到动态规划。首先，要找出一种方法把该问题分解成只有多项式个子问题。考虑 a n 。如果最长递增子序列不 包含 an ，则问题变成要

问题背景 今年的实习生招聘考试，我出了一道二分查找(Binary Search)的题目。题目大意如下： 给定一个升序排列的自然数数组，数组中包含重复数字，例如：[1,2,2,3,4,4,4,5,6,7,7]。问题：给定任意自然数，对数组进行二分查找，返回数组正确的位置，给出函数实现。注：连续相同的数字，返回第一个匹配位置还是最后一个匹配位置，由函数传入参数决定。

1. 查找利用二叉查找树左小右大的性质，可以很容易实现查找任意值和最大/小值。[cpp] view plaincopyBSTNode * bst_search(BSTNode *node, int key)  {       while (node && key != node->key) {

Problem StatementReservoir Sampling is an algorithm for sampling elements from a stream of data. Imagine you are given a really large stream of data elements (queries on google searches in May,

1、内存访问（连续内存访问与跨页面访问内存的区别）注意在访问内存的时候，要注意内存的连续性，如果访问的内存不是连续的，那么程序的运行速度也会受到极大的影响例如访问一个二维数组时，先访问行，再访问列，能够减少页面调度次数，同时cache命中率也相对高些。2、递归调用宏时，需要小心，宏中的某个参数被调用了多次以致数值发生了变化#define Max(a,b) （（a>b）?:（a）：（b））

Problem:Given an integer array, sort the integer array such that the concatenated integer of the result array is max.Example: [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer

转载自：http://blog.csdn.net/beiyeqingteng/article/category/8593951. 找出二叉查找树中第n大的值问题：给一个二叉查找树（BST），找出第 k 大的值。比如：该图中，第3大的值是10.分析：我们可以通过类似中序遍历的方法把BST从大到小排序，然后，就可以得到第 k 大的值了

题目都是来自standford cs library：http://cslibrary.stanford.edu/110/BinaryTrees.html是一个关于二叉树的专题，上面还有很多其他的专题，适合刚入门或者要找工作同学复习用。下面是我自己从二叉树这个专题当中选取的一些有代表性的题目。基本数据结构如下：struct node { int data; stru

You are given an Array of numbers and they are unsorted/random order. You are supposed to find the longest sequence of consecutive numbers in the array. Note the sequence need not be in sorted ord

1.问题描述：求一个正整数序列的最长单调自增子序列，子序列不要求是连续的。例如Input：55 2 4 3 1Output：22. 算法复杂度是O(N^2)其实这也是一个DP的方法！f[i]是以a[i]为最大值的子序列，那么f[]的最大值就是要的结果。int f[],a[];f[0] = 1;// base casef

教你如何迅速秒杀掉：99%的海量数据处理面试题作者：July出处：结构之法算法之道blog前言   一般而言，标题含有“秒杀”，“99%”，“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌，但进一步来讲，如果读者读罢此文，却无任何收获，那么，我也甘愿背负这样的罪名，:-)，同时，此文可以看做是对这篇文章：十道海量数据处理面试题与十个方法大总结的

1. 实现一个memcpy函数。先看下标准memcpy()的解释：void *memcpy(void *dst, const void *src, size_t n);//If copying takes place between objects that overlap, the behavior is undefined.事实上所说的陷阱也在于此，自己动手实现m

数组统计分析原题给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？分析这个题目，是有一定技巧的。技巧是需要慢慢积累，待经验多了之后，可以灵感或者直觉，就产生了技巧。如果不知道技巧，那该怎么办呢？在开

#include #include using namespace std;const int N = 10;int binarySearch(int* arr, int l, int u, int key){ while(l <= u) { int mid = (l+u) >> 1; if (arr[mid] == key)

具体的方法不说了，网上很多，直接贴代码。#includevoid BubbleSort(int* A, int n){ for(int i = 0; i < n; i++) for(int j = 0; j < n - 1 -i; j++) if(A[j] > A[j+1]) {

#include #include #include #define MAX_LEN 200int an1[MAX_LEN+10];int an2[MAX_LEN+10];char szLine1[MAX_LEN+10];char szLine2[MAX_LEN+10];int main(){ scanf("%s", szLine1); scanf("%s"

/* * ===================================================================================== * * Filename: Longest_Palindromic_Substring.cpp * * Description: * * Version: 1.0

/*Given an inorder traversal only for a binary tree (not necessarily aBST), give a pseudo code to generate all possible binary trees forthis traversal sequence.Firstly, how many binary trees can

源于微博上一个同学发了一条微博：“如何对C语言下的矩阵乘法进行优化？我试了几种小技巧，但是发现怎么试都远远比不上MATLAB。”然后他贴了一下他的基本实现方法如下图：基于他的方法，我也做了一下程序实现，代码如下：/* * ==============================================================================

Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is a two-side bound). In my experience this is actually typical of discussions in

问题： 考虑在一个打印机上整齐地打印一段文章的问题。输入的正文是n个长度分别为L1、L2、……、Ln（以字符个数度量）的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来，每行至多M个字符。“整齐度”的标准如下：如果某一行包含从i到j的单词（i<j），且单词之间只留一个空格，则在行末多余的空格字符个数为 M - (j-i) - (Li+ …… + Lj)，它必须是非负值才能让该行容纳这

我常感叹到，学计算机的人是幸福的，因为在这个领域中有如此多的通俗易懂（相对来说）的经典好书，你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了（抱怨一下），除了论文就是论文，满篇公式，晦涩坚深，真不是给人看的（虽然我也没看过几篇）。在这里列出一些我看过或者准备看的算法书籍，以供参考。1. CLRS 算法导论 算法百科全书，只做了前面十几章的习题，便感觉受益无穷。

2011年2月15日更新，加入找出绝对值最小的元素一题数组是最基本的数据结构，关于数组的面试题也屡见不鲜，本文罗列了一些常见的面试题，仅供参考，如果您有更好的题目或者想法，欢迎留言讨论。目前有以下18道题目，如果有好的题目，随时更新。数组求和求数组的最大值和最小值求数组的最大值和次大值求数组中出现次数超过一半的元素求数组中元素的最短距离求两个有序数组的共同元素求三个数组的共同元素找出数

算法导论上第16-1问题 考虑用最少的硬币数找n分钱的问题，假设每个硬币的值都是整数。a）请给出一种贪心算法，使得所换的硬币包括一角的，五分的，二角五分的合一分的。证明所给出的算法能产生最优解。b）假设可换的硬币单位是c的幂，也就是c0,c1, ..., ck  其中整数c>1, k>=1.证明贪心算法总可以产生一个最优解。c） 请给出一组是贪心算法不能产生最优

从B 树、B+ 树、B* 树谈到R 树 作者：July、weedge、Frankie。编程艺术室出品。说明：本文从B树开始谈起，然后论述B+树、B*树，最后谈到R 树。其中B树、B+树及B*树部分由weedge完成，R 树部分由Frankie完成，全文最终由July统稿修订完成。出处：http://blog.csdn.net/v_JULY_v 。 第一节、B树、B+树、B*

《编程珠玑》第一章提到了一个排序问题，具体需求抄在下面：输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。输出：按升序排列的输入整数的列表。约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。整个解题

4.生成[0,n)的之间k个不重复的随机整数。#include#include#include#includeusing namespace std;const int N = 10000000;const int K = 10000000;int randint( int l, int r ){ return rand() % ( r-l ) + l;}

今天看到 boost::unordered_map， 它与 stl::map的区别就是，stl::map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。而boost::unordered_map是计算元素的Hash值，根据Has

A、给定一个最多包含40亿个随机排列的32为整数的顺序文件，找出一个不存在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如何有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决问题？1.在文件中至少缺失一个这样的数？为什么呢？这是因为32为表示能表示N=232-1个数，(42 9496 72

看了刘未鹏的文章《跟波利亚学解题》之后关于解题方法的一些想法。这篇文章提到了我们从小大到看到的数学书上无一不是欧几里得方式定义的：从定义到定理，再到推论。是属于“顺流而下”式的。但这样的书其实完全扭曲了数学的发现过程。所以作者推荐我们去看波利亚的书《How to solve it》中的启发思考方法。刘未鹏自己也总结出了以下几点：1. 时刻不忘未知量2. 用特例启发思考3. 反过来推

#include #include #include using namespace std;typedef int datatype;typedef struct node{ struct node* next; datatype data;}Node;void initHead(Node** head){ *head = NULL;}voi

作者：Hawstein出处：http://hawstein.com/posts/ctci-solutions-contents.html声明：本文采用以下协议进行授权： 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ，转载请注明作者及出处。前言《Cracking the coding interview》是一本被许多