-
LeetCode Cookbook 数组习题（8）
LeetCode Cookbook 数组习题（8）
加把劲，再写两篇九八数组部分给拿下了！ come on.
1002. 查找共用字符
题目链接：1002. 查找共用字符
题目大意：给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。例如：
输入：words = ["bella","label","roller"] 输出：["e","l","l"]- 1
- 2
解题思路：collections.Counter()功能很强大，可以熟悉并在后续中继续使用。
- 计数，统计共有字母的拥有个数 使用 Counter后 进行 与（&） 操作
c = Counter(a=3, b=1) d = Counter(a=1, b=2) c + d # add two counters together: c[x] + d[x] Counter({'a': 4, 'b': 3}) c - d # subtract (keeping only positive counts) Counter({'a': 2}) c & d # intersection: min(c[x], d[x]) Counter({'a': 1, 'b': 1}) c | d # union: max(c[x], d[x]) Counter({'a': 3, 'b': 2})- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 使用 sorted(ans_map.elements()) 输出各元素
class Solution: def commonChars(self, words: List[str]) -> List[str]: ans_map = collections.Counter(words[0]) n = len(words) for i in range(1,n): tmp = [] word_map = collections.Counter(words[i]) ans_map &= word_map ans = sorted(ans_map.elements()) # ans = [] # for i,j in ans_map.items(): # ans += [i]*j return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
1011. 在 D 天内送达包裹的能力 And 410 分割数组的最大值 **
题目链接：1011. 在 D 天内送达包裹的能力 和410 分割数组的最大值
题目大意：传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。例如:
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5 输出：15 解释：船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
解题思路：
- 和 410 分割数组的最大值 一摸一样
- 区别就是 说法不同，且变量名称换了 代码一点也不动。
class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: def check(x: int) -> bool: total,cnt = 0,1 for num in weights: if total+num > x: cnt += 1 total = num else: total += num return cnt > days L,R = max(weights),sum(weights) # 模板二 while L<R: mid = L+(R-L)//2 if check(mid): L = mid+1 else: R = mid return L- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
1051. 高度检查器
题目链接：1051. 高度检查器
题目大意：学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
返回满足 heights[i] != expected[i] 的 下标数量 。例如：
输入：heights = [1,1,4,2,1,3] 输出：3 解释： 高度：[1,1,4,2,1,3] 预期：[1,1,1,2,3,4] 下标 2 、4 、5 处的学生高度不匹配- 1
- 2
- 3
- 4
- 5
- 6
解题思路：按着思路照做就成。
class Solution: def heightChecker(self, heights: List[int]) -> int: rank = sorted(heights) ans = 0 for i,num in enumerate(heights): if num != rank[i]: ans += 1 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
1089. 复写零
题目链接：1089. 复写零
题目大意：给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。- 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
例如：
输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]- 1
- 2
- 3
解题思路： 看我的这篇题解 —— 1089. 复写零：非双指针法 这里使用双指针法也可以 不过个人觉着双指针法在这道题上显得有些不那么灵活 使用双向链表或list特有的insert函数都非常不错，时间和空间上都表现不错。
（一） list 特有的insert 函数 效率不错
class Solution: def duplicateZeros(self, arr: List[int]) -> None: """ Do not return anything, modify arr in-place instead. """ n = len(arr) i = 0 while i < n: if arr[i] == 0: arr.insert(i,0) arr.pop() i += 2 else: i += 1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
(二）deque 双头链表 非常好用
class Solution: def duplicateZeros(self, arr: List[int]) -> None: """ Do not return anything, modify arr in-place instead. """ q = collections.deque() for i,num in enumerate(arr): if num == 0 : q.append(0) q.append(num) arr[i] = q.popleft()- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
1128. 等价多米诺骨牌对的数量 * （降维打击）
题目链接：1128. 等价多米诺骨牌对的数量
题目大意： 给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 ac 且 bd，或是 ad 且 bc。在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。例如：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]] 输出：1- 1
- 2
解题思路： 从 n个中选2个随机组合 一共有 n*(n-1)//2 种
（一）稍微笨一点的
class Solution: def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int: # 降维打击 ~~ 哈哈 vals = [] for (i,j) in dominoes: vals.append(i*10+j if i>=j else j*10+i) counter = collections.Counter(vals) ans = 0 for num in counter: n = counter[num] if n > 1: ans += n*(n-1)//2 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
（二）GF 简便的空间利用率极高
class Solution: def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int: # 降维打击 ~~ 哈哈 nums = [0]*100 ans = 0 for i,j in dominoes: val = i*10+j if i>=j else j*10+i ans += nums[val] nums[val] += 1 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
1157. 子数组中占绝大多数的元素 ** (万恶的Segment Tree）
题目链接：1157. 子数组中占绝大多数的元素
题目大意：设计一个数据结构，有效地找到给定子数组的 多数元素 。子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。实现 MajorityChecker 类:- MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
- int query(int left, int right, int threshold) 返回子数组中的元素 arr[left…right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。
例如：
输入: ["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]] 输出： [null, 1, -1, 2] 解释： MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]); majorityChecker.query(0,5,4); // 返回 1 majorityChecker.query(0,3,3); // 返回 -1 majorityChecker.query(2,3,2); // 返回 2- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
解题思路 线段树，非常难记的代码结构。
class Node: def __init__(self, start: int, end: int, num: int=0, count: int=0) -> None: self.left = None self.right = None self.start = start self.end = end self.num_count = (num, count) class SegmentTree: def __init__(self, data) -> None: self.data = data self.root = self._build(0, len(self.data) - 1) def _build(self, s: int, t: int) -> Node: if s == t: return Node(s, t, self.data[s], 1) cur = Node(s, t) mid = s + ((t - s) >> 1) cur.left = self._build(s, mid) cur.right = self._build(mid + 1, t) left_num, left_count = cur.left.num_count right_num, right_count = cur.right.num_count cur.num_count = (left_num, left_count + right_count) if left_num == right_num else (right_num, right_count - left_count) if left_count <= right_count else (left_num, left_count - right_count) return cur def query(self, s: int, t: int) -> tuple: return self._query(self.root, s, t) def _query(self, node: Node, s: int, t: int) -> tuple: if node.start > t or node.end < s: return (node.num_count[0], 0) if node.start >= s and node.end <= t: return node.num_count left_num, left_count = self._query(node.left, s, t) right_num, right_count = self._query(node.right, s, t) return (left_num, left_count + right_count) if left_num == right_num else (right_num, right_count - left_count) if left_count <= right_count else (left_num, left_count - right_count) class MajorityChecker: def __init__(self, arr: List[int]) -> None: self.segment_tree = SegmentTree(arr) self.data = defaultdict(list) for i in range(len(arr)): self.data[arr[i]].append(i) def query(self, left: int, right: int, threshold: int) -> int: num, _ = self.segment_tree.query(left, right) return num if bisect_right(self.data[num], right) - bisect_left(self.data[num], left) >= threshold else -1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
1160. 拼写单词 *
题目链接：1160. 拼写单词
题目大意： 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和。例如：
输入：words = ["cat","bt","hat","tree"], chars = "atach" 输出：6 解释： 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。- 1
- 2
- 3
解题思路： 使用Counter进行计数对比即可，这里 all() 函数需要学习一下 挺不错的。
class Solution: def countCharacters(self, words: List[str], chars: str) -> int: chars_cnt = collections.Counter(chars) ans = 0 for word in words: word_cnt = collections.Counter(word) if all(word_cnt[i] <= chars_cnt[i] for i in word_cnt): ans += len(word) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1170. 比较字符串最小字母出现频次 **
题目链接：1170. 比较字符串最小字母出现频次
题目大意： 定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。- 例如，若 s = “dcce”，那么 f(s) = 2，因为字典序最小字母是 “c”，它出现了 2 次。
- 现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。
例如：
输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] 输出：[1,2] 解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。- 1
- 2
- 3
解题思路：1089. 复写零 学习了 list的insert函数
- 1170. 比较字符串最小字母出现频次 又学习率 list的count函数
- 不过可以看到 list的count函数功能还是非常有限的 不能完全替代 collections.Counter()的功能 毕竟 哈希表存储的信息要完整更多
- 所以 1002. 查找共用字符还是用collections.Counter()比较方便
class Solution: def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]: # list 的 count 计数功能 ans,q_count,w_count = [],[],[] w_count = [word.count(min(word)) for word in words] for query in queries: tmp = query.count(min(query)) ans.append(len([c for c in w_count if c > tmp])) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1184. 公交站间的距离
题目链接：1184. 公交站间的距离
题目大意：环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。环线上的公交车都可以按顺时针和逆时针的方向行驶。返回乘客从出发点 start 到目的地 destination 之间的最短距离。
例如：
输入：distance = [1,2,3,4], start = 0, destination = 1 输出：1 解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。- 1
- 2
- 3
解题思路： 方向考虑，充分利用数组和。
class Solution: def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int: total = sum(distance) ans = 0 if start>destination: start,destination = destination,start for i in range(start,destination): ans += distance[i] return min(ans,total-ans)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1185. 一周中的第几天
题目链接：1185. 一周中的第几天
题目大意：给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。输入为三个整数：day、month 和 year，分别表示日、月、年。您返回的结果必须是这几个值中的一个 {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}。例如：
输入：day = 31, month = 8, year = 2019 输出："Saturday"- 1
- 2
解题思路： 注意 1970年12月31日 是星期四，这道题给出的日期一定是在 1971 到 2100 年之间的有效日期。
class Solution: def dayOfTheWeek(self, day: int, month: int, year: int) -> str: # 1970年12月31日 星期四 month_28 = [31,28,31,30,31,30,31,31,30,31,30,31] week = ['Monday','Tuesday','Wednesday','Thursday','Friday','Saturday','Sunday'] days = 0 # 计算 1971 到 year的日子 闰年多加1 1968闰年 days += ((year-1971)*365 + (year-1969)//4*1) % 7 days += sum(month_28[mon] for mon in range(month-1)) if ((year%4==0 and year%100!=0) or (year%400==0)) and month>2 : days += 1 days += day return week[(days+3)%7]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
1200. 最小绝对差
题目链接：1200. 最小绝对差
题目大意：给你个整数数组 arr，其中每个元素都 不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。每对元素对 [a,b] 如下：- a , b 均为数组 arr 中的元素
- a < b
- b - a 等于 arr 中任意两个元素的最小绝对差
例如：
输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]- 1
- 2
解题思路： 很巧妙的动态规划题目，非常灵活，需要在不断比较重确定最小绝对差，而后找到符合要求的组合。
class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: n = len(arr) arr.sort() best,ans = float('inf'),list() for i in range(n-1): delta = arr[i+1]-arr[i] if delta < best: best = delta ans = [[arr[i],arr[i+1]]] elif delta == best: ans.append([arr[i],arr[i+1]]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
1217. 玩筹码
题目链接：1217. 玩筹码
题目大意：有 n 个筹码。第 i 个筹码的位置是 position[i] 。我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:- position[i] + 2 或 position[i] - 2 ，此时 cost = 0
- position[i] + 1 或 position[i] - 1 ，此时 cost = 1
- 返回将所有筹码移动到同一位置上所需要的 最小代价 。
例如：
输入：position = [1,2,3] 输出：1 解释：总成本是1。 第一步:将位置3的筹码移动到位置1，成本为0。 第二步:将位置2的筹码移动到位置1，成本= 1。- 1
- 2
- 3
- 4
- 5
解题思路： 典型动态规划的题目，设置 up 和 down 两个动态数组 具体看代码。
class Solution: def minCostToMoveChips(self, position: List[int]) -> int: # 统计奇数和偶数的个数 取最小值 cnt = Counter(p % 2 for p in position) return min(cnt[0],cnt[1])- 1
- 2
- 3
- 4
- 5
1232. 缀点成线
题目链接：1232. 缀点成线
题目大意：给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。例如：
输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] 输出：true- 1
- 2
解题思路： 两点式方程求解 即可。
class Solution: def checkStraightLine(self, coordinates: List[List[int]]) -> bool: # y = k*x+c n = len(coordinates) if n == 2: return True x1,y1 = coordinates[0][0],coordinates[0][1] x2,y2 = coordinates[1][0],coordinates[1][1] if x1 == x2: if all(coordinates[i][0] == x1 for i in range(2,n)): return True else: return False else: k = (y1-y2)/(x1-x2) c = y1 - k*x1 # print(k,c) for i in range(2,n): x,y = coordinates[i][0],coordinates[i][1] if y != k*x+c: return False return True- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
1252. 奇数值单元格的数目
题目链接：1252. 奇数值单元格的数目
题目大意：给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。对 indices[i] 所指向的每个位置，应同时执行下述增量操作：- ri 行上的所有单元格，加 1 。
- ci 列上的所有单元格，加 1 。
- 给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。
例如：
输入：m = 2, n = 3, indices = [[0,1],[1,1]] 输出：6 解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。 第一次增量操作后得到 [[1,2,1],[0,1,0]]。 最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。- 1
- 2
- 3
- 4
- 5
解题思路： 子函数编写，制定好四个移动方向，计算一下就可以了，尽量减少使用for的次数，使用 while 循环可以提升一定是时间空间利用率。
class Solution: def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int: matrix = [[0 for _ in range(n)] for _ in range(m)] for x,y in indices: for j in range(n): matrix[x][j] += 1 for row in matrix: row[y] += 1 return sum(x%2 for row in matrix for x in row )- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
总结
加快进度，不多说了 下一篇就可以结束 数组部分了！ 努力，奋斗。
-
相关阅读:
C语言扫雷游戏完整实现(上)
思伟老友记 | 厦门路桥翔通海砼建材有限公司与思伟软件携手走过23年
Qt学习笔记NO2. QCustomPlot 学习使用笔记
KEIL5.39 5.40 fromelf 不能生成HEX bug
使用 PowerShell 将 Windows 转发事件导入 SQL Server
梯度消失和梯度爆炸问题详解
C++实现UDP可靠传输（二）
【超标量】分支预测的方向预测总结
Ubuntu22.04 vnc远程黑屏
深入理解Java线程间通信
- 原文地址：https://blog.csdn.net/weixin_42269028/article/details/126663591
