傅里叶变换算法、下
从头到尾彻底理解傅里叶变换算法、下 推荐阅读：The Scientist and Engineer’s Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。此书地址：http://www.dspguide.com/pdfbook.htm。 前期回顾，在上一篇里，我们讲了傅立叶变换的由来、和实数形式离散傅立叶变换（Real...
后缀树
后缀树 1.1、后缀树的定义 后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出，既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。 后缀，顾名思义，就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2…Si…Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn便都是字符串S的后缀。 以字符串S=XMADAMYX为例，它的长度为8，所以S[1…8], S[2…8], … , S[8…8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i…n]，我们说这项后缀起始于i。 S[1…8], XMADAMYX， 也就是字符串本身，起始位置为1 S[2…8], MADAMYX，起始位置为2 S[3…8], ADAMYX，起始位置为3 S[4…8], DAMYX，起始位置为4 S[5…8], AMYX，起始位置为5 S[6…8], MYX，起始位置为6 S[7…8], YX，起始位置为7 S[8…8],...
奇偶调序
...
字符串和链表的习题
...
字符串问题
本章导读 字符串相关的问题在各大互联网公司笔试面试中出现的频率极高，比如微软经典的单词翻转题：输入“I am a student.”，则输出“student. a am I”。 本章重点介绍6个经典的字符串问题，分别是旋转字符串、字符串包含、字符串转换成整数、回文判断、最长回文子串、字符串的全排列，这6个问题要么从暴力解法入手，然后逐步优化，要么多种思路多种解法。 读完本章后会发现，好的思路都是在充分考虑到问题本身的特征的前提下，或巧用合适的数据结构，或选择合适的算法降低时间复杂度（避免不必要的操作），或选用效率更高的算法。
实现抽象数据类型
使用C++类声明(或使用其他语言实现下列功能)定义复数的抽象数据类型.要求 在复数内部用浮点数定义实部虚部 实现三个构造函数:默认的构造函数没有参数;第二个将双精度浮点数赋值给实部,虚部为0;第三个将双精度浮点数赋值给实部和虚部. 定义获取和修改复数实部和虚部以及+-*/等运算的成员函数. 定义重载的流函数来输出一个复数.
完美洗牌算法
...
寻找和为定值的两个数
题目描述 输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。 要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。 分析与解法 咱们试着一步一步解决这个问题（注意阐述中数列有序无序的区别）： 直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此举复杂度为O(N^2)。很显然，我们要寻找效率更高的解法 题目相当于，对每个a[i]，查找sum-a[i]是否也在原始序列中，每一次要查找的时间都要花费为O(N)，这样下来，最终找到两个数还是需要O（N^2）的复杂度。那如何提高查找判断的速度呢？ 答案是二分查找，可以将O(N)的查找时间提高到O(log N)，这样对于N个a[i]，都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中，总的时间复杂度已降为O(N log N)，且空间复杂度为O(1)。 （如果有序，直接二分O(N log N)，如果无序，先排序后二分，复杂度同样为O（N log N + N log...
寻找和为定值的多个数
题目描述 输入两个整数n和sum，从数列1，2，3…n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。 分析与解法 解法一 注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相关的问题。 如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum - n, n - 1)； 如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。 参考代码如下： 1234567891011121314151617181920212223list<int>list1;void SumOfkNumber(int sum, int n){ // 递归出口 if (n <= 0 || sum <= 0) return; // 输出找到的结果 if (sum == n) { // 反转list list1.reverse(); for...