11/30 leetcode python longest common prefix/ Merge Two Sorted Lists

someone

30 11月, 2023

14. Longest Common Prefix
問題文
文字列の配列の中から最も長い共通プレフィックス文字列を検索する関数を作成します。共通のプレフィックスがない場合は、空の文字列 "" を返します。

回答：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        for a in zip(*strs):
            if len(set(a)) == 1:
                res += a[0]
            else:
                return res
        return res

理由：
list(zip(*strs))
strs = ["flower","flow","flight"]
strs = ["flower","flow","flight"]
l = list(zip(*strs))
>>> l = [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        l = list(zip(*strs))
        prefix = ""
        for i in l:
            if len(set(i))==1:
                prefix += i[0]
            else:
                break
        return prefix
traditional scan vertically
 i      0  1  2  3  4  5
 0      f  l  o  w  e  r
 1	    f  l  o  w
 2	    f  l  i  g  h  t
		
We choose the first string in the list as a reference. in this case is str[0] = "flower"
the outside for-loop go through each character of the str[0] or "flower". f->l->o->w->e->r
the inside for-loop, go through the words, in this case is flow, flight.
ーーー

21. Merge Two Sorted Lists
問題文
2 つのソートされたリンクリスト list1 と list2 の先頭が与えられます。 2 つのリストを 1 つの並べ替えられたリストにマージします。このリストは、最初の 2 つのリストのノードを結合して作成する必要があります。マージされたリンクリストの先頭を返します。

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

回答

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1
            else:
                cur.next = list2
                list2,cur = list2.next, list2

        if list1 or list2:
            cur.next = list1 if list1 else list2

        return dummy.next
        
2 つのソートされたリンク リスト list1 と list2 の先頭が与えられます。 2 つのリストを 1 つの並べ替えられたリストにマージします。このリストは、最初の 2 つのリストのノードを結合して作成する必要があります。 マージされたリンク リストの先頭を返します。