美文网首页
高频算法题3

高频算法题3

作者: wenyilab | 来源:发表于2022-05-17 10:07 被阅读0次

    链表相加

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            s1, s2 = [], []
            while l1:
                s1.append(l1.val)
                l1 = l1.next
            while l2:
                s2.append(l2.val)
                l2 = l2.next
            ans = None
            carry = 0
            while s1 or s2 or carry != 0:
                a = 0 if not s1 else s1.pop()
                b = 0 if not s2 else s2.pop()
                cur = a + b + carry
                carry = cur // 10
                cur %= 10
                curnode = ListNode(cur)
                curnode.next = ans
                ans = curnode
            return ans
    

    两数相加

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
            pre = ListNode(0)
            cur = pre 
            carry = 0
            while l1 or l2:
                x = l1.val if l1  else 0
                y = l2.val if l2  else 0
                sum_v = x + y + carry
    
                carry = sum_v // 10
                sum_v = sum_v % 10
                cur.next = ListNode(sum_v)
    
                cur = cur.next 
                if l1:
                    l1 = l1.next
                if l2:
                    l2 = l2.next
            if carry == 1:
                cur.next = ListNode(carry)
            return pre.next
    

    有序数组中位数

    def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
            def getKthElement(k):
                index1, index2 = 0, 0
                while True:
                    # 特殊情况
                    if index1 == m:
                        return nums2[index2 + k - 1]
                    if index2 == n:
                        return nums1[index1 + k - 1]
                    if k == 1:
                        return min(nums1[index1], nums2[index2])
    
                    # 正常情况
                    newIndex1 = min(index1 + k // 2 - 1, m - 1)
                    newIndex2 = min(index2 + k // 2 - 1, n - 1)
                    pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
                    if pivot1 <= pivot2:
                        k -= newIndex1 - index1 + 1
                        index1 = newIndex1 + 1
                    else:
                        k -= newIndex2 - index2 + 1
                        index2 = newIndex2 + 1
    
    
            m, n = len(nums1), len(nums2)
            totalLength = m + n
            if totalLength % 2 == 1:
                return getKthElement((totalLength + 1) // 2)
            else:
                return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
    

    数组中逆序对数

    class Solution:
        def mergeSort(self, nums, tmp, l, r):
            if l >= r:
                return 0
    
            mid = (l + r) // 2
            inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r)
            i, j, pos = l, mid + 1, l
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    tmp[pos] = nums[i]
                    i += 1
                    inv_count += (j - (mid + 1))
                else:
                    tmp[pos] = nums[j]
                    j += 1
                pos += 1
            for k in range(i, mid + 1):
                tmp[pos] = nums[k]
                inv_count += (j - (mid + 1))
                pos += 1
            for k in range(j, r + 1):
                tmp[pos] = nums[k]
                pos += 1
            nums[l:r+1] = tmp[l:r+1]
            return inv_count
    
        def reversePairs(self, nums: List[int]) -> int:
            n = len(nums)
            tmp = [0] * n
            return self.mergeSort(nums, tmp, 0, n - 1)
    

    之字打印二叉树

    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root: return []
            res,deque = [],collections.deque([root])
            while deque:
                tmp = collections.deque()
                for _ in range(len(deque)):
                    node = deque.popleft()
                    if len(res) % 2 : tmp.appendleft(node.val)
                    else:tmp.append(node.val)
                    if node.left:deque.append(node.left)
                    if node.right: deque.append(node.right)
                res.append(list(tmp))
            return res
    

    数值的整数次方

    class Solution:
        def myPow(self, x: float, n: int) -> float:
            if x == 0 : return 0
            if n < 0 : x,n = 1/x,-n
    
            res = 1
            while n:
                if n & 1 : res *= x
                x *= x
                n >>= 1
    
            return res
    

    单词拆分

    class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> bool:
            l = len(s)
            if not wordDict: return not s
            dp = [False] * (l + 1)
            dp[0] = True
            for i in range(1, l + 1):
                for j in range(i - 1, -1, -1):
                    if dp[j] and s[j:i] in wordDict:
                        dp[i] = True
                        break
            return dp[-1]
    

    接雨水

    class Solution:
        def trap(self, height: List[int]) -> int:
            if not height:
                return 0
            
            n = len(height)
            leftMax = [height[0]] + [0] * (n - 1)
            for i in range(1, n):
                leftMax[i] = max(leftMax[i - 1], height[i])
    
            rightMax = [0] * (n - 1) + [height[n - 1]]
            for i in range(n - 2, -1, -1):
                rightMax[i] = max(rightMax[i + 1], height[i])
    
            ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
            return ans
    

    最长重复子数组

    class Solution:
        def findLength(self, A: List[int], B: List[int]) -> int:
            n,m = len(A),len(B)
            dp = [[0] * (m+1) for _ in range(n+1)]
            ans = 0
            for i in range(n-1,-1,-1):
                for j in range(m-1,-1,-1):
                    dp[i][j] = dp[i+1][j+1] + 1 if A[i] == B[j] else 0
                    ans = max(ans,dp[i][j]) 
            return ans
    

    0-1缺失的数字

    class Solution:
        def missingNumber(self, nums: List[int]) -> int:
            left = 0
            right = len(nums)-1
    
            while left <= right:
                mid = left + (right - left ) // 2
                if nums[mid] == mid : 
                    left = mid+1
                else:
                    right = mid -1
            return left
    

    路径总和

    class Solution:
        def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
            res = []
            path = []
    
            def dfs(root,targetSum):
                if not root:
                    return
                
                path.append(root.val)
                targetSum -= root.val 
                if not root.left and not root.right and targetSum == 0:
                    res.append(path[:])
                dfs(root.left,targetSum)
                dfs(root.right,targetSum)
                path.pop()
    
            dfs(root,targetSum)
            return res
    

    判断两棵树是否相同

    class Solution:
        def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val != q.val:
                return False
            return self.isSameTree(p.right,q.right) and self.isSameTree(p.left,q.left)
    

    二叉搜索树最近祖先

    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if p.val > root.val and q.val > root.val:
                return self.lowestCommonAncestor(root.right,p,q)
            elif p.val < root.val and q.val < root.val:
                return self.lowestCommonAncestor(root.left,p,q)
            else:
                return root
    

    二叉树镜像

    class Solution:
        def mirrorTree(self, root: TreeNode) -> TreeNode:
            if not root: return
            stack = [root]
            while stack:
                node = stack.pop()
                if node.left:stack.append(node.left)
                if node.right:stack.append(node.right)
                node.left,node.right = node.right,node.left
            return root
    
    class Solution:
        def mirrorTree(self, root: TreeNode) -> TreeNode:
            if not root: return
            root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
            return root
    
    

    二叉树层次遍历

    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            res = []
            if not root:
                return res 
            queue = [root]
            while queue:
                n = len(queue)
                tmp = []
                for _ in range(n):
                    r = queue.pop(0)
                    tmp.append(r.val)
                    if r.left:
                        queue.append(r.left)
                    if r.right:
                        queue.append(r.right)
                res.append(tmp)
            return res 
    

    二叉树前序遍历

    class Solution:
        def preorderTraversal(self, root: TreeNode) -> List[int]:
            stack,rst = [root],[]
            while stack:
                i = stack.pop()
                if isinstance(i,TreeNode):
                    stack.extend([i.right,i.left,i.val])
                elif isinstance(i,int):
                    rst.append(i)
            return rst
    class Solution:
        def preorderTraversal(self, root: TreeNode) -> List[int]:
            def preorder(root: TreeNode):
                if not root:
                    return
                res.append(root.val)
                preorder(root.left)
                preorder(root.right)
            
            res = list()
            preorder(root)
            return res
    
    

    相关文章

      网友评论

          本文标题:高频算法题3

          本文链接:https://www.haomeiwen.com/subject/azvgurtx.html