GaryLeetCode学習ノート・肆(13週目)

58.最後の単語の長さ
大文字と小文字の文字列とスペース''のみを含む文字列を指定し、最後の単語の長さを返します.
最後の単語が存在しない場合は、0を返します.
説明:単語はアルファベットで構成されていますが、スペースを含まない文字列です.
例:
入力:「Hello World」出力:5
以下は先週最後に提出された誤った解法で、海先生はline 11、j=s.index(i)に誤りがあり、永遠に最初のスペースのインデックスであるため、連続したスペースを認識できない場合があると指摘した.

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        a=[]
        b=0
        for i in s:
            if i ==' ':
                j=s.index(i)
                a.append(j)
                b+=1
        if len(a)!=0:
            return (len(s)-a[b-1]-1)
        else:
            return 0
            

その後、海先生はsplit関数を用いて''を区切り文字とし、文字列をn個のサブ文字列に分割し、最後の文字列の長さを計算する構想を与えた.ただし、スペースで終わる場合、「a」のような最後の単語(黒人疑問符顔.jpg)は存在しないとは考えられず、最後の単語は「a」であることに注意してください.したがってsplitの後、removeは新しいリストの空の文字列を削除し、最後の文字列の長さを出力する必要があります.

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        a=s.find(' ')
        if a==-1:
            return len(s)
        else:
            s1=s.split(' ')
            while '' in s1:
                s1.remove('')
            if not s1:
                return 0
            else:
                return(len(s1[-1]))
                

新しい知識の蓄積:

Python特定の値を含むすべてのリスト要素を削除whileループ解決、whileがコンテンツが存在する場合list.remove()でいいです.すべてのremoveが完了するまでループを終了します.

split()関数split()は、区切り記号を指定して文字列をスライスし、パラメータnumに指定値がある場合は、numサブ文字列のみを移動後から分離し、分割された文字列リストを返します.

str.split(str=",num=string.cont(str))str–セパレータ.デフォルトでは、スペース、改行()、タブ(t)など、すべての空の文字が使用されます.num–分割回数.
70.階段を登る
階段を登っているとします.屋上に着くにはn階が必要です.
毎回1つか2つの階段を登ることができます.屋上に登る方法はいくつありますか?
注:指定されたnは正の整数です.
例1:
入力:2出力:2解釈:屋上に登るには2つの方法があります.

1次+1次

次例2:

入力:3出力:3解釈:3つの方法で屋上に登ることができます.

1次+1次+1次

1次+2次

階+1階

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        step=[1,2]
        for i in range(2,n):
            step.append(step[i-1]+step[i-2])
        return step[n-1]

逆に考えると、i段目に達するには、まずi-1段目またはi-2段目にstep[i]をi+1段目にする方法数としなければならず、step[i]=step[i-1]+step[i-2]
21.2つの秩序チェーンテーブルを結合する
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例:
入力:1->2->4、1->3->4出力:1->1->2->3->4->4
本題も下題もチェーンテーブルに関する問題があり、チェーンテーブルは新しい接触の知識です.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
        first = head
        while l1 != None and l2 != None:
            if l1.val > l2.val:
                head.next = l2
                l2 = l2.next
            else :
                head.next = l1
                l1 = l1.next
            head = head.next
        if l1 == None:
            head.next = l2
        elif l2 == None:
            head.next = l1
        return first.next
        

head=ListNode(0)とは、初期ノード、すなわち新しいチェーンテーブルの初期ノードを構築することを意味し、headをルートノードと理解することができる.次のステップはfirst=headです.このステップは重要です.値を付けなければ、head自身にnext伝達ノード関係を継続させなければ、そのノードは見つからないので、headを保存してからwhileサイクルを行う必要があります.l 1とl 2の2つのノードが空ではありません.つまり、2つのチェーンテーブルの長さの範囲内を遍歴する必要があります.l 1(初期はチェーンテーブル1のヘッダノード)の値がl 2の値より小さい場合、headの値をl 1に向ける.最後にループが終了すると、そのうちの1つのチェーンテーブルが遍歴されたに違いない.すなわち、l 1またはl 2がこの2つのチェーンテーブルの末尾ノードに伝達され、nextは下りられない.ループを飛び出して、次のif l 1 is None:この判断条件に来ました.ループが完了した後、l 2が存在するチェーンテーブル2には残りのいくつかのノードがあり、l 1が存在するチェーンテーブル1はループが完了したと仮定します.ではhead.next=l 2という意味はheadをl 2の後のいくつかのノードに導くことであり、つまり新しいチェーンテーブルを残りのチェーンテーブルに接続して最後にreturnするのはfirstである.next、firstはルートノードなのでfirst.nextこそヘッダノードである.
第2の方法は再帰を用いて、プログラムは自身を呼び出して、極めて紙幅を短縮して、しかし私はこのような思想をよく理解することができなくて、解答を求めます.

def mergeTwoLists(self, l1, l2):  
    if not l1:  
        return l2  
    elif not l2:  
        return l1  
    else:  
        if l1.val <= l2.val:  
            l1.next = self.mergeTwoLists(l1.next, l2)  
            return l1  
        else:  
            l2.next = self.mergeTwoLists(l1, l2.next)  
            return l2 `

83.並べ替えチェーンテーブルの重複要素を削除する
ソートチェーンテーブルを指定し、重複するすべての要素を削除して、各要素が一度だけ表示されるようにします.
例1:
入力:1->1->2出力:1->2例2:
入力:1->1->2->3->3出力:1->2->3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        first=head
        while head.next:
            if head.val==head.next.val:
                head.next=head.next.next
            else:
                head=head.next
        return first

まずチェーンテーブルが空かどうかを判断し、whileの次のノードが空でない場合、ヘッダ要素とヘッダ要素の次のノードの値が等しいかどうかを判断し、等しい場合は次のノードの値を現在のノードに割り当て、そうでない場合は、次のノードの判断を行う.戻ってfirst.
88.2つの配列を結合する
2つの秩序整数配列nums 1およびnums 2が与えられ、nums 2がnums 1に結合され、num 1が秩序配列になる.
説明:
初期化nums 1およびnums 2の要素数は、それぞれmおよびnである.nums 1にはnums 2の要素を保存するのに十分な空間(空間サイズがm+n以上)があると仮定できます.例:
入力:nums 1=[1,2,3,0,0],m=3 nums 2=[2,5,6],n=3
出力:[1,2,2,3,5,6]

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:m+n]=nums2[:n]
        nums1.sort()

初期化nums 1の要素数はそれぞれmで、この文は少し分かりにくいですが、例を見ると、前のmの要素を取って、他の意味を捨てます.nums 1の中の第m+1からm+nの要素をnums 2の中の前のnの要素に置き換えて、更にsortは並べ替えて問題の要求に注意することができます
:rtype: void Do not return anything, modify nums1 in-place instead.
返さずにnums 1だけ変更すればいいです.
100.同じ木
2つのツリーを指定し、同じかどうかを確認するために関数を作成します.
2つのツリーが構造的に同じで、ノードが同じ値を持っている場合は、同じとみなされます.
例1:
入力:1//2 3 3

    [1,2,3],   [1,2,3]

出力:true例2:
入力:1/2

    [1,2],     [1,null,2]

出力:false例3:
入力:1//2 1 2

    [1,2,1],   [1,1,2]

出力:false

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

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q
            return True
        if p and q and p.val==q.val:
            l=self.isSameTree(p.left,q.left)#  ，            ，          
            r=self.isSameTree(p.right,q.right)
            return l and r#          return 
        else:
            return False

まず、2つのツリーが空の場合について議論し、trueを返します.2本の木の同じ位置のノードから比較し,異なる場合は一定に異なりfalseに戻り,同じ場合は左右分岐点を新しい頂点として再帰を採用し,左右ノードが同じか否かを判断し,いずれもtrueの場合のみtrueとする.本題の再帰思想は比較的簡単明瞭である.