本文共 3875 字,大约阅读时间需要 12 分钟。
nums1 = [1,2,2,1]nums2 = [2,2]#返回[2,2]
哈希是一种查找算法
from collections import Counterfrom collections import defaultdict #不存在的key时 返回默认值from collections import OrderedDict
nums1 = [1,2,2,1]
nums2 = [2,2]#返回[2,2]
from collections import defaultdictdef insersect(nums1,nums2): dic = defaultdict(int) for i in nums1: dic[i]+=1 result =[] for j in nums2: if dic[j]>0: result.append(j) dic[j]-=1 return result
J = 'aA'#宝石
S = 'aAAbbbb' #输出 3def numJewinStone(J,S): setJ = set(J) return sum(s in setJ for s in S)
3.两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
#forloopclass Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): num2 = target - nums[i] for j in range(i+1,len(nums)): if num2 == nums[j]: return [i,j]
#哈希def twoSum(nums,target): dic = {} for i in range(len(nums)): m = nums[i] if target - m in dic: return ([dic[target - m],i]) dic[m] = i
你正在和你的朋友玩 猜数字(Bulls and Cows)游戏:你写下一个数字让你的朋友猜。每次他猜测后,你给他一个提示,告诉他有多少位数字和确切位置都猜对了(称为“Bulls”, 公牛),有多少位数字猜对了但是位置不对(称为“Cows”, 奶牛)。你的朋友将会根据提示继续猜,直到猜出秘密数字。
示例 1:输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8,奶牛是 0, 1 和 7。
class Solution: def getHint(self, secret: str, guess: str) -> str: secret_dict = {} guess_dict = {} A= 0 B = 0 for i in range(len(secret)): if secret[i] == guess[i]: A += 1 else : if secret[i] in secret_dict: secret_dict[secret[i]] += 1 else: secret_dict[secret[i]] = 1 if guess[i] in guess_dict: guess_dict[guess[i]] +=1 else: guess_dict[guess[i]] =1 for digit in secret_dict: if digit in guess_dict : B += min(secret_dict[digit],guess_dict[digit]) return str(A)+"A" + str(B) +"B"
在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。
现在,给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。
你需要输出替换之后的句子。
输入: dict(词典) = ["cat", "bat", "rat"] sentence(句子) = "the cattle was rattled by the battery"输出: "the cat was rat by the bat"
#暴力破解法class Solution: def replaceWords(self, dict: List[str], sentence: str) -> str: s = sentence.split(' ') for item in dict : for i in range(len(s)):#i=1 s[1] = the n = len(item)#cat 3 if item ==s[i][:n]: s[i] = item return ' '.join(s)
from collections import defaultdictdef replaceWords(dict,sentence): d = defaultdict(set) s = defaultdict(int) sentense = sentence.split() for w in dict: print(w[0]) d[w[0]].add(w) s[w[0]] = max(s[w[0]],len(w)) for i ,w in enumerate(sentence): for j in range(s[w[0]]): if w[:j+1] in d[w[0]]: sentense[i] = w[:j+1] break return ' '.join(sentence)
6 leetcode3. 无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
输入: "pwwkew"
输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。from collections import defaultdictclass Solution: def lengthOfLongestSubstring(self, s: str) -> int: lookup = defaultdict(int) start = 0 end = 0 max_len = 0 counter = 0 while end < len(s): if lookup[s[end]] > 0: counter += 1 lookup[s[end]] += 1 end += 1 while counter > 0: if lookup[s[start]] > 1: counter -= 1 lookup[s[start]] -= 1 start += 1 max_len = max(max_len, end - start) return max_len
转载地址:http://qhrii.baihongyu.com/