目录
第7章
1 不用额外变量交换两个整数的值(士 ★☆☆☆)
2 不用任何比较判断找出两个数中较大的数(校★★★☆)
3 只用位运算不用算术运算实现整数的加减乘除运算
4 整数的二进制表达中有多少个1
5 在其他数都出现偶数次的数组中找到出现奇数次的数
6 在其他数都出现A次的数组中找到只出现一次的数
第8章
1 转圈打印矩阵
2 将正方形矩阵顺时针转动90度
3 之字形打印矩阵
4 找到无序数组中最小的k个数
5 需要排序的最短子数组长度
6 在数组中找到出现次数大于N/K的数
7 在行列都排好序的矩阵中找数
8 最长的可整合子数组的长度
9 不重复打印排序数组中相加和为给定值的所有二元组和三元组
10 未排序正数数组中累加和为给定值的
11 最长子数组长度
12 未排序数组中累加和为给定值的最长子数组系列问题
13 未排序数组中累加和小于或等于给定值的最长子数组长度
14 计算数组的小和
15 自然数数组的排序
16 奇数下标都是奇数或者偶数下标都是偶数
17 子数组的最大累加和问题
18 子矩阵的最大累加和问题
19 在数组中找到一个局部最小的位置
20 数组中子数组的最累乘积
21 打印N个数组整体最大的TopK
22 边界都是1的最大正方形大小
23 不包含本位置值的累乘数组
24 数组的partition调整
25 求最短通路值
26 数组中未出现的最小正整数
27 数组排序之后相邻数的最大差值
第9章
1 从5随机到7随机及其扩展
2 一行代码求两个数的最大公约数
3 有关阶乘的两个问题
4 判断一个点是否在矩形的内部
5 判断一个点是否在三角形内部
6 折纸问题
7 蓄水池算法
8 设计有setAll功能的哈希表
9 最大的leftMax与rightMax之差的绝对值
10 设计可以变更的缓存结构
11 设计RandoPool结构
12 调整[0,x)区间上的数出现的概率
13 路径数组变为统计数组
14 正数数组的最小不可组成和
15 一种字符串和数字的对应关系
16 1到n中1出现的次数
17 从N个数中等概率打印M个数
18 判断一个数是否是回文数
19 在有序旋转数组中找到最小值
19 在有序旋转数组中找到一个数
20 数字的英文表达和中文表达
21 分糖果问题
22 一种消息接收并打印的结构设计
23 设计一个没有扩容负担的堆结构
24 随时找到数据流的中位数
25 在两个长度相等的排序数组中找到上中位数
26 在两个排序数组中找到第K小的数
27 两个有序数组间相加和的TOP K问题
28 Manacher算法
29 KMP算法
30 丢棋子问题
31 画匠问题
32 邮局选址问题
第7章
利用异或的性质，解析可参考书
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int e = 0;
for (int i = 0; i < nums.length; i++) {
e = e^nums[i];
}
return e;
}
第8章
1 转圈打印矩阵
这道题目就是剑指offer中的顺时针打印矩阵，参考剑指offer中的笔记，其实是参考的这本书中的解题思路，利用宏观的调度，不去直接考虑控制移动。
2 将正方形矩阵顺时针转动90度
这道题目中仍可以像上一题中去宏观考虑，将正方形分不同的圈，这样每次只需要一个圈内的数字旋转，那么整个数组便旋转好了，然后圈再不断的缩小
public static void rotate(int[][] matrix) {
//定义左上角和右下角的点
int tR = 0;
int tC = 0;
int dR = matrix.length - 1;
int dC = matrix[0].length - 1;
while (tR < dR) {
//先调用，调用完后再自增的
rotateEdge(matrix, tR++, tC++, dR--, dC--);
}
}
private static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {
int times = dC - tC;
int tmp = 0;
//不断的进行交换
for (int i = 0; i != times; i++) {
tmp = m[tR][tC + i];
m[tR][tC + i] = m[dR - i][tC];
m[dR - i][tC] = m[dR][dC - i];
m[dR][dC - i] = m[tR + i][dC];
m[tR + i][dC] = tmp;
}
}
3 之字形打印矩阵
这道题目和上面两个类似，同样也是考虑宏观调度的问题，不要把问题拘泥于从(0,0)开始什么时候向左下方，什么时候向右下方，什么时候越界
采用a、b两点来进行宏观的调度，每次ab之间便是一条对角线，遍历对角线数据即可，方向可以用一个flag来标志
public static void printMarow1ixZigZag(int[][] marow1ix) {
//定义初始的两个变量，一开始指向(0,0)位置
int row1 = 0;
int col1 = 0;
int row2 = 0;
int col2 = 0;
int endR = marow1ix.length - 1;
int endC = marow1ix[0].length - 1;
//定义对角线的方向
boolean fromUp = false;
while (row1 != endR + 1) {
//打印对角线的数值
printLevel(marow1ix, row1, col1, row2, col2, fromUp);
//控制方向的移动
row1 = col1 == endC ? row1 + 1 : row1;
col1 = col1 == endC ? col1 : col1 + 1;
col2 = row2 == endR ? col2 + 1 : col2;
row2 = row2 == endR ? row2 : row2 + 1;
//控制对角线的方向每次变换
fromUp = !fromUp;
}
System.out.println();
}
private static void printLevel(int[][] m, int row1, int col1, int row2, int col2, boolean f) {
if (f) {
while (row1 != row2 + 1) {
System.out.print(m[row1++][col1--] + " ");
}
} else {
while (row2 != row1 - 1) {
System.out.print(m[row2--][col2++] + " ");
}
}
}
4 找到无序数组中最小的k个数
常用的方法是利用最大堆，其时间复杂度为O(Nlogn)，这里提供一种时间复杂度为O(N)的算法
利用BFPRT算法
5 需要排序的最短子数组长度
6 在数组中找到出现次数大于N/K的数
对于出现次数大于n/2的情况，遍历一次数组删除不同的两个数，剩下的便是符合要求的数。
public int majorityElement(int[] nums) {
int cand = 0; //候选数
int times = 0;//出现的次数
for (int i = 0; i < nums.length; i++) {
if (times == 0){ //当没有候选数时添加一个候选数
cand = nums[i];
times = 1;
}else if (nums[i] == cand){ //当相等时把次数相加
times ++;
}else{
//当不等时，如果直接改变cand前面有可能cand出现了很多次，这样相当于把前面所有的数全部删除了
//因此times--，相当于删除了当前树和一个候选数
times --;
}
}
//判断候选数出现次数是否符合要求，因为还有可能每个数只出现了一次
times = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == cand){
times++;
}
}
if (times > nums.length/2){
return cand;
}else { //当没有符合要求的数时返回-1
return -1;
}
}
进阶：出现n/k次的数
7 在行列都排好序的矩阵中找数
这道题目的详解见剑指offer中：二维数组的查找
8 最长的可整合子数组的长度
9 不重复打印排序数组中相加和为给定值的所有二元组和三元组
10 未排序正数数组中累加和为给定值的
因为全都是正数，扩充一定会增加，缩小一定会减少，因此可以利用窗口进行移动，当累加和小于给定值时窗口R指针向右移动增加数据，当累加和大于等于给定值时窗口L左指针向右移动缩小数据。
public static int getMaxLength(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim <= 0) {
return 0;
}
//设定左右指针累加和
int L = 0;
int R = 0;
int sum = arr[0];
int len = 0;
while (R < arr.length) {
if (sum == aim) {
len = Math.max(len, R - L + 1);
//当相等的时候L或R移动均可，当R移动时一定会出现大于的情况
sum -= arr[L++];
} else if (sum < aim) {
R++;
//保证R不越界
if (R == arr.length) {
break;
}
sum += arr[R];
} else { //sum大于aim的情况
sum -= arr[L++];
}
}
return len;
}
11 最长子数组长度
12 未排序数组中累加和为给定值的最长子数组系列问题
解题分析：
如果求出数组中依次求出该位置结尾的最长子数组，那么答案一定会在其中的，下例为求在1000位置处结尾的最长数组，只要找到最开始以1200结尾的位置，那么该位置后面到1000位置处便是最长子数组
代码实现：
public static int maxLength(int[] arr, int aim) {
if (arr == null || arr.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
//key：当前累加和，value：索引位置
map.put(0, -1); // important,最开始自己定义的
int len = 0;//全局最大长度
int sum = 0;//当前累加和
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - aim)) {
//如果出现过，那么从出现的为到当前位置的长度，更新为最大的
len = Math.max(i - map.get(sum - aim), len);
}
//若没有出现，则添加进去
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}
借用上面的算法原型还可以解决问题：一个数组中有奇数和偶数，求奇数和偶数相等的最长子数组。可以把奇数偶数分别看作1和-1，求出和为0的最长子数组即可。
改编题目：
给定一个整型数组arr，其中可能有正有负有零。你可以随意把整个数组切成若干个不相容的子数组，求异或和为0的子数组最多可能有多少个？
比如： 3 2 1 9 0 7 0 2 1 3。最优划分：{3,2,1},{9},{0},{7},{0},{2,1,3} 其中{3,2,1},{0},{0},{2,1,3}的异或和为0
题目的整体思路无关，但在含i时如何考虑与前面是类似的
public static int mostEOR(int[] arr) {
int ans = 0;
int xor = 0;
int[] dp = new int[arr.length];
//key异或和，value：索引
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < arr.length; i++) {
xor ^= arr[i];
if (map.containsKey(xor)) {
int pre = map.get(xor);
dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
}
if (i > 0) {
dp[i] = Math.max(dp[i - 1], dp[i]);
}
map.put(xor, i);
ans = Math.max(ans, dp[i]);
}
return ans;
}
13 未排序数组中累加和小于或等于给定值的最长子数组长度
这道题目书中给出的算法时间复杂度为O(NlogN)，视频中给出了O(N)的解法
重点在于锁定右边界后如何不回退，若退回则会成为O(N^2)。若0~T位置模块没有超过则考虑以T+1开头的模块，否则提出0位置模块考虑1~T位置模块，之所以不再考虑以1开头的最小累加和模块是因为若在T内则已经包含了可以不用考虑，若在T外则考虑T+1开头的模块，利用这样可以直接排除一部分。
public static int maxLengthAwesome(int[] arr, int aim) {
if (arr == null || arr.length == 0) {
return 0;
}
//进行初始状态设置
int[] sums = new int[arr.length];
int[] ends = new int[arr.length];
sums[arr.length - 1] = arr[arr.length - 1];
ends[arr.length - 1] = arr[arr.length - 1];
//从右向前算
for (int i = arr.length - 2; i >= 0; i--) {
if (sums[i + 1] < 0) {
sums[i] = arr[i] + sums[i + 1];
ends[i] = ends[i+1];
} else {
sums[i] = arr[i];
ends[i] = i;
}
}
//开始扩
int R = 0;//扩右边界
int sum = 0; //从窗口内累加和
int len = 0; //全局长度
for (int start = 0; start < arr.length; start++) {
while (R < arr.length && sum + sums[R] <= aim) {
sum += sums[R];
R = ends[R] + 1;
}
sum -= R > start ? arr[start] : 0;
len = Math.max(len, R - start);
R = Math.max(R, start + 1);
}
return len;
}
14 计算数组的小和
15 自然数数组的排序
16 奇数下标都是奇数或者偶数下标都是偶数
17 子数组的最大累加和问题
18 子矩阵的最大累加和问题
19 在数组中找到一个局部最小的位置
关于局部最小的定义要明确：首位置比下一个小，结尾处比上一个小即可，对于中间位置的只需要比左右两个位置小即可，如下图所示：
在查找的时候可以利用二分法进行查找，首先判断开头和结尾处是否为局部最小，若都不是则去中间位置处寻找。
从上图中可以看出，必然可以找到一个局部最小值
public static int getLessIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return -1; // no exist
}
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
//哪边有减小的趋势就向哪边寻找
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
20 数组中子数组的最累乘积
21 打印N个数组整体最大的TopK
22 边界都是1的最大正方形大小
23 不包含本位置值的累乘数组
24 数组的partition调整
25 求最短通路值
26 数组中未出现的最小正整数
27 数组排序之后相邻数的最大差值
这道题目要求时间复杂度为O(N)，如果采用常规排序只有计数排序可以做得到，但题目中只是给出了一个整型数组的限制并没有其他的限制，这样计数排序其实是不符合的，这里其实用到还是计数排序相关：桶排序的概念，不过并没有排序只是借用了桶的概念。
对于桶的相邻如下图所示：
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = nums[0];
int max = nums[0];
//遍历数组找到最大值和最小值
for (int i = 1; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
//当最大值和最小值相等时直接返回
if (min == max) {
return 0;
}
//利用三个数组分别记录桶的情况：hasNum记录桶中是否有数据；maxs记录桶中的最大值；mins记录桶中的最小值
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
//记录桶的序号
int bid = 0;
for (int i = 0; i < len; i++) {
//把当前数据传入，得到当前数组对应的桶的序号
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
//记录相邻的最大差值
int res = 0;
int lastMax = maxs[0];
//从1号桶开始遍历，记录非空桶
for (int i= 1; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
//计算出当前数据需要放到哪个桶中。桶是如何确定的：数字的个数+1
private static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
如果桶中全部都有数据，按照上述的方法不一定保证求得的相邻数是最大差值，但只要有一个桶是空的，上述的方法就一定是正确的。这样就给出了如何确定桶的数目：桶的数目为数组的长度+1，桶内的范围为最大值和最小值之差的平分。这样就保证了一定有一个空桶。
第9章
1 从5随机到7随机及其扩展
2 一行代码求两个数的最大公约数
3 有关阶乘的两个问题
4 判断一个点是否在矩形的内部
5 判断一个点是否在三角形内部
6 折纸问题
这道题目很新颖但其本质还是二叉树问题，可以实际动手折一下，就会发现如下图的规律：
public static void printProcess(int i, int N, boolean down) {
//递归的终止条件
if (i > N) {
return;
}
//下面就是中序遍历的过程
//没有用实际的节点去遍历，层数i来代表不同的节点，用down这个标志即代表不同的节点值又模拟了遍历节点的左子树还是右子树的过程
printProcess(i + 1, N, true);
//打印
System.out.println(down ? "down " : "up ");
printProcess(i + 1, N, false);
}
注：其实有一些提示的
(1)折了n次，那么会产生2^n-1个折痕，这和一颗二叉树其高度为n对应的节点数目相一致
(2)第一次这产生了1下，第二次折分别在上下两端产生了2下和2上，对照就是二叉树的左右子树问题
有一个问题，在牛客网上采用上述解法并不能保证全部通过95%解决，应该是算法的时间复杂度太高了
7 蓄水池算法
8 设计有setAll功能的哈希表
9 最大的leftMax与rightMax之差的绝对值
10 设计可以变更的缓存结构
//定义节点
public static class Node<V> {
public V value;
public Node<V> last; //上一指针
public Node<V> next;//下一个指针
public Node(V value) {
this.value = value;
}
}
//自己定义的双向链表
public static class NodeDoubleLinkedList<V> {
private Node<V> head; //头指针
private Node<V> tail;//尾指针
public NodeDoubleLinkedList() {
this.head = null;
this.tail = null;
}
public void addNode(Node<V> newNode) {
if (newNode == null) {
return;
}
//当没有进来过节点时，要把头和尾都指向该节点
if (this.head == null) {
this.head = newNode;
this.tail = newNode;
} else { //当有节点时，把新节点挂在后面，并更新尾节点
this.tail.next = newNode;
newNode.last = this.tail;
this.tail = newNode;
}
}
//把指定的节点移动到尾部去，发生该动作前提是一定有该节点
public void moveNodeToTail(Node<V> node) {
if (this.tail == node) {
return;
}
if (this.head == node) { //单独处理头节点的移动
this.head = node.next;
this.head.last = null;
} else { //处理普遍的节点
node.last.next = node.next;
node.next.last = node.last;
}
node.last = this.tail;
node.next = null;
this.tail.next = node;
this.tail = node;
}
//移除头节点并返回该节点
public Node<V> removeHead() {
if (this.head == null) {
return null;
}
Node<V> res = this.head;
if (this.head == this.tail) { //只有一个节点
this.head = null;
this.tail = null;
} else { //多个节点
this.head = res.next;
res.next = null;
this.head.last = null;
}
return res;
}
}
public static class MyCache<K, V> {
//这里准备两张表，保证正反查均可，也可以用一张表，封装的高一点
private HashMap<K, Node<V>> keyNodeMap;
private HashMap<Node<V>, K> nodeKeyMap;
private NodeDoubleLinkedList<V> nodeList; //优先级
private int capacity;
public MyCache(int capacity) {
if (capacity < 1) {
throw new RuntimeException("should be more than 0.");
}
this.keyNodeMap = new HashMap<K, Node<V>>();
this.nodeKeyMap = new HashMap<Node<V>, K>();
this.nodeList = new NodeDoubleLinkedList<V>();
this.capacity = capacity;
}
public V get(K key) {
if (this.keyNodeMap.containsKey(key)) {
Node<V> res = this.keyNodeMap.get(key);
//修改优先级
this.nodeList.moveNodeToTail(res);
return res.value;
}
return null;
}
public void set(K key, V value) {
if (this.keyNodeMap.containsKey(key)) {
Node<V> node = this.keyNodeMap.get(key);
node.value = value;
this.nodeList.moveNodeToTail(node);
} else {
Node<V> newNode = new Node<V>(value);
this.keyNodeMap.put(key, newNode);
this.nodeKeyMap.put(newNode, key);
this.nodeList.addNode(newNode);
if (this.keyNodeMap.size() == this.capacity + 1) {
this.removeMostUnusedCache();
}
}
}
private void removeMostUnusedCache() {
Node<V> removeNode = this.nodeList.removeHead();
K removeKey = this.nodeKeyMap.get(removeNode);
this.nodeKeyMap.remove(removeNode);
this.keyNodeMap.remove(removeKey);
}
}
对于设计结构的问题总体来说并不是很难，只是代码实现比较繁琐在刷题时也要注意，对于在面试场上明显30分钟以上写不出来的问题就可以不用刷了。
还有一个设计LFU的，这里没有写，在算法第四期第6节一开始有讲的。
11 设计RandoPool结构
单独从hash表上而言其增删改查操作都是O(1)，这道题目的关键是如何等概率返回任何一个key，这个key可以是数字，也可以是字符串等各种类型。
用两个map来存储输入的key，当没有删除操作时0~25这些数字是连续的，可以很利用Random随机函数随机得到这些数字
当有删除时，便不连续了很难随机得到，那么有没有办法把不连续的变为连续的？当要删除b时，可以考虑把z覆盖b，25变为1，然后map的长度减一，这样即使删除了数据但仍然是连续的。
public static class Pool<K>{
private HashMap<K,Integer> keyIndexMap;
private HashMap<Integer,K> indexKeyMap;
private int size;
public Pool(){
keyIndexMap = new HashMap<>();
indexKeyMap = new HashMap<>();
size = 0;
}
public void insert(K key){
if (!keyIndexMap.containsKey(key)){
keyIndexMap.put(key,size);
indexKeyMap.put(size++,key);
}
}
public void delete(K key){
if (keyIndexMap.containsKey(key)){
int deleteIndex = keyIndexMap.get(key);
//因为size是从1开始计数的所以要先自减
int lastIndex = --size;
K lastKey = indexKeyMap.get(lastIndex);
keyIndexMap.put(lastKey,deleteIndex);
indexKeyMap.put(deleteIndex,lastKey);
keyIndexMap.remove(key);
indexKeyMap.remove(lastIndex);
}
}
public K getRandom(){
if (size == 0){
return null;
}
int randomIndex = (int)(Math.random()*size);
return indexKeyMap.get(randomIndex);
}
}
12 调整[0,x)区间上的数出现的概率
13 路径数组变为统计数组
14 正数数组的最小不可组成和
15 一种字符串和数字的对应关系
16 1到n中1出现的次数
17 从N个数中等概率打印M个数
18 判断一个数是否是回文数
public static boolean isPalindrome(int n) {
if (n == Integer.MIN_VALUE) {
return false;
}
n = Math.abs(n);
int help = 1;
//注意是否会溢出，因为help为int型，直接用help*10再除的话可能会发生溢出情况
while (n / help >= 10) {
help *= 10;
}
//判断是否回文
while (n != 0) {
//首尾比较
if (n / help != n % 10) {
return false;
}
n = (n % help) / 10;
help /= 100;
}
return true;
}
19 在有序旋转数组中找到最小值
这个题目代码写在剑指offer2.4.1查找和排序中。
19 在有序旋转数组中找到一个数
20 数字的英文表达和中文表达
21 分糖果问题
22 一种消息接收并打印的结构设计
23 设计一个没有扩容负担的堆结构
24 随时找到数据流的中位数
本题与LeetCode295是一样的题目，书中给出的代码稍有繁琐，这里借鉴了LeetCode中评论区代码，但是其实思路是一样的，不同点在于具体操作。
对于数据流中的数，如果能将其存成两部分，分别用最大堆和最小堆存(堆调整时间复杂度为O(logN))，取中位数直接用堆顶元素(O(1))不就可以了
但问题在于，如何把数据分为上面的两部分，这里给出两种方式：以{7,3,4,5}为例
(1)先把第一数据存入最大堆中
(2)当第二个数据小于最大堆堆顶数据时，移动最大堆堆顶元素进入最小堆，并把第二个数据存入最大堆中
(3)当第三个数据大于最大堆堆顶小于最小堆堆顶时，进入最大堆中
(4)当最大堆和最小堆之间size差大于1时，移动多的一方进入另一方中
上面的思路是书中给出的，也是比较容易想到的，但还有一种思路：
(1)先把数据存入最大堆中
(2)把最大堆堆顶数据存入最小堆中
(3)比较二者size，如果最小堆size大，把最小堆的数据存入最大堆中
第二种思路相比第一种更清晰，代码实现也更简单。
class MedianFinder {
//定义两个堆,最大堆和最小堆
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
}
public void addNum(int num) {
//每次取出来都先进最大堆，然后将最大堆的堆顶元素取出来放进最小堆中，然后再比较size这样就保证了最大堆和和最小堆数据最多差1且最大堆数据量大于等于最小堆数据量
maxHeap.add(num);
minHeap.add(maxHeap.remove());
if (minHeap.size()>maxHeap.size()){
maxHeap.add(minHeap.remove());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()){
return (maxHeap.peek()+minHeap.peek())/2.0;
}else {
return maxHeap.peek();
}
}
private class MaxHeapComparator implements Comparator<Integer>{
//可以这样认为，返回正数的在前面或上面，不要去记忆谁大谁小这样容易混的
@Override
public int compare(Integer o1, Integer o2) {
if (o2 > o1){
return 1;
}else {
return -1;
}
}
}
//在Java中默认是用最小堆的，其实这个可以不用写，但为了方便学习比较还是写上了
private static class MinHeapComparator implements Comparator<Integer>{
//可以这样认为，返回正数的在前面或上面，不要去记忆谁大谁小这样容易混的
@Override
public int compare(Integer o1, Integer o2) {
if (o2 < o1){
return 1;
}else {
return -1;
}
}
}
}
25 在两个长度相等的排序数组中找到上中位数
与LeetCode4-寻找两个有序数组的中位数一样，LeetCode上并没有限定是等长的两个数组，这里先分析LeetCode上不等长的情况。
对于一个有序的数组，其中位数的求法可以写成下面的统一公式
对于两个有序数组而言，只要找出第(m+n+1)/2大的数和第(m+n+2)/2大的数，然后求平均数即可(m,n分别是两个数组的长度)。抽象后可表述为在两个有序数组中找第k大的数。由于题目要求我们的时间复杂度为O(log(m+n))，我们很容易联想到二分查找。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int k1 = (m + n + 1) / 2; //第k1大的数
int k2 = (m + n + 2) / 2; //第k2大的数
//统一的求中位数公式
return (getKth(nums1, 0, nums2, 0, k1) + getKth(nums1, 0, nums2, 0, k2)) / 2.0;
}
// 在两个有序数组中二分查找第k大元素
private int getKth(int[] nums1, int start1, int[] nums2, int start2, int k){
// 特殊情况(1)：当某个数组查找的起始位置大于等于该数组长度时，说明这个数组中的所有数已经被淘汰，则只需要在另一个数组找查找即可。
if(start1 > nums1.length-1) return nums2[start2 + k - 1];
if(start2 > nums2.length-1) return nums1[start1 + k - 1];
// 特征情况(2)：如果k=1时，即需要查找第一个数，则找到两个数组起始位置中最小的那个即可
if(k == 1) return Math.min(nums1[start1], nums2[start2]);
// 分别在两个数组中查找第k/2个元素，若存在(即数组没有越界)，标记为找到的值；若不存在，标记为整数最大值
int nums1Mid = start1 + k/2 - 1 < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE;
int nums2Mid = start2 + k/2 - 1 < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;
// 确定最终的第k/2个元素，然后递归查找
if(nums1Mid < nums2Mid)
return getKth(nums1, start1 + k/2, nums2, start2, k-k/2);
else
return getKth(nums1, start1, nums2, start2 + k/2, k-k/2);
}
26 在两个排序数组中找到第K小的数
27 两个有序数组间相加和的TOP K问题
28 Manacher算法
代码实现：
public class Manacher {
public int maxLcpsLength(String str) {
if (str == null || str.length() == 0) {
return 0;
}
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];
int C = -1;//回文中心点
int R = -1;//右边界
int max = Integer.MIN_VALUE;
for (int i = 0; i != charArr.length; i++) {
//2 * C- i对应点i'位置；R-i是另外一个瓶颈点，两者谁小取哪个。这里将总的分为两种情况，i在R外时直接扩，在内部时取值
pArr[i] = R > i ? Math.min(pArr[2 * C- i], R - i) : 1;
//while中没有按照分析的四种情况，是全部都向外扩，对于情况2和3只要外扩就会失败
//这样做可以避免写大量的if else判断，造成代码复杂
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
pArr[i]++;
else {
break;
}
}
//当外扩的范围大于R时更新R
if (i + pArr[i] > R) {
R = i + pArr[i];
C= i;
}
max = Math.max(max, pArr[i]);
}
return max - 1;
}
//将原字符串加#
public char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
}
return res;
}
}
实例应用：对于abcabc添加字符串，使其成为最短的回文字符串
使用manacher算法思路：找到最右侧的右边界R的回文字符串，将左边界以左的全部放到右边界后面即可
public String shortestEnd(String str) {
if (str == null || str.length() == 0) {
return null;
}
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];
int index = -1;
int pR = -1;
int maxContainsEnd = -1;
for (int i = 0; i != charArr.length; i++) {
pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
pArr[i]++;
else {
break;
}
}
if (i + pArr[i] > pR) {
pR = i + pArr[i];
index = i;
}
if (pR == charArr.length) {
maxContainsEnd = pArr[i];
break;
}
}
char[] res = new char[str.length() - maxContainsEnd + 1];
for (int i = 0; i < res.length; i++) {
res[res.length - 1 - i] = charArr[i * 2 + 1];
}
return String.valueOf(res);
}
29 KMP算法
代码实现：
public class KMP {
public int getIndexOf(String str1,String str2){
if (str1 == null || str2 == null ||str2.length()<1){
return -1;
}
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
int index1 = 0;
int index2 = 0;
//生成字符串2的最长前缀后缀长度数组
int[] next = getNextArray(arr2);
while (index1 < arr1.length && index2 < arr2.length){
if (arr1[index1] == arr2[index2]){
index1++;
index2++;
}else if (next[index2] == -1){
index1++;
}else {
//srt2需要移动的长度是该位置的最长前缀后缀长度
index2 = next[index2];
}
}
//当字符串2已经遍历完了说明str1包含str2，只需要返回位置信息即可
return index2 == arr2.length ? index1-index2 : -1;
}
//生成最长前缀最长后缀数组
public int[] getNextArray(char[] arr){
if (arr.length == 1){
return new int[] {-1};
}
int[] next = new int[arr.length];
next[0] = -1; //认为规定位置的值
next[-1] = 0;
int i = 2; //当前移动到的位置
int cn = 0; //跳到的位置
while (i < next.length){
if (arr[i-1] == arr[cn]){
//若相等则把长度自增后赋给i处的值
next[i++] = ++cn;
}else if(cn > 0){
//若不等，则cn跳到子模块再进行比较
cn = next[cn];
}else {
//当cn<=0时说明已经越界了，i位置没有最长前缀后缀长度
next[i++] = 0;
}
}
return next;
}
}
30 丢棋子问题
31 画匠问题
32 邮局选址问题
0