LeetCode Cookbook 数组习题（8）

  加把劲，再写两篇九八数组部分给拿下了！ come on.

1002. 查找共用字符

题目链接：1002. 查找共用字符
题目大意：给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

例如：

输入：words = ["bella","label","roller"]
输出：["e","l","l"]

解题思路：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})

• 使用 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

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) 是不允许的。 

解题思路：

• 和 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

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 处的学生高度不匹配

解题思路：按着思路照做就成。

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

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]

解题思路： 看我的这篇题解 —— 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

(二）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() 

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

解题思路： 从 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

（二）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

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

解题思路 线段树，非常难记的代码结构。

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

1160. 拼写单词 *

题目链接：1160. 拼写单词
题目大意： 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和。

例如：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

解题思路： 使用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

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")。

解题思路：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

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。

解题思路： 方向考虑，充分利用数组和。

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)

1185. 一周中的第几天

题目链接：1185. 一周中的第几天
题目大意：给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。输入为三个整数：day、month 和 year，分别表示日、月、年。您返回的结果必须是这几个值中的一个 {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}。

例如：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

解题思路： 注意 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] 

1200. 最小绝对差

题目链接：1200. 最小绝对差
题目大意：给你个整数数组 arr，其中每个元素都 不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。每对元素对 [a,b] 如下：

• a , b 均为数组 arr 中的元素
• a < b
• b - a 等于 arr 中任意两个元素的最小绝对差

例如：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

解题思路： 很巧妙的动态规划题目，非常灵活，需要在不断比较重确定最小绝对差，而后找到符合要求的组合。

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

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。

解题思路： 典型动态规划的题目，设置 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])

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

解题思路： 两点式方程求解 即可。

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

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 个奇数。

解题思路： 子函数编写，制定好四个移动方向，计算一下就可以了，尽量减少使用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 )

总结

  加快进度，不多说了 下一篇就可以结束 数组部分了！ 努力，奋斗。