Skip to content

Latest commit

 

History

History
597 lines (477 loc) · 23.6 KB

recording.md

File metadata and controls

597 lines (477 loc) · 23.6 KB
Raw

该 readme 用于每天记录 做了哪些题

4/21/2022

4/22/2022

4/23/2022

4/24/2022

4/25/2022

4/28/2022

Binary 专题

May 9th

May 10th

May 11th palindrome

output

May 13th （快慢双指针）double pointer

May 18th （左右双指针）double pointer

May 19th （前缀和）rangesum

May 20th （前缀和）rangesum

May 21st (difference array)

May 22nd (sliding window)

May 24th (特殊二分查找) 需要自己设定 Binary

Mays 25th (接着前一天 还是抽象二分)，但我感觉这题用 dp 也能做 Binary

May 26th (打家劫舍 其实还是 dp 的 table 和 memo) DP

May 27th-May31st (我在摸鱼) 股票问题本质还是多维的 DP table

June 27 复习 二叉搜索树

June 28 复习 DP

June 29 新做

June 30

  • https://leetcode.cn/problems/implement-queue-using-stacks/ 需要两个 stack。
    peek 查看队头的元素怎么办呢？按道理队头元素应该是 1， 但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了： 当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。 https: // leetcode.cn/problems/implement-stack-using-queues/

  • 一个 queue 就行 需要一个 记录栈顶元素(也就队尾元素) push API，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话可以直接返回：

  • 底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop API 要从队尾取元素.解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了.原来的队尾元素被提到队头并删除了，但是 top_elem 变量没有更新.等到在新的队尾元素到对头的时候停止 while 循环，赋值新的 top_element。然后再继续 append https://leetcode.cn/problems/min-stack/ 利用两个栈

    def __init__(self):
        self.stk = deque()
        self.minstk = deque()  # 定义很特别从某元素到栈底的最小元素

下面都是 queue 的题目

July 1st

July 2st

July 3st

July 4th

July 5th

July 13rd

16 th https://leetcode.cn/problems/search-in-rotated-sorted-array/ 这是一道好题目 第一题做这个 21st

21st

22nd

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        start_list=[]
        end_list=[]
        n=len(intervals)
        for i in range(n):
            start_list.append(intervals[i][0])
            end_list.append(intervals[i][1])
        count=0
        start_list=sorted(start_list)
        end_list=sorted(end_list)
        s=e=0
        available=numroom=0
        while s<len(start_list):
            if start_list[s]<end_list[e]:
                if available==0:
                    numroom+=1
                else:
                    available-=1
                s+=1
            else:
                available+=1
                e+=1
        return numroom

heap

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        freerooms=[]
        intervals.sort(key=lambda x:x[0])
        print(intervals)
        heapq.heappush(freerooms,intervals[0][1])
        for i in range(1,len(intervals)):
            if freerooms[0]<=intervals[i][0]:
                heapq.heappop(freerooms)
            heapq.heappush(freerooms,intervals[i][1])
        return len(freerooms)

23th

Gonna do following questions https://leetcode.com/company/amazon/

What difference between subarray, subset, and substring? Basically, subarray(substring) has order and continuity, but subset doesn't. For example: nums = [1, 2, 3] The subarray of nums is: [1], [1,2], [1,2,3], [2], [2,3], [3]. The subset of nums is: [1], [1,2], [1,2,3], [2], [2,3], [3], [1,3]. <- The order doesn't matter in subset, so you can write [1,3] or [3,1]. Both of them are the same subset of nums.

When you are writing the subarray, you can think the bracket parenthesis is moving. [1] 2] 3] <- There is one place to put left bracket, and there are three place to put right bracket. So we get [1], [1,2], [1,2,3]. 13 = 3 1 [2] 3] <- There is one place to put left bracket, and there are two place to put right bracket. So we get [2], [2,3]. 12 = 2 1 2 [3] <- There is one place to put left bracket, and there are one place to put right bracket. So we get [3]. 1*1 = 1

Finally, total subarray of nums is 3+2+1 = 6. (formula to reach the total numbe of subarray is n*(n+1)/2)

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string

        index = {c: [-1, -1] for c in ascii_uppercase}
        res = 0
        for i, c in enumerate(S):
            k, j = index[c]
            res += (i - j) * (j - k)
            index[c] = [j, i]
        for c in index:
            k, j = index[c]
            res += (len(S) - j) * (j - k)
        return res % (10**9 + 7)

https://leetcode.com/problems/sum-of-subarray-ranges

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        res=0
        for i in range(len(nums)):
            max_num=nums[i]
            min_num=nums[i]
            for j in range(i+1,len(nums)):
                max_num=max(max_num,nums[j])
                min_num=min(min_num,nums[j])
                res+=max_num-min_num
        return res

https://leetcode.com/problems/analyze-user-website-visit-pattern/ 这一题多看几遍

python 自带处理 combination 或者 permutation 的工具 from itertools import combinations

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        users=defaultdict(list)
        for user,time,site in sorted(zip(username,timestamp,website), key=lambda x: (x[0],x[1])):
            users[user].append(site)
        patterns=Counter()
        for user,sites in users.items():
            patterns.update(Counter(set(combinations(sites,3))))
        print(sorted(patterns))
        return max(sorted(patterns), key=patterns.get)

24th

https://leetcode.com/problems/reorder-data-in-log-files sorted 的 key 可以用来定义 algorithem 返回值一定是 set

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def sorting_algo(log):
            if log[-1].isnumeric():
                return (1,)
            left_side, right_side=log.split(" ",1)
            return (0,right_side,left_side)
        return sorted(logs,key=sorting_algo)

https://leetcode.com/problems/sum-of-total-strength-of-wizards/ 前缀和 与单调栈(mono stack),use itertools 的 accumulate 来 build range sum

class Solution:
    def suggestedProducts(self, A, word):
        A.sort()
        res, prefix, i = [], '', 0
        for c in word:
            prefix += c
            i = bisect.bisect_left(A, prefix, i)
            print(i)
            res.append([w for w in A[i:i + 3] if w.startswith(prefix)])
        return res

August1 st

class Solution:
    def getMaxLen(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        dp[i][0] : max length of subarray ending with index i With positive product
        dp[i][1] : max length of subarray ending with index i With negative product
        """
        n = len(nums)
        dp = [[0] * 2 for _ in range(n)]
        if nums[0] > 0:
            dp[0][0] = 1
        if nums[0] < 0:
            dp[0][1] = 1
        res = dp[0][0]
        for i in range(1, n):
            cur = nums[i]
            if cur > 0:
                dp[i][0] = dp[i - 1][0] + 1
                if dp[i - 1][1] > 0:
                    dp[i][1] = dp[i - 1][1] + 1
            if cur < 0:
                dp[i][1] = dp[i - 1][0] + 1
                if dp[i - 1][1] > 0:
                    dp[i][0] =  dp[i - 1][1] + 1
            res = max(res, dp[i][0])
        return res
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        def reverseN(head, n):
            if n == 1:
                return head
            # 以 head.next 为起点，需要反转前 n - 1 个节点
            last = reverseN(head.next, n-1)
            successor = head.next.next
            # 以head.next为开头的链表已经完成翻转，那么head.next.next正确指向后继节点
            head.next.next = head
            head.next = successor
            return last
        fast=head
        slow=head
        count=0
        while fast is not None and fast.next is not None:
            count+=1
            fast=fast.next.next
            slow=slow.next
        head=reverseN(head,count)
        p2=slow
        p1=head
        max_num=-(math.inf)
        while p2 is not None:
            max_num=max(p1.val+p2.val,max_num)
            p1=p1.next
            p2=p2.next
        return max_num
class Solution:
    def minimumHealth(self, damage: List[int], armor: int) -> int:
        return 1 + sum(damage) - min(max(damage), armor)
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:

        def lca(node):
            """Return lowest common ancestor of start and dest nodes."""
            if not node or node.val in (startValue , destValue): return node
            left, right = lca(node.left), lca(node.right)
            return node if left and right else left or right

        root = lca(root) # only this sub-tree matters

        ps = pd = ""
        stack = [(root, "")]
        while stack:
            node, path = stack.pop()
            if node.val == startValue: ps = path
            if node.val == destValue: pd = path
            if node.left: stack.append((node.left, path + "L"))
            if node.right: stack.append((node.right, path + "R"))
        return "U"*len(ps) + pd

August 2nd

import itertools
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        preSum=list(itertools.accumulate(nums))
        preSum.insert(0,0)
        valtoIndex={}
        for i in range(0,len(preSum)):
            val=preSum[i]%k
            if val not in valtoIndex:
                valtoIndex[val]=i
        res=0
        for j in range(1,len(preSum)):
            need=preSum[j]%k
            if need in valtoIndex:
                if j-valtoIndex[need]>=2:
                    return True
        return False

Aug 3

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        global_max,pre_max,pre_min=nums[0],nums[0],nums[0]
        for num in nums[1:]:
            cur_min=min(pre_max*num,pre_min*num,num)
            cur_max=max(pre_max*num,pre_min*num,num)
            global_max=max(cur_max,global_max)
            pre_max=cur_max
            pre_min=cur_min
        return global_max

Aug 4th

August 5 th