这部分的问题都集中在数据集合上。主要有：
- 数组排序
- top-k
- 子数组
- 多个数组合并，交集
解决这一类问题时，可以从以下几个方面考虑：
- 万能的蛮力穷举
- 散列表空间换事件
- 分治法，然后归并 （归并排序）
- 选择合适的数据结构可以显著提高算法效率 （堆排序求top-k）
- 对无序的数组先排序，使用二分
- 贪心算法或动态规划
题目：定义Fibonacci数列如下：
0 n=0
f(n)= 1 n=1
f(n-1)+f(n-2) n=2
输入n，用最快的方法求该数列的第n项。
思路一：递归，虽然fibonacci数列是递归的经典应用，但递归效率很差，会有很多重复的计算，复杂度是成指数递增的,我测试了下计算50的时候已经要300s了。
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
思路二：从下往上计算，复杂度O（N），一个循环就搞定
public int fib(int n){
if (n == 0) return 0;
//缓存
int[] dp = new int[n + 1];
// base case
dp[0] = 0; dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
说一个细节优化点，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
int fib(int n) {
if (n < 1) return 0;
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5} 是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
- 右移，二分查找。 找到最小的数，右移到第一个位置的时候，右移完成 O(N)
- 直接二分查找
给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里
分析：扑克牌54张2~10,J,Q,K,A,小王，大王
1）产生随机数， 随机数 rand()%54 ,rand()每次运行都一样，要改为srand(time(NULL)) 2) 遍历数组, 随机数k属于区间[i,n]，然后a[i] 和 随机数 a[k] 对换
在一维坐标轴上有n个区间段，求重合区间最长的两个区间段 如【-7，21】，【4，23】，【14，100】，【54，76】
思路一：两两比较，复杂度 N^2 思路二：先排序+分而治之
在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。 直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数， 一个解答：这需要两次遍历，然后再遍历一次原数组， 将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。 给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。
一排N（最大１Ｍ）个正整数+1递增，乱序排列，第一个不是最小的，把它换成-1， 最小数为ａ且未知。求第一个被-1替换掉的数原来的值，并分析算法复杂度。
[4,3,5,2,7,6] 题目啥意思？
正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12 (1)、设计一个函数void generate（int a,int b,int N ,int * Q）计算Q的前几项 (2)、设计测试数据来验证函数程序在各种输入下的正确性。
分析： 这个输出序列是要 递增排列 思路一： 类似对2各数组merge，取min( A[i],B[j]) .复杂度O(N) 不过这里要注意，去掉 a， b的公倍数。如 3，5 都有15可以整除
题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。 例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。 请给出解决问题的算法，并证明该算法。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素， 时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。
n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。
如 0,1,2,3,4,5 删除第2个数字 （n=6，m=2）
第一次删除：1
第二次删除: 3
第三次删除：5
第四次删除：2
因此，左后的一个数字就是 4
从数学上分析下规律：
题目描述：请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。 对一个正整数 n ，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B ，则 n 属于该行； 如果 n 同时属于行i和j ，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为 [12 20] ，其大小为9，行(20 10)和（ 20 30 ）的重叠区间大小为 1 。
比如两对括号可以有两种：（）（）和（（））
有一个整数数组,请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。 如 [-1， 3， 5， 9] 绝对值最小的是2（5-3）
最短区间问题 如果是有重复元素，那最小值就是0了
解题思路: 可以将这个问题转化为 ”求最大字段和“ 问题。。。
一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。 注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。
这个问题跟”扑克牌顺子“判断问题一样，通过比较0的个数和相邻数字之间间隔总和来判断所有数是否连续。
////////////// 数列 ///////////////
给出两个集合A和B，其中集合A={name}， 集合B={age、sex、scholarship、address、...}，
要求： 问题1、根据集合A中的name查询出集合B中对应的属性信息； 问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name。