「数据结构与算法」面试中常见的数据结构与算法

数据结构与算法

第二章排序

2.1 O(n²) 算法

给定一数组，其大小为8个元素，数组内的数据无序。

6 3 5 7 0 4 1 2

冒泡排序：两两比较，将两者较少的升上去，第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1

public class bubbleSort {

    public static void main(String[] args) {
        int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
        for (int i = 0; i < test.length - 1; i++) {
            for (int j = 0; j < test.length - i - 1; j++) {
                if (test[j] > test[j + 1]) {
                    int temp = test[j];
                    test[j] = test[j + 1];
                    test[j + 1] = temp;
                }
            }
        }
        for (int k = 0; k < test.length; k++) {
            System.out.println(test[k]);
        }

    }

}

选择排序：在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换……第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

public class selectSort {

    public static void main(String[] args) {
        int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
        for (int i = 0; i < test.length; i++) {
            int min = i;
            for (int j = i + 1; j < test.length; j++) {
                if (test[min] > test[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = test[i];
                test[i] = test[min];
                test[min] = temp;
            }
        }
        for (int k = 0; k < test.length; k++) {
            System.out.println(test[k]);
        }
    }

}

插入排序：对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

public class insertSort {
    public static void main(String[] args) {
        int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
        for (int i = 0; i < test.length; i++) {
            for (int j = i; j > 0; j--) {
                if (test[j] < test[j - 1]) {
                    int temp = test[j];
                    test[j] = test[j - 1];
                    test[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
        for (int k = 0; k < test.length; k++) {
            System.out.println(test[k]);
        }
    }

}

2.2 O(nlogN) 算法

归并排序:将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列（分治法），每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
快速排序：任取一个分界值，大于划分值放在右边，小于划分值放在左边，然后分别递归处理划分值的左右两边。实现方法：将划分值放在数组最后的位置，然后初始化一个长度为0的小于等于空间放在最左边，接着从左到右遍历所有元素，如果当前元素大于划分值，继续遍历下一个元素，如果当前元素小于等于划分值，将当前数和小于等于空间的下一个数交换位置，小于等于空间向右扩一个位置，遍历完所有元素，直到最后一个数，将划分值与小于等于空间下一个元素交换。（一次完整划分过程）

堆排序：堆是一种重要的数据结构，为一棵完全二叉树,底层如果用数组存储数据的话，假设某个元素为序号为i(java数组从0开始,i为0到n-1),如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序，我们使用的是最大堆。堆排序的大概步骤如下:(1)构建最大堆；(2)选择顶，并与第0位置元素交换；(3)由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2。
希尔排序：又称缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序，一般增量设置由大到小。

2.3 O(N) 算法

思想：不是基于比较，而是来自于桶排序，桶排序的基本思想则是把数则是arr划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。

计数排序：需要占用大量空间，它仅适用于数据比较集中的情况。比如[0~100]，[10000~19999]这样的数据，对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数，假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。
基数排序：实质为多关键字排序，思路是将待排数据里排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字等，然后，根据子关键字对待排序数据进行排序，如个位数，十位数，百位数等。

经典排序算法的空间复杂度

O(1)：插入排序、选择排序、冒泡排序、堆排序、希尔排序；
O(logN)~O(N)：快速排序；
O(N)：归并排序；
O(M): 计数排序、基数排序（和选择桶的数量有关）。

经典排序算法的稳定性

稳定性：假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。

稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

第三章字符串

字符串特点：广泛性(1)字符类型数组；(2)其它类型题目可以看做字符串类型题目。Java处理字符串须注意String类在Java中不可更改，可尝试StringBuffer类，string builder类和toCharArray方法处理。
字符串相关概念：回文；字串（连续）；子序列（不连续）；前缀树（Trie树）；后缀树和后缀数组；匹配；字典序
需掌握的操作：与数组有关的操作（增删改查）；字符的替换；字符串的旋转
常见类型：判断规则；数字运算；与数组操作有关的类型；字符计数；动态规划类型（最长公共字串等）；搜索类型；高级算法与数据结构解决的问题。

栈和队列

基本性质：栈是先进后出，队列是先进先出；栈和队列在实现结构上可以有数组和链表两种形式（数组结构容易，链表涉及很多指针操作）
栈结构基本操作：pop；top或peek；push；size
双端队列：首尾都可以压入弹出元素；优先级队列：根据元素的优先级值，决定元素的弹出顺序，实为堆结构，并不是线性结构
深度优先遍历用栈来实现，宽度优先用队列实现，平时使用的递归函数实际上用到了提供的函数系统栈。

链表

链表和数组区别：都是一种线性结构，数组是一段连续的存储空间，而链表空间不一定保证连续，为临时分配；
链表分类：按连接方向（单链表，双链表）；按照有无环分类（普通链表，循环链表）
代码实现的关键点：(1)链表调整函数的返回值类型，根据要求往往是节点类型；(2)处理链表过程中，先采用画图的方式理清逻辑；(3)对于边界条件处理。
插入删除注意事项：(1)特殊处理链表为空，或者链表长度为1的情况；(2)注意插入操作的调整过程；(3)注意删除操作调整过程。注意点：头尾节点及空节点需要特殊考虑。
单链表的翻转操作：(1)当链表为空或者长度为时，特殊处理；(2)对于一般情况如动画所示。

单链表翻转

二分搜索

常见应用场景

在有序序列中查找一个数，时间复杂度为O(logN);
并不一定非要在有序序列中才得到应用。

常见考察点

对于边界条件的考察以及代码实现的能力

常见题目变化

给定处理或查找的对象不同；
判断条件不同；
要求返回的内容不同。

重要提醒

mid = (left + right)/2

(left+right)可能会溢出，更安全的写法：

mid = left + (right - left)/2

位运算

常见操作符

算术运算常见操作符：+ - * / %
位运算常见操作符：& | ^ ~ <<(左移右侧补0) >>(右移左侧补符号位) >>>(右移左侧补0)

案例

(1) 网页黑名单系统，垃圾邮件过滤系统，爬虫的网址判断重复系统，容忍一定程度的失误率，但对空间要求较严格。

布隆过滤器：可精确地代表一个集合；可精确判断某一元素是否在此集合中；精确程度由用户的具体设计决定；做到100%的精确即正确是不可能的。布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。

这里写图片描述

布隆过滤器的bitarray大小如何确定？
大小为m(过小)，样本数量为n(相较于m过大)，失误率为p(过大)。

举例输入：n = 100亿，p = 0.01%

1. m = - n x lnp / (ln2)² 得到m = 19.19n 向上取整为20n，2000亿bit，约为25G。 2. k = ln2 x m/n = 0.7 x m/n = 14 因此需要14个彼此独立的哈希函数。 3. 此时失误率为(1 - e^-nk/m)^k = 0.006%，其中m = 20n, k = 14。

(2) 不用任何额外变量交换两个整数的值

给定整数a和b
a = a0, b = b0
a = a ^ b --> a = a0 ^ b0, b = b0;
b = a ^ b --> a = a0 ^ b0, b = a0 ^ b0 ^ b0 = a0;
a = a ^ b --> a = a0 ^ b0 ^ a0 = b0, b = a0;

(3) 给定两个32位整数a和b，返回a和b中较大的，但是不能用任何比较判断。

方法1：得到a - b的符号，根据该符号决定返回a或b。

public static int flip(int n){
    return n ^ 1;
}
public static int sign(int n){
    return flip((n >> 31) & 1);
}
public static int getMax(int a, int b){
    int c = a - b;
    int scA = sign(c);
    int scB = flip(scA);
    return a = a * scA + b * scB;
}

方法一可能会有问题，当a = b溢出时，会发生错误。

方法2

public static int getMax(int a, int b){
    int c = a - b; 
    int as = sign(a); //a的符号，as == 1表示a为非负，as == 0表示a为负
    int bs = sign(b);  //b的符号，bs == 1表示a为非负，bs == 0表示b为负
    int cs = sign(c);  //a - b的符号
    int difab = as ^ bs;  //表示a和b是否符号不相同，不相同为1，相同为0
    int sameab = flip(difab);  //表示a和b是否符号相同，相同为1，不相同为0
    int returnA = difab + as + sameab + cs;
    int returnB = flip(returnA)
    return  a * returnA + b * returnB;
}

(3) 给定一个整型数组arr，其中只有一个数出现了奇数次，其他数都出现了偶数次，请打印这个数，要求时间复杂度为O(n)，额外空间复杂度为O(1)。

注意点：n与0异或结果为n，n与n异或结果为0。
异或运算满足交换律，结合律。

(4) 给定一个整型数组arr，其中有两个数出现了奇数次，其他数都出现了偶数次，请打印这个数，要求时间复杂度为O(n)，额外空间复杂度为O(1)。

(5) 请设置一种加密过程，完成对明文text的加密和解密工作。

明文text，用户给定密码pw，假设密文为cipher。
cipher = text ^ pw
text = cipher ^ pw = text ^ pw ^ pw = text
如果text长度大于pw，循环使用pw与text进行按位异或。

排列组合

概率组合题目分类

以高中数学为基础的古典概率计算方法；
斐波那契数和卡特兰数；
以选择题居多

案例

在6x9的方格中，以左上角为起点，右下角为终点，每次只能向下或者向右走，请问一共有多少种不同的走法。

解法：一共走13步，其中必然有5步向下，剩下的8步向右，所以一共有C13(5) = 1287.

ABCDEFG七人战队，要求A必须站在B的左边，但不要求一定相邻，请问共有多少种排法？如果要求A必须在B的左边，并且一定要相邻，请问一共有多少种排法？

不相邻：一共有7!种排法，其中一半的情况是A在B的左边，一半的情况是B在A的左边，所以第一种情况共有7!/2 = 2520种
相邻：A和B看作为一个人，所以第二种情况为6! = 720种

A六个人排成一排，要求甲与乙不相邻，并且甲与丙不相邻的排法数是多少？

方法一：
6个人全排列6! = 720; 甲与乙相邻总数2 * 5! = 240; 甲与丙相邻总数2 * 5! = 240; 相交的情况(乙甲丙或丙甲乙)2 * 4! = 48种
720 - 240 -240 + 48 = 288
方法二：
考虑甲的位置 3 * 4! * 2 + 6 * 3! * 4 = 288

卡特兰数重要公式

概率

常见问题类型

作为客观题出现；
概率、期望计算；
往往利用古典概率进行计算(组合数学)。

概率的应用

利用随机来改进著名算法(快速排序)；
随机数发生器(用给定的随机数发生器构造另一个)；

案例

8只球队，有3个强队，其余都是弱队，随机把它们分成四组比赛，每组两个队，问两强相遇的概率是多大？

1. 首先求出8只球队分成4组比赛的方法数：7 x 5 x 3 x 1 = 105;
2. 没有两强相遇的方法数：C5(3) x A3(3) = 60;
3. (105 - 60)/105 = 3/7

三只蚂蚁从正三角形的三个顶点沿着边移动，速度是相同的，问他们碰头的概率是多少？

方向相同不会相遇，所以(8 - 2)/8 =  3/4

某地区重男轻女，一个家庭如果生出一个女孩就一直生，直到生出男孩就停止生育。假设一胎只出生一个孩子，问时间足够长后，男女比例是会变为多少？

男女比例依然为1:1

给定一个等概率随机产生1~5的随机数，除此之外，不能使用任何额外的随机机制，请实现等概率随机产生1~7的随机函数。

1. 已经有等概率随机产生1、2、3、4、5的随机函数；
2. 根据步骤1得到的结果减1，将得到f() → 0、1、2、3、4；
3. f() x 5 → 0、5、10、15、20；
4. f() x 5 + f()→ 0、1、2、3、4...24；
注意：步骤4中的f()是分别调用的，不要化简。
5. 如果步骤4产生的数大于20，则重复地进行步骤4，直到产生的结果在0~20之间；
6. 步骤5的结果将等概率产生0~20，所以步骤5的结果%7之后等概率产生0~6;
7. 步骤6的结果加1，将等概率产生1~7.

大数据

哈希函数(散列函数)：拥有无限的输入值域；输入值相同时，返回值一样；输入值不同时，返回值可能一样，也可能不一样；不同输入值得到的哈希值，整体均匀的分布在输出域上。

1~3点性质是哈希函数的基础，第4点是评价一个哈希函数优劣的关键。MD5与SHA1算法都是经典的哈希函数算法，了解即可。

Map-Reduce和Hadoop逐渐成为面试热门
1. Map阶段 –> 把大任务分成子任务。
2. Reduce阶段 –>子任务并发处理，然后合并结果。

注意点：备份的考虑，分布式存储的设计细节，以及容灾策略；任务分配策略与任务进度跟踪的细节设计，节点状态的呈现；多用户权限的控制。

常见海量处理题目解题关键

分而治之。通过哈希函数将大任务分流到机器上或分流成小文件；
常用的hashMap或bitmap。
难点：通讯、时间和空间的估算。
一致性哈希算法

动态规划

CSDN博主：常敲代码手不抖

1. 教你彻底学会动态规划——入门篇

2. 教你彻底学会动态规划——进阶篇

案例

给定数组arr，arr中所有的值都为正数且不重复，每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。

arr = [5、10、25、1], aim = 1000.

暴力搜索方法–>记忆搜索方法–>动态规划方法–>状态继续化简后的动态规划方法

暴力搜索

1. 用0张5元的货币，让[10,25,1]组成剩下的1000，最终方法数记为---------------------------res1
2. 用1张5元的货币，让让[10,25,1]组成剩下的995，最终方法数记为---------------------------res2
3. 用2张5元的货币，让让[10,25,1]组成剩下的990，最终方法数记为---------------------------res3

...........................................................................................

201. 用200张5元的货币，让让[10,25,1]组成剩下的0，最终方法数记为-------------------------res201
定义递归函数：int p1(arr,index,aim)，它的含义是如果用arr[index...N-1]这些面值的钱组成aim,返回总的方法数。

记忆搜索

arr = [5、10、25、1], aim = 1000. p(index,aim) 结果表map
1. 每计算完一个p(index,aim)，都将结果放入到map中，index和aim组成共同key，返回结果为value;
2. 要进入一个递归过程p(index,aim)，先以index和aim注册的key在map中查询是否已经存在value，如果存在，则直接取值，如果不存在，才进行递归运算。

动态规划

如果arr长度为N，生成行数为N，列数为aim + 1的矩阵dp.dp[i][j]的含义是在使用arr[0...i]货币的情况下，组成钱数j有多少种方法。

动态规划

记忆搜索方法与动态规划方法的联系
1. 记忆化搜索方法就是某种形态的动态规划方法；
2. 记忆化搜索方法不关心到达某一个递归过程的路径，只是单纯地对计算过的递归过程进行记录，避免重复的递归过程；
3. 动态规划的方法则是规定好每一个递归过程的计算顺序，依次进行计算，后面的计算过程严格依赖前面的计算过程；
4. 两者都是空间换时间的方法，也都有枚举的过程，区别就在于动态规划规定计算顺序，而记忆搜索不用规定。

什么是动态规划方法？
1. 其本质是利用申请的空间来记录每一个暴力搜索的计算结果，下次要用结果的时候直接使用，而不再进行重复的递归过程；
2. 动态规划规定每一种递归状态的计算顺序，依次进行计算。

状态继续化简后动态规划方法

动态规划方法中dp[i][j]等于如下值的累加：
dp[i-1][j]
dp[i-1][j-1*arr[i]]
dp[i-1][j-2*arr[i]]
dp[i-1][j-3*arr[i]]

以上可以化简为：dp[i][j] = dp[i-1][j-arr[i]] + dp[i-1][j]

暴力递归题目可以优化成动态规划方法的大体过程：
1. 实现暴力递归方法；
2. 在暴力搜索方法的函数中看看哪些参数可以代表递归过程；
3. 找到代表递归过程的参数之后，记忆化搜索的方法非常容易实现，利用hashmap将部分递归值进行存储；
4. 通过分析记忆化搜索的依赖路径，进而实现动态规划；
5. 根据记忆化搜索方法该出动态规划方法，进而看看是否能化简，如果能化简，还能实现时间复杂度更低的动态规划方法。

面试中常见的数据结构与算法