字符串和链表的习题
...
实现抽象数据类型
使用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...
数据结构概述
数据结构就是按一定的逻辑关系组织起来的待处理数据元素的表示和相关操作,包含数据的逻辑结构,存储结构和数据的运算. 数据的逻辑结构 从具体问题中抽象出来的数学模型,反应了事物的组成结构和事物之间的逻辑关系. 逻辑结构可以用一个二元组B = (K,...
数组相关的问题
本章导读 笔试和面试中，除了字符串，另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后，读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举（递归、回溯），如求n个数的全排列或八皇后（N皇后问题）。但因为穷举时间复杂度通常过高，所以需要考虑更好的方法，如分治法（通过分而治之，然后归并），以及空间换时间（如活用哈希表）。 此外，选择合适的数据结构可以显著提升效率，如寻找最小的k个数中，用堆代替数组。 再有，如果题目允许排序，则可以考虑排序。比如，寻找和为定值的两个数中，先排序，然后用前后两个指针往中间扫。而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必要二分。但是，如果题目不允许排序呢？这个时候，我们可以考虑不改变数列顺序的贪心算法（如最小生成树Prim、Kruskal及最短路dijkstra），或动态规划（如 01背包问题，每一步都在决策）。 最后，注意细节处理，不要忽略边界条件，如字符串转换成整数。