笔记剑指 Offer 全解（Java 版）3rd>

想法：github上写个本文升级版：每题都像前两题这样有动图具象化思路分析。
本文中用到jdk提供的库函数并当成时空复杂度为O(1)：ArrayList#add()、addAll(ArrayList)，Stack#add()、push()、pop()，Arrays.fill(数组，一个元素)，Math.pow()

1. 数组中重复的数字
  “要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。”QQQ 为什么时间复杂度O(N)就不能使用排序方法？都达不到O(N)吗？？？排序方法是什么样的？有哪几种？？？AAA 链接各排序算法复杂度及稳定性表图
  答案思路：
  从第一个位置开始将“值为 i 的元素调整到第 i 个位置上”。调整方法是先看是否nums[i] != i，是的话再看是否nums[i] == nums[nums[i]]，否的话，两者加起来说明i位置上和nums[i]位置上都不是该有的值即索引值，于是互换这两个位置的值。这样一直互换直到i位置上的值是i，或者i位置上虽然不是i但是和某位置数重复。QQQ 这种互换方法是怎么保证最终i位置上的值能换得i？？？UUU 假设没有重复的数，那么数组中的数就是数组的索引被打散的样子，那么显然这种互换方法肯定能保证最终i位置上的值能换得i
  重复的数至少有一个数不在该在的位置上。
  答案思路4th:

while (nums[i] != i) { //nums[i]说：本值放在当前位置是错的  
  if (nums[i] == nums[nums[i]]) { //nums[i]说：本值该放的位置也没放本值同胞，互换一下放本值过去。互换后当前位置对错本次不管。（如果数组中没有0，那么对0位的while遍历就会得出结果）

作者小结：“对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。”

1. 二维数组中的查找
  答案思路：该二维数组中的一个数，小于它的数一定在其左上边，大于它的数一定在其右下边。因此，从最右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
  答案思路第三遍：可以从右上角和左下角开始，但不能从左上角和右下角开始，因为比如从左上角开始，如果比目标数小既可以往右找也可以往下找，有不确定性。
  答案思路4th：

小结：在两个维度都排好序的二维数组中查找问题，用向左上角/右下角或类似方向缩小范围的方式查找。

1. 从尾到头打印链表（与24题重复）
  4th:

小结：链表的反转，很基础常见的算法题，递归解法、迭代法（就是遍历）（头插法只是一种迭代过程的形象化描述）、栈。

1. 替换空格
  答案思路：先遍历一次字符串看有多少空格就在字符串尾部追加多少任意占位字符。然后两个“指针”p1和p2同时从原结尾字符和现结尾字符开始向前遍历。p1遍历到空字符，p2就逐位向前写02%；p1遍历到非空字符，p2就写p1指向的字符。
  4th:
  链接StringBuffer与StringBuilder
7、重建二叉树

//该方法的入参，pre一直是前序数组，preL是被上次递归中前序数组中某数分割出来的子树的数们在前序数组中首索引，preR是被上次递归中前序数组中某数分割出来的子树的数们在前序数组中的尾索引，inL是被上次递归中前序数组中某数分割出来的子树的最左节点在中序数组中索引。
private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {}

答案思路：

利用中序数组对前序数组中的数进行处理：找出左子树、右子树进行处理。
每次reConstructBinaryTree(int[] pre, int preL, int preR, int inL) 处理的子树中的所有节点数据为索引从preL到preR到的数据。
前序数组中每个数据都可以看成某子树的根节点（其实中序数组中每个数据也可以这样看），因此在对树逐次递归处理的过程中，步进可以写preL+1。
处理左子树的reConstructBinaryTree()和处理右子树的reConstructBinaryTree()最后一个入参，分别为inL和inL+leftTreeSize+1，之所以差leftTreeSize+1，是因为前者reConstructBinaryTree()处理的子树的节点数量是leftTreeSize，后者reConstructBinaryTree()是处理右子树的，再+1是因为在中序遍历数组中左右子树数据中间有个根节点数据。
4th:

前序遍历的某/每个值，将中序遍历分成左子树和右子树。前序遍历的某/每个值，紧跟后面是一段左子树前序遍历和一段右子树前序遍历，两段的长度可通过中序遍历得知。
TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL){}该方法的入参:整树的前序遍历，当前处理的树/子树的前序遍历首位，当前处理的树/子树的前序遍历末位，当前处理的s树/子树的中序遍历首位。

10.1 斐波那契数列
4th:

小结：递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而本题可以避免重复求解子问题的情况。递归从大问题入手，一层一层递归到最小子问题，动态规划从最小子问题入手，一步一步推进到大问题。

10.2 矩形覆盖解题思路中这样一段文字：
要覆盖 2*n 的大矩形，可以先覆盖 2*1 的矩形，再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，再覆盖 2*(n-2) 的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。该问题的递推公式如下： f(n)=f(n-1)+f(n-2)。
为什么不是f(n)=f(n-1)+2*f(n-2)？毕竟先覆盖2*2是有两种情况的。因为2*2的两种情况中，有一种是和先覆盖2*1是重复的情况。
第三遍：最小子问题的确定也是递归、动态规划这类将问题拆成子问题思路的一个关键。
10.4 变态跳台阶动态规划的解法思路是：
比如4级台阶时，方法是从地直接跳到第4级有1种，从地直接到第2级台阶然后从第3级到第4级即1级台阶的跳法有dp[0]种，从地直接到第2级台阶然后从第2级到第4级即2级台阶的跳法有dp[1]种，从地直接到第1级台阶然后从第1级到第4级即3级台阶的跳法有dp[2]种，所以dp[3] = 1 + dp[0] + dp[1] + dp[2]。
4th:

小结：动态规划可能是当前问题计算用到之前一、两个子问题的结果，也可能是当前问题计算用到之前所有子问题的结果比如本题。

11 旋转数组的最小数字
感想：算法中的临界问题好难想通，比如奇数中间位置最后归于左边还是归于右边、偶数中间位置开始取自左边还是取自右边、许多数不断分割处理到最后只剩一两个数时候的处理、处理理想状态是小于但有特殊情况等于的≤。
这题解中奇数中间位置先在思维中归于右边，看在右边构成的对象是非递减数组还是旋转数组，然后根据右边构成的不同在代码上将其归于左边。偶数中间位置取自左边。许多数不断分割处理到最后只剩两个数继续按许多数逻辑处理最后只剩一个数（即最左、中间、最右都指向一个数）。处理≤的特殊情况=时，QQQ 想不通顺畅的逻辑？？？答案是怎么想到特殊情况时nums[l] == nums[m] == nums[h]？？？答案怎么想通nums[l] == nums[m] == nums[h]不会出现在正常情况中？？？ UUU 只能照着答案想：nums[m] >和< nums[h]的情况是确定的，就剩nums[m] == nums[h]的情况是不确定的特殊的，这时有两种情况，一种是可以和<一致的情况即旋转在左如79111、91333等，一种是旋转在右边。那就找找看这时旋转在右边有没有规律，我找出来的规律是左边的非递减数列只能全部相等，所以采取遍历处理这种特殊情况，所以用nums[l] == nums[m] == nums[h]表示特殊情况。
4th:
答案思路：一直对半分，且最小值在旋转数组那一半中。QQQ 秉承这样的思路，最后以nums[l]而不是nums[m]或nums[h]作为结果，这是必然吗？nums[m]nums[h]怎么了？怎么想出排除它们作为结果的？？？UUU 估计不是必然，因为退出while的条件肯定是l=h，所以nums[h]也可以。至于nums[m]，如果是h=m导致退出遍历可以，如果是l=m+1导致退出遍历不行。
1. 矩阵中的路径

private boolean backtracking(char[][] matrix, char[] str,
                             boolean[][] marked, int pathLen, int r, int c) {
 	//这里返回的不是目标字符串长度为0就是已经在上一次backtracking()中找到了目标字符串最后一个字符了。
    if (pathLen == str.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols
            || matrix[r][c] != str[pathLen] || marked[r][c]) {
 		//这里大多情况的返回是matrix[r][c] != str[pathLen]，而且是从上一次backtracking()命中向四周邻格搜索到目前一次都没搜到。
        return false;
    }
    marked[r][c] = true;
    for (int[] n : next)
        if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1]))
            return true;
    //这里返回的情况是本次backtracking()命中了但是从该位置向四周邻格搜索一个都没命中只能放弃当前命中的位置。
    marked[r][c] = false;
    return false;
}

4th:
if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] != str[path(ing)Len] || marked[r][c]) {//~||~||~||~||矩阵当前搜索位置字符不等于字符串当前位置字符||矩阵当前搜索位置在本次搜索（一次指从第一个位置开始）从最开始到目前没被搜过

小结：回溯法是一种基础算法（递归算法）在具体场景（搜索）中的名称/应用，是遍历所有可能的暴力搜索，一次遍历结束或者一次遍历中一小段结束会清空本次或本段已搜痕迹/全局状态或局部状态（本地marked[][]既存全局状态也存局部状态），回到最开始位置或某段的开始位置进行下一次遍历。

13.机器人的运动范围
基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）
“回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态（比如本题的boolean[][] marked，用来标记所有搜索过程中走过的格子，使后面的搜素不搜这些格子）。”
答案思路：
代码中digitSumOne[]数组的元素是从1开始的数位之和，n % 10是得到个位数，n /= 10是去除个位数。
4th:

小结：深度优先搜索是一种基础算法（递归算法）在具体场景（搜索）中的名称/应用。一种特例是回溯算法比如上一题就是，二者都会记录搜索痕迹/全局状态，后者还会记录局部状态并在局部搜索完成后清除局部状态。

本题和上题，之所以一个选择深度优先搜索一个选择回溯搜索，因为本题不用区分不同的搜索路径只需关注有无搜过某位置，上题需要记录不同的搜索路径。也因此本题只需记录全局状态，上题需要记录全局状态和局部状态（都是marked[][]，尚未被清空的就可以理解成目前全局的，被清空的当然就是局部的）。也因区不区分不同搜索路径，使得本题只需要从一个点开始就能完成完整的搜索过程，上题需要不断回溯到最始然后换一个最始点重新开始一次搜索。

14.剪绳子
贪心：
为什么只需要考虑整数？因为原题是这样描述“给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。”
为什么只需要验证2和3这两个值？我觉得：是从最小数1开始，越早发现能使乘积更大的数就越是这个数，因为更大的数能拆成这样的数。为什么发现了2能使乘积更大还要继续发现3呢？我觉得：因为3比较特殊，虽然能拆成2*1，但是还不如不拆，所以继续发掘3。再往大的数总能拆出乘积不小于自己的数。

动态规划：
```
//该方法n = 1的结果不对。
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;  //为了代码而写的特殊值
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j))); //里面的max是比较将n长绳子截成两段的乘积和截成小于n长的最大截形、剩下作为1段的乘积。
    return dp[n];
}
```
QQQ 为什么感觉dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)))中没必要比较j * (i - j)和dp[j] * (i - j))的最大值呢，毕竟dp[j]已经代表j段的最大值了？？？
4th:
QQQ dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)))里面的Math.max换成dp[j] * dp(i - j)会不会效率更高？？？

小结：本题贪心算法，需要先找出“贪的目标”：先尽可能多分出3，有1时再“借来”一个3分成两个2。然后使用基础算法——动态规划进行运算。
1. 二进制中 1 的个数

小结：神奇的位运算：x & -x，获取到二进制中最右边的 1，且其它位设置为 0。x & (x - 1)，去除二进制中最右边的1。

17.打印从1到最大的n位数

java中将int类型转换成char类型的方式：
（1）// 将int类型数字8转换为char类型数字8
int num1 = 8;
char ch1 = (char) (num1 + 48); //根据计算结果值去ascii码表中找到对应的字符就是转换后的字符。ascii码表字符'8'的十进制码值是56，或者写 (char) (num1 + '0')因为字符'0'的十进制码值是48所以num1 + '0'其实是num1 + 48
System.out.println("ch1 = " + ch1);
（2）//只一位数的int 先把他转换成String　在通过String转换成char，比如一个int i=3；
String str=String.valueOf(i); char c=str.charAt(0); //如果多位数吗，就只能用char[]数组表示（因为一个char只能容纳一位数） int i=33; String str=String.valueOf(i); char[] ch=str.toCharArray();
QQQ 不理解为什么该解法是回溯法？？？AAA 在“13.机器人的运动范围”中有对回溯法的简单说明，可以帮助思考理解。本题从最高位开始逐位（第一个for的递归）给每个数位设置一个数，设置到最低位输出，等下次从最高位换一个数开始逐位设置时，前面设置的数位会被修改被无视。AAA 3rd 本题从最高位开始逐位（第一个for的递归）给每个数位设置一个数，设置到最低位输出（深度优先），最低位的可能情况输出完毕后，回到次低位设置另一个数（之前设置的数被覆盖掉即清除掉），又回到最低位设置数输出一轮（之前设置的数被覆盖掉），……，直至回到最高位设置另一个数又开始逐位设置，前面设置的数位会被修改被无视即被清除。所以作为特殊的深度优先算法回溯法，如果用数组存储搜索过程中的全局状态和局部状态，存储局部状态的位置，会被使用多轮。本题number数组第1位是全局状态，全程只使用1轮从0到9，其他位都是局部状态，都使用了多轮，每轮从0到9设置一遍。
对位数很长的数字，int可能会溢出，可以考虑用char[]字符数组（整个数组只表示一个数）。
答案思路：

public void print1ToMaxOfNDigits(int n) {
   if (n <= 0)
       return;
   char[] number = new char[n];
   print1ToMaxOfNDigits(number, 0);
}

private void print1ToMaxOfNDigits(char[] number, int digit) { //digit：数位的索引，0最高位，1第二高位，……
   if (digit == number.length) {
       printNumber(number); //从最高位开始给每个位设置一个数，当设置到最低位时，一轮完成，可以输出了。
       return;
   }
   for (int i = 0; i < 10; i++) {
       number[digit] = (char) (i + '0');
       print1ToMaxOfNDigits(number, digit + 1);
   }
}

private void printNumber(char[] number) {
   int index = 0;
   while (index < number.length && number[index] == '0') //从高位开始获取到第一位不为0的索引
       index++;
   while (index < number.length)
       System.out.print(number[index++]);
   System.out.println();
}

4th:

//入参1：从第一位开始目前已顺序填入的一些数字。入参2：当前遍历轮次的有效已填入的位长，因为当递归返回一次后再次递归进入时，上次进入的输入会被无视被覆写。
private void print1ToMaxOfNDigits(char[] number, int digit) {
   if (digit == number.length) {//该条件表示从第一位开始已经填满，可以输出了。
       printNumber(number);
       return;
   }
   for (int i = 0; i < 10; i++) {
   	//下面这两句逻辑放一起，是说再多填入一位，尝试打印。
       number[digit] = (char) (i + '0');
       print1ToMaxOfNDigits(number, digit + 1);
   }
}

//以n=5的演算为例，如下是一部分演算过程
...
number = [0,0,0,,]
print1ToMaxOfNDigits([0,0,0,,], 3)
   enter for
   i = 0
   	number = [0,0,0,0,]
   	print1ToMaxOfNDigits([0,0,0,0,], 4)
   		enter for
   		i = 0
   			number = [0,0,0,0,0]
   			print1ToMaxOfNDigits([0,0,0,0,0], 5) 
   				digit == number.length ： {
   					printNumber([0,0,0,0,0])
   						》》》》》》》》》》换行
   					↑
   				}
   			↑
   		i = 1 //一般递归只是嵌套解套，这里因为是在遍历中递归，所以递归时除了嵌套解套外，还出现了“遍历”，要局部遍历完一轮再解套。
   			number = [0,0,0,0,1]
   			print1ToMaxOfNDigits([0,0,0,0,1], 5) 
   				digit == number.length ： {
   					printNumber([0,0,0,0,1])
   						》》》》》》》》》》1换行
   					↑
   				}
   			↑
   		...
   		i = 9
   						》》》》》》》》》》9换行
   		exit for //局部遍历完一轮才解套。
   	↑
   i = 1
   	number = [0,0,0,1,9]
   	print1ToMaxOfNDigits([0,0,0,1,9], 4) //一般递归开始解套后会一直解套，这里因为在遍历中递归，所以出现解一层套后，因为要进行遍历会再次嵌套解套。
   		enter for
   		i = 0
   			number = [0,0,0,1,0]
   			print1ToMaxOfNDigits([0,0,0,1,0], 5)
   				digit == number.length ： {
   					printNumber([0,0,0,1,0])
   						》》》》》》》》》》10换行
   					↑
   				}
   			↑
   		i = 1
   		...
   		i = 9
   		exit for
...

QQQ 这就是回溯法，那第12题的时候也是这样，怎么没感觉到遍历+递归与递归的区别？？？UUU 因为12题更具象化？！，外加当时比较专注

18.1 在 O(1) 时间内删除链表节点
QQQ “如果进行 N 次操作，那么大约需要操作节点的次数为……”这个N次操作是什么意思，是删除N个节点吗？？？“(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)”是什么意思，意思是操作次数/问题规模表示平均时间复杂度吗？？？
4th:
UUU 本题因为是对每个节点的复杂度求了和，所以才除以问题规模。QQQ 这种平均算法复杂度的计算具备通用性吗？？？
18.2 删除链表中重复的结点
该题有个前提是“有序的链表”。
根据答案猜其思路：整体上不断递归，递归到链表最后一个节点时开始返回。递归的整体思路是从头节点开始逐个往后，把每个当前节点作为deleteDuplication()的入参进行处理。剔除重复节点就是通过这段

   if (pHead.val == next.val) {
       while (next != null && pHead.val == next.val)
           next = next.next;
       return deleteDuplication(next);
   }

答案思路新理解：if中逻辑是遇到相同的数，一直循环，全部跳过，从下一个无重复的数开始继续处理。else中逻辑用pHead.next构建出新链表。

19. 正则表达式匹配

“'' 表示它前面的字符可以出现任意次（包含 0 次）”的理解：例如，字符串"aaa"与模式"abaca"匹配，但是与"aba"不匹配。
与"abaca"匹配，表示第一个前面的字符b出现0次，第二个前面的字符c出现0次。与"aba"不匹配是因为前面的字符b出不出现都匹配不到aaa。

位运算符：
＆如果相对应位都是1，则结果为1，否则为0
| 如果相对应位都是 0，则结果为 0，否则为 1
^ 如果相对应位值相同，则结果为0，否则为1
〜按位取反运算符翻转操作数的每一位，即0变成1，1变成0。
<< 按位左移运算符。左操作数按位左移右操作数指定的位数。
>> 按位右移运算符。左操作数按位右移右操作数指定的位数。
>>> 按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。

答案思路：
代码中构建的数组 alt

    for (int i = 1; i <= n; i++) // QQQ 构建dp[0]、处理dp[0]的道理？？？
        if (pattern[i - 1] == '*')
            dp[0][i] = dp[0][i - 2];

    for (int i = 1; i <= m; i++) //逐个将目标串中字符与模式串中字符逐个匹配，因为每次匹配的结果都依赖之前匹配的结果，所以每次某个目标符和某个模式符的匹配结果dp[i][j]又表示了前i个目标字符段与前j个模式字符段的匹配结果。（2nd：对下面for中的逻辑按照一段字符串来理解的，3rd：对下面for中的逻辑按照单个字符比较来理解的。）
        for (int j = 1; j <= n; j++)
            if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') //如果目标串中某字符与模式串中某字符相同，则目标串此段与模式串此段的匹配结果取决于目标串此前段与模式串此前段的匹配结果。因为两串的最后一个字符是匹配的就不影响结果了。
                dp[i][j] = dp[i - 1][j - 1];
            else if (pattern[j - 1] == '*') //模式串中该字符是*则看它前一个字符
                if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') { //目标串当前字符和模式串*前字符匹配
                    dp[i][j] |= dp[i][j - 1]; // a* counts as single a //忽略*：当前结果可取决于目标此段匹配模式此前段结果
                    dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a //*当作前一字符的副本或者把*当作前一字符和两个副本：当前结果可取决于目标此前段匹配模式此段结果。因为目标此前段在匹配模式此段的时候把*忽略了或者把*当成一个副本，目标此段在匹配模式此段的时候把*复制成*前或者复制成2个*前了。
                    dp[i][j] |= dp[i][j - 2]; // a* counts as empty //忽略*前和*：当前结果可取决于目标此段匹配模式此前前段结果。因为有可能*前前字符和目标当前字符相同
                } else
                    dp[i][j] = dp[i][j - 2];   // a* only counts as empty //如果模式串中*前字符不能匹配则忽略*前字符，结果取决于目标串此段和模式串*前前段的匹配结果。

4th:
答案思路：

dp[i][j]：表示i长字符串匹配j长模式串的结果。i长即长度为i。
if (pattern[i - 1] == '*')
	dp[0][i] = dp[0][i - 2]; //0长字符串匹配i长模式串的结果与0长字符串匹配i-2长模式串的结果相同，因为模式串第i位是*，那么可以表示第i-1位和第i位没有字符。不用考虑*表示的第i-1位重复多次的情况，因为0长字符串匹配过第i-2位，现在字符串长度没变而模式串长度增加了，考虑重复多次的情况肯定匹配不上。
for (int i = 1; i <= m; i++) //m长字符串匹配分析
        for (int j = 1; j <= n; j++)//n长模式串匹配分析
            if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')//因为第i个字符等于第j个模式符，所以i长字符串匹配j长模式串结果与i-1长字符串匹配j-1长模式串结果相同。
                dp[i][j] = dp[i - 1][j - 1];
            else if (pattern[j - 1] == '*')
                if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {//QQQ 没有pattern[j - 2] == '.'的事？？？UUU 因为pattern[j - 2] == '.'也是一种pattern[j - 2] == str[i - 1]
                    dp[i][j] |= dp[i][j - 1]; // a* counts as single a //i长字符串匹配j长模式串与i长字符串匹配j-1长模式串结果相同（角度一按匹配成功来，因为*可以表示第j-1位字符只在该位出现一次，第j位是空的）（角度二不考虑匹配成功与否<但必须有成功的情况，如果只有匹配失败的结果，处理没有意义，dp[][]默认就是false>，因为前者可以将第j位看成空来匹配保证不因多一位模式符*影响结果）
                    dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a //或者i长字符串匹配j长模式串与i-1长字符串匹配j长模式串结果相同，比如字符串y2，模式串x2*（角度一按匹配成功来，后者匹配时把x2*看成x，前者匹配时把x2*看成x2，或后者匹配时把x2*看成xn个2，前者匹配时把x2*看成x(n+1)个2）（角度二不考虑匹配成功与否<但必须有成功的情况，如果只有匹配失败的结果，处理没有意义，dp[][]默认就是false>，这两者结果之所以相同，是因为前者匹配时可以在后者匹配的基础上增加一个模式符2来匹配来保证新增一位字符不影响结果。）
                    dp[i][j] |= dp[i][j - 2]; // a* counts as empty//或者i长字符串匹配j长模式串与i长字符串匹配j-2长模式串结果相同（因为*可以表示第j-1位字符没出现过，第j-1位和第j位是空的）（因为前者可以将第j-1位和第j位看成空的来匹配保证不因多两位模式符而影响结果）
                } else
                	//QQQ 为什么不能这么思考： i长字符串匹配j长模式串与i长字符串匹配j-1长模式串结果相同（）（因为前者可以将第j位看成空来匹配保证不因多一位模式符*影响结果），从而得出dp[i][j] = dp[i][j - 1]？？？UUU 因为模式串倒数第二位与字符串最后一位不同，所以dp[i][j - 1]不可能为true只能为false，当然dp[i][j] = dp[i][j - 1]是成立的，而dp[i][j]默认就为false，写dp[i][j] = dp[i][j - 1]没意义。
                	// i长字符串匹配j长模式串与i长字符串匹配j-2长模式串结果相同（因为*可以表示第j-1位字符没出现过，第j-1位和第j位是空的）（因为前者可以将第j-1位和第j位看成空来匹配保证不因多两位模式符影响结果）
                	dp[i][j] = dp[i][j - 2];

QQQ 怎么想出思路的？？？怎么做到该思路的各种情况没有重复性？重复会不会影响结果？？？

20. 表示数值的字符串
答案有问题，比如一个+也能得到true，比如不符合科学计数法表示规则的12e1也能得到true（科学计数法表示10次幂的e前面也该是绝对值小于10的数）。
4th:
()匹配字符串的，[]用字符范围匹配字符的。
1. 调整数组顺序使奇数位于偶数前面
  链接冒泡排序动图演示
  4th:
  QQQ 方法一数组.clone()的复杂度考不考虑？是多少？？？
1. 链表中倒数第 K 个结点
  QQQ 答案这么做的优势是什么？？？
  4th:AAA 好理解算不算优势。链表的特殊之处在于不知道总长度，根据当前节点不能直接找到上一个节点。
1. 链表中环的入口结点
  QQQ 解题思路中的x、y、z是怎么想出来的？？？
1. 反转链表
  QQQ 递归解题思路是怎么想出来的？毕竟连顺着思路都要画图仔细推敲才看出来的东西？？？迭代思路为什么叫头插法？搞一个对象当指针用为什么叫头插法？？？什么叫迭代？？？
1. 合并两个排序的链表

吴书小结：关于变量和对象。
单独变量如a：=右边的理解成对象本身。=左边的先理解成对象本身，如果有再被赋值的操作理解成指针，或者在左边之前在右边出现过理解成指针。
变量的变量如a.b：这种对象中的变量，如a对象.b，在=右边理解成对象本身，在=左边理解成a对象持有的一个引用/指针。类似的如a.b.c，理解成a.b.c对象或a.b对象持有的一个引用/指针。
之所以一会儿理解成对象本身，一会儿理解成指针，是因为程序的操作确实有时是对对象本身进行，有时是对指针/地址进行。
“a=b; b=c;”别脑子打结想成a=c。a指向的对象还是b之前指向的对象，b现在指向了和c所指向的相同的新对象。
返回值理解成对象本身，入参在方法体开始执行前理解成对象本身然后按照上述过程理解。
没有=的其他地方，优先按照对象理解。

本题的迭代解法中，对cur.next = xxx的理解很关键，简单理解成一个指针指向了xxx后续就行不通，应理解成cur对象本身的一个引用/指针指向了xxx。

26. 树的子结构
#HasSubtree(TreeNode, TreeNode)使可以继续递归。
#isSubtreeWithRoot(root1, root2)判断是否从这个root1和root2位置开始链表重合。
QQQ 该题在线编程题目中的代表两棵树的写法{8,8,#,9,#,2,#,5},{8,9,#,2}是什么意思？？？不像下一题的写法{8,6,6,5,7,7,5}就很容易明白是一种层序遍历，就是按层从上到下每层从左到右遍历
1. 顺时针打印矩阵
  四个for的执行逻辑
1. 包含 min 函数的栈
  Stack#peek和pop的相同点：大家都返回栈顶的值。不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。
1. 栈的压入、弹出序列
  在线编程页面的一个说明“由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入QQQ 为什么，不是先进后出吗？？？，且1，2不能弹出QQQ 怎么来的？？？，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false”
  答案思路：用一个Stack来执行正确的压栈出栈过程。
32.1 从上往下打印二叉树
接口Queue 中 remove() 和 poll() 区别：Queue 中 remove() 和 poll()都是用来从队列头部删除一个元素。在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null 。
双层ArrayList可以当作二维数组。
32.3 按之字形顺序打印二叉树 4th：QQQ 用到Collections.reverse(ArrayList)，该库函数的时间复杂度？？？
1. 二叉搜索树的后序遍历序列
  二叉搜索树BST的一个特性是树中每个节点若存在左子树则左子树中每个节点的值小于该节点的值，若存在右子树则右子树中每个节点的值大于该节点的值。二叉搜索树有两种特殊情况，一种是完全二叉树：所有节点尽量填满树的每一层，上一层填满后还有剩余节点的话，则由左向右尽量填满下一层；一种是每一层只有一个节点的二叉树。
  答案思路：递归，从大树到小树的递归：先判断整个树的根节点和根节点左子树、右子树整体满不满足数值的大小关系，满足了再分别进入根节点的左子树和右子树判断。
  代码中if (last - first <= 1)，=1时，表名当前只剩两个节点需要进行分析，两个节点肯定满足后序遍历，当前一个比后一个大时，说明前面是右子节点后面是根节点，当后一个比前一个大时，说明前面是左子节点后面是根节点。
1. 二叉树中和为某一值的路径
  QQQ new ArrayList<>(ArrayList对象)这会得到什么？是拷贝出一个元素和入参元素一样的新ArrayList对象吗？？？
  4th:AAA new ArrayList<>(ArrayList对象)是入参对象的深度拷贝
  QQQ 怎么能写出递归算法？像本答案的path.remove(path.size() - 1);和if (node == null) return;怎么想到的？？？
1. 复杂链表的复制
  答案中拆分的逻辑就是遍历链表，让每个节点的next指向下下个节点。
1. 二叉搜索树与双向链表
  java在值传递调用过程中即参数是基本数据类型，只能把实参传递给形参，而不能把形参的值反向作用到实参上，即在函数调用过程中，形参的值发生改变，而实参的值不会发生改变。而在引用传递调用的机制中即参数是引用数据类型，实际上是讲实参引用的地址传给了形参，所以任何发生在形参上的改变也会发生在实参变量上。
  形参只有在方法被调用的时候，虚拟机才会分配内存单元。
  答案思路：QQQ 看得懂代码过程想不通思路。？？？
```
private void inOrder(TreeNode node) {//每次调用都把node当成根节点。
    if (node == null)
        return;
    inOrder(node.left);
    node.left = pre; 		//
    if (pre != null)		//
        pre.right = node;	//
    pre = node;				//这四行的代码中pre相当于游标指针，游标遍历的顺序就是中序遍历的顺序。这四行代码的逻辑就是将pre和中序下一个节点互相指向。
    if (head == null)
        head = node;
    inOrder(node.right);
}
```
答案思路3rd：
通过inOrder()的递归逻辑对BST进行中序遍历，借助pre指针来构建双向链表。下面这几行代码可以理解成构建双向链表的过程是先把链表两个节点之间的相互指向设置好然后pre移动一下即pre=node。在设置两个节点的相互指向时是先把“后面”的指向“前面”即node.left=pre再把“前面”的指向“后面”即pre.right=node。
```
inOrder(TreeNode node) {
	...
	node.left = pre; 
	...
	pre.right = node;
	pre = node;
}
```
1. 序列化二叉树
  QQQ 在线编程页面的题目中有段描述“根据满二叉树结点位置的标号规律来序列化”，什么意思？？？
  答案中是按照前序遍历进行序列化，所有nil节点也要序列化出来，用#表示。
1. 字符串的排列
  知识点：数组是引用类型
  答案中的boolean数组，将第几个设置为true表明要将原数组中第几个数追加到当前的字符串中试试。这个条件if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1])只会出现在相同字符相邻时遍历到后面的字符时判断，hasUsed[i - 1]=false表示当前一样的字符串没必要再试了因为位置比自己靠前的相同字符串已经试过了。
  答案的思路：原字符串数组不动，在空的StringBuilder对象上试数，根据原字符串数组从左往右开始试数，将数从左往右填到StringBuilder对象中，试了一个数后再把这个数拿掉试剩余的其他数。这种思路得到的结果顺序为{abbc, abcb, acbb, babc, bacb, bbca, bcab, bcba, cabb, cbab, cbba}，该结果的顺序可以帮助理解一点答案思路。
  答案思路：
  QQQ 原题要求的空间复杂度O(n!)怎么理解？？？UUU 答案的空间复杂度应该是2n吧 3rd：QQQ 看得懂代码过程想不通思路。？？？
  4th：“回溯+迭代”的回溯算法。还是看懂代码想不通思路。
  答案思路中的!hasUsed[i - 1]作为保证不重复的一部分逻辑，对此的理解，前后联系在一起考虑不好考虑，就考虑当前所处的迭代中：在本代i，首先hasUsed[i]=true，然后才能执行到!hasUsed[i - 1]所在行代码，迭代肯定是从i=0开始一代一代迭的，所以hasUsed[i - 1]=false，说明上一代i-1已经迭过回溯了所以置为false。
  上一代i-1的hasUsed为true，那都不是当前迭代中设置了，是“包着”当前迭代的外层迭代设置的。
1. 数组中出现次数超过一半的数字
  答案思路重新表述：使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 cnt++，否则令 cnt--。如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority但是出现的次数少于 i / 2（因为如果多于 i / 2 的话 cnt 就一定不会为 0）。不管是二者中哪种情况，此时剩下的 n - i 个元素中majority 的数目都多于 (n - i) / 2，因此继续查找就能找出 majority。
  答案中写第二个for的原因是经过第一个for得到的结果要么是多数要么是不符合的数只是碰巧这个数最后一次出现的时候把前面多数积累的cnt减完了。4th:原因不是这个，因为不可能出现这种情况。所以只能将第二个for理解为验证。
  4th:
小结：多数投票算法是一种场景化的算法，用的基础算法是迭代法。
1. 最小的 K 个数
快速排序的思路：直接对原数组进行修改。从第一个元素开始作为当前标准元素，对后面的元素从两头开始与标准元素比较，从前开始发现比标准元素大的停下等着往后放，从后开始发现比标准元素小的停下等着往前放。放的方法就是交换当前发现的较大和较小元素。最后再交换一下当前标准元素和较小元素段的最后一个元素位置。
QQQ 为什么答案说这种算法复杂度是O(n)+O(1)？真不是的话是O(nlogn)吗？怎么计算这题复杂度？？？

>>>表示的是无符号右移：https://www.jianshu.com/p/927009730809

原码、反码和补码：一个数可以分成符号位（0正1负）+ 真值，原码是我们正常想法写出来的二进制。由于计算机只能做加法，负数用单纯的二进制原码书写会出错，于是大家发明了反码（正数不变，负数符号位不变，真值部分取反）；再后来由于+0， -0的争端，于是改进反码，变成补码（正数不变，负数符号位不变，真值部分取反，然后+1）。二进制前面的0都可以省略，所以总结来说：计算机里的负数都是用补码（符号位1，真值部分取反+1）表示的。
但是补码表示的如1000 0000比较特殊，不能理解成原码真值位取反加1得来的，只能理解成带上符号位一起取反加1得来的，表示-128。
QQQ 怎么知道一个左边第一位是1的二进制数表示的是正数还是负数？？？

PriorityQueue是小顶堆的数据结构，该类中用数组存放数据。https://blog.csdn.net/u010623927/article/details/87179364这篇文章写得不错。QQQ 唯一疑问是#remove和#poll源码中#siftDown()的half作为遍历条件的依据是什么？是不是因为超过size的一半就表示又回到了起初的位置？？？

堆排序的思路：作者写的“最小堆”是作者自创的，不是指数据结构中的小顶堆，作者的意思是这个堆中的数据都是源数据中的最小数。

PriorityQueue竟然可以这样new ArrayList(PriorityQueue)转成ArrayList

堆排序的的时间复杂度是初始化堆和删除元素时的重建堆时间复杂度。QQQ 为什么是O(NlogN)
4th：
答案维护固定大小的大顶堆的逻辑：开始添加元素建好K大小的堆，后续再添加元素先入堆、重新堆化，然后移除堆顶、重新堆化。可以优化为：开始添加元素建好K大小的堆，后续再添加元素时先与堆顶比较，比堆顶大忽略，比堆顶小移除堆顶、入堆、重新堆化。

小结：快速选择算法是基于快速排序算法思想的用于解决Top K 问题的算法。快速排序算法最优时间复杂度是O(nlogn)，最坏时间复杂度是O(n²)，平均时间复杂度是O(nlogn)。

堆逻辑上是一个完全二叉树物理上是存放在数组中（QQQ 为什么不用链表存放？？？），它的基本作用是快速找集合中的最值，适合处理海量数据，因为不需要一次性将全部数据取出来，只需要将数据一个个取出与堆顶比较。

入堆采用尾插法然后向上调整，出堆（删除堆顶元素）采用用尾节点替换堆顶然后向下调整的方式。

堆排序的复杂度：“对N个元素建堆的时间复杂度为O(N)，删除堆顶元素的时间复杂度为O(logN)，尽管随着元素的不断删除，堆的调度越来越小，但是总的而言，删除所有元素的时间复杂度为O(NlogN)。空间复杂度为O(1)。”。

堆排序经典应用场景——解决TOP K问题的过程：“以小顶堆解决最大TOP K问题为例，对原始数组构建并维护大小为K的小顶堆，开始构建，当堆的大小满了，只需要将堆顶元素与下一个数比较，如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，TOP K的元素就都在堆中。遍历数组需要O(n)的时间复杂度，一次堆化操作需要O(logK)，加起来就是O(nlogK)的复杂度。”

41.2 字符流中第一个不重复的字符
标准ASCII码表有128个字符，7位二进制表示。扩展ASCII码表在前者基础上又扩展出128个即256个，8位二进制表示。

Java标准库中定义了Queue接口，
int #size获取队列长度，
boolean #add/#offer将元素添加到队列尾部，
E #remove/poll获取队列首位元素且删除，
E #element/peek获取队列首位元素但不删除。
Queue和List的区别是List可以在任意位置插入和删除元素，Queue只能向队尾插入元素从队首删除元素。
LinkedList是Queue的实现。
1. 连续子数组的最大和 4th：简单的题，但是关键简单的两步
  sum = sum <= 0 ? val : sum + val;//之所以这样就能找出最大和子数组：是sum <= 0而不是val <= 0，因为后续可能出现更大的正值抵消了负值val这次的影响，当然也有可能后续没有更大的正值，但是sum已经过被greateSum记录下来。sum <= 0重新计算sum，新的子数组第一个数val是正数，正合适；是负数，如果比sum大也正合适，如果比sum小，没关系greateSum已经记录过最大的sum。
  greatestSum = Math.max(greatestSum, sum);
  却很值得推敲。
1. 从 1 到 n 整数中 1 出现的次数
  答案思路第一遍小结：答案中“int a = n / 10的倍数m, b = n % 10的倍数m”是将一个整数xxxyyy拆成高位数xxx即a和低位数yyy即b，比如n=124、m=10时就是拆成了12和4。
  答案中“(a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0)”是计算出1出现在高位数最低位的数字有多少个。
  答案中“(a + 8) / 10 * m”是计算这样的情况：高位数的最后一位可以写1，当写1时有多少个数字。利用该位后面的位数可以写m个数字，该位前面的数决定了m可以乘以几，这个几就通过(a + 8) / 10得出。
  答案中“a % 10 == 1 ? b + 1 : 0”，因为高位数的最后一位就是1的话，就意味着可以写出b+1个符合条件的数：xx1000~xx1yyy。这个xx只是原数中的数不能是其他小于数。
  答案思路第二遍总结：
  遍历：入参/目标数是几位数，就遍历几次。
  “int a = n / m, b = n % m;”：将目标数拆成左右两半。
  “(a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0)”：分第一个+前和第一个+后理解，比如当前是第二次遍历，+前计算十位是1、左半数值小于目标数左半数值的数字个数，+后计算十位数是1、左半数值等于目标数左半数值的数字个数。
  QQQ (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0)是计算出1出现在高位数最低位的数字有多少个，但是看不懂这个加法前一半的奇妙的8是怎么定出来的？？？AAA 用6069这10个数来理解，假设这是三位数的第二次遍历左半数，a+8使得这10个数前2个数的+前结果都是60，后8个数+前计算结果都是70。因为+前计算的是左半数值小于目标数左半数值，以分界处的61y、62y为例，61y左半小于61的x1有01、11、21 ... 51即6种，62y左半小于62的x1有01、11、21 ... 51、61即7种。
  答案思路第三遍总结：从个数开始遍历，总共进行n值位数次，比如234197就进行6次。
  int a = n / m, b = n % m;将n值拆成两部分，a是前部分我暂称为高位数，b是后部分我暂称为低位数。
  (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);关注高位数最后一位，计算出最后一位是1有多少种数。这时分两种情况讨论，高位数最后一位是0或1，高位数最后一位是29，通过a + 8完成这两种情况分类。
  比如高位数是2341低位数是97时，关注高位数最后一位是1即xxx1xx，m = 100表示的是xxx100~xxx199，(a + 8) / 10 = 234表示0001xx、0011xx、0021xx、...、2321xx、2331xx，对于2341xx，因为是“最值”所以xx达不到100种，也就不能m，于是通过(a % 10 == 1 ? b + 1 : 0)来计算2341xx，b + 1 = 98表示234100234197。
  比如高位数是2342低位数是97时，关注高位数最后一位是1即xxx1xx，因为高位数最后一位>1，这时2341xx能达到100种即234100234199，于是可以放心大胆地用m统一计算出包含2341xx的情形，这时(a + 8) / 10 = 235表示0001xx、0011xx、0021xx、...、2321xx、2331xx、2341xx。
  4th:
  答案思路：假设n的字符串表示是abcdefg，从个位开始逐位迭代，每一代讨论该位是1有多少种情况。
  讨论方法：从本代讨论的位置处分割，将abcdefg分成两部分，且本代讨论的位置分到前半部分，比如讨论c位就分成abc和defg，再把abc分成两部分，一部分是讨论位，剩下的是另一部分，即abc分成ab和c。
  当c位数值大于等于2时，那么就把c位前后各有多少种数相乘即可。...1...，前面的从0开始到ab，后面的从0开始到999...。
  当c位数值等于0时，那么就把c位前面构成的最大数减1，比如35cdefg的这里就是34，再把c位考虑成1，然后把这时c位前后各有多少种数相乘即可。...1...，前面的从0开始到ab-1，后面的从0开始到999...。
  当c位数值等于1时，先把c位前面构成的最大数减1，然后把这时c位前后各有多少种数相乘得到一部分情况；再单独讨论c位前面构成的最大数，这时就是c位后面构成的数+1代表有多少种情况，即从0到defg，这部分情况与c位前面最大数减1的情况之和就是c位数值等于1的情况。
1. 数字序列中的某一位数字
  题意是将0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21...这些数字拼接成字符串。
  答案中place表示几位数，1就是表示1位数，2就是2位数。getAmountOfPlace(int place)方法表示几位数的数字有多少个，比如1位数的数字有10个，2位数的数字有90个，3位数的数字有900个。getDigitAtIndex(int index, int place)是最后在确定的几位数中找对应索引处的数。
  QQQ getDigitAtIndex(int index, int place)中找指定索引处的数不复杂，但是是怎么得出来的，比如？？？
1. 把数组排成最小的数
  String#compareTo()方法：https://blog.csdn.net/ted_cs/article/details/82712248。
  ASCII是字符编码字符集，最开始的时候使用一个字节表示一个字符后来有扩展。Unicode是一种字符编码规范，最开始的时候使用的是两个字节表示一个字符后来有扩展，有具体实现该规范的字符集比如UTF-8、UCS-2。像UCS-2是使用两个字节，如果字符是ASCII码中的字符，则一个字节为空（值为0），另一个字节为原ASCII码中的值。
  Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));//s1、s2在入参中的顺序不代表什么，这时两个数可以分别是原数组中任意两个位置，经过compareTo之后两者的顺序就代表了在修改后数组中的相对位置。
1. 把数字翻译成字符串
  答案思路：dp[0]是个为程序代码一致性设置的特殊初始值。从dp[1]开始dp[1]对应数字第一位、dp[2]对应数字第二位…… 从只有1个数字时开始，结果就是1，即dp[1]；然后开始计算多出1个数字时即共有2个数字时的情况，一种是多出的数字单个成字符，结果就是0 + 前面的结果dp[i-1]即dp[1]，另一种是多出的数字和相邻数字一起成字符（因为数字不能超过26所以最多只能两位数字成字符），结果就是前前面的计算结果dp[i-2]即dp[0] + 前一种结果；然后继续计算多出1个数字即共3个数字时的情况……
1. 礼物的最大价值
  答案思路：dp[]数组是从左上角到每行每个位置的最大和，下面这两个for，第一个for是逐行遍历，第二个for是行内逐列/个遍历。第二个for中，dp[0] += value[0]是表示到每行行首只能是从上面一行行首来的，dp[i] = Math.max(dp[i], dp[i - 1]) + value[i]的最大值函数表示求出从左边邻数dp[i-1]来的和从上面邻数dp[i]来的哪个更大。
```
for (int[] value : values) {
  dp[0] += value[0];
  for (int i = 1; i < n; i++)
      dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
}
```
QQQ 动态规划和深度优先搜索、和特别的深度优先搜索回溯法如13题的区别？？？难道是深度优先搜索不设置一次搜索过程中的局部状态只可能会设置全局状态，回溯会在一次搜索过程中设置局部状态并在下一次搜索中清除这些局部状态，动态规划会在一次搜索中设置局部状态并在下一次搜索中利用这些状态再修改这些状态？？？
1. 最长不含重复字符的子字符串 char字符变量进行加减运算的时候，通过查找对应字符变量值的ASCII值，利用其在ASCII里的对应值进行加减运算。char与别的类型运算时，先自动转换为int型的，再做其它类型的自动转换。
  答案思路：到当前遍历处为止，curLen是记录最近一段无重复字符的长度，maxLen是记录从开始到目前无重复字符的长度历史最大值。preIndexs数组记录每个字符出现在目标字符串中的最新位置。if (preI == -1 || curI - preI > curLen)这个判断条件当是前假后真时，前假表示当前遍历的字母之前出现过，后真表示当前字符虽然重复出现过，但已经不在curLen表示范围内，所以不影响curLen++；当这个判断条件为假时，curI - preI = curLen:当前字符上次出现的位置正是curLen表示范围的起始位。curI - preI < curLen:当前字符上次出现的位置在curLen表示范围中间某个位置。curLen = curI - preI表示将长度更新为从当前字符上次重复处下一位开始到当前位置的长度。
1. 丑数不是“把只包含因子 2、3 和 5 的数称作丑数”，应该是“把只包含质因子 2、3 和 5 的数称作丑数”。
  QQQ 一个丑数会不会有多种质因数组合？如果有本答案有没有解决这种问题？？？AAA 解决了，因为答案中遍历的方式能保证从1开始所有质数都不会遗漏
  答案思路：新丑数肯定是旧丑数*某质因子得到的。
  dp数组是存放从第1个丑数开始的丑数。
  i2、i3、i5分别表示包含质因子2、3、5的数目前出现了几次。
  next2、next3、next5分别表示之前某个丑数*2、*3、*5后的新丑数。
  每次遍历比较出前三者最小值得到当前第遍历次数个丑数。
  dp[i2]、dp[i3]、dp[i5]之所以把出现某质因子的次数作为dp索引是因为要让整个遍历中*2、*3或*5前的乘数是从最小丑数开始的逐个丑数。一个质因子出现了几次，目前dp数组的大小肯定是大于等于几的。
  第二遍答案思路：
  next2：整个遍历过程中，从第1个丑数开始每次*2得出个新丑数。next3：整个遍历过程中，从第1个丑数开始每次*3得出个新丑数。next5：整个遍历过程中，从第5个丑数开始每次*5得出个新丑数。在一次遍历中，比较中next2、next3、next5的最小值。这样就能从最小丑数开始一个不落地找出所有丑数。

第一个只出现一次的字符位置 ASCII码使用指定的7位或8位二进制数组合来表示128或256种可能的字符。
Bitset可以用非常紧凑的格式来表示给定范围的连续数据。基本原理是，用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。比如以下代码的输出

public static void main(String args[]) {
   BitSet bits1 = new BitSet(16);
   BitSet bits2 = new BitSet(16);
    
   // set some bits
   for(int i=0; i<16; i++) {
      if((i%2) == 0) bits1.set(i);
      if((i%5) != 0) bits2.set(i);
   }
   System.out.println("Initial pattern in bits1: ");
   System.out.println(bits1);
   System.out.println("\nInitial pattern in bits2: ");
   System.out.println(bits2);
}
//输出如下，输出的是大小为16的bit数组中为1的索引
Initial pattern in bits1:
{0, 2, 4, 6, 8, 10, 12, 14}

Initial pattern in bits2:
{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

1. 数组中的逆序对
  Java的8种基本类型（实际上9种，void也是，但是我们操作不了它）存储在栈中，因此它们的存取速度要快于存储在堆中的对应包装类的实例对象。所有基本类型（包括void）的包装类都使用了final修饰。
  答案思路：
  整体就是归并排序法，该方法使用分治策略。将无序数组排序成升序数组，顺便统计中逆序对。
  最后一步的“cnt % 1000000007”奇怪的求模是原题要求。
  将整个数组不断二分mergeSort()，直到只包含一个元素的数组，然后与另一个“同级别”的二分数组升序合并merge()。每次merge()后都能保证本次合并范围内的元素是从小到大的升序。
  merge()中while遍历是对同级别被二分的两数组元素的逐个比较，并按升序暂存到tmp数组中。i > m表示两被二分数组中小组已经全部比较完毕，剩下大组中的数就是剩下的升序数。同理j > h。 this.cnt += m - i + 1，统计逆序对数量，当二分数组中小组的i位置数大于大组的j位置数时执行该统计，m - i是因为经过之前的mergeSort()能保证小组中i位置后的数都比i位置数大，那肯定也比大组的j位置数，所以逆序对数就是“整体”数组中间位置m - i + 1。
1. 数字在排序数组中出现的次数
  原题明确了“非降序数组和一个非负数整数 k”。
  答案思路：“int first = binarySearch(nums, K);”、“int last = binarySearch(nums, K + 1);”分别是找到第一个K的位置后最后一个K的位置，后者之所以能保证找到的是最后一个K的位置，是因为binarySearch()中当nums[m] < K时，修改l的值。
  答案思路：快速找到K的第一个位置和值最接近K+1的第一个位置。
1. 二叉查找树的第 K 个结点
  答案思路3rd：
  之所以能把cnt++放在inOrder左子节点和inOrder右子节点中间，可以理解成：这样就表示统计了当前节点。
  答案没有在获得ret时及时返回，因为这是递归，没办法马上跳出递归，所以只能通过cnt >= k条件来尽快结束递归。
1. 数组中只出现一次的数字
  java的位运算符
   为什么“diff &= -diff 得到出 diff 最右侧不为 0 的位”，为使我更好理解，对该博客的一段修改：
  首先在补码表示法中，负数/补码 = 取反 +1，这个都知道，但你可能没发现：
  取反后：原来最右边的 0 的位置对应于现在最右边的 1 的位置，
  而取反后 +1 ，则会把现在该位的1往前进位（同时现在该位也会恢复为原来的0），直到遇到第一个0停止，并把此位置为1，而第一个0就恰恰对应原来第一个1。
  所以负数/补码则相当于将最右边的 1 的左边的所有位取反，该1和右边的所有位不变。
  答案思路：
  》diff_1没有& -diff之前，diff_1就是所有数异或累计，也是两个不重复数的异或结果。
  》“diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位”，之所以这样说就是因为diff_1是两个不重复数的异或结果，该结果的1位说明两数在该位上不同。
  》之所以能通过遍历数组num1[0] ^= num、num2[0] ^= num这样异或累计得到结果，因为除了两个不重复数以外其他数都是成对重复、异或后都是0。
57.1 和为 S 的两个数字
答案的思路能保证“如果有多对数字的和等于 S，输出两个数的乘积最小的”，可以比较数学表达式x*(y-x)和(x+1)*(y-x-1)的大小来理解这种保证。
57.2 和为 S 的连续正数序列
答案思路：从第1个数开始累计尝试，试出结果比S小则将最后数的索引end往后移一位继续试，试到比S大则将起始数索引start往后移一位，试出等于S则记录下跨越的数字然后将起始数位置start和最后数位置end都往后移一位继续试。
58.1 翻转单词顺序列
“任何使用了额外空间的解法在面试时都会大打折扣，包括递归解法。”QQQ 意思是递归法的空间复杂度肯定比O(N)大？？？
答案思路：
“先旋转每个单词，再旋转整个字符串”，让[I ma a student.]先逐个单词旋转变成[I ma a .tndeuts]，再整个旋转变成[student. a am I]。
“i = j + 1”是记录下个单词的首位置，下次旋转单词是在从该位置到当前遇到的空格前一位之间进行，即旋转单词。
答案思路3th:
实现翻转单词顺序列的效果：一是如该题先翻转每个单词再翻转整个句子，二是先翻转整个句子再翻转每个单词。两种效果最终一致，而且第二种更容易理解，还能帮助理解第一种。
58.2 左旋转字符串
答案对if (n >= str.length())的处理不对，应该要n%str.length()，再LeftRotateString(str, n%str.length())
1. 滑动窗口的最大值
  PriorityQueue的用法和底层原理
  QQQ PriorityQueue的什么特性让其能成为大顶/小顶堆的实现？？？AAA 因为PriorityQueue的优先级特性，在添加或移除一个元素时，PriorityQueue内部会对存储在数组中的数据位置进行调整以维持优先级特性。
  答案思路：就是利用PriorityQueue这个大（小）顶堆数据结构，第一个for先得到第一个窗口的最大值，第二个for开始往后逐个滑动。
  3rd：一个小结论：插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。没看文章内容。
  QQQ PriorityQueue对象的时间复杂度是不是不考虑，算法题是不是都不考虑封装了数据结构的java对象自身操作的时间复杂度，只考虑解题步骤中开发者写的时间复杂度？？？
1. n 个骰子的点数
  答案一思路：
  dp[][]是这样的二维数组
  dp[][]二维数组存放的是i个骰子置地后点数和是j的情形数量。
  第一个for计算出1个骰子置地后是1、是2、是3、是4、是5、是6的情形数。
  face是一个骰子最大点数。
  dp[i][j] += dp[i - 1][j - k]比如dp[2][2] = dp[1][1] + dp[1][0]，能这样写是因为2个骰子出现2点时，其中1个骰子则是1点或0点。
  动态规划：从这解法我的理解是从最简单的情况开始计算，后面的结果的计算会依据前面计算出来的结果。当然每一步结果的保存就需要额外的对象来存储，比如本题的二维数组。
  totalNum = Math.pow(6, n)表示n个骰子置地后情形数量为6的n次幂。
  QQQ 这个思路的空间复杂度“O(N²)”应该怎么理解/计算？？？所有算法题的算法空间复杂度和时间复杂度应该怎么计算出来？？？AAA 二维数组的规模大约是n6n即6n^2
  答案一思路3rd： dp[][]二维数组存放的是i个骰子置地后点数和是j的排列数（非组合数）。
  第二个for：按照2》3》4》…i》…》n个骰子依次进行遍历
  第三个for：按照i个骰子掷出i》i+1》i+2》…j…》6*n的情形依次进行遍历。
  第四个for：按照j个骰子最后一个掷出1》2》3》……》min(6,j)的情形依次进行遍历。
  答案二思路：
  在答案一的思路基础上缩小了算法空间，因为dp[][]二维数组在动态规划到过程中和最后都只关注当前最新/大行的数据，而当前行的数据又只依赖于上一行的数据，所以该思路就dp[][]二维数组缩小成dp[2][]二维数组，每计算好一行数据后，然后清空另一行数据，用另一行数据计算存放新数据。
  不明白为啥叫“旋转”，flag就是这两行的行标0和1，不断切换。
  答案一思路第二遍： for (int i = 2; i <= n; i++)//i表示骰子个数或者1个骰子掷数 for (int j = i; j <= pointNum; j++)//j表示i个骰子掷出的总点数 for (int k = 1; k <= face && k <= j; k++) dp[i][j] += dp[i - 1][j - k];//i个骰子掷出j点的次数 = i-1个骰子掷出1点、2点、3点、...j-1点的次数和。
  Map.Entry<Integer, Double>这个对象就是Map中的一个元素，包含了kv两个信息的一种对象。
1. 扑克牌顺子 Arrays.sort()利用快排时平均时间复杂度O(nlogn)，利用归并时间复杂度是O(nlogn)并且空间复杂度是O(n)。QQQ 算法题要不要考虑比如Arrays.sort(nums);这种Java自身方法复杂度？？？
1. 圆圈中最后剩下的数
  “圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余”。QQQ 怎么理解？？？AAA这篇博客写了推导过程，基于规律推导出来：https://blog.csdn.net/wusuopubupt/article/details/18214999
  3rd：递归与动态规划抽象新理解：都可以解决大问题能转化为子问题求解的情况，递归是从大问题进入一层一层进入最小子问题然后递归返回，动态规划是从最小子问题进入一步一步递进求出大问题。
1. 求 1+2+3+...+n
  “使用递归解法最重要的是指定返回条件”QQQ 这是递归算法的通点吗？？？
  答案思路：巧妙利用的条件与即&&的短路原则即第一个条件为false时则不会执行第二个条件，从而代替了题目不允许使用的条件关键字if else。
1. 不用加减乘除做加法
  答案思路：
  “a ^/异或 b 表示没有考虑进位的情况下两数的和”：这里的进位是二进制下的进位，比如12 + 19就是
  00001100
  ^00010011
  =00011111
  “(a & b) << 1 就是进位”：a & b是取得需要向前进位的原位，因为&只在1 & 1有结果1。然后再左移1位就得到进位后的结果位。
  代码中b == 0这个条件就类似于十进制两数相加时，如果发生进位就向前进一位，如果进一位后又发生进位就继续向前直至不发生进位。
  答案思路3rd:
  因为是每次递归都是基于上次两数的进位，所以自然而然“进位右边的 0 会慢慢增多”，即1会慢慢逐位往前进。因为算进位包含了a&b运算，当进位超过a的最左非0位，就没有进位了即没有1了，所以“最后进位会变为 0”，即(a & b) << 1最终肯定会变成000...。
1. 构建乘积数组
  答案思路：第一个for，利用product每个B[i]分别累乘了A数组中小于当前索引的所有数。第二个for，利用product每个B[i]分别累乘了A数组中大于当前索引的所有数。
1. 把字符串转换成整数
  答案思路：char类型即字符类型，c < '0' || c > '9'表示是非合法数字字符，c - '0'得到c字符的数值（直接用c参与数学计算或者用(int)c时，c的值是该阿拉伯数字符号在ascii表中数值非本身值）， ret = ret * 10 + (c - '0')是因为从左往右遍历字符串，所以逐个累乘10。
1. 树中两个节点的最低公共祖先
  答案思路：第一遍【普通二叉树】
  “left == null ? right : right == null ? left : root;”这代码就是“在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先”的思路的实现。
  “left == null ? right : right == null ? left : root;”当返回left或right的值时，是在root的左右某边子树中找到了p或q，或者是root就是p或q；当返回root的值时，是在root的左右子树分别找到了p和q。
  第二遍【普通二叉树】
  QQQ 不知道作者怎么想出思路？？？3rd：难在两种递归结束条件，第一种是节点可以是自己的祖先节点；第二个是当两个节点分列在某节点左右两侧时，某节点必然就是最低祖先节点。证明：可以反向思考，假如发现了某个祖先节点后继续找第二个祖先节点时，往上找或往下找。往上找只能往左或往右，这样就导致两个节点必然成为一侧。往下找只能往左或往右，但无论往那边，都会失去两个节点中一个。假设不成立。