11.9 至 11.17 四道典型题记录： Counter 弹出 | map函数 | 子集求取 | 有序字符桶分装

11.9 至 11.17 四道典型题记录： Counter 弹出 | map函数 | 子集求取 | 有序字符桶分装

   昨天休息的时候一直在想应该学习哪种语言，我想这也是好多人发愁无法下手的原因之一，今年找工作的时候发现更多的研究岗位需要的是 C 语言 或 C++ 语言，而对于一些大型互联网企业则更喜欢 Java 语言，对于我而言，我更想做一些深度学习相关的工作，单纯地觉着这个行业有意思，能够支持我更长久的学习下去，虽然 搞电路和硬件设备的走得更稳定长久，不过对于我而言，我更相信学习新的、有趣的、更能激发自我动力的学科，其实没有那么多好犹豫的，想做什么就赶紧去做，不要想那么多，担忧焦虑最咩意思了！我现在就想学 py3 那就好好学，算法、计组、网络、操作系统 都会跟上脚步系统学习一下。不想了，学起来。
  本节主要是 关于py3的几个函数的使用以及个人认为非常不错的几道题的记录，一定要总结一下，就当复习了。
  部分代码借鉴他人，提前说一声，这并不都是我自己码出来的。~~

791. 自定义字符串排序 （Counter 弹出）

题目链接：791. 自定义字符串排序
题目大意：给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意一种排列 。

例如：

输入: order = "cba", s = "abcd"
输出: "cbad"
解释: 
“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。


输入: order = "cbafg", s = "abcd"
输出: "cbad"
1
2
3
4
5
6
7
8
9

• 解题思路：与 6230. 长度为 K 子数组中的最大和 的使用思路一样，需要灵活地将存储的数组进行存在元素的判断。
• 时间复杂度： $O(M+N)$ ，其中 M 和 N 分别是字符串 order 和 s 的长度。
• 空间复杂度： $O(M)$

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        cnt = collections.Counter(s)
        ans = ""
        for ch in order:
            if ch in s:
                ans += ch *cnt[ch]
                cnt.pop(ch)
        tmp = ""
        for ch in s:
            if ch not in ans:
                tmp += ch
        # print(ans,tmp)
        return ans+tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

764. 最大加号标志 map函数（灵活运用 dmap函数）

题目链接：764. 最大加号标志 map函数
题目大意：
在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

例如：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

1
2
3
4
5
6
7
8

• 解题思路：遍历 题目，使用动态数组继续每个点的数据记录，进行四次for循环记录满足要求的1的最小个数。需要自左向右，自右向左、自上而下以及自下而上的四次遍历，确定最小的 十字。代码中用到两次 map，非常地有趣，简单说一下：
  （1）anned = set(map(tuple,mines)) 将mines的内容转换为元素 tuple 之后使用set()函数进行去重操作 ，map 在这里可以充当数据类型转换的作用；
  （2） max(map(max,dp)) map()的存在让此语句更容易梳理一些，其实可以写成max([max(dp[i,:]) for i in range(len(dp))]) 。
• 时间复杂度：$O(N^2)$ ，N为矩阵的行数或列数
• 空间复杂度：$O(N^2)$

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        # map 函数 非常值得学习！！！
        dp = [[n]*n for _ in range(n)]
        banned = set(map(tuple,mines))
        # print(banned)
        for i in range(n):
            # left
            cnt = 0
            for j in range(n):
                cnt = 0 if (i,j) in banned else cnt+1
                dp[i][j] = min(dp[i][j],cnt)
            # right
            cnt = 0
            for j in range(n-1,-1,-1):
                cnt = 0 if (i,j) in banned else cnt+1
                dp[i][j] = min(dp[i][j],cnt)
        for j in range(n):
            # up
            cnt = 0
            for i in range(n):
                cnt = 0 if (i,j) in banned else cnt+1
                dp[i][j] = min(dp[i][j],cnt) 
            # down
            cnt=0
            for i in range(n-1,-1,-1):
                cnt = 0 if (i,j) in banned else cnt+1
                dp[i][j] = min(dp[i][j],cnt)
        return max(map(max,dp))
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

 

805. 数组的均值分割 子集求取（map巧用非常好地一个用法 值得学习！）

题目链接：805. 数组的均值分割 子集求取
题目大意：给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，
使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
如果可以完成则返回true ， 否则返回 false 。
注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

输入: nums = [3,1]
输出: false
1
2
3
4
5
6

• 解题思路：位运算获取子数组和 思路如下：
  • 对于 nums = [1,2], i 从 1到3
  • i = 01 则为 nums[0] = 1
  • i= 10 则为 nums[1] = 2
  • i= 11 则为 nums[0]+nums[1] = 3。
• 时间复杂度：$O(n\times 2^{\frac{n}{2}})$，n为数组长度
• 空间复杂度：$O(n\times 2^{\frac{n}{2}})$

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        # 折半查找法
        n = len(nums)
        if n==1: return False
        s = sum(nums)
        for i in range(n):
            nums[i] = nums[i]*n-s 
        m = n//2
        # print(1<
        left = set()
        for i in range(1,1<<m):
            # i>>j&1 把 i 算术右移 j 位，然后检测最低位是否为1
            tot = sum(x for j,x in enumerate(nums[:m]) if i>>j&1)
            if tot==0: return True
            left.add(tot)
        rsum = sum(nums[m:])
        for i in range(1,1<<(n-m)):
            tot = sum(x for j,x in enumerate(nums[m:]) if i>>j&1)
            if tot==0 or (rsum != tot and -tot in left):
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

792. 匹配子序列的单词数（有序字符桶分装）

题目链接：792. 匹配子序列的单词数
题目大意：
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
例如， “ace” 是 “abcde” 的子序列。

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2
1
2
3
4
5
6

• 解题思路：细细品味，这道题 太 tm 棒了，这个 桶 真滴香。
• 时间复杂度：$O(n+{\sum }_{i=0}^{m-1}|w_i|)$，n和m分别为s和words的长度，$O(w_i)$为words[i]的长度。
• 空间复杂度：$O(m)$

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        d = collections.defaultdict(deque)
        ans = 0
        for i,w in enumerate(words):
            d[w[0]].append((i,0))
        for ch in s:
            for _  in range(len(d[ch])):
                i,j = d[ch].popleft()
                j += 1
                if j == len(words[i]):
                    ans += 1
                else:
                    d[words[i][j]].append((i,j))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

   努力 奋斗！最近学一下 粤语 背一下 张国荣哥哥的歌曲，感觉 他的歌 好棒好棒，好有力量！像“默默向上游”的”现实欺弄不担忧，我要与他决斗，挺着胸对抗命运，努力握实我拳头“、“我愿那苦痛变力量，默默忍泪向上游”，让我感觉到一种前所未有的力量在里面，和 迈克杰克逊的洒脱率真不一样，张国荣哥哥有一种不服输、抗争、顽强不屈的精神在其中，他要把事情做好、做到极致，他爱自己的事业、爱自己的人生，要全身心地去做、去努力，正如歌曲中的“求能用心”、“求能用功”、“求能做个好鼓手”。我要学习，要继续努力，“努力不会有极限”，“若遇失败再重头”。这算法不好学，那就更用心、更用功，我还就不信有学不会的！