LeetCode 每日一题 2022/9/19-2022/9/25

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

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

9/25