526互联

LeetCode|383. 赎金信

发布时间 2023-03-22 21:14:00作者: Weltㅤ

题目链接：383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

解题思路

字符统计

题目要求使用字符串 \(magazine\) 中的字符来构建新的字符串 \(ransomNote\)，且 \(ransomNote\) 中的每个字 符只能使用一次，只需要满足字符串 \(magazine\) 中的每个英文字母(’a’-’z’)的统计次数都大于等于 \(ransomNote\) 中相同字母的统计次数即可。

  • 如果字符串 magazine 的长度小于字符串 \(ransomNote\) 的长度，则我们可以肯定 magazine 无法构 成 \(ransomNote\)，此时直接返回 false。
  • 首先统计 magazine 中每个英文字母 \(a\) 的次数 \(cnt [a]\)， 再遍历统计 \(ransomNote\) 中每个英文字母 的次数，如果发现 \(ransomNote\) 中存在某个英文字母 \(c\) 的统计次数大于 \(magazine\)中该字母统计 次数 \(c n t[c]\) ，则此时我们直接返回 false。

Python中collections.Counter的用法

Python collections.Counter用法详解，Counter 计数器，顾名思义就是用来计数的，最主要的作用就是计算“可迭代序列中”各个元素（element）的数量。具体用法参看目录，基本涵盖了主要用法。

统计“可迭代序列”中每个元素的出现的次数

#首先引入该方法
from collections import Counter
对列表/字符串作用
#对列表作用
list_01 = [1,9,9,5,0,8,0,9] #GNZ48-陈珂生日
print(Counter(list_01)) #Counter({9: 3, 0: 2, 1: 1, 5: 1, 8: 1})

#对字符串作用
temp = Counter('abcdeabcdabcaba')
print(temp) #Counter({'a': 5, 'b': 4, 'c': 3, 'd': 2, 'e': 1})
#以上其实是两种使用方法，一种是直接用，一种是实例化以后使用,如果要频繁调用的话，显然后一种更简洁

以上其实是两种使用方法，一种是直接使用，一种是实例化以后使用，如果要频繁调用的话，显然后一种更简洁 ，因为可以方便地调用Counter内的各种方法。

对于其他可迭代序列也是一样的套路。

输出结果

#查看类型
print( type(temp) ) #<class 'collections.Counter'>

#转换为字典后输出
print( dict(temp) ) #{'b': 4, 'a': 5, 'c': 3, 'd': 2, 'e': 1}

for num,count in enumerate(dict(temp).items()):
print(count)
"""
('e', 1)
('c', 3)
('a', 5)
('b', 4)
('d', 2)
"""
用自带的items()方法输出

显然这个方法比转换为字典后再输出的方法更为方便。

print(temp.items()) #dict_items([('e', 1), ('c', 3), ('b', 4), ('d', 2), ('a', 5)])

for item in temp.items():
print(item)
"""
('a', 5)
('c', 3)
('d', 2)
('e', 1)
('b', 4)
"""

统计出现次数最多的元素

利用most_common()方法

#求序列中出现次数最多的元素

from collections import Counter

list_01 = [1,9,9,5,0,8,0,9]
temp = Counter(list_01)

#统计出现次数最多的一个元素
print(temp.most_common(1)) #[(9, 3)] 元素“9”出现3次。
print(temp.most_common(2)) #[(9, 3), (0, 2)] 统计出现次数最多个两个元素

#没有指定个数，就列出全部
print(temp.most_common()) #[(9, 3), (0, 2), (1, 1), (5, 1), (8, 1)]

elements()和sort()方法

关于elements()方法，官方的帮助文档是这样写的，Iterator over elements repeating each as many times as its count. 。

或许可以翻译为：按照元素出现次数迭代。所以用汉语比较难解释，直接看例子会比较方便了解。

from collections import Counter

c = Counter('ABCABCCC')
print(c.elements()) #<itertools.chain object at 0x0000027D94126860>

#尝试转换为list
print(list(c.elements())) #['A', 'A', 'C', 'C', 'C', 'C', 'B', 'B']

#或者这种方式
print(sorted(c.elements())) #['A', 'A', 'B', 'B', 'C', 'C', 'C', 'C']

#这里与sorted的作用是： list all unique elements，列出所有唯一元素
#例如
print( sorted(c) ) #['A', 'B', 'C']

一个来自官方文档的例子。

# Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1
prime_factors = Counter({2: 2, 3: 3, 17: 1})
product = 1
for factor in prime_factors.elements(): # loop over factors
product *= factor # and multiply them
print(product) #1836
#1836 = 2*2*3*3*3*17
注意，如果数量为“0”，或者是负值，则忽略。

计算元素总数/Keys()&Values()

from collections import Counter

c = Counter('ABCABCCC')
print(sum(c.values())) # 8 total of all counts

print(c.keys()) #dict_keys(['A', 'B', 'C'])
print(c.values()) #dict_values([2, 2, 4])

对具体元素的操作

查询单元素结果
from collections import Counter
c = Counter('ABBCC')
#查询具体某个元素的个数
print(c["A"]) #1
添加
for elem in 'ADD': # update counts from an iterabl
c[elem] += 1
print(c.most_common()) #[('C', 2), ('D', 2), ('A', 2), ('B', 2)]
#可以看出“A”增加了一个，新增了两个“D”
删除（del）
del c["D"]
print(c.most_common()) #[('C', 2), ('A', 2), ('B', 2)]
del c["C"]
print(c.most_common()) #[('A', 2), ('B', 2)]
更新（update）
d = Counter("CCDD")
c.update(d)
print(c.most_common()) #[('B', 2), ('A', 2), ('C', 2), ('D', 2)]
增加与减少（+-）

示例一

c['C'] -= 2
print(c.most_common())
# [('D', 2), ('A', 2), ('B', 2), ('C', 0)]
# 本来上面，C有两个，现在只有零个了，被减少了。

#注意官方文档的这句话
# If a count is set to zero or reduced to zero, it will remain in the counter until the entry is deleted or the counter is cleared
# 如果计数设置为零或减少为零，它将保留在计数器中，直到删除条目或清除计数器：

c['C'] += 1
print(c.most_common())
# [('D', 2), ('A', 2), ('B', 2), ('C', 1)]
# C又变成一个了。](javascript:void(0);)

示例二

print(Counter('AAB') + Counter('BCC'))
#Counter({'B': 2, 'C': 2, 'A': 2})
print(Counter("AAB")-Counter("BCC"))
#Counter({'A': 2})

subtract的“减”操作

subtract_test01 = Counter("AAB")
subtract_test01.subtract("BCC")
print(subtract_test01) #Counter({'A': 2, 'B': 0, 'C': -2})

这里的计数可以减到零一下，可以包含零和负数。

subtract_test02 = Counter("which")
subtract_test02.subtract("witch") #从另一个迭代序列中减去元素
subtract_test02.subtract(Counter("watch")) #^……

#查看结果
print( subtract_test02["h"] ) # 0 ,whirch 中两个，减去witch中一个，减去watch中一个，剩0个
print( subtract_test02["w"] ) #-1

“与”和“或”操作

print(Counter('AAB') & Counter('BBCC'))
#Counter({'B': 1})

print(Counter('AAB') | Counter('BBCC'))
#Counter({'A': 2, 'C': 2, 'B': 2})

Counter支持加减法的操作，将两个Counter相加，会自动将两个Counter合并，相同的key对应的value累加。相减也是同理，会将能对应的value做减法，被减的key对应不上的会保留，而减数中对应不上的key则会被丢弃。并且需要注意，Counter支持value为负数。

Python代码

import collections
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        c1 = collections.Counter(magazine)
        c2 = collections.Counter(ransomNote)
        return not c2-c1