递归求解该题，对于n个括号的情况，首先返回n-1个括号的所有结果，然后把一个新的括号插入到n-1个括号结果的每个情况中，组成新的情况，这个插入方法为：新的括号插在最前面，插在最后面，插在每一个(的后面。需要注意的是，对于n-1个括号返回的结果，便利每个结果进行新括号插入时，会有几种情况下是重复的，解决该重复问题的方法是使用set自动去重即可。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int整型 # @return string字符串一维数组 # class Solution: def generateParen...

我的解题思路如下：对于n*n的这样一个棋盘，其实N皇后问题可以转化为这样一个问题，给定一个list，[0,1,2,```,n-1]，index代表行，list[i]代表第i行的皇后所在的列，比如list[1]=2,代表第1行的皇后在第2列，皇后的方法其实有n!种，也就是这个list的一个全排列，这种全排列自然而然就解决了皇后不再同一行不再同一列这个约束，但是这种方式暂且无法解决，皇后不再对角线的问题。 对于皇后不能对角线的问题，可以这样来解决，建两个set，第一个set解决皇后不能正对角线的问题，第二个set解决皇后不能负对角线的问题。正对角线的皇后有一个特征是所在列号减所在行号都相等，比如对...

还是dp，只是相较于没有首末次约束的情况下多了一个思维过程而已。由于不能同时偷首末家，因此一共有三种可能：偷最多的钱要么是1.偷了首家，不偷末家，要么是2.偷了末家，不偷首家，要么是3.首末家都没偷。因此可以做两个dp向量，一个dp不包括首家，一个dp不包括末家，最后返回两者较大者即可。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def rob(self , nums) -> int: # writ...

本题使用层序遍历，如果遇到none的结点，就将标记变量标记为1，然后继续层序遍历，若后面没有结点了，就是完全二叉树，如果后面还有结点就不是。 主要就是考察层序遍历，之前我写的层序遍历都很复杂，把每一层都存起来才行，这次用了queue的方法写了一遍，感觉不错。 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param ...

看了题解我的方法最麻烦了，先说下题解的好方法： 中序遍历，序列升序则是二叉搜索树； 2.递归法，遍历第一个节点，判断该结点是否在指定范围内，然后遍历该结点的左右子节点，遍历左结点时，范围是父节点范围的左边界和父节点值作为有边界，依次类推。 3.我实现的方法：递归法，判断左右子树是不是二叉搜索树，如果不是，直接返回false，都是的话取出左子树最大值和右子树最小值，看左子树最大值是不是比父节点小，右子树最小值是不是比父节点大。 class TreeNode: def __init__(self, x): self.val = x self.left =...

最简单的方法就是排序，返回第n-k大的即可，此外可以使用最大堆，这些复杂度都是O(nlogn)的。 我在代码里自己写了一遍quicksort，mergesort，用python的sort试了一下，用最大堆试了一下，发现单纯用quicksort是不能行的，其他都是可以通过的。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param a int整型一维数组 # @param n int整型 # @param K int整型 # @return int整型 # import heapq class Solution: def fin...

很简单的dp，设定dp[i]为偷窃到第i家为止不被发现的做多的钱，状态转移方程如下： dp[i]=max{dp[i−1],nums[i]+dp[i+2]}dp[i]=max\{dp[i-1],nums[i]+dp[i+2] \}dp[i]=max{dp[i−1],nums[i]+dp[i+2]} 其实就是每次有两种可能性，偷第i家伙不偷第i家，偷的话就肯定不能偷i-1家了，因此是dp[i-2]+nums[i]，不偷的话最大就是dp[i-1]。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @re...

该题最关键的是要想到逆序对的数量和对数组进行排序，调换元素位置的数量是一致的。举个例子[2,1,3,5,4]进行排序时，首先1,2要换一下位置，然后5,4要换一下位置，所以调换位置的数量是2，逆序数也是2.也就是说逆序对数量其实就是排序过程中调换位置的数量。所以只需要记录下排序过程中的位置调换数量就行了，排序算法刚好是O(nlogn)的，所以满足要求。 代码中我使用的归并排序。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param data int整型一维数组 # @return int整型 # class Solution: ...

用dp来解，设dp[i]为以第i个字符为结尾的最长匹配括号序列。 状态转移方程为： if s[i+1]+s[i]==′()′,dp[i+1]=dp[i−2]+2if \ s[i+1]+s[i]=='()',dp[i+1]=dp[i-2]+2if s[i+1]+s[i]==′()′,dp[i+1]=dp[i−2]+2 （1） if s[i+1]+s[i]!=′()′ and dp[i]=0,dp[i+1]=0if \ s[i+1]+s[i]!='()' \ and \ dp[i]=0,dp[i+1]=0if s[i+1]+s[i]!=′...

用了两种方法求解。 第一种方法是非常容易求解的，新建一个list存放所有的listnode，然后用sorted()函数进行排序就行了，其中key取的是listnode的val，然后将排序好的listnode按照顺序连接起来就行。 第二种方法是使用归并排序，首先找到待排序的listnode的中间结点，然后将listnode从中间断开，变成两个listnode，对这两个sub listnode分别排序，排好了之后返回回来，得到两个有序的listnode，在对这两个有序的listnode进行merge，这个merge在前面写过好多次了，就是new两个指针，分别指向开头，然后cur不断指向小的那个no...

做了2个小时终于解出来了，使用dp来解，设dp[i][j]为str[0:i]和pattern[0:j]是否可以匹配，存放true或者false。 接着写状态转移方程： dp[i][j]=dp[i−1][j−1],if str[i−1]=pattern[j−1]dp[i][j]=dp[i-1][j-1],if \ str[i-1]=pattern[j-1] dp[i][j]=dp[i−1][j−1],if str[i−1]=pattern[j−1] dp[i][j]=false,if str[i−1]!=pattern[j−1] and patt...

有点难，详细的写在这里面了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str1 string字符串 # @param str2 string字符串 # @return int整型 # class Solution: def editDistance(self , str1: str, str2: str) -> int: # write code here # 初始化dp矩阵 dp = [[0]*(len(str2)+1) for _ in range(len...

用了两种方法求解： 转化成数字在求解，先分别遍历两个链表得到两个链表的数字，然后数字求和，求和得到结果后把结果变成listnode就行了。时间复杂度是O(n)，空间复杂度是O(n)，但是没有通过，报错是时间超时，应该是python语言导致的，因此使用了第二种方法。 把head1和head2两个链表的每个node分别放在两个list里面去，然后不断的pop，pop出来的是同一位的最低位数字，直接相加，若超过10，则记录jinwei=1，然后把链表1中的值改为pop出来的两个值%10。需要注意的是当比如list2 pop完了，那么我们只需要去pop list1就行了，然后加上jinwei，...

有点难，一直在想怎么用dp解，其实根本不是用dp解的，大意了。 使用递归求解该题，递归函数传进去三个参数，第一个是s：剩余字符串，第二个是num，已经有的ip数字的数量，第三个是ip，目前已经组成好前面部分的ip，如255.255.255。然后如果构成完整的ip了，就存在self.result = []里就行了。 递归思路是我先取出第一个数字，第一个数字有多种可能，1位，两位，3位都有可能，然后取出第一个位的数字后，递归是找第二位数字，依次类推，如果能找到第4位数字，则是一个成功的ip，存起来就行了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # ...