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 つのリストのノードを結合して作成する必要があります。 マージされたリンク リストの先頭を返します。
Next Post Previous Post
No Comment
Add Comment
comment url