记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
6/30 594. 最长和谐子序列
m记录每一个数字出现的次数
l记录去重后从小到大排序的所有数字
def findLHS(nums):
"""
:type nums: List[int]
:rtype: int
"""
from collections import defaultdict
m = defaultdict(int)
l = list(set(nums))
l.sort()
for num in nums:
m[num]+=1
ans = 0
for i in range(len(l)-1):
if l[i]+1==l[i+1]:
v = m[l[i]]+m[l[i+1]]
ans = max(ans,v)
return ans
7/1 3330. 找到初始输入字符串 I
如果当前位置字符串和之前的一样 那么有可能是多打的
def possibleStringCount(word):
"""
:type word: str
:rtype: int
"""
ans=1
for i in range(1,len(word)):
if word[i]==word[i-1]:
ans+=1
return ans
7/2 3333. 找到初始输入字符串 II
计算不考虑k的限制可以有多少情况
再减去小于k的情况即可
def possibleStringCount(word, k):
"""
:type word: str
:type k: int
:rtype: int
"""
from itertools import accumulate
MOD=10**9+7
n=len(word)
if n<k:
return 0
ans = 1
cnt = 0
cnts=[]
for i in range(n):
cnt +=1
if i==n-1 or word[i]!=word[i+1]:
if cnt>1:
if k>0:
cnts.append(cnt-1)
ans = ans*cnt%MOD
k-=1
cnt=0
if k<=0:
return ans
f=[[0]*k for _ in range(len(cnts)+1)]
f[0]=[1]*k
for i,c in enumerate(cnts):
s=list(accumulate(f[i],initial=0))
for j in range(k):
f[i+1][j]=(s[j+1]-s[max(j-c,0)])%MOD
return (ans-f[-1][-1])%MOD
7/3 3304. 找出第 K 个字符 I
长度从1->2->4->8…
对于位置k的字符 可以通过k-1的二进制中1的个数来判断从起始位置变化了几次
def kthCharacter(k):
"""
:type k: int
:rtype: str
"""
k-=1
ans=0
while k:
ans+= k%2
k=k//2
return chr(ord('a')+ans)
7/4 3307. 找出第 K 个字符 II
计算能够得到k个字符需要操作的次数
如果第i次操作 和k相关的字符在字符串右半侧 那么需要增加operations[i]
def kthCharacter(k, operations):
"""
:type k: int
:type operations: List[int]
:rtype: str
"""
m=(k-1).bit_length()
add=0
for i in range(m-1,-1,-1):
if k> 1<<i:
add+=operations[i]
k-=1<<i
return chr(ord('a')+add%26)
7/5 1394. 找出数组中的幸运数
统计每个数出现的次数 寻找幸运数
def findLucky(arr):
"""
:type arr: List[int]
:rtype: int
"""
from collections import defaultdict
m=defaultdict(int)
for num in arr:
m[num]+=1
ans=-1
for v in m:
if v==m[v]:
ans=max(ans,v)
return ans
7/6 1865. 找出和为指定值的下标对
nums1不变 即找到nums2中值为tot-val的数量
class FindSumPairs(object):
from collections import defaultdict
def __init__(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
"""
self.m=defaultdict(int)
self.nums1=nums1
self.nums2=nums2
for num in nums2:
self.m[num]+=1
def add(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
self.m[self.nums2[index]]-=1
self.nums2[index]+=val
self.m[self.nums2[index]]+=1
def count(self, tot):
"""
:type tot: int
:rtype: int
"""
ans=0
for x in self.nums1:
ans+=self.m[tot-x]
return ans