https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
题意
这一题与116的区别就在于这一题不是满二叉树，所以下一行的起点不是第一个节点的左结点，因此不能用116中的解法。最笨的办法就是用116的方法先层次遍历将每一个结点的next指向下一个遍历到的，然后再右序遍历将最右边结点的next清空，时间复杂度为O(2n)，空间复杂度为O(n)，这样也能AC😂
class Solution {
//上一个遍历的元素
Node last;
public Node c...
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
这题一开始想着使用按层遍历，但是不知道怎么遍历☹️，经查阅后得知使用LinkedList实现。
给root的next增加一个特殊标签，当取到next为标签时，说明这个元素是每行第一个，并给它的右结点增加标签，因为右结点是下一层第一个遍历的(满二叉树才行)
AC代码
class Solution {
//上一个遍历的元素
Node last;
//第一行起始结点的特殊标签
Node mark = new Node();
...
https://leetcode.com/problems/distinct-subsequences/
开始时候想着递归做，后来想想肯定会超时，就放弃了。昨天刚做了八皇后问题，感觉跟这个比较像，先定确定一个位置，再继续向后查找，直到找到一个解。找到解后再回溯，写出来发现还是超时😞
先贴下超时的解
class Solution {
public int numDistinct(String s, String t) {
int count = 0;
//标记s和t的查找位置
int sIndex = 0, tIndex = 0;
L...
https://leetcode.com/problems/recover-binary-search-tree/
二叉搜索树中序遍历(In-Order Traversal)必定有序
先来看一个naive的方法，即使用O(n)的空间复杂度应该怎么解决．我们可以开一个数组，中序遍历树，并将其依次保存在数组中．如果是一个正常的二叉搜索树将会是完全有序的．然而当交换了其中两个结点之后就会出现两个结点出现在错误的位置．举个栗子：[1, 2, 3, 4, 5, 6]，这是一个正常的二叉搜索数的序列，当交换了其中两个结点之后变成了[1, 5, 3, 4, 2, 6]．那么如何找到这两个交换的结...
https://leetcode.com/problems/n-queens/
经典N皇后问题，先背一个解法吧，具体见注释
class Solution {
int q[];
List<List<String>> results = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
int r = 0, c = 0;
q = new int[n];
for (int i = 0; i < ...
https://leetcode.com/problems/edit-distance/
这一题没做出来，参考的别人的答案😞
使用dis[i][j]记录匹配到i,j位置里的最短距离
边界情况dis[0][i]和dis[0][j]，即words1, words2一方为空串，可知距离为另一方长度
当words[i]==words[j]， 则dis[i][j]=dis[i-1][j-1]
当words[i]!=words[j-1]，则有下面三种情况，取最小值
words1插入，dis[i][j]=dis[i][j-1]+1
words1删除，dis[i][j]=dis[i-1][j]+1
...
https://leetcode.com/problems/wildcard-matching/
前几天做https://leetcode.com/problems/interleaving-string/的时候，开始用的递归，在最后一个测试用例时TLF。学习别人思路时看到一句话，所以字符串匹配的都用动态规划，要不然肯定TLF，很有道理的样子。因此这题一开始就没打算用递归。
以”adceb”和”*a*b”为例讲下思路
a
b
c
e
b
*
T
T
T
T
T
T
a
F
T
F
F
F
F
*
F
T
T
T
T
T
b
F
F
F
T
F
T
...
https://leetcode.com/problems/trapping-rain-water/
开始的想法是从i往后找，直到找到第一个不比height[i]小的数的位置j，计算i-j之间的区域，然后继续从j向后找。但是这样会导致递增里无法计算面积，因此方法变成从i向两找不小于height[i]的位置，但是...
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick StartCreate a new post$ hexo new "My New Post"
More info: Writing
Run server$ hexo se...
