1.剑指 Offer 14- II. 剪绳子 II，这道题目关于求余算法，还没有掌握。
2.剑指 Offer 16. 数值的整数次方 这道题目前也没有很好掌握
2020.11.10学习：这道题用递归比较好理解，代码如下：
关键的问题是当 n == Integer.MIN_VALUE时，-n == n，即 -1 * -2,147,483,648 == 2,147,483,648 == -2,147,483,648，为什么会这样呢，因为int(Integer)类型的取值范围是
\[{\rm{[ - }}{{\rm{2}}^{{\rm{31}}}},{2^{31}} - 1] = [ - 2,147,483,648,2,147,483,647]\]
很明显，-n此时比Integer.MAX_VALUE还要大一，所以数据溢出了，-n==n。解决方法是手动提取出一个1/x，然后让指数部分-1,即可。
class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
if (n < 0) return 1 / x * myPow(1 / x, -n - 1);
return ((n & 1) == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
}
}
3.剑指 Offer 17. 打印从1到最大的n位数
这道题目虽然是简单题目，但是如果稍微改变条件，即不限制每位数字都在int范围内，即出现大数的情况，就不是那么简单能够写出来的了。大数问题要用String.
放一个题解：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
2020.11.11学习：说是用到了全排列的算法，主要还是要理解这里用到的递归，并且递归外面套一层循环。
还要注意对001，002，011，这类高位是0的数值的截断细节，用到了nine和start辅助变量来实现。
贴个代码：
今天学习中，我对nine--那里还有一点没理清，回溯
class Solution {
int[] res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public int[] printNumbers(int n) {
this.n = n;
res = new int[(int)Math.pow(10, n) - 1];
num = new char[n];
start = n - 1;
dfs(0);
return res;
}
void dfs(int x) {
if(x == n) {
String s = String.valueOf(num).substring(start);
if(!s.equals("0")) res[count++] = Integer.parseInt(s);
if(n - start == nine) start--;
return;
}
for(char i : loop) {
if(i == '9') nine++;
num[x] = i;
dfs(x + 1);
}
nine--;
}
}
4.剑指 Offer 27. 二叉树的镜像
2020/11/14 18:30
这道题目虽然标题为简单，虽然我目前会做了（然而并没有百分百掌握理解），但是这道题目我觉得很有意义，值得特别记录一下。
对于二叉树的题目，目前为止我认为有有两种形式的方法很适合，一是递归（二叉树的前后中遍历）；二是队列（层序遍历）
而这道题目，考察的正是二叉树的遍历，前后中，层序。直接上代码吧
后续遍历，从下至上，从左至右，交换：
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return root;
recur(root);
return root;
}
private void recur(TreeNode root) {
//后续遍历，即在最底层开始交换，并逐渐向上走
if (root == null) return;
recur(root.left);
recur(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
采用队列的方式，从上至下，从左向右交换：
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
LinkedList<TreeNode> queue = new LinkedList<>() {{add(root);}};
while (!queue.isEmpty()) {
TreeNode ans = queue.removeFirst();
if (ans.left != null) queue.addLast(ans.left);
if (ans.right != null) queue.addLast(ans.right);
TreeNode tmp = ans.left;
ans.left = ans.right;
ans.right = tmp;
}
return root;
}
}
前序遍历，从上向下，从左至右，交换：
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
中序遍历交换应该不行，递归之后没有变化，因为左边的交换之后，右边又会交换一遍，等于没交换。
5.剑指 Offer 30. 包含min函数的栈
这道题目需要注意的一点就是，Integer类型，判断是 == 和 equals()的区别
像Integer类型，当需要判断A和B的数值是否相等时，最好使用A.equals(B)，因为这个方法是纯粹比较数值大小的，源码如下：
public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
}
具体可以看下面这篇博客：
https://cloud.tencent.com/developer/article/1688593
6.剑指 Offer 31. 栈的压入、弹出序列
模拟栈的入栈和出栈即可。
7.剑指 Offer 33. 二叉搜索树的后序遍历序列
这道题我知道大致的思路，但是2020/11/18号来做，竟然提交老有错误，值得好好记录一番
class Solution {
boolean ans = true;
public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length < 1) return ans;
recur(postorder, 0, postorder.length - 1);
return ans;
}
private void recur(int[] postorder, int low, int high) {
if (low >= high) return;
//对于index的情况,针对[5,2,-17,-11,25]的情形，i <= high 才行
int rootVal = postorder[high], index = -1;
for (int i = 0; i <= high; i++) {
if (postorder[i] >= rootVal) {
index = i;
break;
}
}
for (int i = index + 1; i < high; i++) {
if (postorder[i] < rootVal) {
ans = false;
return;
}
}
recur(postorder, low, index - 1);
recur(postorder, index, high - 1);
}
}
8.剑指 Offer 34. 二叉树中和为某一值的路径
2020/11/18，靠，回溯又不太熟了。其实大体思路还是对的，但是没注意到list的回溯时，改变list种的指，ans中list对应的值也对应改变了。
在ans添加满足答案的list前，要使用ArrayList的构造函数(Collections c)新建一个ArrayList，否则在后续的改动中，ans中的list的值也会发生变化。
另外可以使用(sum + root.val)的形式去传值，这样就不用在返回阶段，手动的再去sum - root.val的值了。
另外使用LinkedList插入删除数据比ArrayList快很多，LInkedlist既可以当作List，也可以当作Queue，Deque
class Solution {
List<List<Integer>> ans = new ArrayList<>();;
int target;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) return ans;
ans = new ArrayList<>();
target = sum;
LinkedList<Integer> list = new LinkedList<>();
recur(root, list, 0);
return ans;
}
private void recur(TreeNode root, LinkedList<Integer> list, int sum) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (sum + root.val == target) {
list.add(root.val);
ans.add(new ArrayList<>(list));
list.removeLast();
}
return;
}
list.add(root.val);
recur(root.left, list, sum + root.val);
recur(root.right, list, sum + root.val);
list.removeLast();
}
}
9.剑指 Offer 36. 二叉搜索树与双向链表
又是大体知道思路，但是实现细节上出了问题。
2020/11/19，我的想法是利用后续遍历，修改左子节点的右指向，修改右子节点的左指向。同时用类变量记录第一个节点和最后一个节点，在主程序中实现头结点和尾节点的连接。
这种代码如下：
class Solution {
Node pre, tail;
int count;
public Node treeToDoublyList(Node root) {
if (root == null) return null;
recur(root);
pre.left = tail;
tail.right = pre;
return pre;
}
private void recur(Node root) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (count++ == 0) pre = root;
return;
}
recur(root.left);
recur(root.right);
if (root.left != null) root.left.right = root;
if (root.right != null) {
root.right.left = root;
tail = root.right;
}
}
}
但是对于下面这颗树，我的输出是，漏了节点3，不知道是哪出了问题！我初步估计是在tail的赋值过程。
2020/11/20 其实一开始我的大方向变了，跟tail的赋值过程没有关系。
这道题目是关于二叉搜索树的升序，所以应该用中序遍历，因为二叉搜索树的中序遍历就是节点值的升序排列。
巧妙的利用了head指针和pre指针，来构建双向链表以及头结点和尾节点的捕捉，便于在主函数中实现头尾相连。具体上代码吧，非常巧妙
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if (root == null) return null;
recur(root);
head.left = pre;
pre.right = head;
return head;
}
private void recur(Node root) {
if (root == null) return;
recur(root.left);
if (pre != null) pre.right = root;
else head = root;
root.left = pre;
pre = root;
recur(root.right);
}
}
10剑指 Offer 37. 序列化二叉树
2020/11/20 这道题目到没什么难点，用好层序遍历和队列即可。
新收获：StringBuilder()的对象sb.append(root.val + ",") ;时应该改写成sb.append(root.val).append(",");可大幅减少耗时
11剑指 Offer 38. 字符串的排列
2020/11/21 这种递归的题我目前愿称之为递归最难题，似乎是排列组合？有时间深入探讨一下这种类型的题目，和前面3.剑指 Offer 17. 打印从1到最大的n位数的算法有点像。还是多敲代码多理解吧
直接放代码：
class Solution {
List<String> ans;
char[] tmp;
public String[] permutation(String s) {
if (s == null || s.length() < 1) return new String[0];
//这里可以思考一下ArrayList和LinkedList性能区别
ans = new LinkedList<>();
tmp = s.toCharArray();
dfs(0);
return ans.toArray(new String[ans.size()]);
}
private void dfs(int index) {
if (index == tmp.length - 1) {
ans.add(new String(tmp));
return;
}
Set<Character> set = new HashSet<>();
for (int i = index; i < tmp.length; i++) {
if (set.contains(tmp[i])) continue;
set.add(tmp[i]);
swap(i, index);
dfs(index + 1);
swap(index, i);
}
}
private void swap(int i, int j) {
char t = tmp[i];
tmp[i] = tmp[j];
tmp[j] = t;
}
}
12剑指 Offer 42. 连续子数组的最大和
这道题目用到了滑动窗口，我理解的滑动窗口，就是利用上前面窗口计算过的信息进行后续计算，避免了重复计算，提高了效率。
思路：定一个滑动窗口，如果窗口内的值<=0时，就把滑动窗口重置，并把最左端放到当前计算数的右边一位。
Tips：通过比较求最大/最小值时，一般设定ans初始值为Integer.MIN_VALUE/Integer.MAX_VALUE 比较好。
代码如下：
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE, i = 0, j = 0, tmp = 0;
while (j < nums.length) {
tmp += nums[j++];
ans = Math.max(ans, tmp);
if (tmp <= 0) {
i = j;
tmp = 0;
}
}
return ans;
}
}
也可以用动态规划，代码如下：
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int ans = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = nums[i];
dp[i] += Math.max(dp[i - 1], 0);
ans = Math.max(dp[i], ans);
}
return ans;
}
}
13 剑指 Offer 46. 把数字翻译成字符串
2020/11/27 不会
动态规划
14 剑指 Offer 48. 最长不含重复字符的子字符串
2020/11/28 不会
15 剑指 Offer 53 - II. 0～n-1中缺失的数字
2020/12/1 不会 尝试先找到一个中间数字，然后向两端扩散，若数字不连续，则返回当前值+1的数值，但是对于特殊情况，例如[0]应返回1，[1]应该返回0，还不能得出正确结果。面试题53 - II. 0～n-1 中缺失的数字（二分法，清晰图解） - 0～n-1中缺失的数字 - 力扣（LeetCode） (leetcode-cn.com)
16 剑指 Offer 57 - II. 和为s的连续正数序列
这道题目用到了滑动窗口的方法，知道了方法，重要的是具体的代码实现。
此题还有一个非常重要知识点，如何将一个List<List<Integer>>快速转换成一个int[][]数组
2020/12/5 我利用了List<List<Integer>>，还有一个内部的LinkedList来记录数据，最后能返回正确结果，但是还不知道怎么转换成二维数组，代码如下：
public List<List<Integer>> findContinuousSequence(int target) {
List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> tmp = new LinkedList<>();
int low = 1, high = 1, sum = 1;
tmp.add(1);
while (high <= (target + 1) / 2) {
if (sum < target) {
high++;
sum += high;
tmp.add(high);
} else if (sum > target) {
tmp.removeFirst();
sum -= low;
low++;
} else {
ans.add(new ArrayList<>(tmp));
low++;
high++;
tmp.add(high);
sum += high - tmp.removeFirst();
}
}
return ans;
}
更简便的代码如下所示：可以看出，List<int[]>可以非常简单的利用toArray()方法转化为二维数组。
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> vec = new ArrayList<int[]>();
for (int l = 1, r = 2; l < r;) {
int sum = (l + r) * (r - l + 1) / 2;
if (sum == target) {
int[] res = new int[r - l + 1];
for (int i = l; i <= r; ++i) {
res[i - l] = i;
}
vec.add(res);
l++;
} else if (sum < target) {
r++;
} else {
l++;
}
}
return vec.toArray(new int[vec.size()][]);
}
}
2020/12/6 贴一个我自己写的，与上面的代码，判断条件有所不同
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> ans = new ArrayList<>();
if (target < 3) return new int[0][0];
int low = 1, high = 2;
while (low < high && high <= (target + 1) / 2) {
int sum = (low + high) * (high + 1 - low) / 2;
if (sum == target) {
int[] tmp = new int[high + 1 - low];
for (int i = low; i <= high; i++) {
tmp[i - low] = i;
}
ans.add(tmp);
low++;
high++;
} else if (sum < target) {
high++;
} else {
low++;
}
}
return ans.toArray(new int[ans.size()][]);
}
}
17 剑指 Offer 60. n个骰子的点数
2020/12/9 这道题目我知道要用动态规划做，关键点在于求出每个点数对应出现的频率。这次我用的是一维数组，但是出错了，emm代码已经被我覆盖了。
我的思路就是，
但是这种思路只能正确求解n = 2····
所以说动态规划，还是要和前面的dp数值联系起来，这种思路，与前面的dp，没有联系。
正确的思路代码应该是这样
public double[] twoSum(int n) {
//先确定n个筛子，有多少种可能性 n ~ 6n，所以个数为5n + 1
int[][] dp = new int[n + 1][6 * n + 1];//我喜欢用直接的下标来表示，所以需要+1
for (int i = 1; i <= 6; i++) dp[1][i] = 1;//给一个筛子的情况初始化
for (int i = 2; i <= n; i++) {
for (int j = i; j <= i * 6; j++) {
int check = j > 6 ? 6 : j - 1;
for (int k = 1; k <= check; k++) {
dp[i][j] += dp[i - 1][j - k];
}
}
}
double[] ans = new double[5 * n + 1];
double fen_mu = Math.pow(6, n);
for (int i = n; i <= 6 * n; i++) {
ans[i - n] = dp[n][i] / fen_mu;
}
return ans;
}