|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
9/19 1636. 按照频率将数组升序排序
counter统计个数 排序
def frequencySort(nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
from collection import Counter
cnt = Counter(nums)
nums.sort(key=lambda x:(cnt[x],-x))
return nums
9/20 698. 划分为k个相等的子集
求总和 如果无法被k整除 则不能分割
如果能被分割 每组总和为m
回溯 cur记录每个数是否被使用
def canPartitionKSubsets(nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
n = len(nums)
s = sum(nums)
if s%k>0:
return False
m = s//k
if max(nums)>m:
return False
nums.sort()
cur = (1<<len(nums))-1
mem = {}
print(nums,m)
def find(cur,v):
if (cur,v) in mem:
return mem[(cur,v)]
if cur==0:
return True
for i in range(n):
if nums[i]+v>m:
break
if (cur>>i) &1 and find(cur^(1<<i),(v+nums[i])%m):
print(nums[i])
mem[(cur,v)]=True
return True
mem[(cur,v)]=False
return False
return find(cur,0)
9/21 854. 相似度为 K 的字符串
长度只有20 bfs
def kSimilarity(s1, s2):
"""
:type s1: str
:type s2: str
:rtype: int
"""
step = 0
n = len(s1)
q = [(s1,0)]
mem = {s1}
while q:
tmp = []
for s,i in q:
if s==s2:
return step
while i<n and s[i]==s2[i]:
i+=1
for j in range(i+1,n):
if s[j]==s2[i] and s[j]!=s2[j]:
t = list(s)
t[i],t[j] = t[j],t[i]
t = "".join(t)
if t not in mem:
mem.add(t)
tmp.append((t,i+1))
step+=1
q = tmp
9/22 1640. 能否连接形成数组
使用map 记录pieces中每个数组开头数值和其位置
遍历arr 找到开头值和其位置一一比较
def canFormArray(arr, pieces):
"""
:type arr: List[int]
:type pieces: List[List[int]]
:rtype: bool
"""
m = {}
for i,p in enumerate(pieces):
m[p[0]] = i
loc = 0
n = len(arr)
while loc<n:
v = arr[loc]
if v in m:
idx = m[v]
l = pieces[idx]
print(v,l)
if arr[loc:loc+len(l)]!=l:
return False
loc += len(l)
else:
return False
return True
9/23 707. 设计链表
单链表
class Node(object):
def __init__(self,val):
self.val = val
self.next = None
class MyLinkedList(object):
def __init__(self):
self.len = 0
self.head = Node(0)
def get(self, index):
"""
:type index: int
:rtype: int
"""
if index<0 or index>=self.len:
return -1
cur = self.head
for _ in range(index+1):
cur = cur.next
return cur.val
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(0,val)
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
self.addAtIndex(self.len,val)
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index > self.len:
return
index = max(0,index)
self.len +=1
pre = self.head
for _ in range(index):
pre = pre.next
tmp = Node(val)
tmp.next = pre.next
pre.next = tmp
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if index<0 or index>=self.len:
return
self.len-=1
pre = self.head
for _ in range(index):
pre = pre.next
pre.next = pre.next.next
9/24 1652. 拆炸弹
三种情况分别判断
def decrypt(code, k):
"""
:type code: List[int]
:type k: int
:rtype: List[int]
"""
n = len(code)
ans = [0]*n
if k>0:
cur = sum(code[:k])
for i in range(n):
cur = cur-code[i]+code[(k+i)%n]
ans[i] = cur
elif k<0:
cur = sum(code[n+k:])
for i in range(n):
ans[i] = cur
cur = cur+code[i]-code[(n+k+i)%n]
return ans
9/25
|