LeetCode习题整理（中等）I

• 花匠小妙招
• 2024-09-10 19:03

快速排序

class Solution(object): def quickSort(self, L, low, high): if low < high: i = self.partition(L, low, high) self.quickSort(L, low, i-1) self.quickSort(L, i+1, high) def partition(self, L, low, high): i, j = low, high x = L[low] while i < j: while L[j] <= x and i < j: j -= 1 while L[i] >= x and i < j: i += 1 if i != j: temp = L[j] L[j] = L[i] L[i] = temp ''' temp = L[j] L[j] = L[low] L[low] = temp ''' return j def lexicalOrder(self, n): """ :type n: int :rtype: List[int] """ L = [str(i) for i in range(1, n+1)] self.quickSort(L, 0, n-1) return L 1234567891011121314151617181920212223242526272829303132333435363738

分割连接字符串

给定一个字符串列表，你可以将这些字符串连接成一个循环字符串，对于每个字符串，你可以选择是否翻转它。在所有可能的循环字符串中，你需要分割循环字符串（这将使循环字符串变成一个常规的字符串），然后找到字典序最大的字符串。

具体来说，要找到字典序最大的字符串，你需要经历两个阶段：

1.将所有字符串连接成一个循环字符串，你可以选择是否翻转某些字符串，并按照给定的顺序连接它们。
2.在循环字符串的某个位置分割它，这将使循环字符串从分割点变成一个常规的字符串。
你的工作是在所有可能的常规字符串中找到字典序最大的一个。

示例：
输入: “abc”, “xyz”
输出: “zyxcba”
解释: 你可以得到循环字符串 “-abcxyz-”, “-abczyx-”, “-cbaxyz-”, “-cbazyx-”，
其中 ‘-’ 代表循环状态。
答案字符串来自第四个循环字符串，
你可以从中间字符 ‘a’ 分割开然后得到 “zyxcba”。

注意：

输入字符串只包含小写字母。所有字符串的总长度不会超过 1,000。

答案：

class Solution(object): def splitLoopedString(self, strs): """ :type strs: List[str] :rtype: str """ # 首先，如果要求是字典排序最大的，那么对每个字符串而言， # 它自己和自己的翻转字符串之间，选取字典排序大的保留下来， # 这样，后续构造出的拼接字符串才是大的。 strs = [s[::-1] if s[::-1] > s else s for s in strs] #''.join(strs)是将strs中的每个字符串之间用''连接，最终构成一个字符串 # 这样就构成了一个默认串ans，就相当于是从strs的第0个字符串的第0个位置做的分割 ans = ''.join(strs) # enumarate是迭代器，可以同时迭代数组或list等对象的下标和内容。 for i, s in enumerate(strs): # 另外，考虑到分割的位置可能是在任意第i个小字符串中的第j个位置 # 故首先将第i个小字符串除外，其他的所有字符串拼接起来组成other字符串 other = ''.join(strs[i + 1:]) + ''.join(strs[: i]) # 然后，因为中间部分的other已经有了，那么，现在就是需要将头和尾补上 # 因为是从strs中的第i个字符串中的第j个位置分割的，所以 # head = s[j:]为头部，tail = s[:j]为尾部，cur = head + other + tail # 另外，通过将ans与不同的cur比较，最终保留最大的放在ans并返回 for j, _ in enumerate(s): head = s[j:] tail = s[:j] cur = head + other + tail ans = max(ans, cur) # 注意，这里还要增加一次将头和尾同时翻转的比较，因为在一开始 # 我们只是考虑了当字符串没有从中间切分开的情况下， 取字典排序最大的 # 保留在strs中，但是，一旦从中间切分开，可能情况就不一样了，因此 # 必须增加这一次比较，但是头和尾是否翻转，必须是一致的。 cur = tail[::-1] + other + head[::-1] ans = max(ans, cur) return ans 12345678910111213141516171819202122232425262728293031323334

花括号展开II

如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。

花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串，定义下面几条语法规则：

如果只给出单一的元素 x，那么表达式表示的字符串就只有 “x”。
例如，表达式 {a} 表示字符串 “a”。
而表达式 {ab} 就表示字符串 “ab”。
当两个或多个表达式并列，以逗号分隔时，我们取这些表达式中元素的并集。
例如，表达式 {a,b,c} 表示字符串 “a”,“b”,“c”。
而表达式 {a,b},{b,c} 也可以表示字符串 “a”,“b”,“c”。
要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。
例如，表达式 {a,b}{c,d} 表示字符串 “ac”,“ad”,“bc”,“bd”。
表达式之间允许嵌套，单一元素与表达式的连接也是允许的。
例如，表达式 a{b,c,d} 表示字符串 “ab”,“ac”,"ad"​​​​​​。
例如，表达式 {a{b,c}}{{d,e}f{g,h}} 可以代换为 {ab,ac}{dfg,dfh,efg,efh}，表示字符串 “abdfg”, “abdfh”, “abefg”, “abefh”, “acdfg”, “acdfh”, “acefg”, “acefh”。
给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。

假如你希望以「集合」的概念了解此题，也可以通过点击 “显示英文描述” 获取详情。

示例 1：

输入："{a,b}{c{d,e}}"
输出：[“acd”,“ace”,“bcd”,“bce”]

示例 2：

输入："{{a,z}, a{b,c}, {ab,z}}"
输出：[“a”,“ab”,“ac”,“z”]
解释：输出中 不应 出现重复的组合结果。

提示：

1 <= expression.length <= 50expression[i] 由 ‘{’，’}’，’,’ 或小写英文字母组成给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串

class S(set): def __add__(self, other): #|是位运算符 return S(self | other) def __mul__(self, other): return S(i + j for i, j in itertools.product(self, other)) class Solution:# python中快速定义函数的方法# def 函数名(参数:类型)->返回值类型:函数体 def braceExpansionII(self, expression: str) -> List[str]: expression = re.sub('(w+)', r'S(["1"])', expression) d = {',': '+', '{': '(', '}': ')'} expression = re.sub('[,{}]', lambda x: d[x.group(0)], expression) expression = re.sub(')([S(])', r')*1', expression) return sorted(S(eval(expression))) 1234567891011121314151617

安装栅栏

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
示例 1:

输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
解释:

示例 2:

输入: [[1,2],[2,2],[4,2]]
输出: [[1,2],[2,2],[4,2]]
解释:

即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。输入的整数在 0 到 100 之间。花园至少有一棵树。所有树的坐标都是不同的。输入的点没有顺序。输出顺序也没有要求。

class Solution(object): def outerTrees(self, points): n = len(points) if n < 3: return points pts = sorted(set(points), key = lambda a: (a.x, a.y)) # 利用向量外积判断凸点，如果外积小于零说明新的点属于外围点，也就是凸点，反之新的点就是凹点。 cross = lambda o, a, b: (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x) low = [] for p in pts:# 若新点是凸点则将新点放入low，将凹点low[-1]从low中删除。# 先进行下面那半边外圈线的扫描 while len(low) > 1 and cross(low[-2], low[-1], p) < 0: low.pop() low.append(p) up = [] for p in reversed(pts):# 若新点是凸点则将新点放入low，将凹点low[-1]从low中删除。# 再进行上面那半边外圈线的扫描 while len(up) > 1 and cross(up[-2], up[-1], p) < 0: up.pop() up.append(p) return list(set(low[:-1] + up[:-1])) 123456789101112131415161718192021222324252627

等差数列划分II

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, …, Pk)，P 与 Q 是整数且满足 0 ≤ P0 < P1 < … < Pk < N。

如果序列 A[P0]，A[P1]，…，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。

函数要返回数组 A 中所有等差子序列的个数。

输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 2^31-1。

示例：

输入：[2, 4, 6, 8, 10]

输出：7

解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

class Solution: def numberOfArithmeticSlices(self, A: List[int]) -> int: from collections import defaultdict dp = [defaultdict(int) for _ in range(len(A))] res = 0 for i in range(len(A)): # 选择第i个位置为当前子序列的最后一个元素 for j in range(i): # 从第0个元素开始到第i个元素# 计算第j个位置元素和第i个位置元素之间的差，记作diff。 diff = A[i] - A[j] # 因为dp[k][diff]存的是以第k个元素作为结尾且元素之间的间距为diff的子序列的个数 # 故dp[i][diff] += dp[j][diff] + 1，相当于将第i个元素放到了原本第j个元素的后面构成了更长的新的子序列 dp[i][diff] += dp[j][diff] + 1 # A[i] - A[j] == diff 且 dp[j][diff] >= 1 # 则将A[i]放到原本dp[j][diff]所表示的子序列后面生成的新序列满足长度大于等于3 if diff in dp[j]: res += dp[j][diff] # 计数 return res 12345678910111213141516171819

路径和IV

对于一棵深度小于 5 的树，可以用一组三位十进制整数来表示。

对于每个整数：

百位上的数字表示这个节点的深度 D，1 <= D <= 4。十位上的数字表示这个节点在当前层所在的位置 P， 1 <= P <= 8。位置编号与一棵满二叉树的位置编号相同。个位上的数字表示这个节点的权值 V，0 <= V <= 9。

给定一个包含三位整数的升序数组，表示一棵深度小于 5 的二叉树，请你返回从根到所有叶子结点的路径之和。

样例 1:

输入: [113, 215, 221]
输出: 12
解释:
这棵树形状如下:

路径和 = (3 + 5) + (3 + 1) = 12.

样例 2:

输入: [113, 221]
输出: 4
解释:
这棵树形状如下:

路径和 = (3 + 1) = 4.

def pathSum(self, nums: List[int]) -> int: node = [[None]*8 for _ in range(4)] # 初始化数组 for n in nums: node[n//100-1][(n-n//100*100)//10-1] = n%10 # 将三位整数所携带的节点信息按规则填入数组 # 百位 n//100 为层数 # 十位 (n-n//100*100)//10 为所处位置 # 个位 n%10 为携带值 #print(*node,sep='n') # 用于检验所得数组是否正确 res = 0 for i in range(4): # 对数组进行遍历 for j in range(2**i): # 第i层最多包含2^i个节点 if node[i][j] != None and (i==3 or (node[i+1][j*2]==None and node[i+1][j*2+1]==None)): # 判断是否为叶节点，条件： # 1. 节点值非空 # 2. 节点是否为最底层节点，或者子节点为空 res += node[i][j] ii,jj = i,j while ii>0: #如果节点为子节点，自下至上回溯直到根节点 ii -= 1 jj >>= 1 res += node[ii][jj] return res 1234567891011121314151617181920212223242526

我的做法：

class Node(): def __init__(self, value, left=None, right=None, deep_idx=0, pos_idx=0): self.value = value self.left = left self.right = right self.deep_idx = deep_idx self.pos_idx = pos_idx self.fathernode = None def addFartherNode(self, fathernode): self.fathernode = fathernode class Tree(): def __init__(self, L): nodes = [] for s in L: deep_idx = s // 100 pos_idx = (s - deep_idx * 100) // 10 value = (s - deep_idx * 100) % 10 assert deep_idx>=1 and deep_idx<=4 assert pos_idx>=1 and pos_idx<=2**(deep_idx-1) assert value>=0 and value<=9 node = Node(value,deep_idx=deep_idx,pos_idx=pos_idx) print('deep_idx={}, pos_idx={}, value={}'.format(deep_idx, pos_idx, value)) nodes.append(node) self.root = nodes[0] for i in range(len(nodes)-1): for j in range(i+1,len(nodes)): if nodes[i].deep_idx + 1 == nodes[j].deep_idx and nodes[i].pos_idx * 2 - 1 == nodes[j].pos_idx: nodes[i].left = nodes[j] nodes[j].addFartherNode(nodes[i]) elif nodes[i].deep_idx + 1 == nodes[j].deep_idx and nodes[i].pos_idx * 2 == nodes[j].pos_idx: nodes[i].right = nodes[j] nodes[j].addFartherNode(nodes[i]) self.FindLeaf(nodes) #return self.root, self.Leaves def FindLeaf(self, nodes): self.Leaves = [] for node in nodes: if node.left == None and node.right == None: self.Leaves.append(node) class Solution(object): def pathSum(self, nums): """ :type nums: List[int] :rtype: int """ tree = Tree(nums) root, Leafnodes = tree.root, tree.Leaves #print(Leafnodes) #print('{}->{},{}'.format(root.value,root.right.value)) self.Sum = 0 for leaf in Leafnodes: fn = leaf print(leaf.value) #print('[') while fn != None: self.Sum += fn.value #print('{}'.format(fn.value)) fn = fn.fathernode #print(']') return self.Sum 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172

将数组分割成和相等的子数组

给定一个有 n 个整数的数组，你需要找到满足以下条件的三元组 (i, j, k) ：

0 < i, i + 1 < j, j + 1 < k < n - 1
子数组 (0, i - 1)，(i + 1, j - 1)，(j + 1, k - 1)，(k + 1, n - 1) 的和应该相等。
这里我们定义子数组 (L, R) 表示原数组从索引为L的元素开始至索引为R的元素。

示例:

输入: [1,2,1,2,1,2,1]
输出: True
解释:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

注意:

1 <= n <= 2000。
给定数组中的元素会在 [-1,000,000, 1,000,000] 范围内。

class Solution: def splitArray(self, arr: List[int]) -> bool: prefix = arr[::] for i in range(1, len(arr)): prefix[i] += prefix[i-1] mapsum = collections.defaultdict(list) for i in range(len(prefix)): mapsum[prefix[i]].append(i) # find pairs pairs = [] for k in range(5, len(arr)): val = prefix[-1]-prefix[k] pairs += [(i+1, k) for i in mapsum[val] if i+5 <= k] for i, k in pairs: for j in range(i+2, k-1): if prefix[i-1] == prefix[j-1]-prefix[i] == prefix[k-1]-prefix[j]: return True return False 123456789101112131415161718192021

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

def twoSum(nums, target): lens = len(nums) j=-1 for i in range(lens): if (target - nums[i]) in nums: if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。 continue else: j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2 break if j>0: return [i,j] else: return [] 1234567891011121314

找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

方法:
1.题目获取两个数组的中位数，那么遍历这两个数组到他们的mid(中间)位置即可
2.将mid前的两个数存入事先声明好的长度为2的数组ary[0,0]
3.接下来根据这两个数组的总长度判断直接返回中位数还是取其中间的两个数相加后的平均值。
图解:

判断是一个中位数，还是二个中位数，然后根据对应规则返回结果集。

class Solution: def findMedianSortedArrays(self, nums1, nums2) -> float: # 1. 下面这些情况进行处理 len1 = len(nums1) len2 = len(nums2) # 一个数组为空，补上另一个数组，中值/2后还是原来的结果(类似于: 3 * 2 / 2还是原来的结果) if len1 == 0: nums1 = nums2 elif len2 == 0: nums2 = nums1 if len1 == 1 and len2 == 1: return (nums1[0] + nums2[0]) / 2 # 这个情况直接返回 # 2. 获取基本变量信息 lenAll = len1 + len2 mid = int(lenAll / 2 + 1) # 使运行到这里长度总>=3，mid中值的位置(3/2+1=2、4/2+1=3) i = j = 0 # 便利索引 ary = [0, 0] # 存储中值的列表 # 3. 核心代码 while i < len1 and j < len2: # 假定两个数字长度相同，和一个数组遍历到临界点的时候，刚好i + j == mid if nums1[i] < nums2[j]: ary[(i + j) % 2] = nums1[i] i += 1 else: ary[(i + j) % 2] = nums2[j] j += 1 if i + j == mid: break # 达到中值 退出循环 # 对两个数组长度不一，以及一个数组下标i或j先行达临界点(nums1.length = i或nums2.length == j)进行补充 while i + j < mid and i == len1: ary[(i + j) % 2] = nums2[j] j += 1 while i + j < mid and j == len2: ary[(i + j) % 2] = nums1[i] i += 1 # 4. 判断后返回对应的运行结果 if lenAll % 2 != 0: return ary[(i + j - 1) % 2] # 总长度为奇数，最后一个赋值就是中值。 else: return (ary[0] + ary[1]) / 2 # 总长度为偶数，直接返回他们相加的平均值。 12345678910111213141516171819202122232425262728293031323334353637383940

LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

import numpy as np class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.stack = [] self.capacity = capacity def get(self, key): """ :type key: int :rtype: int """ # 先获取键值对 for i in range(len(self.stack)-1, -1, -1): if self.stack[i][0] == key:# 如果存在，返回 #print('找到{}'.format(key)) last_key_idx = i last_key, last_value = self.stack[i][0], self.stack[i][1] # 由于最近使用过key这个键值对，将其放到stack的最后一位 self.stack.pop(last_key_idx) self.stack.append([last_key, last_value]) return last_value return -1 def put(self, key, value): """ :type key: int :type value: int :rtype: None """ for i in range(len(self.stack)-1, -1, -1): if self.stack[i][0] == key: #这个键已经存在，更新该位置的值，并移动到最后面。 self.stack[i][1] = value last_key_idx = i last_key, last_value = self.stack[i][0], self.stack[i][1] # 由于最近使用过key这个键值对，将其放到stack的最后一位 self.stack.pop(last_key_idx) self.stack.append([last_key, last_value]) return if len(self.stack) == self.capacity: self.stack.pop(0) #print('放入{}，{}'.format(key, value)) self.stack.append([key, value]) # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162

线程阻塞队列

from threading import Condition import threading class BoundedBlockingQueue(object): def __init__(self, capacity: int): self.capacity = capacity self.queue = collections.deque([]) self.mutex = threading.Lock() self.not_full = Condition(self.mutex) self.not_empty = Condition(self.mutex) def enqueue(self, element: int) -> None: with self.not_full: while self.size() >= self.capacity: self.not_full.wait() self.queue.appendleft(element) self.not_empty.notify_all() def dequeue(self) -> int: with self.not_empty: while not self.size(): self.not_empty.wait() ans = self.queue.pop() self.not_full.notify_all() return ans def size(self) -> int: return len(self.queue) 123456789101112131415161718192021222324252627282930313233

轰炸敌人

想象一下炸弹人游戏，在你面前有一个二维的网格来表示地图，网格中的格子分别被以下三种符号占据：

‘W’ 表示一堵墙
‘E’ 表示一个敌人
‘0’（数字 0）表示一个空位

请你计算一个炸弹最多能炸多少敌人。

由于炸弹的威力不足以穿透墙体，炸弹只能炸到同一行和同一列没被墙体挡住的敌人。

注意：你只能把炸弹放在一个空的格子里

示例:

输入: [[“0”,“E”,“0”,“0”],[“E”,“0”,“W”,“E”],[“0”,“E”,“0”,“0”]]
输出: 3
解释: 对于如下网格

0 E 0 0
E 0 W E
0 E 0 0

假如在位置 (1,1) 放置炸弹的话，可以炸到 3 个敌人

class Solution(object): def maxKilledEnemies(self, grid): """ :type grid: List[List[str]] :rtype: int """ if len(grid) == 0: return 0 rownum = len(grid) colnum = len(grid[0]) Max = 0 for i in range(rownum): for j in range(colnum): if grid[i][j] == '0':# 可放置炸弹 # 检查同行或同列是否有墙 count_in_row = 0 count_in_col = 0 for k in range(j+1, colnum):# 向右探索 if grid[i][k] == 'W': break elif grid[i][k] == 'E': count_in_row += 1 for k in range(j-1, -1, -1):# 向左探索 if grid[i][k] == 'W': break elif grid[i][k] == 'E': count_in_row += 1 for k in range(i+1, rownum):# 向下探索 if grid[k][j] == 'W': break elif grid[k][j] == 'E': count_in_col += 1 for k in range(i-1, -1, -1):# 向上探索 if grid[k][j] == 'W': break elif grid[k][j] == 'E': count_in_col += 1 Count = count_in_row + count_in_col if Count > Max: Max = Count return Max 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

字典序排数

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

class Solution(object): def lexicalOrder(self, n): """ :type n: int :rtype: List[int] """ def dfs(cur,n,res): # cur为根结点 if cur > n: return else: res.append(cur) for i in range(10): if 10 * cur + i > n: # 比如叶子结点为14，而n是13，dfs就结束了 return dfs(10 * cur + i, n, res) res = [] # 对每棵树进行dfs for i in range(1,10): dfs(i, n, res) return res 1234567891011121314151617181920

螺旋矩阵III

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：R = 1, C = 4, r0 = 0, c0 = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

示例 2：

输入：R = 5, C = 6, r0 = 1, c0 = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

提示：

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

class Solution(object): def Circle(self, L, R, C, center_i, center_j, r, start_i, start_j): # 先向右进一格 start_j += 1 if start_i >= 0 and start_i <= R-1 and start_j >= 0 and start_j <= C-1: L.append([start_i, start_j]) # 向下探索 for i in range(start_i+1, center_i+r+1): #print('i={}, start_j={}'.format(i, start_j)) if i >= 0 and i <= R-1 and start_j >= 0 and start_j <= C-1: L.append([i, start_j]) # 向左探索 for k in range(start_j-1, center_j-r-1, -1): #print('i={}, k={}'.format(i, k)) if i >= 0 and i <= R-1 and k >= 0 and k <= C-1: L.append([i, k]) # 向上探索 for m in range(i-1, center_i-r-1, -1): #print('m={}, k={}'.format(m, k)) if m >= 0 and m <= R-1 and k >= 0 and k <= C-1: L.append([m, k]) # 向右探索 for s in range(k+1, center_j+r+1): #print('m={}, s={}'.format(m, s)) if m >= 0 and m <= R-1 and s >= 0 and s <= C-1: L.append([m, s]) # 增加半径 return m, s, r+1 def spiralMatrixIII(self, R, C, r0, c0): """ :type R: int :type C: int :type r0: int :type c0: int :rtype: List[List[int]] """ if R ==1 and C == 1: return [[0,0]] r_max = max(r0, c0, R-r0-1, C-c0-1) print(r_max) L = [] center_i = r0 center_j = c0 L.append([r0,c0]) #L.append([r0,c0+1]) start_i = r0 start_j = c0 r = 1 while r <= r_max: start_i, start_j, r = self.Circle(L, R, C, center_i, center_j, r, start_i, start_j) #print(start_i, start_j) return L 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556

搜寻名人

假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n - 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B。你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。

在本题中，你可以使用辅助函数 bool knows(a, b) 获取到 A 是否认识 B。请你来实现一个函数 int findCelebrity(n)。

派对最多只会有一个 “名人” 参加。若 “名人” 存在，请返回他/她的编号；若 “名人” 不存在，请返回 -1。

示例 1:

输入: graph = [
[1,1,0],
[0,1,0],
[1,1,1]
]
输出: 1
解析: 有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人，而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人，因为 0 和 2 均认识他/她，但 1 不认识任何人。
示例 2:

输入: graph = [
[1,0,1],
[1,1,0],
[0,1,1]
]
输出: -1
解析: 没有 “名人”

注意:

该有向图是以邻接矩阵的形式给出的，是一个 n × n 的矩阵， a[i][j] = 1 代表 i 与 j 认识，a[i][j] = 0 则代表 i 与 j 不认识。
请记住，您是无法直接访问邻接矩阵的。

# The knows API is already defined for you. # @param a, person a # @param b, person b # @return a boolean, whether a knows b # def knows(a, b): class Solution(object): def findCelebrity(self, n): """ :type n: int :rtype: int """ for i in range(n): j = 0 while j < n: if i != j and knows(i,j) == True: break j += 1 if j == n: k = 0 while k < n: if knows(k, i) == False: break k += 1 if k == n: return i return -1 12345678910111213141516171819202122232425262728

距离相等的条形码

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

示例 1：

输入：[1,1,1,2,2,2]
输出：[2,1,2,1,2,1]
示例 2：

输入：[1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

提示：

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

class Solution(object): def rearrangeBarcodes(self, barcodes): """ :type barcodes: List[int] :rtype: List[int] """ #print(collections.Counter(barcodes)) counter = dict(collections.Counter(barcodes)) #按出现次数统计元素 sortedCounter = sorted(counter, key=lambda k: 0 - counter[k]) #print(sortedCounter) barcodes = [] #重新排序 for i in sortedCounter: #print(i) barcodes += [i] * counter[i] #print([i] * counter[i]) #print(barcodes) arrangedBarcodes = [None for _ in range(len(barcodes))] #间隔插入 arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])] arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):] return arrangedBarcodes 12345678910111213141516171819202122232425

稀疏矩阵的乘法

给你两个 稀疏矩阵 A 和 B，请你返回 AB 的结果。你可以默认 A 的列数等于 B 的行数。

请仔细阅读下面的示例。

示例：

输入：

A = [
[ 1, 0, 0],
[-1, 0, 3]
]

B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]

输出：

| 7 0 0 | | -7 0 3 | 12

import numpy as np class Solution(object): def multiply(self, A, B): """ :type A: List[List[int]] :type B: List[List[int]] :rtype: List[List[int]] """ AD = {} BD = {} result = np.zeros((len(A),len(B[0])), dtype = int) for i in range(len(A)): AD[i] = [] for j in range(len(A[0])): if A[i][j] != 0: AD[i].append(j) for i in range(len(B)): BD[i] = [] for j in range(len(B[0])): if B[i][j] != 0: BD[i].append(j) # 利用AD和BD做A和B的乘法 for key, value in AD.items(): for col_A in AD[key]: for col_B in BD[col_A]: result[key][col_B] += A[key][col_A] * B[col_A][col_B] for i in range(len(result)): result[i] = list(result[i]) return list(result) 12345678910111213141516171819202122232425262728293031323334

预测赢家

给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1:

输入: [1, 5, 2]
输出: False
解释: 一开始，玩家1可以从1和2中进行选择。
如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。
所以，玩家1的最终分数为 1 + 2 = 3，而玩家2为 5。
因此，玩家1永远不会成为赢家，返回 False。
示例 2:

输入: [1, 5, 233, 7]
输出: True
解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。
最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。
注意:

1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于10000000。
如果最终两个玩家的分数相等，那么玩家1仍为赢家。

分析：
核心思想就是动态规划，用一个二维数据dp记录当前情况是从i到j时，先取分数的人，能比后取分数的人多得多少分。

length=j-i+1从1开始递增：
1、当长度是1时，先取数的可以多得nums[i]分；
2、当长度是2时，先取数的人取两个数中较大的数，最终比后取数的人多得abs(nums[i] - nums[j])；
3、当长度大于等于3时，可能先取左边的数，也可能先取右边的数，分别可以多得nums[i] - dp[i + 1][j]和num[j] - d[i][j - 1]分，取两者中较大的数即可。

class Solution(object): def PredictTheWinner(self, nums): """ :type nums: List[int] :rtype: bool """ n = len(nums) if n == 1: return True dp = [[0 for j in range(n)] for i in range(n)] for length in range(1, n + 1): for i in range(0, n - length + 1): j = i + length - 1 if length == 1: dp[i][j] = nums[i] elif length == 2: dp[i][j] = abs(nums[i] - nums[j]) else: dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])# 减号式因为nums[i]被拿出去之后，另一个人成为了dp[i+1][j]中先拿的那个人。 if dp[0][n-1] >= 0: return True else: return False 1234567891011121314151617181920212223

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ p = l1 q = l2 result = ListNode(0) pre = result R = result while p != None and q != None: S = p.val + q.val + result.val if S < 10: result.val = S Next = ListNode(0) else: result.val = S%10 Next = ListNode(1) pre = result result.next = Next result = result.next p = p.next q = q.next print(result.val) if result.val == 0: pre.next = result.next result = pre if p != None: result.next = p elif q != None: result.next = q #result.next = result.next.next else: if p != None: pre.next = self.addTwoNumbers(result, p) elif q != None: pre.next = self.addTwoNumbers(result, q) return R 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

平面上的最短距离

表 point_2d 保存了所有点（多于 2 个点）的坐标 (x,y) ，这些点在平面上两两不重合。

写一个查询语句找到两点之间的最近距离，保留 2 位小数。

最近距离在点 (-1,-1) 和(-1,2) 之间，距离为 1.00 。所以输出应该为：

注意：任意点之间的最远距离小于 10000 。

# Write your MySQL query statement below select convert(power(power(a.x-b.x, 2)+power(a.y-b.y, 2), 1/2), decimal(7,2)) as shortest from point_2d as a, point_2d as b where not (a.x = b.x and a.y = b.y) order by shortest asc limit 1; 123456

子数组的最小值之和

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 10^9 + 7。

示例：

输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

提示：

1 <= A <= 30000
1 <= A[i] <= 30000

class Solution(object): def sumSubarrayMins(self, A): """ :type A: List[int] :rtype: int """ len_A = len(A) if len_A == 0: return 0 if len_A == 1: return A[0] ans = 0 left = [0] * len_A right = [0] * len_A # 查找包含A[i]且以A[i]为最小值的连续子数组 # 即找到A[i]左边第一个比A[i]小的值的位置和A[i]右边第一个比A[i]小的值的位置 stack = [] for i in range(len_A): while stack and A[stack[-1]] > A[i]: stack.pop() if not stack: left[i] = -1 else: left[i] = stack[-1] stack.append(i) stack = [] for i in range(len_A - 1, -1, -1): while stack and A[stack[-1]] >= A[i]: stack.pop() if not stack: right[i] = len_A else: right[i] = stack[-1] stack.append(i) for i in range(len_A): # 子数组的左端点有(i-left)种选择，右端点有(right-i)种选择 ans += (i - left[i]) * (right[i] - i) * A[i] ans %= 10**9 + 7 return ans 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

给单链表加一

用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:

输入: [1,2,3]
输出: [1,2,4]

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def __init__(self): self.pre = None def plusOne(self, head): """ :type head: ListNode :rtype: ListNode """ if self.pre == head: new_head = ListNode(1) new_head.next = head head = new_head return new_head p = head while p.next != self.pre: p = p.next s = p.val + 1 self.pre = p if s >= 10: # 向前进一位，迭代 p.val = s % 10 head = self.plusOne(head) else: p.val = s return head 123456789101112131415161718192021222324252627282930313233343536

验证前序遍历序列二叉搜索树

给定一个整数数组，你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

参考以下这颗二叉搜索树：

5 / 12

2 6
/
1 3
示例 1：

输入: [5,2,6,1,3]
输出: false
示例 2：

输入: [5,2,1,3,6]
输出: true
进阶挑战：

您能否使用恒定的空间复杂度来完成此题？

class Solution(object): def verifyPreorder(self, preorder): """ :type preorder: List[int] :rtype: bool """ ''' n = len(preorder) if n <= 1: return True center_node = preorder[0] division_idx = n flag = 0 for i in range(1, n): if flag == 0 and preorder[i] > center_node: division_idx = i flag = 1 if division_idx < n and i > division_idx and preorder[i] < center_node: return False re1 = self.verifyPreorder(preorder[1:division_idx]) re2 = self.verifyPreorder(preorder[division_idx:]) return re1 and re2 ''' stack = [] new_min = float('-inf') # 初始化下限值 for i in range(len(preorder)): if preorder[i] < new_min: return False while stack and preorder[i] > stack[-1]: new_min = stack.pop() stack.append(preorder[i]) return True 12345678910111213141516171819202122232425262728293031323334

相关知识

LeetCode习题整理（中等）I
LeetCode 1
LeetCode
花粥没有花
Leetcode 题解
贪心算法练习
力扣题目训练：605
分子生物学I（蔡刚, 丁勇, 刘强）
leetcode题库——搜索插入位置
每日一题

网址: LeetCode习题整理（中等）I https://m.huajiangbk.com/newsview106052.html

上一篇: 理正岩土软件学习指南最新

下一篇: The program numb