fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

1617-卿同学

发表文章数:84

热门标签

, ,
首页 » MySQL » 正文

最近父节点:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None:
            return 
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        return left if left else right

时间复杂度 O(N): 其中 N 为二叉树节点数;最差情况下,需要递归遍历树的所有节点。
空间复杂度 O(N): 最差情况下,递归深度达到 N ,系统使用 O(N)大小的额外空间。

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        for i, char in enumerate(s):
            if char == '(':
                stack.append([i,'('])
            if char == ')':
                if stack and stack[-1][1] == '(':
                    stack.pop()
                else:
                    stack.append([i,')'])
        new_stack = set(i[0] for i in stack)
        ans = ""
        for i,char in enumerate(s):
            if i not in new_stack:
                ans += char
        return ans

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        if not root:
            return []
        ans = []
        queue = [root]
        while queue:
            ll = []
            for node in queue:
                if node.right:
                    ll.append(node.right)
                if node.left:
                    ll.append(node.left)
            ans.append(queue[0].val)
            queue = ll
        return ans
                
        

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

思路:

1. 直接变列表,然后排序

2.merge 2 list

3.merge sort 

4. heap sort

5. override the compare function, and use heapsort

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return
        if len(lists) == 1:
            return lists[0]
        heap = []
        heapq.heapify(heap)
        for node in lists:
            while node:
                heapq.heappush(heap,node.val)
                node = node.next
        cur = dummy = ListNode(-1)
        while heap:
            n = heapq.heappop(heap)
            cur.next = ListNode(n)
            cur = cur.next
        return dummy.next

前缀和: 1,暴力解, 2,前缀和 3.前缀和加hashtable查询

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        #prefix sum
        totalarray = [0] 
        length = len(nums)
        total = 0
        cnt = 0
        for num in nums:
            total += num
            totalarray.append(total)
        for i in range(length+1):
            for j in range(i+1,length+1):
                if totalarray[j] - totalarray[i] == k:
                    cnt += 1
        return cnt
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        #prefix sum
        prefixdict = defaultdict(int)
        prefixdict[0] = 1
        length = len(nums)
        total = 0
        cnt = 0
        for i in range(length):
            total = total +nums[i]
            cnt += prefixdict[total-k]
            prefixdict[total] += 1
        return cnt

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

 fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        def compare(a):
            return (a[0]-0)**2 + (a[1]-0)**2
        points.sort(key=compare)
        print(points)
        return points[0:k]

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

最小堆问题:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        heapq.heapify(heap)
        for num in nums:
            if len(heap) < k:
                heapq.heappush(heap,num)
            else:
                heapq.heappush(heap,num)
                heapq.heappop(heap)
        return heapq.heappop(heap)

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

两两比较,一定是递增的

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        dictorder = defaultdict(int)
        for i in range(len(order)):
            dictorder[order[i]] = i
        ordernum = []
        for i in range(len(words)-1):
            if not self.compare(words[i],words[i+1],dictorder):
                return False
        return True
    def compare(self,word1,word2,dictorder):
        for i in range(len(word1)):
            if i >= len(word2):
                return False
            if dictorder[word1[i]] > dictorder[word2[i]]:
                return False
            if dictorder[word1[i]] < dictorder[word2[i]]:
                return True
        return True
            
        

fb面经: 最近父节点,括号,右看二叉树,merge k list,外星人字典,离原点最近的k个点, @lru_cache,自动缓存

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        res = set()
        left , right = 0, 0
        for i in s:
            if i == "(":
                left += 1
            if i == ")":
                if left >0:
                    left -= 1
                else:
                    right += 1
        @lru_cache
        def dfs(index,leftmove,rightmove,st):
            if index == len(s):
                if leftmove == 0 and rightmove == 0:
                    res.add(st)
                return
            if s[index] not in "()":
                dfs(index+1,leftmove,rightmove,st+s[index])
            
            #delete

            if s[index] =='(' and leftmove >0:
                dfs(index+1,leftmove-1,rightmove,st)
            if s[index] ==')' and rightmove >0:
                dfs(index+1,leftmove,rightmove-1,st)
            # not delete
            if s[index] =='(':
                dfs(index+1,leftmove,rightmove,st+'(')
            if s[index] ==')':
                dfs(index+1,leftmove,rightmove,st+')')
        dfs(0,left,right,'')
        print(res)
        ans = res.copy()
        for char in res:
            total = 0
            for c in char:
                if c == '(':
                    total += 1
                elif c == ')':
                    total -= 1
                if total < 0:
                    ans.remove(char)
                    break
        return ans
分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录