Home

题目链接 看到这个题目的第一反应是顺序扫描数组，每扫描到一个数字就逐个比较该数字和它后面的数字的大小，如果后面数字比他小，则这俩数字就组成一个逆序对，但这种算法的时间复杂度为O（n^2）。我们需要尝试找到更快的算法，以数组[7, 5, 6, 4]为例子，我们考虑先比较两个相邻的数字。我们先把数组分解成两个长度为2的子数组，再将他们拆成长度为1的子数组。接下来一边合并相邻的子数组一边统计逆序对的数目。在第一对长度为1的子数组[7], [5]中，7大于5，因此（7，5）组成一个逆序对。同样，在第二对长度为1的子数组[6], [4]中，也有逆序对（6，4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组排序，以免在以后的统计过程中再重复统计。接下来我们再统计两个长度为2...

题目链接 这题比较简单，遍历两次即可，这个算法的时间复杂度是O（N），空间复杂度是O（1）。 from collections import defaultdict class Solution: def firstUniqChar(self, s: str) -> str: hashtable = defaultdict(int) for x in s: hashtable[x] += 1 for x in s: if hashtable[x] == 1: return x return " "

题目链接 此题与jz049.丑数相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def nthUglyNumber(self, n: int) -> int: res, a, b, c = [1]*n, 0, 0, 0 for i in range(1, n): m2, m3, m5 = res[a] * 2, res[b] * 3, res[c]* 5 res[i] = min(m2, m3, m5) if m2 == res[i]: a += 1 if m3 == res[i]: b += 1...

题目链接 在把以前leetcode美国账号的题都在中国账号上重新刷一遍。这题目就很简单了吧不用多说。也贴了一下官方的题解实现比我好看多了2333.这个算法的时间复杂度是O（N^2），空间复杂度是O（N^2）。 class Solution: def generate1(self, numRows: int) -> List[List[int]]: res = [] if numRows == 0: return res elif numRows == 1: return [[1]] elif numRows == 2: return ...

相交链表 此题与lc160.想叫链表相同。思路很简单，也可以说是双指针法，即将两个链表拼接，得到两个相同长度但前后顺序不同的链表（假设输入的是两个链表X和Y，则拼接成的新链表为XY和YX）。分别从头遍历这俩链表，当节点值相等时则为相交位置，否则遍历结束返回指针指向的None。该算法的时间复杂度为O（M+N），空间复杂度为O（N）。 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode...

题目链接 此题与jz048相同。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: dic = {} res = tmp = 0 for i in range(len(s)): p = dic.get(s[i], -1) dic[s[i]] = i tmp = tmp + 1 if i - p > tmp else i - p res = max(res, tmp) r...

题目链接 逐个判断每个整数是不是丑数的做法很直观但并不高效。首先我们来分析一下如何判断一个数是不是丑数，所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3、5整除。也就是说，如果一个数能被2整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5。如果最后得到的是1，那么这个数就是丑数，否则不是。因此我们可以写出isUgly函数来判断一个数是不是丑数。接下来只要按照顺序判断每个整数是不是丑数。该实现如1所示，时间复杂度非常高是O（N^2），空间复杂度是O（N）。 上述的思路最大的问题就是需要计算每一个整数，即使一个数字不是丑数，我们还是需要对它执行求余数和除法操作，因此该算法的时间效率不是很高。接下去...

题目链接 事实上，这是一个典型的“动态规划”问题，并且原型就是“0-1背包问题“，代码的执行过程就是在填表格的过程。但是做这题需要做一个等价转换，将问题看成：是否可以从数组中挑出一部分正整数使得这些数的和等于整个数组元素的和的一半，当然我们要先提前判断数组和是否能被2整除。本题和0-1背包问题有一个很大的不同，那就是0-1背包问题选取的物品的容积总量不能超过规定的总量，但本题所选取的数字之和责需要恰好等于规定的和的一半。这一点区别决定了在初始化的时候，所有的值应该初始化为 作为0-1背包问题，它的特点是：每个数只能用一次。思路是：物品一个一个选，容量也一点一点放大考虑。具体做法是：画一个len行，target+1列的表格。这里len是物品的个数，target是背包的容量。len行表示...

题目链接 我们不难找出字符串中的所有子字符串，然后可以判断每个子字符串中是否包含重复的字符，但是这种蛮力法效率太低。对于一个长度为n的字符串，其含有O（N^2）个字串，我们需要O（N）的时间来判断一个字符串中是否包含连续字串。因此暴力法的总时间效率是O（N^3）。 接下来我们用动态规划算法来提高效率，首先定义函数f（i）表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。我们从左到右逐一扫描字符串中的每个字符。当我们计算以第i个字符为结尾的不包含重复字符的子字符串的最长长度f（i）时，我们已经知道f（i-1）了。 如果第i个字符之前没有出现过，那么f（i）= f（i-1）+ 1，例如，在字符串“arabcacfr”中，显然f（0）等于1，在计算f（1）时，下标为1的字符“...

题目链接 做过很多次的，典型的2维dp，所以就不复述了。这个算法的时间复杂度是O（MN），如果在原先的矩阵上改的话空间复杂度是O（1）。 class Solution: def maxValue1(self, grid: List[List[int]]) -> int: rows, columns = len(grid), len(grid[0]) res = [[0]*columns for i in range(rows)] res[0][0] = grid[0][0] for y in range(1, columns): res[0][y] = res[0][y-1] + ...