leetcode practice - python3 (8)

169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1: Input: [3,2,3] Output: 3
Example 2: Input: [2,2,1,1,1,2,2] Output: 2
構想:プログラミングの美髪帖水王

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 2:
            return nums[0]

        cur, cnt = nums[0], 1
        for n in nums[1 : ]:
            if n != cur:
                cnt -= 1
                if cnt == 0:
                    cur, cnt = n, 1
            else:
                cnt += 1

        return cur

Beat 13.69% python3 2018-05-25

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt, cur = 0, None
        for n in nums:
            if cnt == 0:
                cur = n
            if n == cur:
                cnt += 1
            else:
                cnt -= 1

        return cur

Beat 91.20% python3 2018-05-25

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums) // 2]

Beat 98.76%python 3 2018-05-25よし、ソートはかえって早い...
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
構想:チェーン時計を切って、新しいheadと古い頭部を保存して、毎回古い頭部のチェーンを新しい頭部の前に着きます

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

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head

        p, q = head, head.next
        head.next = None
        while q:
            p = q
            q = q.next
            p.next = head
            head = p

        return head

Beat 99.86%python 3 2018-05-25注:複数回のコミット時間が異なる
226. Invert Binary Tree
Invert a binary tree.
Example:
Input:
4 /\ 2 7 /\/\ 1 3 6 9 Output:
4 /\ 7 2 /\/\ 9 6 3 1 Trivia: This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
考え方:DFS

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

class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return root

        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

Beat 99.43% python3 2018-05-25
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Example 1: Input: 1->2 Output: false
Example 2: Input: 1->2->2->1 Output: true Follow up: Could you do it in O(n) time and O(1) space?
構想:中点を見つけて、後半reverse、比較

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

class Solution:
    def revertList(self, head):
        if head is None or head.next is None:
            return head

        p, q = head, head.next
        head.next = None
        while q:
            p = q
            q = q.next
            p.next = head
            head = p

        return head

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return True

        slow, fast = head, head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next

        revert = self.revertList(slow.next)
        while revert:
            if revert.val != head.val:
                return False
            head, revert = head.next, revert.next

        return True

Beat 96.70% python3 2018-05-25
283. Move Zeroes
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note:
You must do this in-place without making a copy of the array. Minimize the total number of operations.
単純な考え方:2つのポインタ、1つは0を指し、1つは非0を指し、交換

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        if length <= 1:
            return

        left, right = 0, 0
        while left < length and right < length:
            while left < length and nums[left] != 0:
                left += 1

            if right < left:
                right = left
            while right < length and nums[right] == 0:
                right += 1

            if left < right and right < length:
                nums[left] = nums[right]
                nums[right] = 0

        return

Beat 33.86% python3 2018-05-25
最適化:より簡単な書き方

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        pos = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[pos], nums[i] = nums[i], nums[pos]
                pos += 1

Beat 99.30% python3 2018-05-25