《程序员代码面试指南-左程云》笔记
《程序员代码面试指南-左程云》笔记
第一章 栈和队列
设计一个有getMin功能的栈
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求：pop、push、getMin操作的时间复杂度都是O(1)。
解答：增加一个栈（minStack），用来维护每个元素进栈时栈的最小值。每个元素进栈时，minStack的更新规则：若当前元素比minStack栈顶元素小，则直接将当前元素进栈；否则，将之前的栈顶元素复制再次进栈。
由两个栈组成的队列
编写一个类，用两个栈实现队列，支持队列的基本操作（add，poll，peek）。
解答：两个栈，一主一辅。在poll或peek的时候，将主栈中的元素依次出栈然后进栈到辅栈，这样队列头就是辅栈的栈顶元素。
这里朴素的想法是在每次poll或peek的时候将主栈的元素全部dump到辅栈，得到队列头元素，然后再全部dump回主栈。但其实没有必要。add永远是在主栈add，但poll或peek的时候，先看辅栈是否为空，若辅栈非空，说明队列头部已经dump过来了，直接取栈顶；若辅栈为空，再进行dump操作。重点是，dump完后，不必再dump回去。
image.png
如何仅用递归函数和栈操作逆序一个栈
要求：只有一个待逆转的栈，不能有其他数据结构。
这道题的确没有想到。解法用了两个递归函数，其中一个非常的“tricky”：
public int getAndRemoveLastElement(Stack<Integer> stack) {
int top = stack.pop();
if (stack.isEmpty())
return top;
int last = getAndRemoveLastElement(stack);
stack.push(top);
return last;
}
getAndRemoveLast，得到并移除栈底元素，递归可以做到吗？怎么做？
这个递归和我以前理解的递归是有些不一样的。回想一下，不论是汉诺塔问题或是中序遍历二叉树，父问题向子问题的转化是十分清晰的、自然而然的；但这里，getAndRemoveLast(n)与getAndRemove(n-1)一眼是看不出转化过程的。所以，有点tricky.
可以从两个角度来再现这个递归过程：1，自底向上；2，递归栈。
这道题另一个“tricky”的地方在于，没有见识过两个递归的情况，而习惯性的想怎么用一个递归解决，陷入死胡同。
用一个栈实现另一个栈的排序
“维持一个有序的栈”系列开始。
解答：将要排序的栈记为stack，辅助栈为helpStack。在stack上执行pop操作，弹出的元素记为cur。
- 如果cur小于等于helpStack的栈顶元素，则直接将cur压入helpStack；
- 如果cur大于helpStack的栈顶元素，则将helpStack的元素依次出栈，压入stack，直到cur小于等于helpStack栈顶元素，然后再将cur压入helpStack。
用栈解决汉诺塔问题
条件：不能直接从A到C或C到A，必须经过B。
这道题我的第一反应是用栈模拟递归。然而，好像并没有“用栈模拟递归”这回事（也不知道这个印象怎么来的）。以树的遍历为例，要说也是递归模拟栈吧？
睡觉前躺床上又想了想，补上。
用栈实现和递归实现没有半毛钱关系。用栈和用队列本质上是一样的，都只是借助栈或队列这种结构的特点。
解答：用3个栈来模拟3座塔。那么，每一步该选哪个栈呢？出栈后又该往哪个栈进呢？
这里的关键是，有两个原则：
- 小压大原则：小的只能在大的上面（汉诺塔的要求）；
- 相邻不可逆原则：X->Y和Y->X是互斥的；
根据着两条原则，假如上一步是A->B，那么当前就不能是B->A，而B-C和C->B中只有一个可以选（根据B、C栈顶元素大小）。所以每一步的走法都是由上一步确定的。
public void hanoi(int n) {
Stack<Integer> stackA = new Stack<>();
Stack<Integer> stackB = new Stack<>();
Stack<Integer> stackC = new Stack<>();
int lastMove = 3; // 1, 2, 3, 4, 分别代表左至中、中至左、中至右、右至中；1/2互斥、3/4互斥。初始化为3或4都行，trick。
int thisMove = 0;
int moveCnt = 0;
for (int i = n; i > 0; i--) {
stackA.push(i);
}
while (stackC.size() != n) {
moveCnt++;
if (lastMove <= 2) { // 上一步是1或2，下一步只能是3或4；
if (stackB.isEmpty())
thisMove = 4;
else if (stackC.isEmpty())
thisMove = 3;
else if (stackB.peek() < stackC.peek())
thisMove = 3;
else
thisMove = 4;
if (thisMove == 3) {
System.out.println(String.format("Move %d B ==> C", stackB.peek()));
stackC.push(stackB.pop());
} else {
System.out.println(String.format("Move %d C ==> B", stackC.peek()));
stackB.push(stackC.pop());
}
} else {
if (stackA.isEmpty())
thisMove = 2;
else if (stackB.isEmpty())
thisMove = 1;
else if (stackA.peek() < stackB.peek())
thisMove = 1;
else
thisMove = 2;
if (thisMove == 1) {
System.out.println(String.format("Move %d A ==> B", stackA.peek()));
stackB.push(stackA.pop());
} else {
System.out.println(String.format("Move %d B ==> A", stackB.peek()));
stackA.push(stackB.pop());
}
}
lastMove = thisMove;
}
System.out.println("Total move count: " + moveCnt);
}
生成窗口最大值数组
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑动到最右边，一共可产生n-w+1个窗口的最大值，请返回这个最大值数组。
要求：O（N）实现。
维护最大值可以用堆，但堆怎么在窗口移动过程中移除掉被窗口划过的值？
这里介绍了一种简单但性质强大的结构：有序栈（自己起的名字）。即将一系列值依次入栈，但在入栈过程中要始终保持栈的有序性，不合格的元素要弹出来（过程很像插入排序）。
image.png
有序栈的性质有（假设从栈顶到栈底递增顺序）：
- 当前元素 i 入栈后，栈底元素即为数组中 i 左边（包括 i）的最大值；
- i 下面的一个元素即为数组中 i 左边第一个比它大的值；
- 若被弹出的元素为 j，则 i 是 j 右边第一个比它大的元素（这样对每个弹出的元素来说，就获取了其左右两边第一个比它大的元素）；
简单说就是：左边最大值，左、右两边第一个比它大的值；而且，栈中元素不仅大小有序，序号也是有序的！
而且而且，对一个大小为n的数组来说，数组元素依次进栈，维护这个有序栈的时间复杂度是O（N）！（考虑一个元素不好想，但全局来看，基本操作只有进栈和出栈两种，而每个元素进栈出栈最多一次，所以时间最多是2n-1）
回到这道题，因为窗口是移动的，不断有元素要移出窗口，所以每次移动都要看栈底元素是否已经在窗口之外了（看上面，栈底元素就是栈中所有元素里序号最小的），若是，则从栈底移除——这样就是队列了（大部分时候它都是个栈）。另，因为要根据序号来移除元素，所以栈中的元素是数组元素的下标，而不是元素值。
int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || w > arr.length)
return null;
int[] result = new int[arr.length - w + 1];
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
while (!queue.isEmpty() && arr[queue.peekLast()] < arr[i]) {
queue.pollLast();
}
queue.addLast(i);
if (queue.peekFirst() <= i - w) {
queue.pollFirst();
}
if (i >= w - 1) {
result[i - w + 1] = arr[queue.peekFirst()];
}
}
return result;
}
求最大子矩阵的大小
给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1的矩形区域中，最大的一个有多少个1。
例如：
1 0 1 1
1 1 1 1
1 1 1 0
返回6.
矩阵大小为MN，要求时间复杂度为O（MN）。
解答：矩阵的行数为M，以每一行做切割，统计以当前行作为底的情况下，每个位置上的1的“高度”，并计算以当前行为底的最大矩阵的大小。
例如，遍历到第三行时，每个位置1的高度为{3,2,3,0}：
image.png
接下来就要求以每根柱子向两边扩展出去的最大矩形，即要找到左右两边第一根比它矮的柱子——左右两边第一个比它小的值——有序栈。
public int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[stack.peek()] > height[i]) {
// 对于被弹出去的元素来说，就找到了它左右两边第一个比它小的元素；
int mid = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
int area = height[mid] * (i - left - 1);
maxArea = Math.max(maxArea, area);
}
stack.push(i);
}
while (!stack.isEmpty()) { // 全部元素遍历完后，栈可能非空，需继续处理；
// 此时的栈是什么样子呢？数组最后一个元素一定在栈顶，栈中元素的右边没有比它小的元素（如果有它就被弹出了）；
int mid = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
int area = height[mid] * (height.length - left - 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
"此时的栈是什么样子呢？数组最后一个元素一定在栈顶，栈中元素的右边没有比它小的元素（如果有它就被弹出了）"
最大值减去最小值小与或等于num的子数组的数量
给定数组arr和整数num，返回共有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num
要求：O（N）实现。
关键字：最大值、最小值、O（N）
解答：使用两个有序队列（相对于有序栈来命名）qmax和qmin，分别维护arr[i..j]的最大值和最小值更新结构。当子数组a[i..j]向右滑动一个位置变成arr[i..j+1]时，qmax和qmin可以在O（1）时间更新（上面已经分析，平均来看的确是O（1）），并且可以在O（1）时间得到arr[i..j+1]的最大值和最小值。
步骤是这样的：i，j 从0开始，首先 j 向右滑动，这个过程中维护arr[i..j]的最大值和最小值更新结构，同时观察(max-min)的值，当其大于num时，停止 j，此时，arr[i..j] 内以 i 为起始满足条件的子数组有 j - i 个；然后 i 向右滑动一位，继续上诉过程，直到 i 到达数组末尾。
public int getNum(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return 0;
}
LinkedList<Integer> qmax = new LinkedList<>();
LinkedList<Integer> qmin = new LinkedList<>();
int i = 0, j = 0;
int cnt = 0;
while (i < arr.length) {
while (j < arr.length) {
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j])
qmax.pollLast();
qmax.addLast(j);
while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j])
qmin.pollLast();
qmin.addLast(j);
if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
break;
}
j++;
}
cnt += j - i;
i++;
if (qmax.peekFirst() < i)
qmax.pollFirst();
if (qmin.peekFirst() < i)
qmin.peekFirst();
}
return cnt;
}
注意上面的<= 和 >=，是为了在 i 向前移动一步的时候保持 j 不变（先进栈再出栈）。
第二章 链表问题
如何找到有环链表的入口点？
image.png
一快一慢两个指针（fast和slow）同时出发，相遇时，fast回到链表头，速度降为1，slow仍在相遇点，两指针再同时前进，再次相遇的点就是环的入口点。
第三章 二叉树
二叉树的序列化和反序列化
先序遍历
image.png
（如上二叉树先序遍历序列化的结果为：1!2!#!3!#!#!4!#!#!）
序列化
public String serialByPreOrder(Node head) {
if (head == null)
return "#!";
String res = head.value + "!";
res += serialByPreOrder(head.left);
res += serialByPreOrder(head.right);
return res;
}
反序列化
public Node rebuildByPreOrderString(String str) {
String[] values = str.split("!");
Queue<String> queue = new LinkedList<>();
for (String s : values) {
queue.offer(s);
}
}
public Node rebuildByPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#"))
return null;
Node head = new Node(Integer.parseInt(value));
head.left = rebuildByPreOrder(queue);
head.right = rebuildByPreOrder(queue);
return head;
}
这里，有点想不到，流式读取处理，构建树节点，会自然结束。看上面的图记忆。
层次遍历
image.png
反序列化
public Node rebuildByLevelString(String str) {
String[] values = str.split("!");
int index = 0;
Node head = generateNodeByString(values[index++]);
Queue<Node> queue = new LinkedList<>();
if (head != null)
queue.offer(head);
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
return head;
}
public Node generateNodeByString(String val) {
if (val.equals("#"))
return null;
return new Node(Integer.parseInt(val));
}
又是一个流式的处理，流式扫描数组，生成节点，将非空的节点入队列。
在二叉树中找到累加和为指定值的最长路径长度
image.png
public int getMaxLength(Node head, int num) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 0); // 重要；
int[] maxLen = new int[1];
preOrder(head, num, 0, 1, maxLen, map);
return maxLen[0];
}
public void preOrder(Node head, int sum, int preSum, int level, int[] maxLen, Map<Integer, Integer> map) {
if (head == null)
return;
int curSum = preSum + head.value;
if (map.containsKey(curSum - sum))
maxLen[0] = Math.max(level - map.get(curSum - sum), maxLen[0]);
if (!map.containsKey(curSum))
map.put(curSum, level);
preOrder(head.left, sum, curSum, level + 1, maxLen, map);
preOrder(head.right, sum, curSum, level + 1, maxLen, map);
if (map.get(curSum) == level)
map.remove(curSum);
}
两个注意点：1，不同路径的和是不能共用的，所以在回退的时候需要恢复现场；2，map.put(0, 0)的初始化；
找到二叉树中的最大搜索二叉子树
image.png
递归函数需要收集上来这些信息：最大搜索二叉树头，大小，子树最小值，子树最大值；
判断条件为：
if (head.left == lBST && head.right == rBST && lMax < head.value && rMin > head.value)
二叉树递归，父子问题如何衔接。
找到二叉树中符合搜索二叉树条件的最大拓扑结构
image.png
（题与上题的区别是，上题必须是完整的子树，而这题可以取部分结构。）
这道题的关键点在于，父问题并不是由子问题构成——父问题与子问题没有衔接转化关系！
左子树的最大拓扑结构与右子树的最大拓扑结构并不一定能构成父节点的最大拓扑结构。
public int bstTopoSize(Node head) {
if (head == null)
return 0;
int max = maxTopo(head, head);
max = Math.max(bstTopoSize(head.left), max);
max = Math.max(bstTopoSize(head.right), max);
return max;
}
// 以curNode为头，条件为可达head的最大拓扑结构的大小；
public int maxTopo(Node head, Node curNode) {
if (head != null && curNode != null && isBSTNode(head, curNode))
return maxTopo(head, curNode.left) + maxTopo(head, curNode.right) + 1;
return 0;
}
public boolean isBSTNode(Node head, Node curNode) {
if (head == null)
return false;
if (head == curNode)
return true;
return isBSTNode(curNode.value < head.value ? head.left, curNode);
}
二叉树的按层打印与ZigZag打印
image.png
public static void printByLevel(Node head) {
if (head == null)
return;
Queue<Node> queue = new LinkedList<>();
int level = 1;
Node last = head;
Node nLast = null;
queue.offer(head);
System.out.println("Level " + (level++) + " : ");
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.value + " ");
if (node.left != null) {
queue.offer(node.left);
nLast = node.left;
}
if (node.right != null) {
queue.offer(node.right);
nLast = node.right;
}
if (node == last && !queue.isEmpty()) {
System.out.println("Level " + (level++) + " : ");
last = nLast;
}
}
}
层次打印，关键是last和nLast的更新。
ZigZag打印：不再是用队列，而是双端队列，每打印一层，队列换一个方向；nLast是下一层的第一个节点而不是最后一个；
调整搜索二叉树中两个错误的节点
一棵搜索二叉树中有两个节点调换了位置，请找出来；其中，所有节点值都不一样。
image.png
直接在树上看。。好像看不出来。。
中序遍历之，会出现两次降序，第一次降序的大值和第二次降序的小值，既是。
判断t1树是否包含t2树全部的拓扑结构
image.png
又是，父问题不是由子问题构成，而是一个独立的问题。
public boolean contains(Node t1, Node t2) {
return check(t1, t2) || contains(t1.left, t2) || contains(t1.right, t2);
}
public boolean check(Node head, Node t2) {
if (t2 == null)
return true;
if (head == null || head.value != t2.value)
return false;
return check(head.left, t2.left) && check(head.right, t2.right);
}
判断t1树中是否含有t2子树
image.png
和上题类似，也可以用递归来判断。但递归是暴破，时间复杂度为O（M*N）。这里有O（M+N）。
先序遍历序列化，得到两个字符串，然后通过KMP算法判断str1是否包含str2子串即可。也可以中序遍历或后续遍历。但有个关键点是，空节点一定要用 # 表示出来！否则该算法就是错的。
平衡二叉树一定是搜索二叉树。否则平衡就失去了意义。
判断一棵二叉树是否为搜索二叉树或完全二叉树
二叉树问题的两种视角：1，树，子树；2，前中后遍历，将树铺平；
判断是否为搜索二叉树：中序遍历的结果是递增序列。
image.png
完全二叉树不满。
判断完全二叉树：层次遍历，第一个不满的节点之后，都是叶节点。
image.png
在二叉树中找到两个节点的最近公共祖先
image.png
public Node lowestAncestor(Node head, Node n1, Node n2) {
if (head == null || head == n1 || head == n2)
return head;
Node left = lowestAncestor(head.left, n1, n2);
Node right = lowestAncestor(head.right, n1, n2);
if (left != null && right != null)
return head;
return left == null ? right : left;
}
递归函数的作用是：要么返回n1和n2的最近公共祖先，要么返回n1或n2，要么什么都没有返回null；
进阶问题：如果查询两个节点的最近公共祖先的操作十分频繁，想法让单条查询的查询时间减少。
用一个哈希表记录所有节点的父节点。两个节点沿父节点上溯到头结点的路径相交点既是所求。
时间复杂度O（N），空间复杂度O（N）。查询时间复杂度为O（h），h为树高。
或者，直接建立任意两个节点之间的最近公共祖先记录。
二叉树节点间的最大距离问题
image.png
一个意识：任何对树的遍历都可以顺便把高度信息收集上来。
public int maxDistance(Node head, int[] height) {
if (head == null) {
height[0] = 0;
return 0;
}
int lMax = maxDistance(head.left, height);
int lHeight = height[0];
int rMax = maxDistance(head.right, height);
int rHeight = height[0];
int curMax = lHeight + rHeight + 1;
height[0] = Math.max(lHeight, rHeight) + 1;
return Math.max(Math.max(lMax, rMax), curMax);
}
先序、中序和后序数组两两结合重构二叉树
二叉树所有节点值都不一样。
中左右 左中右 左右中
public Node preInToTree(int[] pre, int[] in) {
if (pre == null || in == null)
return null;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
}
public Node preIn(int[] p, int pi, int pj, int[] n, int ni, int nj, Map<Integer, Integer> map) {
if (pi > pj)
return null;
Node head = new Node(p[pi]);
int index = map.get(p[pi]);
head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);
head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
return head;
}
三个函数格式都是类似的。map的作用是方便的找到对应点的位置。
有点tricky的是中左右+左右中：
image.png
统计和生成所有不同的二叉树
中序遍历的结果为{1，2，3，...，N}，返回可能的二叉树结构有多少。
public static List<Node> generate(int start, int end) {
List<Node> resList = new ArrayList<>();
if (start > end) {
resList.add(null);
return resList;
}
for (int i = start; i <= end; i++) {
List<Node> lSubs = generate(start, i - 1);
List<Node> rSubs = generate(i + 1, end);
for (Node lSub : lSubs) {
for (Node rSub : rSubs) {
Node head = new Node(i);
head.left = lSub;
head.right = rSub;
resList.add(head);
}
}
}
return resList;
}
public static int numTrees(int n) {
if (n < 2)
return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
统计完全二叉树的节点数
image.png
image.png
image.png
bs(head, treeHeight(head));
public static int bs(Node head, int totalHeight) {
if (totalHeight == 1)
return 1;
if (treeHeight(head.right) == totalHeight - 1) {
return (1 << (totalHeight - 1)) + bs(head.right, totalHeight - 1);
} else {
return (1 << (totalHeight - 2)) + bs(head.left, totalHeight - 1);
}
}
public static int treeHeight(Node head) {
int h = 0;
while (head != null) {
h++;
head = head.left;
}
return h;
}
T(h) = h + T(h-1)，时间复杂度为O（h2）.
第四章 递归和动态规划
矩阵的最小路径和
从左上角出发到达右下角。
标准写法：
public static void main(String[] args) {
int[][] arr = {
{1, 3, 5, 9},
{8, 1, 3, 4},
{5, 0, 6, 1},
{8, 8, 4, 0}
};
printMinPath(arr, minPathSumDp1(arr));
System.out.println(minPathSum2(arr));
}
public static int[][] minPathSumDp1(int[][] arr) {
if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0)
return null;
int[][] dp = new int[arr.length][arr[0].length];
dp[0][0] = arr[0][0];
for (int i = 1; i < dp[0].length; i++) {
dp[0][i] = dp[0][i - 1] + arr[0][i];
}
for (int i = 1; i < arr.length; i++) {
dp[i][0] = dp[i - 1][0] + arr[i][0];
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
}
}
// return dp[dp.length - 1][dp[0].length - 1];
return dp;
}
public static int minPathSum2(int[][] arr) {
if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0)
return 0;
int more = Math.max(arr.length, arr[0].length);
int less = Math.min(arr.length, arr[0].length);
boolean rowmore = more == arr.length ? true : false;
int[] dp = new int[less];
dp[0] = arr[0][0];
for (int i = 1; i < less; i++) {
dp[i] = dp[i - 1] + (rowmore ? arr[0][i] : arr[i][0]);
}
for (int i = 1; i < more; i++) {
dp[0] += rowmore ? arr[i][0] : arr[0][i];
for (int j = 1; j < less; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + (rowmore ? arr[i][j] : arr[j][i]);
}
}
return dp[dp.length - 1];
}
public static void printMinPath(int[][] arr, int[][] dp) {
if (dp == null || dp.length == 0 || dp[0] == null || dp[0].length == 0)
return;
int[] path = new int[dp.length + dp[0].length - 1];
path[path.length - 1] = arr[arr.length - 1][arr[0].length - 1];
int i = dp.length - 1;
int j = dp[0].length - 1;
while (i + j != 0) {
if (i == 0) {
path[i + j - 1] = arr[0][j - 1];
j--;
} else if (j == 0) {
path[i + j - 1] = arr[i - 1][0];
i--;
} else if (dp[i - 1][j] < dp[i][j - 1]) {
path[i + j - 1] = arr[i - 1][j];
i--;
} else {
path[i + j - 1] = arr[i][j - 1];
j--;
}
}
for (i = 0; i < path.length; i++) {
System.out.print(path[i]);
if (i != path.length - 1)
System.out.print(" -> ");
}
System.out.println();
}
动态规划问题一定要时时注意边界检查！
换钱的最少货币数
数组arr中的每个值代表一种面值的货币，每种货币可以使用任意张，再给定一个整数aim代表要找的钱数，求组成aim的最少货币数。不能换开时返回-1.
image.png
注意点1：这道题空间压缩的方法只能横向，不能纵向。纵向要准备多个数组，滚动更新。原因是向上和向左回溯的距离是不一样的，不都是1. 其次，横纵坐标的意义是不一样的，横纵写的区别很大。
注意点2：“不能换开时返回-1”，这里的-1需要着重注意！假如向左是-1，向上是2，那么当前值只能取2！不注意的话就取-1了！
public static int minCoins(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0)
return -1;
if (aim == 0)
return 0;
int[] dp = new int[aim + 1];
for (int i = 1; i <= aim; i++) {
if (i % arr[0] == 0)
dp[i] = i / arr[0];
else
dp[i] = -1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = arr[i]; j <= aim; j++) {
// 请着重注意对-1的处理！
if (dp[j - arr[i]] == -1)
dp[j] = dp[j];
else if (dp[j] == -1)
dp[j] = dp[j - arr[i]] + 1;
else
dp[j] = Math.min(dp[j - arr[i]] + 1, dp[j]);
}
}
return dp[aim];
}
另，上面空间压缩的动态规划貌似和dp(n) = min{dp(n-2), dp(n-3), dp(n-5)} + 1是等价的，时间复杂度和空间复杂度一样。
补充问题：数组arr中的每个值仅代表一张钱的面值，在此条件下求组成aim的最小货币数。
image.png
public static int minCoins(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0)
return -1;
if (aim == 0)
return 0;
int[] dp = new int[aim + 1];
for (int i = 1; i <= aim; i++) {
// 变化1，初始化；
if (i == arr[0])
dp[i] = 1;
else
dp[i] = -1;
}
for (int i = 1; i < arr.length; i++) {
// 变化2，循环方向；
for (int j = aim; j >= arr[i]; j--) {
if (dp[j - arr[i]] == -1)
dp[j] = dp[j];
else if (dp[j] == -1)
dp[j] = dp[j - arr[i]] + 1;
else
dp[j] = Math.min(dp[j - arr[i]] + 1, dp[j]);
}
}
return dp[aim];
}
image.png
换钱的方法数
数组arr中每种面值的货币都可以使用任意张，求换成aim面值有多少种方法。（组成0元的方法有一种，就是所有面值的货币都不用）
public static int coins(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0)
return 0;
int[] dp = new int[aim + 1];
for (int i = 0; i <= aim; i++) {
if (i % arr[0] == 0)
dp[i] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= aim; j++) {
if (j - arr[i] >= 0)
dp[j] += dp[j - arr[i]];
}
}
return dp[aim];
}
最长递增子序列
image.png
dp[i]：以arr[i]结尾的最长递增子序列的长度
public static int[] getDp(int[] arr) {
if (arr == null || arr.length == 0)
return null;
int[] dp = new int[arr.length];
int maxLen;
for (int i = 0; i < arr.length; i++) {
maxLen = 0;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i] && dp[j] > maxLen)
maxLen = dp[j];
}
dp[i] = maxLen + 1;
}
return dp;
}
public static void printLIS(int[] dp, int[] arr) {
if (dp == null || dp.length == 0)
return;
int maxPos = 0;
for (int i = 0; i < dp.length; i++) {
if (dp[i] > dp[maxPos])
maxPos = i;
}
int[] path = new int[dp[maxPos]];
path[dp[maxPos] - 1] = arr[maxPos];
int prePos = maxPos;
while (dp[prePos] != 1) {
for (int i = prePos - 1; i >= 0; i--) {
if (arr[i] < arr[prePos] && dp[i] == dp[prePos] - 1) {
path[dp[i] - 1] = arr[i];
prePos = i;
break;
}
}
}
for (int i = 0; i < path.length; i++) {
System.out.print(path[i]);
if (i != path.length - 1)
System.out.print(" ");
else
System.out.println();
}
}
最长公共子序列问题
1A2C3D4B56 与 B1D23CA45B6A的最长公共子序列。
dp[i][j]：str1[0...i]与str2[0...j]的最长公共子序列的长度。而不是“以i，j结束的最长公共子序列的长度”。子序列并不是连续的，而是跳动的，所以这里用的是范围形式的DP。
image.png
目前最好的理解是：str1[i] 和 str2[j] 是不是 str1[0...i] 与 str2[0...j] 的最长公共子序列的一部分。假如是，则要求 str1[i] == str2[j]，假如不是，则递归向前进一步。
public static int[][] getDp(char[] str1, char[] str2) {
int[][] dp = new int[str1.length][str2.length];
for (int i = 0; i < dp[0].length; i++) { // 第一个1后面全部为1；
if (str2[i] == str1[0] || (i > 0 && dp[0][i - 1] == 1))
dp[0][i] = 1;
}
for (int i = 0; i < dp.length; i++) {
if (str1[i] == str2[0] || (i > 0 && dp[i - 1][0] == 1))
dp[i][0] = 1;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j])
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
return dp;
}
public static void printLCS(int[][] dp, char[] str1, char[] str2) {
if (str1 == null || str1.length == 0 || str2 == null || str2.length == 0)
return;
char[] path = new char[dp[str1.length - 1][str2.length - 1]];
int index = path.length - 1;
int i = str1.length - 1;
int j = str2.length - 1;
while (index >= 0) {
System.out.println("(" + i + ", " + j + "), index: " + index);
if (j > 0 && dp[i][j] == dp[i][j - 1])
j--;
else if (i > 0 && dp[i][j] == dp[i - 1][j])
i--;
else {
path[index--] = str1[i];
i--;
j--;
}
}
System.out.println(Arrays.toString(path));
}
如果要打印路径，则就不能用空间压缩的方法了。
最长公共子串问题
子串，要求连续，所以“以i，j结尾”又来了。
public static int[][] getDp(char[] str1, char[] str2) {
int[][] dp = new int[str1.length][str2.length];
for (int i = 0; i < dp[0].length; i++) {
if (str2[i] == str1[0])
dp[0][i] = 1;
}
for (int i = 0; i < dp.length; i++) {
if (str1[i] == str2[0])
dp[i][0] = 1;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (str1[i] == str2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
return dp;
}
最小编辑代价
给定两个字符串str1和str2，再给定三个整数ic，dc和rc分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。
这道题，当前有四种选择，所以dp[i][j]有四个方向。
另，这里在str1和str2的前面都加了个""空字符，因为在原来的情况下，初始情况不都初始，不好初始化，而加了空字符后就变得清晰明了了。
image.png
public static int minCost(char[] str1, char[] str2, int ic, int dc, int rc) {
if (str1 == null || str2 == null)
return 0;
int[][] dp = new int[str1.length + 1][str2.length + 1];
for (int i = 1; i < dp[0].length; i++) {
dp[0][i] = ic * i;
}
for (int i = 1; i < dp.length; i++) {
dp[i][0] = dc * i;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = dp[i - 1][j - 1] + rc;
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
}
}
return dp[str1.length][str2.length];
}
字符串的交错组成
给定三个字符串str1、str2和aim，如果aim包含且仅包含来自str1和str2的所有字符，且保持原来的相对顺序，那么称aim是str1和str2的交错组成。
例如：str1 = "AB"，str2 = "12"，那么"AB12"，"A1B2"，"A12B"，"1A2B"，"1AB2"等都是str1和str2的交错组成。
image.png
public static boolean isCross(char[] str1, char[] str2, char[] aim) {
if (str1 == null || str2 == null || aim == null)
return false;
boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
dp[0][0] = true;
for (int i = 1; i < dp[0].length; i++) {
if (str2[i - 1] != aim[i - 1])
break;
dp[0][i] = true;
}
for (int i = 1; i < dp.length; i++) {
if (str1[i - 1] != aim[i - 1])
break;
dp[i][0] = true;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if ((str1[i - 1] == aim[i + j - 1] && dp[i - 1][j]) ||
(str2[j - 1] == aim[i + j - 1] && dp[i][j - 1]))
dp[i][j] = true;
}
}
return dp[str1.length][str2.length];
}
两个非常容易出错的地方：1，初始化，一旦不相等就跳出，后面全部为false；2，i - 1, i + j - 1，下标注意清楚；**
龙与地下城游戏问题
image.png
public static int minHP(int[][] map) {
if (map == null || map.length == 0 || map[0] == null || map[0].length == 0)
return 1;
int[][] dp = new int[map.length][map[0].length];
dp[dp.length - 1][dp[0].length - 1] = Math.max(1 - map[map.length - 1][map[0].length - 1], 1);
for (int i = dp.length - 2; i >= 0; i--) {
dp[i][dp[0].length - 1] = Math.max(dp[i + 1][dp[0].length - 1] - map[i][map[0].length - 1], 1);
}
for (int i = dp[0].length - 2; i >= 0; i--) {
dp[dp.length - 1][i] = Math.max(dp[dp.length - 1][i + 1] - map[map.length - 1][i], 1);
}
for (int i = dp.length - 2; i >= 0; i--) {
for (int j = dp[0].length - 2; j >= 0; j--) {
int less = Math.min(dp[i][j + 1], dp[i + 1][j]);
dp[i][j] = Math.max(less - map[i][j], 1);
}
}
return dp[0][0];
}
表达式得到期望结果的组成种数
一个表达式只由0, 1, &, |, ^组成，再给定一个布尔值disired，返回表达式能有多少种组合方式，可以达到desired的结果。
如express = "1^0|0|1", desired = false，有"1^((0|0)|1)", "1^(0|(0|1))"两种组合可以得到false，返回2.
没有组合返回0.
public static int foo(String express, boolean desired) {
if (express == null || express.isEmpty())
return 0;
char[] chs = express.toCharArray();
int[][] t = new int[chs.length][chs.length];
int[][] f = new int[chs.length][chs.length];
for (int i = 0; i < chs.length; i += 2) { // 初始情况，窗口大小为1；
if (chs[i] == '1')
t[i][i] = 1;
else
f[i][i] = 1;
}
for (int w = 3; w <= chs.length; w += 2) { // 窗口大小；
for (int i = 0; i + w - 1 < chs.length; i += 2) { // 左边界
for (int j = i + 1; j < i + w - 1; j += 2) { // 遍历窗口内符号；
if (chs[j] == '&') {
t[i][i + w - 1] += t[i][j - 1] * t[j + 1][i + w - 1];
f[i][i + w - 1] += f[i][j - 1] * (t[j + 1][i + w - 1] + f[j + 1][i + w - 1]);
f[i][i + w - 1] += t[i][j - 1] * f[j + 1][i + w - 1];
} else if (chs[j] == '|') {
f[i][i + w - 1] += f[i][j - 1] * f[j + 1][i + w - 1];
t[i][i + w - 1] += t[i][j - 1] * (t[j + 1][i + w - 1] + f[j + 1][i + w - 1]);
t[i][i + w - 1] += f[i][j - 1] * t[j + 1][i + w - 1];
} else {
t[i][i + w - 1] += t[i][j - 1] * f[j + 1][i + w - 1] + f[i][j - 1] * t[j + 1][i + w - 1];
f[i][i + w - 1] += t[i][j - 1] * t[j + 1][i + w - 1] + f[i][j - 1] * f[j + 1][i + w - 1];
}
}
}
}
return desired ? t[0][chs.length - 1] : f[0][chs.length - 1];
}
这种（i...j）小窗口逐渐增大的动态规划，想象的图形不再是二维矩阵，而是一个滑动的窗口。
排成一条线的纸牌博弈问题
给定一个整型数组arr，代表不同数值的纸牌，两个绝顶聪明的人先后拿走最左或最右的纸牌，问最后两人的得分为多少。
如arr = {1, 2, 100, 4}，先拿得101， 后拿得6.
public static int[] win(int[] arr) {
if (arr == null || arr.length == 0)
return new int[2];
int[][] first = new int[arr.length][arr.length];
int[][] second = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
first[i][i] = arr[i];
}
for (int w = 2; w <= arr.length; w++) {
for (int i = 0; i + w - 1 < arr.length; i++) {
if (arr[i] + second[i + 1][i + w - 1] > arr[i + w - 1] + second[i][i + w - 2]) {
first[i][i + w - 1] = arr[i] + second[i + 1][i + w - 1];
second[i][i + w - 1] = first[i + 1][i + w - 1];
} else {
first[i][i + w - 1] = arr[i + w - 1] + second[i][i + w - 2];
second[i][i + w - 1] = first[i][i + w - 2];
}
}
}
return new int[]{first[0][arr.length - 1], second[0][arr.length - 1]};
}
数组中的最长连续序列
给定无序数组arr，返回其中最长的连续序列的长度。
举例：arr = [100, 4, 200, 1, 3, 2]，最长连续序列为[1, 2, 3, 4]。
方法：区间合并。map<Integer, Integer> 代表每个值所在最长连续区间的长度。
public static int longestConsecutive(int[] arr) {
if (arr == null || arr.length == 0)
return 0;
Map<Integer, Integer> map = new HashMap<>();
int maxLen = 1;
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], 1);
if (map.containsKey(arr[i] - 1)) {
maxLen = Math.max(maxLen, merge(map, arr[i] - 1, arr[i]));
}
if (map.containsKey(arr[i] + 1)) {
maxLen = Math.max(maxLen, merge(map, arr[i], arr[i] + 1));
}
}
}
return maxLen;
}
public static int merge(Map<Integer, Integer> map, int leftTail, int rightHead) {
int left = leftTail - map.get(leftTail) + 1;
int right = rightHead + map.get(rightHead) - 1;
int len = right - left + 1;
map.put(left, len);
map.put(right, len);
return len;
}
第五章 字符串问题
字符串转数字时的溢出判断
未
调整字符串问题的一个常用技巧：两个指针，倒着复制。
添加最少字符使字符串变成回文字符串
给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。
如“ABC”，返回“ABCBA”，或“CABAC”。
还是滑动窗口的DP。
public static int[][] getMinCost(String str) {
char[] chs = str.toCharArray();
int[][] dp = new int[chs.length][chs.length];
for (int w = 2; w <= chs.length; w++) {
for (int i = 0; i + w - 1 < chs.length; i++) {
dp[i][i + w - 1] = Math.min(dp[i + 1][i + w - 1], dp[i][i + w - 2]) + 1;
if (chs[i] == chs[i + w - 1] && w > 2)
dp[i][i + w - 1] = Math.min(dp[i][i + w - 1], dp[i + 1][i + w - 2]);
}
}
return dp;
}
public static void printDPStr(int[][] dp, String str) {
String res = "";
char[] chs = str.toCharArray();
int i = 0, j = chs.length - 1;
String add = "";
while (i < j) {
if (dp[i][j] == dp[i][j - 1] + 1)
add += chs[j--];
else if (dp[i][j] == dp[i + 1][j] + 1)
add += chs[i++];
else {
add += chs[i];
i++;
j--;
}
}
System.out.println(add + chs[i] + new StringBuilder(add).reverse().toString());
字符串求值
str = "48*((70-65)-43)+8*1"，返回-1816.
解答：
两个栈，一个操作符栈，一个操作数栈。若当前是加减，则前一个无论是加减乘除都可以计算；若当前是乘除，则前面只能计算乘除；左括号直接进栈，遇到右括号不断计算直到将左括号弹出；注意检查孔栈。
public static int computeExpress(String exp) {
char[] chs = exp.toCharArray();
Stack<Integer> numStack = new Stack<>();
Stack<Character> opStack = new Stack<>();
int i = 0;
while (i < chs.length) {
if (Character.isDigit(chs[i])) { // 解析数字，进栈；
int num = 0;
while (i < chs.length && Character.isDigit(chs[i])) {
num = num * 10 + (chs[i] - '0');
i++;
}
numStack.push(num);
continue;
} else if (chs[i] == '+' || chs[i] == '-') { // 1 + 2 * 3 - 4
if (!opStack.isEmpty() && opStack.peek() != '(') {
compute(numStack, opStack);
} else {
opStack.push(chs[i++]);
}
continue;
} else if (chs[i] == '*' || chs[i] == '/') {
if (!opStack.isEmpty() && (opStack.peek() == '*' || opStack.peek() == '/')) {
compute(numStack, opStack);
} else {
opStack.push(chs[i++]);
}
continue;
} else if (chs[i] == '(') {
opStack.push(chs[i++]);
} else if (chs[i] == ')') {
while (opStack.peek() != '(')
compute(numStack, opStack);
opStack.pop();
i++;
continue;
}
}
while (!opStack.isEmpty())
compute(numStack, opStack);
return numStack.pop();
}
public static void compute(Stack<Integer> numStack, Stack<Character> opStack) {
int right = numStack.pop();
int left = numStack.pop();
char op = opStack.pop();
int sum = 0;
if (op == '+')
sum = left + right;
else if (op == '-')
sum = left - right;
else if (op == '*')
sum = left * right;
else if (op == '/')
sum = left / right;
numStack.push(sum);
}
找到字符串的最长无重复字符子串
如“aabcb”，最长无重复字符子串为“abc”，返回3.
dp[i]：以i结尾的最长无重复字符子串的长度；遍历到i+1时，从chs[i]向前回溯dp[i]范围看是否出现chs[i+1]，若是，则该位置即为dp[i+1]的值；若没有找到，则dp[i+1] = dp[i] + 1；
用一个map记录每个字符最近出现的位置，可以免去遍历的过程，将时间复杂度将为O（N）。
回文最少分割数
给定一个字符串str，返回把str全部切成回文子串的最小分割数。
如“ACDCDCDAD”，最少切割为“A”，“CDCDC”，“DAD”，返回2.
字符串（字符数组）or数组的DP，要么是滑动窗口O（N2）；要么是以i结尾，若有遍历O（N2），无遍历O（N）。
不要被O（N）限制住了，不要拿到一道题就想用O（N）解决。大部分DP都是N2的！
dp[i]：chs[0...i]的最少分割数；i+1时，向前回溯到j，若chs[j...i+1]是回文，则dp[i+1]可能等于dp[j-1] + 1；即dp[i+1] = min{dp[j] + 1, chs[j+1...i+1]是回文}
因为需要判断chs[i...j]是否是回文，所以这道题需要一个辅助DP：dp[i][j]是否是回文。
这两个DP可以合在一起进行。
public static int minCut(String str) {
char[] chs = str.toCharArray();
boolean[][] isRecurStr = new boolean[chs.length][chs.length];
int[] dp = new int[chs.length];
for (int i = 0; i < chs.length; i++) {
int minCut = Integer.MAX_VALUE;
for (int j = 0; j <= i; j++) {
if (chs[j] == chs[i]) {
if (j + 1 < i && !isRecurStr[j + 1][i - 1])
isRecurStr[j][i] = false;
else
isRecurStr[j][i] = true;
} else
isRecurStr[j][i] = false;
if (isRecurStr[j][i]) {
minCut = j == 0 ? 0 : Math.min(minCut, dp[j - 1] + 1);
}
}
dp[i] = minCut;
}
return dp[chs.length - 1];
}
第六章 大数据和空间限制
布隆过滤器
不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B。现在想要实现一个网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。
要求：1，该系统允许有万分之一以下的判断失误率；2，使用的额外空间不要超过30GB。
解答：
保存全部的网页就需要640GB空间，所以用哈希表是不行的。这道题奇怪的地方在于，“允许有万分之一以下的判断失误率”，这是以前没有遇到过的。
如果面试者遇到网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统等题目，又看到系统容忍一定程度的失误率，但是对空间要求比较严格，那么很可能是面试官希望面试者具备布隆过滤器的知识。一个布隆过滤器精确地代表一个集合，可以精确的判断一个元素是否在集合中。注意，只是精确代表和精确判断，到底有多精确呢？则完全取决于具体的设计，但想做到完全正确是不可能的。布隆过滤器的优势就在于使用很少的空间就可以将准确率做到很高的程度。
假设有一个长度为m的bit类型的数组，另有k个哈希函数，这些哈希函数的输出域都大于或等于m，彼此之间完全独立。那么对同一个输入对象，经过k个哈希函数算出k个结果，每个结果对m取余（%m），然后在bit数组上将相应的位置涂黑（设为1）。
image.png
按上述方法处理所有的输入对象。
如何检查某个对象a是否在集合中呢？对a作上述同样处理，看计算出的k个位置是否全部为黑，如果有一个不为黑，说明a一定不在集合中；如果全部为黑，说明a在这个集合里，但可能有误判。
宁杀错，不放过。
参数计算
n：集合中元素个数；p：失误率
布隆过滤器的大小：m = - n * In(p) / (In2)^2
哈希函数的个数：k = 0.7 * m / n
布隆过滤器会有误报，对已经发现的误报样本可以通过建立白名单来防止误报。
只用2GB内存在20亿个整数中找到出现次数最多的数
有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。
内存限制为2GB。
解答
注意点1，用哈希表来计数的话，键和值都要占用4B空间；2，关键不是有多少个数，而是有多少不同的数。
解决办法是把包含20亿个数的大文件用哈希函数分成10个小文件，根据哈希函数的性质，同一种数不可能被哈希到不同的小文件上，同时每个小文件中不同的数一定不会超过2亿种（20亿个数全部不同），假设哈希函数足够好。然后对每一个小文件用哈希表来统计每种数出现的次数（最多2亿个不同的数，0.2G * 4B * 2 = 1.6GB），这样就得到了10个小文件中出现次数最多的数，接下来只要选出最大的即可。
把一个大的集合通过哈希函数分配到多台机器中，或者分配到多个文件里，这种技巧是处理大数据面试题时最常用的技巧之一。但是到底分配多少台机器、分配到多少个小文件中，在解题时一定要确定下来。
40亿个非负整数中找到没有出现的数
32位无符号整数的范围是0~4294967295，现在有一个真好包含40亿个无符号整数的文件，所以在整个范围内必然有没有出现的数。可以使用最多1GB内存，怎么找到所有没出现过的数？
进阶：内存限制为10MB，但是只用找到一个没出现过的数即可。
解答：
“出没出现”——用位图。正好0.5GB。
进阶：分区间统计落在各区间的数的个数，必有少的，再用10MB位图统计该区间各个数出现与否。
区间不能太大，否则10MB位图就不够了；合适大小是：（2^32）/（10* 2^20 *8）= 51.2，所以取一个64，挺合适。64个区间，每个区间的大小是：（232）/（26）= 2^26b = 8MB.
找到100亿个URL中重复的URL以及搜索词汇的top K问题
有一个包含100亿个URL 的大文件，假设每个URL占用64B，请找出其中所有重复的URL。
补充题目：某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种方法求出每天最热top 100词汇。
大文件通过哈希分配到多台机器或多个小文件上。
首先，你要向面试官询问在资源上的限制有哪些，包括内存、计算时间等要求。在明确了限制要求之后，可以将每条URL通过哈希函数分配到若干台机器或拆分成若干小文件，这里的“若干”由具体的资源限制来计算出精确的数量。
原问题：哈希成若干小文件之后，再利用哈希表遍历，找出重复的URL。
补充问题：哈希成若干小文件之后，通过哈希表遍历，统计词频；再利用小根堆或直接排序找出每个小文件中的top 100词汇及其词频；然后把每个小文件的top 100再进行排序或利用小根堆，找出整个大文件的top 100.
40亿个非负整数中找到出现两次的数和所有数的中位数
32位无符号整数的范围是0~4294967295，现在有40亿个无符号数，可以使用最多1GB内存，找出所有出现了两次的数。
补充题目：可以使用最多10MB内存，怎么找到这40亿个整数的中位数（即排序后的第20亿个数）？
解答：
原问题：每个数用2位统计词频，需要2^32 * 1 / 4 B = 1GB.
补充问题：区间计数。划分区间统计落在每个区间的数的个数，这样就可以知道第20亿个数落在了哪个区间；然后用长度为区间大小的数组对落在该区间的数做频率统计，就可以得到第20亿个数。
这里用的是数组来统计频率而不是哈希表，省了一半的空间，而且不用排序。
数组大小或区间大小取2M，比较合适。这样就是2048个区间。
一致性哈希算法的基本原理
工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：
1，无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key；
2，如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。
以上缓存策略的潜在问题是如果增加或删除机器时（N变化），代价会很高，所有的数据都需要重新哈希一次，进行大规模的数据迁移。
为了解决这些问题，下面介绍一下一致性哈希算法。
一致性哈希算法中的哈希值范围是2^32，我们可以将这些值首尾相连，想象成一个闭合的环形，那么一个数据经过哈希之后就对应到环中的一个位置上。对服务器作同样的处理也将其映射到环的某个位置上。查找数据时，从数据映射的位置沿环顺时针查找离这个位置最近的服务器，那台服务器就是该数据的归属。
image.png
添加服务器时的处理：只用将m1到m3这一段的数据从m2迁移到m3上；
删除服务器：将删除服务器上的数据全部复制到顺时针找到的下一台服务器上即可。
image.png
机器负载不均衡时的处理
如果机器较少，很有可能造成机器在整个环上的分布不均匀，从而导致机器之间的负载不均衡。
为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一台机器通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。节点数变多了，根据哈希函数的性质，平衡性自然会变好。
image.png
第七章 位运算
不用额外变量交换两个整数的值
a = a ^ b
b = a ^ b
a = a ^ b
在其他数都出现偶数次的数组中找到出现奇数次的数
给定一个数组arr，其中只有一个数出现了奇数次，其他的数都出现了偶数次，打印这个数。
进阶：有两个数出现了奇数次，其他的数都出现了偶数次，打印这两个数。
解答：
两个相同的数异或为0. 0与任何一个数异或都为这个数本身。
原问题：将数组中所有的数一起求异或，最后得到的就是出现奇数次的数。
进阶：将数组中所有的数一起求异或，得到的结果res必定不为0，而res亦为两个数a和b异或的结果。res必定有一位为1，在这位上，a和b必定一个为0，另一个为1；所以可以根据这一点将数组中的数分组，在这一位上为1和为0的分别求异或，得到的两个数就是a和b。
第八章 数组和矩阵问题
转圈打印矩阵
image.png
恩，考研复试真题。
public static void spiralPrint(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
return;
int r1 = 0, c1 = 0, r2 = matrix.length - 1, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
printEdge(matrix, r1++, c1++, r2--, c2--);
}
}
public static void printEdge(int[][] matrix, int r1, int c1, int r2, int c2) {
if (r1 == r2) {
for (int i = c1; i <= c2; i++) {
System.out.print(matrix[r1][i] + " ");
}
} else if (c1 == c2) {
for (int i = r1; i <= r2; i++) {
System.out.print(matrix[i][c1] + " ");
}
} else {
for (int i = c1; i <= c2; i++) {
System.out.print(matrix[r1][i] + " ");
}
for (int i = r1 + 1; i <= r2; i++) {
System.out.print(matrix[i][c2] + " ");
}
for (int i = c2 - 1; i >= c1; i--) {
System.out.print(matrix[r2][i] + " ");
}
for (int i = r2 - 1; i > r1; i--) {
System.out.print(matrix[i][c1] + " ");
}
}
}
topK
public static void main(String[] args) {
int[] arr = new int[]{1, 9, 2, 8, 3, 7, 4, 6, 5};
for (int i = 1; i <= arr.length; i++) {
printTopMinK(arr, i);
}
}
public static void printTopMinK(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0)
return;
// 建堆；
for (int i = 0; i < k; i++) {
heapify(arr, i);
}
// 循环比较更新堆；
for (int i = k; i < arr.length; i++) {
heapInsert(arr, k, i);
}
for (int i = 0; i < k; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void heapify(int[] arr, int n) { // 上溯建堆
while (n > 0) {
int parent = (n - 1) / 2;
if (arr[parent] < arr[n]) {
swap(arr, parent, n);
n = parent;
} else
break;
}
}
public static void heapInsert(int[] arr, int size, int i) { // 下溯更新堆
if (arr[i] > arr[0])
return;
swap(arr, 0, i);
int cur = 0;
int cand;
while (cur < size) {
cand = cur;
if (cur * 2 + 1 < size && arr[cur * 2 + 1] > arr[cand])
cand = cur * 2 + 1;
if (cur * 2 + 2 < size && arr[cur * 2 + 2] > arr[cand])
cand = cur * 2 + 2;
if (cand == cur)
break;
else {
swap(arr, cur, cand);
cur = cand;
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
在数组中找到出现次数大于N/K的数
一次删掉K个不同的数。
用一个哈希表来计数，当哈希表大小为K时，所有计数减一。最后剩下的数还要进行验证，因为下面这样的情况：{1, 2, 3, 1, 2, 3, 4, 4, 5}，K = 3
【未排序正数数组中累加和为给定值的最长子数组长度】
不要多想，这里用的是O（N）+ O（1）的“特殊”解法。
left和right代表子数组的左右边界，sum为累加和。
public static int getMaxLength(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0)
return 0;
int left = 0;
int right = 0;
int sum = arr[0];
int maxLen = 0;
while (right < arr.length) {
if (sum == k) {
maxLen = Math.max(maxLen, right - left + 1);
sum -= arr[left];
left++;
} else if (sum < k) {
if (right + 1 == arr.length)
break;
sum += arr[++right];
} else {
sum -= arr[left++];
}
}
return maxLen;
}
未排序数组中累加和为给定值的最长子数组系列问题
给定一个无序数组arr，其中元素可正、可负、可0，给定一个整数k，求arr所有的子数组中累加和为k的最长子数组长度。
补充题目1：给定一个无序数组arr，其中元素可正、可负、可0，求arr所有的子数组中正数与负数个数相等的最长子数组长度。
补充题目2：给定一个无序数组arr，其中元素只是1或0，求arr所有的子数组中0和1个数相等的最长子数组长度。
一遍扫描，累加和减累加和，用哈希表记录某个累加和最早出现的位置。
public static int maxLength(int[] arr, int k) {
if (arr == null || arr.length == 0)
return 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // IMPORTANT!
int sum = 0;
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
maxLen = Math.max(maxLen, i - map.get(sum - k));
}
if (!map.containsKey(sum))
map.put(sum, i);
}
return maxLen;
}
补充题目1：正数变为1，负数变为-1，k = 0；
补充题目2：0变成-1，k = 0；
子数组的最大累加和问题
dp[i]：以i结尾的子数组的最大累加和
dp[i] = arr[i] （dp[i-1] < 0）| dp[i-1] + arr[i] （dp[i-1] >= 0）
时间复杂度O（N），空间复杂度O（1）
子矩阵的最大累加和问题
找到累加和最大的子矩阵
本题的最优解深度利用了上一题的解法。
首先一个问题，如何求行数为2的子矩阵中的最大累加和？可以把两行的元素累加，得到一个一维数组，然后用上题的方法求解。
也就是说，如果一个矩阵限定必须有k行元素，我们只需要把每一列的k个元素相加形成一个累加数组，然后求出这个数组的最大累加和，这个最大累加和就是必须含有k行的所有子矩阵的最大累加和。
public static int maxSum(int[][] arr) {
if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0)
return 0;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
int[] sum = new int[arr[0].length];
for (int j = i; j < arr.length; j++) {
int preSum = 0;
for (int k = 0; k < arr[0].length; k++) {
sum[k] += arr[j][k];
if (preSum < 0) {
preSum = sum[k];
} else {
preSum += sum[k];
}
maxSum = Math.max(maxSum, preSum);
}
}
}
return maxSum;
}
第九章 其他题目
从5随机到7随机及其扩展
用rand1To5实现rand1To7.
public static int rand1to5() {
return (int) (Math.random() * 5) + 1;
}
public static int rand1to7() {
int res;
while (true) {
res = (rand1to5() - 1) * 5 + rand1to5() - 1;
if (res < 21)
return res % 7 + 1;
}
}
image.png
用“插空”的方式产生一个大于目标值范围的随机分布。
but，下面这样好像也行？
public static int rand1to7() {
int res;
while (true) {
// 等概率产生1~10
res = rand1to5();
if (res < 3) // 1, 2
res = rand1to5(); // 1, 2, 3, 4, 5
else if (res > 3) { // 4, 5
res = 5 + rand1to5(); // 6, 7, 8, 9, 10
}
if (res <= 7)
return res;
}
}
补充题目：给定一个以概率p产生0，以1-p概率产生1的随机函数rand01p如下：
public int rand01p() {
int p = 0.83;
return Math.random() < p ? 0 : 1;
}
请用rand01p实现等概率随机产生1~6的随机函数rand1To6.
先等概率随机产生0和1：
public static int rand01() {
int pre = rand01p();
int cur;
while (true) {
cur = rand01p();
if (cur != pre)
return pre;
else
pre = cur;
}
}
原理是产生“01”和产生“10”是等概率的。
等概率产生01后，就可以等概率产生03，然后就可以产生0~6了，像上面那样。
正数数组最小不可组成和
给定一个正数数组arr，取其中若干数求和，得到的和中最小为min，最大为max，[min, max]范围内第一个不可被数组arr求和得到的称为“最小不可组成和”；若[min, max]内每一个数都可得到，则返回max+1.
例如arr = {2, 3, 5}，min为2，max为10，最小不可组成和为4.
用递归+HashSet收集所有的组成和，复杂度为2^N.
public void generateSum(int[] arr, int preSum, int i, Set<Integer> set) {
if (i == arr.length) {
set.add(preSum);
return;
}
generateSum(arr, preSum + arr[i], i + 1, set);
generateSum(arr, preSum, i + 1, set);
}
动态规划：
public int unformedSum(int[] arr) {
if (arr == null || arr.length == 0)
return 1;
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i : arr) {
sum += i;
min = Math.min(min, i);
}
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
dp[arr[0]] = true;
for (int i = 1; i < arr.length; i++) {
for (int j = sum; j >= arr[i]; j--) {
dp[j] = dp[j] | dp[j - arr[i]];
}
}
for (int i = min; i <= sum; i++) {
if (dp[i] == false)
return i;
}
return sum + 1;
}
复杂度O（N × sum）。
KMP
上面是待匹配字符串，下面是模式，当前未匹配字符为B。原理是在B的后面和模式的开头找到一段相同的子串，使得在B不匹配时可以把模式向前滑动尽量远的距离。其中b是能找到的最长子串。
也就是说，模式能直接滑动到b所在的位置。那么在a和b之间有没有一个位置可以使模式匹配成功呢？
假设模式滑动到d'可以匹配成功，那么可以得到d = d' = e，与“b是能找到的最长相同子串”矛盾。
接下来是如何找到next数组，原理和上面一样，同时类似DP。
求next[i]：若match[i-1] = next[i-1]，则next[i] = next[i-1] + 1；否则，cn = next[cn]，向前跳，继续寻找匹配。
《程序员代码面试指南-左程云》笔记
public int[] getNextArray(String match) {
if (match.length() == 1)
return new int[] {-1};
char[] chs = match.toCharArray();
int[] next = new int[chs.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < chs.length) {
if (chs[pos - 1] == chs[cn]) {
next[pos++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[pos++] = 0;
}
}
return next;
}
丢棋子问题
一座大楼有0～N层，地面算作第0层，最高的一层为第N层。已知棋子从第0层掉落肯定不会摔碎，从第i层掉落可能会摔碎，也可能不会摔碎。给定N作为楼层数，K作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最少次数。一次只能扔一个棋子。
在所有最差情况里最好的一个。
dp[k][n] = min{ max{dp[k-1][i], dp[k][n-i]} + 1 }, 1<=i<=n
需要向前遍历的DP。
public static int solution(int k, int n) {
if (k < 1 || n < 1)
return 0;
if (k == 1)
return n;
int[][] dp = new int[k + 1][n + 1];
for (int i = 1; i <= n; i++) {
dp[1][i] = i;
}
for (int i = 1; i <= k; i++) {
dp[i][1] = 1;
}
for (int i = 2; i <= k; i++) {
for (int j = 2; j <= n; j++) {
int min = Integer.MAX_VALUE;
for (int l = 1; l <= j; l++) {
if (l == 1) {
min = Math.min(min, dp[i - 1][j - 1] + 1);
} else if (l == j) {
min = Math.min(min, dp[i][j - 1] + 1);
} else {
min = Math.min(min, Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);
}
}
dp[i][j] = min;
}
}
return dp[k][n];
}
画匠问题
给定一个整型数组arr，数组中每个值代表完成一幅画作需要的时间，再给定一个num代表画匠的数量，每个画匠只能画连在一起的画作。所有画家并行工作，请返回完成所有画作的最少时间。
相当于对整型数组作划分，求所有划分里最大划分和最小的一个。
f(arr, i, n) = min{ max{arr[i..j], f(arr, j+1, n-1)} }
邮局选址问题
一条直线上有居民点，邮局只能建在居民点上。给定一个有序整型数组arr，每个值表示居民点的一维坐标，再给定一个正数num，表示邮局数量。选择num个居民点建立num个邮局，使所有的居民点到邮局的总距离最短，返回最短的总距离。
dp[i][j]：从i开始建j个邮局
dp[i][n] = min{ max{arr[i...j], dp[j+1][n-1]} }
