1.5最长回文子串
最长回文子串 题目描述 给定一个字符串，求它的最长回文子串的长度。 分析与解法 最容易想到的办法是枚举所有的子串，分别判断其是否为回文。这个思路初看起来是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的。 解法一 那么如何高效的进行判断呢？我们想想，如果一段字符串是回文，那么以某个字符为中心的前缀和后缀都是相同的，例如以一段回文串“aba”为例，以b为中心，它的前缀和后缀都是相同的，都是a。 那么，我们是否可以可以枚举中心位置，然后再在该位置上用扩展法，记录并更新得到的最长的回文长度呢？答案是肯定的，参考代码如下： 12345678910111213141516171819202122232425int LongestPalindrome(const char *s, int n){ int i, j, max,c; if (s == 0 || n < 1) return 0; max = 0; for (i = 0; i < n; ++i) { // i is the middle...
1.6字符串的全排列
字符串的全排列 题目描述 输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。 分析与解法 解法一、递归实现 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例 固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac 固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba 固定c，求后面ba的排列：cba，cab。 代码可如下编写所示： 1234567891011121314151617181920212223void CalcAllPermutation(char* perm, int from, int to){ if (to <= 1) { return; } if (from == to) { for (int i = 0; i...
10.01.01
sift算法的编译与实现 代码：Rob Hess维护的sift 库。 环境：windows xp+vc6.0。 条件：opencv1.0、gsl-1.8.exe 昨日，下载了Rob Hess的sift库，将其源码粗略的看了看，想要编译时，遇到了不少问题，先修改了下代码，然后下载opencv、gsl。最后，几经周折，才最终编译成功。 以下便是sift源码库编译后的效果图： 为了给有兴趣实现sift算法的朋友提供个参考，特整理此文如下。要了解什么是sift算法，请参考：九、图像特征提取与匹配之SIFT算法。ok，咱们下面，就来利用Rob Hess维护的sift 库来实现sift算法： 首先，请下载Rob Hess维护的sift 库： http://blogs.oregonstate.edu/hess/code/sift 下载Rob Hess的这个压缩包后，如果直接解压缩，直接编译，那么会出现下面的错误提示： 编译提示:error C1083: Cannot open include file: 'cxcore.h': No such file or...
10.01.02
教你一步一步用c语言实现sift算法、上 参考：Rob Hess维护的sift 库 环境：windows xp+vc6.0 条件：c语言实现。 引言： 在我写的关于sift算法的前倆篇文章里头，已经对sift算法有了初步的介绍：九、图像特征提取与匹配之SIFT算法，而后在：九（续）、sift算法的编译与实现里，我也简单记录下了如何利用opencv，gsl等库编译运行sift程序。 但据一朋友表示，是否能用c语言实现sift算法，同时，尽量不用到opencv，gsl等第三方库之类的东西。而且，Rob Hess维护的sift 库，也不好懂，有的人根本搞不懂是怎么一回事。 那么本文，就教你如何利用c语言一步一步实现sift算法，同时，你也就能真正明白sift算法到底是怎么一回事了。 ok，先看一下，本程序最终运行的效果图，sift...
40亿个数中快速查找
40亿个数中快速查找 题目描述 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？ 分析与解法 海量数据处理往往会很有趣，有趣在什么地方呢？ 空间，available的内存不够，需要反复交换内存 时间，速度太慢不行，毕竟那是海量数据 处理，数据是一次调用还是反复调用，因为针对时间和空间，通常来说，多次调用的话，势必会增加预处理以减少每次调用的时候的时间代价。 解法一 咱们回到眼前要解决的这个问题，1个unsigned int占用4字节，40亿大约是4G个数，那么一共大约要用16G的内存空间，如果内存不够大，反复和硬盘交换数据的话，后果不堪设想。 那么怎么储存这么多的数据呢？还记得伴随数组么？还是那种思想，利用内存地址代替下标。 先举例，在内存中应该是1个byte=8bit，那么明显有 0 = 0000 0000 255 = 1111 1111 69 = 0100...
K个最小和 (UVA 11997 K Smallest Sums)
题目大意： You’re given k arrays, each array has k integers. There are k^k ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them. Input There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size...
Readme
#《编程之法：面试和算法心得》 ##目录 第一部分 数据结构 第一章 字符串 1.0 本章导读 1.1 旋转字符串 1.2 字符串包含 1.3 字符串转换成整数 1.4 回文判断 1.5 最长回文子串 1.6 字符串的全排列 1.10 本章习题 第二章 数组 2.0 本章导读 2.1 寻找最小的 k 个数 2.2 寻找和为定值的两个数 2.3 寻找和为定值的多个数 2.4 最大连续子数组和 2.5 跳台阶 2.6 奇偶排序 2.7 荷兰国旗 2.8 矩阵相乘 2.9 完美洗牌 2.15 本章习题 第三章 树 3.0 本章导读 3.1 红黑树 3.2 B树 3.3 最近公共祖先LCA 3.10 本章习题 第二部分 算法心得 第四章 查找匹配 4.1 有序数组的查找 4.2 行列递增矩阵的查找 4.3 出现次数超过一半的数字 第五章 动态规划 5.0 本章导读 5.1 最大连续乘积子串 5.2 字符串编辑距离 5.3 格子取数 5.4 交替字符串 5.10 本章习题 第三部分 综合演练 第六章 海量数据处理 6.0 本章导读 6.1...
10.01.03
...
一致性哈希算法
一致性哈希算法 tencent2012笔试题附加题 问题描述： 例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。 已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%（n-1）]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。 问： 如何改进或者换一种方法，使得： (1)...
hash表算法
hash表算法 ##第一部分：Top K 算法详解 ####问题描述 百度面试题： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。 ####必备知识 什么是哈希表？ 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表hashtable(key，value)...