Leetcode: 89-100解题笔记

~~什么解题笔记，完全是抄答案笔记~~

~~我好菜啊~~

~~啊啊啊啊啊啊啊啊啊~~

89. 格雷编码

给定数字$n$，把$0\sim 2^n-1$构成一个全排列。要求全排列相邻数字两两之间的二进制表示有且只有一位不同。

比如，给定$n=2$，则要获得一个$0,1,2,3$的全排列，答案$[0,1,3,2]$符合要求，因为$00,01,11,10$符合相邻二进制只有一位不同的情况（这也是题目叫做 格雷码 的原因）

~~网上的答案都说~~ 这就是一道找规律的题。对于一个$n-1$位的格雷码序列$S_{n-1}$，可以按如下规律生成$n$位的格雷码序列$S_n$（从二进制角度看）：

$S_n$的前$2^{n-1}$个数字是$S_{n-1}$加上前缀0
$S_n$的后$2^{n-1}$个数字是$S_{n-1}$加上前缀1之后倒序

网上的代码大多从二进制角度解题，其实可以直接从十进制角度来考虑：

$S_n$的前$2^{n-1}$个数字就等于$S_{n-1}$（因为在二进制角度加上前缀0没有任何影响）
$S_n$的后$2^{n-1}$个数字是$S_{n-1}$十进制数字的倒序加上$2^{n-1}$

这样只需要维护一个result数组，每当n增加1，用规则2扩展result的后半部分就可以了。

90. 子集II

给定一个整数数组，给出这个数组所有可能的子集，注意 数组中可能存在相同的元素 但是 解集中不能包含相同的解集 。

先对数组做一个排序，这样方便找到整个数组中重复的数字（因为都排在一起了）。

随后使用递归找到所有的情况。

这个递归的 入参 设置成别名 & 类型，也就是说不需要每次递归都对递归内容创建新的参数。
扩展新的元素时候，对 元素数相同的子集 需要检验放进去的数字是不是一样的，如果是就别放进去了。
整个递归函数的参数传递以及边界条件的设置是我要学习的地方。

下面专门贴上递归部分的代码：

// 传入参数：当前的子集，整个数组元素（排过序的），当前待添加元素在数组中的下标
void dfs(vector<int>&temp, vector<int>& nums, int index){
    res.push_back(temp);
    
    for(int i=index;i<nums.size();i++){
        if(i > index && nums[i] == nums[i-1]) continue;
        temp.push_back(nums[i]);
        dfs(temp, nums, i+1);
        temp.pop_back();
    }
    return;
}

91. 解码方法

说字母$A\sim Z$能够分别被编码成$1\sim26$，那么给一个数字构成的非空字符串，问能解码的方法数有多少个？

~~网上说~~ 这其实是个动态规划的问题，假设已经知道了前$i$个字符串能够解码的方法数$\mathrm{dp[i]}$，现在要求$i+1$，需要考虑下面的情况：

新字符与前一个字符能否构成一个有解码意义的数字。
如果具备解码意义，当前字符能够独立构成一个具备解码意义的数字（说的就是你！字符0！）

具体而言，对于一个新加入的字符$i+1$，我们结合前一个已经知道的字符$i$构成一个数字$n$，动态规划的递推方程是这样的：

如果$n>26$，说明当前字符与前一个字符不能构成解码的意义，此时：

如果当前字符为0，则当前字符串已经无法进行解码——此时实际$n=30/40/…/90$。
如果当前字符不为0，则当前字符能够单独成为一个解码后的字母，此时$dp[i+1]=dp[i]$，因为新到来的字符无法产生一种新的解码方式——此时$n>26且n\mathrm{mod}\neq0$。

下面的所有情况中，都保证了$n\leq26$，但还有其它情况需要考虑：

如果字符$i=0$，说明当前字符无法与字符$i$构成一个可解码的字符：

如果当前字符为0，则字符串$n=00$没有意义，当前字符串已经无法进行解码。
如果当前字符不为0，则当前字符能够单独成为一个解码后的字母，此时$dp[i+1]=dp[i]$——这种情况下，实际的$1\leq n\leq 9$。
如果字符$i\neq0$，则还有两种情况需要考虑：

如果当前字符为0，则当前字符不能单独进行解码（因为字符0没有意义），但是能配合字符$i$进行解码，所以没有增加解码方式，$dp[i+1]=dp[i-1]$——此时$n=10/20$
如果当前字符不为0，则当前字符能够配合上一个字符进行解码，此外自己也具备解码意义，所以$dp[i+1]=dp[i-1]+dp[i]$——$n=11\sim19/21\sim26$

92. 反转链表

不会做，感觉自己对链表系列的题目都不怎么熟练，等针对性练习后再来补全。

93. 复原IP地址

判断一个字符串是否能被复原成一个IP地址。首先从数字的位数初步判断，然后在三个不同点插入三个标记，将字符串分割成四个部分，然后判断这四个部分是否都在$[0,255]$之间就可以了。

94. 二叉树的中序遍历

题目本身很简单，但是附加部分有一点值得仔细思考一下：如果不用递归方式，而是用迭代的方式来求，怎么求呢？

简单说一下：就是 栈 。

具体地，对于一个二叉树，如果要求它的中序遍历（也就是’左中右’），可以对于一棵树，分别把它的右子结点、自身、左子节点压栈；每次从栈中弹出一个元素：如果这个元素是第一次被压栈，并且还有左右子节点，迭代地继续压栈，否则就把它输出。如果这个元素是第二次压栈，那么这一次它仅仅只是输出，不再继续入栈。

为了实现判断一个节点是第一次入栈还是第二次入栈，我们需要定义一个结构体：

struct inorderNode{
    TreeNode *root;
    bool scaned;
}

95&96. 不同的二叉搜索树

同样占坑，等自己回头补完后再来补全。

97. 交错字符串

难题先搁置

98. 验证二叉搜索树

要判断一棵树是否是有效的二叉搜索树。一棵二叉搜索树具有如下的特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题很简单，对树进行中序遍历，如果遍历的节点元素序列严格递增，则该树是一棵二叉搜索树，否则就不是。

99. 恢复二叉搜索树

一个二叉搜索树里面有两个节点被人为交换了，所以它已经不再是一棵二叉搜索树了，问如何把这棵树恢复回去。

首先我们还是进行中序遍历。中序遍历之后对于获得的结点值序列，存在两种情况：

序列中只存在一个逆序对，如：$1,2,3,5,4,6,7,8$。
序列中存在两个逆序对，如：$1,2,6,4,5,3,7,8$。

对于前一种情况，我们可以知道就是逆序对的两个元素进行了互换；而后面一种情况，就是 第一个逆序对的前面那个元素 ，与 第二个逆序对的后面那个元素 进行了交换。

找到这两个元素值之后，接下来我们重新扫描一遍树，找到值为这两个元素的两个节点，然后把这两个节点中的元素值进行交换就可以了。 ~~刚开始做的时候我还傻乎乎的想把两个节点的链接关系也给换掉，或许是受到链表系列习题的荼毒太深了吧🤦‍~~

100. 相同的树

判断两棵树是否相同。

这个很简单，两种实现方式：

因为树的前序+中序/中序+后序遍历能够唯一确定一棵树，我们只需要给出两棵树的四个遍历结果，然后比较是否相同就可以了。
使用逐个比较的方式依次比较树的每个节点值以及结构是否相同。