Home

题目链接 最近在复习并查集，所以做了下这个题，这个题用bfs或dfs也是能做的，不过这里只讲一讲quick-union方法。显然，对于各个城市，我们用union函数将有直接或者间接联系的两个城市连接起来，前面这部分我倒是写对了，只是在计算省份数量多时候没有彻底搞清楚，要知道UF这个字典里存的是其父节点而非最祖先的根节点，因此在计算连通分量的时候，应该计算对于所有UF里的键值对键和值想等的情况。这个算法的时间复杂度是O（N^2logN），空间复杂度是O（N）。注意目前并没有使用按秩排序，而2是在union函数中使用了按秩排序的。 python: class Solution: def findCircleNum1(self, isConnected: List[List[i...

题目链接 对于这个问题，印象中是用快慢指针的方法去判断有无环，但是具体怎么做已经记不清楚了。我看了一下官方题解，里面介绍了两种方法，把它们记录如下。 第一个方法是用哈希集合检测循环。我们先举几个例子，我们从7开始，下一个数是49，然后下一个数字是97，我们可以不断重复该过程，直到我们得到1。因为我们得到了1，我们知道了7是一个快乐数，函数返回true。而对于另外一个例子116，我们分别得到38，73，58，并且从58开始一个“58，89，145，42，20，4，16，37，58”的循环。所以对于116，函数会返回false。根据我们的推测，我们猜测会有以下三种可能。1.最终会得到1。2.最终会进入循环。3.值会越来越大，最后接近无穷大。第三种情况看起来比较难检测和处理，我们怎么知道...

题目链接 可以看作单调栈来解决。 这个算法的时间复杂度是O（N），空间复杂度是O（N）。 python: class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: res = 0 arr = arr + [0] stack = [-1] size = len(arr) for i in range(size): while arr[stack[-1]] > arr[i]: idx = stack.pop() res +=...

题目链接 遍历，一个简单题。这个算法的时间复杂度是O(min(m, n))，空间复杂度是O(min(m, n))。 python: class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True elif not p or not q: return False elif p.val != q.val: return False else: return self.i...

题目链接 这个比较简单吧，零的数量本质上由5的数量决定，比如说5的因子里有一个5，10的因子里有一个5，25的因子里有两个5。有几个5就会在末尾产生几个0，因为2的数量肯定都是足够的。所以我们只需要求出因子里有5的数字有几个，25的有几个，125的有几个，以此类推，每次相应地在答案上加1，2，3…即可。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。 python: class Solution: def trailingZeroes(self, n: int) -> int: ans = 0 five = 5 while five <= n: ans += n // five...

题目链接 啊这个，我之前面试的时候倒是做了一个最大正方形，一下就做出来了的。现在这个思考一下感觉和“lc042接雨水”有点像。在那道题里面用到了暴力算法和单调栈，这道题里也是。在做这道题之前，我先做了一下lc84最大矩形，因为那个题里的思路能够很好地用到本题上面。简而言之，我们扫描每一行，用类似前缀和的思想记录下每个位置到当前为止连续1的个数，对于每一行，我们再将这一行看作底，去求若干以该行为底的柱形中所包含的最大矩形有多大。将上述计算用在每一行中找到最终的答案。 后续发现用“哨兵”避免分类讨论时没必要用俩，只要用一个就行并且要将stack里的初始元素设为-1即指向新加入的末尾哨兵。这样在遍历时就没必要从1开始而是自然地从0开始即可。 这个算法的时间复杂度是O（NM），空间复杂度...

题目链接 为了做lc85特意先做一下这个题来复习复习单调栈。首先是用暴力算法，对于每个位置，都分别向左向右延伸一下找到比当前位置小的第一个高度，记录前一个位置，同时找到左边和右边的边界后就计算一次面积，将改面积与之前记录的面积比较从而得到答案。这样做的时间复杂度为O（N^2），空间复杂度为O（1）。 考虑用空间换时间，用单调栈的做法。首先考虑，我们在用单调栈的时候记录的是什么信息。如果仅仅记录高度，那么是不够的，因为计算矩形还需要宽度，所以我们应该在栈内记录下标。我们拿数组[2, 1, 5, 6, 2, 3]为例。1.一开始看到的柱形高度为2，这个时候以2为高度的最大面积的矩形还不能确定，我们需要继续向右遍历。2.然后我们看到高度为1的柱形，这个时候以这个柱形为高度的矩形的最大面积...

题目链接 很久没有做算法题了，居然看到简单题也很生疏。当即就看了一题解，我印象中有做过类似的题目的来着。有两种做法，第一种就是模拟，末尾对齐，逐位相加。在二进制中我们需要逢二进一。具体来说，我们先取n为a和b中较大的一个length，循环n次，从最低位开始遍历。我们用一个变量carry表示上一个位置的进位，初始值为0。记当前位置对齐的两个位为ai和bi，则每一位的答案为(carry+ai+bi)mod2，下一位的进位为[(carry+ai+bi)//2]。重复上述步骤，直到数字a和b的每一位计算完毕。最后如果carry的最高位不为0，则将最高位添加到计算结果的末尾。注意，为了使得各个位置对齐，可以先反转这个代表二进制数字的字符串然后低下标对应低位，高下标对应高位。要记住最终答案也要进...

题目链接 很久没有做算法题了，居然看到简单题也很生疏。当即就看了一题解，我印象中有做过类似的题目的来着。有两种做法，第一种就是模拟，末尾对齐，逐位相加。在二进制中我们需要逢二进一。具体来说，我们先取n为a和b中更大的length，循环n次，从最低位开始遍历。我们用一个变量carry表示上一个位置的进位，初始值为0。记当前位置对齐的两个位为ai和bi，则每一位的答案为(carry+ai+bi)mod2，下一位的进位为[(carry+ai+bi)//2]。重复上述步骤，直到数字a和b的每一位计算完毕。最后如果carry的最高位不为0，则将最高位添加到计算结果的末尾。注意，为了使得各个位置对齐，可以先反转这个代表二进制数字的字符串然后低下标对应低位，高下标对应高位。要记住最终答案也要进行翻...

题目链接 暴力算法就不说了时间复杂度是O（N^3），写一个时间复杂度稍微优一点的算法吧，就是用二维的动态规划。思路如下。对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道“bab”是回文串，这是因为它的首位两个字母都是“a”。我们用P（i，j）表示字符串s的第i到第j个字母组成的串（下文表示成s[[i:j]）是否为回文串：如果它的子串Si…Sj为回文串，那么P（i，j）是回文串，除非当发生i>j或者s[i,j]本身不是一个回文串的情况。那我们可以写出状态转移方程: P(i,j) = P(i+1,j-1) and (Si == Sj)，也就是说只有s[i+1;j-1]是回文串且s的第i...