字符串和链表的习题
...
字符串问题
本章导读 字符串相关的问题在各大互联网公司笔试面试中出现的频率极高，比如微软经典的单词翻转题：输入“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...
寻找最小的k个数
题目描述 输入n个整数，输出其中最小的k个 分析与解法 解法一 要求一个序列中最小的k个数，按照惯有的思维方式，则是先对这个序列从小到大排序，然后输出前面的最小的k个数。 至于选取什么的排序方法，我想你可能会第一时间想到快速排序（我们知道，快速排序平均所费时间为n*logn），然后再遍历序列中前k个元素输出即可。因此，总的时间复杂度：O（n * log n)+O(k)=O（n * log n）。 解法二 咱们再进一步想想，题目没有要求最小的k个数有序，也没要求最后n-k个数有序。既然如此，就没有必要对所有元素进行排序。这时，咱们想到了用选择或交换排序，即： 1、遍历n个数，把最先遍历到的k个数存入到大小为k的数组中，假设它们即是最小的k个数； 2、对这k个数，利用选择或交换排序找到这k个元素中的最大值kmax（找最大值需要遍历这k个数，时间复杂度为O（k））； 3、继续遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与kmax比较：如果x < kmax ，用x替换kmax，并回到第二步重新找出k个元素的数组中最大元素kmax‘；如果x >=...
搜索关键词智能提示suggestion
搜索关键词智能提示suggestion 题目详情 百度搜索框中，输入“北京”，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词，输入“结构之”，会提示“结构之法”，“结构之法 算法之道”等搜索词。 请问，如何设计此系统，使得空间和时间复杂度尽量低。 分析与解法 本题来源于去年2012年百度的一套实习生笔试题中的系统设计题（为尊重原题，本章主要使用百度搜索引擎展开论述，而不是google等其它搜索引擎，但原理不会差太多。然脱离本题，平时搜的时候，鼓励用…），题目比较开放，考察的目的在于看应聘者解决问题的思路是否清晰明确，其次便是看能考虑到多少细节。 我去年整理此题的时候，曾简单解析过，提出的方法是： 直接上Trie树「Trie树的介绍见：从Trie树（字典树）谈到后缀树」 + TOP K「hashmap+堆，hashmap+堆 统计出如10个近似的热词，也就是说，只存与关键词近似的比如10个热词」 方法就是这样子的：Trie树+TOP K算法，但在实际中，真的只要Trie树 + TOP...
数据结构与算法概述
计算机科学已经深入应用到各个领域,不仅能有效解决各种工程和科学计算中的数值计算,而且还有效解决了许多文本处理,信息检索,数据库管理,图像识别,人工智能等非数值数据的处理. 什么是数据结构 百度百科对于数据结构的定义为： 数据结构(data...