1.2 字符串包含
字符串包含 题目描述 给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？ 为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B) 比如，如果是下面两个字符串： String 1：ABCD String 2：BAD 答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。 如果是下面两个字符串： String 1：ABCD String 2：BCE 答案是false，因为字符串String2里的E字母不在字符串String1里。 同时，如果string1：ABCD，string...
1.3 字符串转换成整数
字符串转换成整数 题目描述 输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串"123"，输出整数123。 给定函数原型int StrToInt(const char *str)...
1.4回文判断
#回文判断 题目描述 回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗。 那么，我们的第一个问题就是：判断一个字串是否是回文？ 分析与解法 回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也比较广泛，而且也是面试题中的常客，所以本节就结合几个典型的例子来体味下回文之趣。 解法一 同时从字符串头尾开始向中间扫描字串，如果所有字符都一样，那么这个字串就是一个回文。采用这种方法的话，我们只需要维护头部和尾部两个扫描指针即可。 代码如下：： 123456789101112131415161718192021222324bool IsPalindrome(const char *s, int n){ // 非法输入 if (s == NULL || n < 1) { return false; } const char* front,*back; // 初始化头指针和尾指针 front...
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...
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...
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...
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...