Home

题目链接 这个题考虑用dfs或回溯法。一共有4个数和3个运算操作，因此可能性非常有限。一共有多少种可能性呢？首先从4个数字中有序地选出2个数字，共有4x3=12种选法，并选择加减乘除4种运算之一，得到的结果取代选出的两个数字，剩下3个数字。然后在剩下的3个数字中有序地选出2个数字，共有3x2=6种选法，并选择4种运算操作之一，用得到的结果取代选出的两个数字，剩下2个数字。最后剩下2个数字，有2种不同的顺序，并选择4中运算操作之一。因此，一共有12x4x6x4x2x4=9216种不同的可能性。 可以通过回溯的方法遍历所有不同的可能性，具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出2个数字，再选择一种操作，用计算得到的结果取代选出的2个数字，这样列表中的数字就减少了1。重...

题目链接 就这个题也不用多说什么吧。这个算法的时间复杂度是O（logx），x中大概有log10x个数字，空间复杂度是O（N）不知道为什么他们都写O（1），讲道理翻转字符串是要占用空间的，可能是因为不需要额外的吧。 python: class Solution: def reverse(self, x: int) -> int: if x == 0: return 0 str_x = str(x) sign = 1 if str_x[0] == "-": sign = -1 str_x = str_x[1:] reve...

题目链接 就这个题也不用多说什么吧。这个算法的时间复杂度是O（logx），x中大概有log10x个数字，空间复杂度是O（N）不知道为什么他们都写O（1），讲道理翻转字符串是要占用空间的，可能是因为不需要额外的吧。 python: class Solution: def reverse(self, x: int) -> int: if x == 0: return 0 str_x = str(x) sign = 1 if str_x[0] == "-": sign = -1 str_x = str_x[1:] reve...

题目链接 这题是一个bfs，不过稍微复杂一点的是bfs的起始点不止一个而是有很多个源头。其实还是比较好写的，直接参考了官方的代码，因为有几个不常用的小技巧可以讲一下。首先，我之前在枚举方向时一般用一个类似[(0, 1), (0, -1), (1, 0), (-1, 0)]的列表，而在1中的代码中我们直接用一个包含了各个方向改变的元组，并且在生成方向时用了yield而非产生一个列表，这样比较优雅。另外还有在最后判断gird中是否还有新鲜橘子时用的any(1 in row for row in grid)也是我不常用的。 这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。 python: class Solution: def orangesRotting(self...

题目链接 这个题没什么思路，还以为和编辑距离有关系，要先求出每对词的编辑距离然后判断之类的，不过估计这种思路是不可行的或者有比较大的时间复杂度（好像确实）？就看了一下题解，用的是bfs和双向bfs。首先呢我们先考虑去建图。我们注意到有说明是“每个单词的长度相同”并且“字母都是小写”，所以不同于上面讲到的将每两个单词都判断是否他们之间有路径，我们用的方法是，依次从a到z变换一个选定单词中的每个字母然后去判断新生成的单词是否在词典之中，如果是的话就说明这两个单词之间有边，按照这样的思想可以建立起一个无向图。接下来，由于我们要找一条最短的路径，我们要使用bfs来做，当然我们知道dfs也能做只是bfs可以在找到答案的时候马上停止遍历而非像dfs一样有可能遍历所有点。注意，我们在遍历图的时候，...

题目链接 这题是一个bfs，不过稍微复杂一点的是bfs的起始点不止一个而是有很多个源头。其实还是比较好写的，直接参考了官方的代码，因为有几个不常用的小技巧可以讲一下。首先，我之前在枚举方向时一般用一个类似[(0, 1), (0, -1), (1, 0), (-1, 0)]的列表，而在1中的代码中我们直接用一个包含了各个方向改变的元组，并且在生成方向时用了yield而非产生一个列表，这样比较优雅。另外还有在最后判断gird中是否还有新鲜橘子时用的any(1 in row for row in grid)也是我不常用的。 这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。 python: class Solution: def orangesRotting(self...

题目链接 这个题没什么思路，还以为和编辑距离有关系，要先求出每对词的编辑距离然后判断之类的，不过估计这种思路是不可行的或者有比较大的时间复杂度（好像确实）？就看了一下题解，用的是bfs和双向bfs。首先呢我们先考虑去建图。我们注意到有说明是“每个单词的长度相同”并且“字母都是小写”，所以不同于上面讲到的将每两个单词都判断是否他们之间有路径，我们用的方法是，依次从a到z变换一个选定单词中的每个字母然后去判断新生成的单词是否在词典之中，如果是的话就说明这两个单词之间有边，按照这样的思想可以建立起一个无向图。接下来，由于我们要找一条最短的路径，我们要使用bfs来做，当然我们知道dfs也能做只是bfs可以在找到答案的时候马上停止遍历而非像dfs一样有可能遍历所有点。注意，我们在遍历图的时候，...

题目链接 这个题我们考虑用bfs的方法来解决。如何做呢？我们做bfs，上一层level和下一层level之间的关系为：把所有上一层level中的每个元素都拿出来，列举出再删除一个括号后的所有可能情况。（不管删除后是否合法），添加到下一个level中。例如：现在的level是[”())”, “())”]，那么下一层level的元素应该是：1. 对“())”删除一个括号的所有可能为：(),(),((。 2. 对”())”删除一个括号的所有可能为：(),)),()。这六个就是下一个level的全部内容了。但是我们也会发现，就是有重复元素出现的情况，那么我们可以将level中的list换成set就能避免这个重复的发生。至于我们如何检查某个序列是否是一个合法的括号序列，可以维护一个计数器或者用...

题目链接 这个题我们考虑用bfs的方法来解决。如何做呢？我们做bfs，上一层level和下一层level之间的关系为：把所有上一层level中的每个元素都拿出来，列举出再删除一个括号后的所有可能情况。（不管删除后是否合法），添加到下一个level中。例如：现在的level是[”())”, “())”]，那么下一层level的元素应该是：1. 对“())”删除一个括号的所有可能为：(),(),((。 2. 对”())”删除一个括号的所有可能为：(),)),()。这六个就是下一个level的全部内容了。但是我们也会发现，就是有重复元素出现的情况，那么我们可以将level中的list换成set就能避免这个重复的发生。至于我们如何检查某个序列是否是一个合法的括号序列，可以维护一个计数器或者用...

题目链接 对于这个题，暴力解法就不说了。首先讲一下动态规划的方法，如1所示，我们用dp[i]来记录前i个字符中的最长有效括号数。我们可以发现，在遍历s时，只有当前元素为“）”时才有可能更新dp的值，否则保持不变。当遍历到某个元素位“）”时，我们要寻找在它之前的可以刚好与其配对的“（”，目前有两种情况，如果前一个元素是“（”，那么dp[i]的值可以直接加2，如果不是，那么就要考察前一个元素“）”所在的位置的dp值，并找到该“）”对应的最长序列的前一个元素，如果是”（“，我们才能将dp[i]加2，但是此时考虑到如果我们加上被新形成的括号所包含的最长括号序列，我们就要将改值加到dp[i]上。在寻找i所在位置的“）”前一个所对应的“（”要注意，不能使得i小于0，否则会跑到列表的末尾，这样大概...