pythonブラシleetcodeテーマ(24)

38.報数
報数シーケンスとは、1つの整数シーケンスを指し、その中の整数の順序で報数を行い、次の数を得る.最初の5つは次のとおりです.

1.     1
2.     11
3.     21
4.     1211
5.     111221

1は、"one 1"(" ")、すなわち11と読まれる.11は、"two 1s"(" ")、すなわち21と読まれる.21は、"one 2"、「one 1"(" "、" ")、すなわち1211と読まれる.
正の整数nが与えられ、報数シーケンスのn番目の項が出力される.
注:整数の順序は文字列として表示されます.
例1:

  : 1
  : "1"

例2:

  : 4
  : "1211"

この問題の構想は1つの関数を通じて次の報数を必要とする文字列を見つけて、それからappendは1つのlistの中に着いて、この逆数を行きます
コードは次のとおりです.

def getNext(s):
    s = list(str(s))
    temp, cnt, res = -1, 1, ""
    for num in s:
        if num == str(temp):
            cnt += 1
        else:
            if temp != -1:
                res += (str(cnt) + str(temp))
            temp, cnt = num, 1
    res += (str(cnt) + str(temp))
    # print("res", res)
    return res

class Solution:
    ans = ["1"]
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        while len(self.ans) < n:
            self.ans.append(getNext(int(self.ans[-1])))
        return self.ans[n - 1]
    

234.回文チェーン表
チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:

  : 1->2
  : false

例2:

  : 1->2->2->1
  : true

考え方:その中の1つの方法はこの問題を回転して数字が回文であるかどうかを求めることができて、私たちはチェーンテーブルの値を1つのlistの中に置くことができて、それから彼らの逆順序が等しいかどうかを比較して、等しいのは回文で、さもなくばです.
コード:

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


class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        ##### the first method
#         if head is None or head.next is None:
#             return True
#         values = []
#         p = head 
#         while p.next:
#             values.append(p.val)
#             p = p.next
#         values.append(p.val)
        
#         return values == values[::-1]
        
        ##### the second method
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:#                    
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head):
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val

学び合い、教え合う.