第三章 字符串
字符串特点：
广泛性(1)字符类型数组；(2)其它类型题目可以看做字符串类型题目。Java处理字符串须注意String类在Java中不可更改，可尝试StringBuffer类，StringBuilder类和toCharArray方法处理。
字符串相关概念：
回文；字串(连续)；子序列(不连续)；前缀树(Trie树)；后缀树和后缀数组；匹配；字典
序
需掌握的操作：
与数组有关的操作(增删改查)；字符的替换；字符串的旋转
常见类型：判断规则；数字运算；与数组操作有关的类型；字符计数；动态规划类型(最长公共字串等)；搜索类型；高级算法与数据结构解决的问题。
栈和队列
基本性质：栈是先进后出，队列是先进先出；栈和队列在实现结构上可以有数组和链表两种形式(数组结构容易，链表涉及很多指针操作)
栈结构基本操作：pop；top或peek；push；size
双端队列：首尾都可以压入弹出元素；优先级队列：根据元素的优先级值，决定元素的弹出顺序，实为堆结构，并不是线性结构
深度优先遍历用栈来实现，宽度优先用队列实现，平时使用的递归函数实际上用到了提供的函数系统栈。
链表
链表和数组区别：都是一种线性结构，数组是一段连续的存储空间，而链表空间不一定保证连续，为临时分配；
链表分类：按连接方向(单链表，双链表)；按照有无环分类(普通链表，循环链表)
代码实现的关键点：(1)链表调整函数的返回值类型，根据要求往往是节点类型；(2)处理链表过程中，先采用画图的方式理清逻辑；(3)对于边界条件处理。
插入删除注意事项：(1)特殊处理链表为空，或者链表长度为1的情况；(2)注意插入操作的调整过程；(3)注意删除操作调整过程。注意点：头尾节点及空节点需要特殊考虑。
单链表的翻转操作：(1)当链表为空或者长度为时，特殊处理；(2)对于一般情况如动画所示。
二分搜索
int Binary_Search(SeqList L,int n,ElemType k){ int low=0,high=n-1,mid; while(low<=high) { mid=(low+high)/2; if(L[mid].key==k) return mid+1; if(L[mid].key>k) high=mid-1; else low=mid+1; } return 0; }
常见应用场景
在有序序列中查找一个数，时间复杂度为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)2 得到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。
异或运算满足交换律，结合律。
1
2
(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逐渐成为面试热门
Map阶段 –> 把大任务分成子任务。
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. 根据记忆化搜索方法该出动态规划方法，进而看看是否能化简，如果能化简，还能实现时间复杂度更低的动态规划方法。
