2020年11月刷题日志

class Solution:
    def reorganizeString(self, S: str) -> str:
        dic = dict()
        for i in S:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
            if dic[i] > (len(S)+1)//2:
                return ""
        inds = list(set(S))
        inds.sort(key = lambda x:dic[x])
        res = [0 for i in range(len(S))]
        index = 1
        for i in inds:
            cnt = dic[i]
            char = i
            for j in range(cnt):
                if index>=len(S):
                    index = 0
                res[index] = char
                index += 2
        return "".join(res)

class Solution:
    def largestPerimeter(self, A: List[int]) -> int:
        A.sort()
        n = len(A)
        for i in range(n-3,-1,-1):
            if A[i+2]>=A[i+1]+A[i]:
                continue
            else:
                return A[i]+A[i+1]+A[i+2]
        return 0

class Solution:
    def find_pairs(self, nums, left, right):
        # 计算可用对数
        # 假设nums[left:mid]和nums[mid+1:right]都是升序排列
        res, mid = 0, (left+right)//2
        # 利用双指针去计算当前可以有多少个匹配项
        j = mid+1
        for i in range(left, mid+1):
            while j<=right and nums[i]>2*nums[j]:
                # 当右边找到的数比左边的数两倍还大的时候
                # 说明左边数组i位置和剩下的数字都可以和j自称翻转对
                # 那就加上这么多对,继续考虑j之后的数字
                res += mid-i+1
                j += 1
            # 当j对应的数字太大了,说明需要增加i对应的数字的大小
        return res
    def merge_sort(self, nums, nums_sorted, l, r):
        if l>= r:
            return 0
        mid = (l+r)//2
        # 每次递归的值就是左数组中的翻转对+右数组中的翻转对+两个数组中交叉的翻转对
        res = self.merge_sort(nums, nums_sorted, l, mid)+self.merge_sort(nums, nums_sorted, mid+1, r)+self.find_pairs(nums, l, r)
        # 接下来进行归并排序,把左数组和右数组合并成有序的数组
        i, j, k = l, mid+1, l
        while i<= mid and j<= r:
            if nums[i]<=nums[j]:
                nums_sorted[k] = nums[i]
                i += 1
            else:
                nums_sorted[k] = nums[j]
                j += 1
            k += 1

        while i<=mid:
            nums_sorted[k] = nums[i]
            i += 1
            k += 1
        while j<= r:
            nums_sorted[k] = nums[j]
            j += 1
            k += 1
        for k in range(l, r+1):
            nums[k] = nums_sorted[k]
        
        return res
    def reversePairs(self, nums: List[int]) -> int:
        # 归并排序解决问题
        if not nums:
            return 0
        nums_sorted = [0] * len(nums)
        return self.merge_sort(nums, nums_sorted, 0, len(nums)-1)

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        dic1, dic2 = dict(), dict()
        # A和B可能的和存入dic1中，C和D可能的和存入dic2中
        n = len(A)
        for i in range(n):
            for j in range(n):
                a, b, c, d = A[i], B[j], C[i], D[j]
                if a+b in dic1:
                    dic1[a+b] += 1
                else:
                    dic1[a+b] = 1
                if c+d in dic2:
                    dic2[c+d] += 1
                else:
                    dic2[c+d] = 1
        res = 0
        for i in dic1.keys():
            if -i in dic2:
                res += dic1[i]*dic2[-i]
        return res
        

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        # 利用桶排序解题
        if len(nums)<2:
            return 0
        # 首先确定桶的长度，每个桶都是等间距
        buckt_len = max(1, (max(nums)-min(nums))//(len(nums)-1))
        # 最多可能要把数字放到这么多个桶中
        buckt_num = (max(nums)-min(nums))//buckt_len+1
        buckets = [[] for i in range(buckt_num)]
        # 然后把所有的数字放到桶中
        min_num = min(nums)
        for num in nums:
            buckets[(num-min_num)//buckt_len].append(num)
        # 然后计算相邻非空桶之间的最大差值
        prev = min_num
        res = 0
        for bucket in buckets:
            if not bucket:
                continue
            res = max(res, min(bucket)-prev)
            prev = max(bucket)
        return res

class Solution:
    def sortString(self, s: str) -> str:
        dic = dict()
        for i in set(s):
            dic[i] = s.count(i)
        keys = sorted(list(set(s)))
        res = ""
        cnt = len(s)
        while cnt>0:
            for key in keys:
                if dic[key]>0:
                    res += key
                    dic[key] -= 1
                    cnt -= 1
            for key in keys[::-1]:
                if dic[key]>0:
                    res += key
                    dic[key] -= 1
                    cnt -= 1
        return res

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        def exist(root, level, mid):
            bits, node = 1 << (level-1), root
            while node and bits>0:
                if bits&mid:
                    node = node.right
                else:
                    node = node.left
                bits>>=1
            return node
        level = 0
        node = root
        while node and node.left:
            node, level = node.left, level+1
        low, high = 1<<level, (1<<(level+1)) -1
        mid = 0
        while low<high:
            mid = (high-low+1)//2 + low
            if exist(root, level, mid):
                low = mid
            else:
                high = mid-1
        return min(low, mid)

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 按照气球结束坐标的大小排序
        points.sort(key = lambda x:x[1])
        cnt = 1
        length = len(points)
        if length<1:
            return 0
        left, right = points[0]
        i = 1
        while i<len(points):
            cur_left, cur_right = points[i]
            if cur_left>right:
                cnt += 1
                left,right = cur_left, cur_right
            else:
                left = max(cur_left, left)
            i += 1
        return cnt

from collections import defaultdict
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic_s, dic_t = defaultdict(int), defaultdict(int)
        if len(s) != len(t):
            return False
        for i in range(len(s)):
            dic_s[s[i]] += 1
            dic_t[t[i]] += 1
        return dic_s == dic_t

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 首先用快慢指针将链表分成两段
        if not head or not head.next:
            return head
        slow,fast=head,head.next
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        # 此时slow指向中间结点或者是前半部分的最后一个结点
        tmp = slow.next
        slow.next = None
        # 将前后段链表进行排序
        left, right = self.sortList(head), self.sortList(tmp)
        dummy = ListNode(0)
        new_head = dummy
        # 利用双指针合并两个有序链表
        while left and right:
            if left.val<right.val:
                new_head.next = left
                left = left.next
            else:
                new_head.next = right
                right = right.next
            new_head = new_head.next
        if left:
            new_head.next = left
        else:
            new_head.next = right
        return dummy.next        

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        cur_node = head.next
        last_node = head
        while cur_node:
            if cur_node.val>=last_node.val:
                last_node  = last_node.next
            else:
                prev = dummy
                while prev.next.val<cur_node.val:
                    prev = prev.next
                last_node.next = cur_node.next
                cur_node.next = prev.next
                prev.next = cur_node
            cur_node = last_node.next
        return dummy.next

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, j = 0, 0
        while j<len(nums):
            if nums[j]!=0:
                nums[i] = nums[j]
                i += 1
            j += 1
        for k in range(i, len(nums)):
            nums[k] = 0
    

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        diffs = []
        for i in range(len(gas)):
            diffs.append(gas[i]-cost[i])
        # 找到一段累加和一直为0的一段序列
        start = 0
        while start<len(diffs):
            tmp = 0
            for i in range(len(diffs)):
                index = (start+i)%len(diffs)
                tmp += diffs[index]
                if tmp<0:
                    start = start + i + 1
                    break
            else:
                return start
        return -1

class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        res= []
        for i in range(R):
            for j in range(C):
                res.append([i,j])
        res.sort(key = lambda x: (abs(x[0]-r0)+abs(x[1]-c0)))
        return res

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 首先将所有人按身高的从低到高排序
        people.sort(key = lambda x: (x[0], -x[1]))
        length = len(people)
        res = [0 for i in range(length)]
        for person in people:
            # 找空插入这个人
            space = person[1]+1
            for i in range(length):
                if not res[i]:
                    space -= 1
                    if space == 0:
                        res[i] = person
        return res

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        nums = []
        for i in num:
            while nums and i<nums[-1] and k:
                nums.pop()
                k-=1
            nums.append(i)
        
        if k>0:
            nums = nums[:-k]
        return ''.join(nums).lstrip('0') or "0"

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        dic = dict()
        # 第一遍遍历arr1 统计每个元素的出现次数
        for i in arr1:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        res = []
        # 第一遍遍历arr2 输出对应元素
        for i in arr2:
            res += dic[i]*[i]
            dic[i] = 0
        # 第二遍遍历arr1 输出未在arr2中出现的元素
        tmp = []
        for i in arr1:
            if dic[i]>0:
                tmp.append(i)
        return res+sorted(tmp)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        odd = head
        even = head.next
        even_head = head.next
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        res = []
        tmp1, tmp2 = [], []
        for i in A:
            if i%2==1:
                tmp1.append(i)
            else:
                tmp2.append(i)
        for i in range(len(tmp1)):
            res+=[tmp2[i], tmp1[i]]
        return res

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        dic = dict()
        # 首先初始化字典，把每种字母转换成一个字典
        for word in set(list(ring)):
            # dic['a'] = {a出现的第一个位置: 0, a出现的第二个位置: 0...}
            tmp = dict()
            for i in range(len(ring)):
                if ring[i] == word:
                    tmp[i] = 0
            dic[word] = tmp
        # 然后根据当前的字典去找最短路
        last_word = ring[0]
        head = True
        for word in key:
            # 每次更新dic[word]对应的字典
            for i in dic[word].keys():
                min_dis = float("inf")
                target = i
                for j in dic[last_word].keys():
                    start = j
                    last_dis = dic[last_word][j]
                    if head:
                        start = 0
                    # 正向走到对应字母所需要的距离
                    foward_dis  = abs(start-target)
                    # 逆向
                    backword_dis = len(ring)-foward_dis
                    min_dis = min(min_dis,backword_dis+last_dis, foward_dis+last_dis)
                dic[word][i] = min_dis+1
            head = False
            last_word = word
        return min(dic[key[-1]].values())

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums)-2
        # 从后往前找需要交换的小数
        while i>=0 and nums[i]>nums[i+1]:
            i -= 1
        # 此时nums[i+1:]都是降序 且num[i]<nums[i+1]
        # i位置的数就是我们要找的小数
        # 从后往前找 找到尽可能小的大数
        if i>=0:
            j = len(nums)-1
            while j>=0 and nums[i]>=nums[j]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 将小数后面进行升序排列
        left = i+1
        right = len(nums)-1
        while left<right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key = lambda x:x[0]**2+x[1]**2)
        return points[:K]

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        res = []
        for i in range(K):
            x,y = points[i]
            res.append((-x**2-y**2,i))
        heapq.heapify(res)
        for i in range(K,len(points)):
            x,y = points[i]
            dis = -x**2-y**2
            if dis>res[0][0]:
                heapq.heappushpop(res, (dis, i))
        return [points[i[1]] for i in res]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 动态规划
        dp0, dp1 = 0, -prices[0]
        # 用两个变量来存储某一天手中无股票和手中有股票时的最大利润
        for price in prices:
            dp0 = max(dp1+price, dp0)
            dp1 = max(dp1, dp0-price)
        return dp0

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def countOne(num):
            return (bin(num).count('1'), num)
        arr.sort(key = countOne)
        return arr

from collections import deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if len(word_set)==0 or endWord not in word_set:
            return 0
        if beginWord in word_set:
            word_set.remove(beginWord)
        visited = set()
        visited.add(beginWord)
        visited.add(endWord)
        begin_visited = set()
        begin_visited.add(beginWord)
        end_visited = set()
        end_visited.add(endWord)

        word_len = len(beginWord)
        step = 1
        while begin_visited:
            if len(begin_visited) > len(end_visited):
                begin_visited, end_visited = end_visited, begin_visited
            next_level_visited = set()
            for word in begin_visited:
                word_list = list(word)
                for j in range(word_len):
                    origin_char = word_list[j]
                    for k in range(26):
                        word_list[j] = chr(ord('a')+k)
                        next_word = ''.join(word_list)
                        if next_word in word_set:
                            if next_word in end_visited:
                                return step+1
                            if next_word not in visited:
                                next_level_visited.add(next_word)
                                visited.add(next_word)
                    word_list[j] = origin_char
            begin_visited = next_level_visited
            step+=1
        return 0

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals)==0:
            return [newInterval]
        tmp = []
        new_left, new_right = newInterval[0], newInterval[1]
        if new_right<intervals[0][0]:
            return [newInterval]+intervals
        if new_left>intervals[-1][1]:
            return intervals+[newInterval]
        flag = False
        for i in range(len(intervals)):
            left, right = intervals[i][0], intervals[i][1]
            if new_left<=left and new_right>=right:
                # 第一种情况newInterval包含了[left, right]
                tmp.append(newInterval)
                flag = True
            elif left<=new_left and right>=new_right:
                tmp.append(intervals[i])
                flag = True
            elif new_left<=right and new_right>=right:
                tmp.append([left, new_right])
                flag = True
            elif new_left<=left and new_right>=left:
                tmp.append([new_left, right])
                flag = True
            else:
                tmp.append(intervals[i])
        if not flag:
            # 说明没插入
            for i in range(len(tmp)-1):
                if tmp[i+1][0]>new_right:
                    tmp = tmp[:i+1]+[newInterval]+tmp[i+1:]
        # 合并有重叠的数组
        if len(tmp) == 1:
            return tmp
        ans = []
        i = 0
        while i<len(tmp)-1:
            left1, right1 = tmp[i]
            left2, right2 = tmp[i+1]
            if right1<left2:
                ans.append(tmp[i])
            else:
                while i<len(tmp)-1 and tmp[i+1][0]<=right1:
                    i += 1
                # 这个时候找到了需要合并的右边界
                ans.append([left1,tmp[i][1]])
            i += 1
            if i==len(tmp)-1:
                ans.append(tmp[-1])
                break
        return ans

class Solution:
    def validMountainArray(self, A: List[int]) -> bool:
        if len(A)<3:
            return False
        prev = A[0]-1  # 用来记录经过的上一个数
        flag = 0  # 用来记录是否已经翻过山峰
        for i in A:
            if flag==0 and i>prev:
                prev = i
            elif flag==0 and i<prev and i!=A[0]-1:
                flag = 1
                prev = i
            elif flag == 1 and i<prev:
                prev = i
            else:
                return False
        if flag == 1:
            return True
        else:
            return False

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1)>len(nums2):
            nums1, nums2 = nums2, nums1
        ans = []
        for i in set(nums1):
            if i in nums2:
                ans.append(i)
        return ans