喀什网站建设百度推广,网络开发工程师,马尾区建设局网站,泉州企业做网站文章目录 78. 子集#xff08;集合的所有子集#xff09;90. 子集 II#xff08;集合的所有子集#xff09;792. 匹配子序列的单词数#xff08;判断是否为子集#xff09;500. 键盘行#xff08;集合的交集#xff09;409. 最长回文串#xff08;set#xff09; 更多… 文章目录 78. 子集集合的所有子集90. 子集 II集合的所有子集792. 匹配子序列的单词数判断是否为子集500. 键盘行集合的交集409. 最长回文串set 更多 leetcode 题解可参考【Programming】 78. 子集集合的所有子集
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集 思路可以迭代可以回溯 算 1 的子集的时候新增 1 结合 空集 算 2 的子集的时候2 结合 1 的所有子集 算 3 的子集的时候3 结合 2 的所有子集 …
class Solution(object):def subsets(self, nums)::type nums: List[int]:rtype: List[List[int]]result [[]]for i in nums:result.extend([j [i] for j in result])return result相似题目 1863. 找出所有子集的异或总和再求和 90. 子集 II集合的所有子集
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。 思路和 78 唯一不同的是 nums 可能包含一样的元素这个时候就会存在 [1,2] 和 [2,1] 或者更难一点的 [1,2,2] 和 [2,1,2] 的情况78 的解法这两个都会保留78中元素不一样但是这题只能保留其中一种 简单的 set 好像排除不了我用的是 sorted
class Solution(object):def subsetsWithDup(self, nums)::type nums: List[int]:rtype: List[List[int]]result [[]]for i in nums:result.extend([j [i] for j in result])set1 set(tuple(sorted(item)) for item in result) # tuple 才能 hash——setsorted 配合set来去重list1 list(list(item) for item in set1)# 转化成输出的格式return list1792. 匹配子序列的单词数判断是否为子集
给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例: 输入: S “abcde” words [“a”, “bb”, “acd”, “ace”] 输出: 3 解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。 注意:
所有在words和 S 里的单词都只由小写字母组成。 S 的长度在 [1, 50000]。 words 的长度在 [1, 5000]。 words[i]的长度在[1, 50]。
思路in 或者 find 都不能判断这种跨越的子集暴力法遍历了
class Solution(object):def numMatchingSubseq(self, S, words)::type S: str:type words: List[str]:rtype: intcount 0for item in words:i 0j 0flag 0while(ilen(S) and jlen(item)):if S[i] item[j]:i1j1if jlen(item):breakelse:i1if ilen(item) and item[j] not in S: # 根本不在S中就不浪费表情去一个一个滑动找了breakif j len(item):count1return count但是超时了字典树
class Solution(object):def numMatchingSubseq(self, S, words)::type S: str:type words: List[str]:rtype: intimport collectionswaiting collections.defaultdict(list)for w in words:waiting[w[0]].append(iter(w[1:]))for c in S:# print(c, c)# Python 字典 pop() 方法删除字典给定键 key 所对应的值返回值为被删除的值。key值必须给出。 否则返回default值。# 把所有以c开头的word都删除for it in waiting.pop(c, ()):# 如果这个word还有其他字母则与之前的合并否则放到None中表示该word能匹配waiting[next(it, None)].append(it)return len(waiting[None])500. 键盘行集合的交集
给定一个单词列表只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。 示例 输入: [“Hello”, “Alaska”, “Dad”, “Peace”] 输出: [“Alaska”, “Dad”] 注意 你可以重复使用键盘上同一字符。 你可以假设输入的字符串将只包含字母。
思路暴力法比较每一个字母是否在键盘的三行中
class Solution(object):def findWords(self, words)::type words: List[str]:rtype: List[str]s1 qwertyuiops2 asdfghjkls3 zxcvbnmresult []for word in words: # 遍历单词item set(word.lower())num1 0num2 0num3 0for i in item:if i in s1:num11elif i in s2:num21else:num31if num1len(item) or num2len(item) or num3len(item):result.append(word)return result还可以用集合的交集和三行的交集是否为本身是的话就表示该 string 是由一行键盘打出来的这样就不用两层循环了
class Solution(object):def findWords(self, words)::type words: List[str]:rtype: List[str]s1 qwertyuiops2 asdfghjkls3 zxcvbnmresult []for word in words: # 遍历单词if set(word.lower()) set(s1) set(word.lower()) or\set(word.lower()) set(s2) set(word.lower()) or \set(word.lower()) set(s3) set(word.lower()):result.append(word)return result拓展集合的并集 | 集合的差 - 409. 最长回文串set
给定一个包含大写字母和小写字母的字符串找到通过这些字母构造成的最长的回文串。
在构造过程中请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。 示例 1: 输入: “abccccdd” 输出: 7 解释: 我们可以构造的最长的回文串是dccaccd, 它的长度是 7。 思路先用 set 统计每个元素的数量偶数的可以直接算作回文串的子集奇数减1成偶数让其构成回文串子集如果元素数量是1减去后就为0最后输出结果把子集拼起来1 即可如果子集拼起来的长度和原字符串的长度相等就不用加1了
class Solution(object):def longestPalindrome(self, s)::type s: str:rtype: intset1 set(s)number_list []sum1 0for i in set1: # 统计每个元素的数量number_list.append(s.count(i))for i,j in enumerate(number_list): # 遍历数量偶数不变奇数减一if j % 2 1:number_list[i] - 1sum1 number_list[i]if sum11 len(s): # 这里避免bb 的情况return len(s)else:return sum11
