欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

那些和“公共“有关的算法题

程序员文章站 2024-03-19 15:28:10
...

一、二叉树类

1、二叉树的最近公共祖先

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

2、二叉搜索树的最近公共祖先

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

3、首个共同祖先

暂时空

二、链表类

1、两个链表的第一个公共节点

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # if not headA and not headB:
        #     return None
        node1,node2 = headA,headB 
        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA
        return node1

2、环形链表

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next :
            return False 

        slow = head
        fast = head
        while (fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True 
            
        return False

3、环形链表 II

暂时为空

三、动态规划类

1、最长公共子串

转移方程为:那些和“公共“有关的算法题

同时输出长度和公共子串

class LCS3:
    def lcs3_dp(self, text1, text2):
        # input_y as column, input_x as row
        dp = [([0] * (len(text2)+1)) for i in range(len(text1)+1)]
        maxlen = maxindex = 0
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                if i == 0 or j == 0:  # 在边界上,自行+1
                        dp[i][j] = 0
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    if dp[i][j] > maxlen:  # 随时更新最长长度和长度开始的位置
                        maxlen = dp[i][j]
                        maxindex = i - maxlen

                else:
                    dp[i][j] = 0
        for dp_line in dp:
            print(dp_line)
        return maxlen, text1[maxindex:maxindex + maxlen]

2、最长公共子序列:

转移方程为:

那些和“公共“有关的算法题

同时输出长度和公共子序列:

class Solution:
    def LCS(list_n, list_m):
        # 计算LCS的长度
        n = len(list_n)
        m = len(list_m)
        dp = [[0]*(m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if list_n[i-1] == list_m[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        print(dp[m][n])
        # 输出LCS
        if dp[-1][-1] == 0:
            return -1
        list_LCS = []
        i, j = n, m
        while i > 0 and j > 0:
            if list_n[i-1] == list_m[j-1]:
                list_LCS.append(list_n[i-1])
                i -= 1
                j -= 1
                continue
            else:
                if dp[i][j-1] >= dp[i-1][j]:
                    j -= 1
                else:
                    i -= 1
        return ''.join(list(reversed(list_LCS)))

四、字符串类

最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        max_str = max(strs)
        min_str = min(strs)
        for i,j in zip(max_str,min_str):
            if i==j:
                res+=i
            else:
                return res
        return min_str

那些和“公共“有关的算法题