leetcode上的python練習（5）

來自專欄 python的學習

(217)給定一個整數數組，判斷是否存在重複元素。

如果任何值在數組中出現至少兩次，函數返回 true。如果數組中每個元素都不相同，則返回 false。

示例 1:

輸入: [1,2,3,1]輸出: true

示例 2:

輸入: [1,2,3,4]輸出: false

示例 3:

輸入: [1,1,1,3,3,4,3,2,4,2]輸出: true

答：(超時)

class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ for i in nums: if nums.count(i)>1: return True return False

答：

class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ return len(nums)!=len(set(nums))

(219)給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的絕對值最大為 k。

示例 1:

輸入: nums = [1,2,3,1], k= 3輸出: true

示例 2:

輸入: nums = [1,0,1,1], k=1輸出: true

示例 3:

輸入: nums = [1,2,3,1,2,3], k=2輸出: false

答：

class Solution(object): def containsNearbyDuplicate(self, n, k): """ :type nums: List[int] :type k: int :rtype: bool """ record = {} for i, num in enumerate(n): if num in record and i - record[num] <= k: return True record[num] = i return False

（225）使用隊列實現棧的下列操作：

• push(x) -- 元素 x 入棧
• pop() -- 移除棧頂元素
• top() -- 獲取棧頂元素
• empty() -- 返回棧是否為空

答：

class MyStack(object): def __init__(self): """ Initialize your data structure here. """ self.a=[] def push(self, x): """ Push element x onto stack. :type x: int :rtype: void """ self.a.append(x) def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ b=self.a[-1] del self.a[-1] return b def top(self): """ Get the top element. :rtype: int """ return self.a[-1] def empty(self): """ Returns whether the stack is empty. :rtype: bool """ return self.a==[] # Your MyStack object will be instantiated and called as such:# obj = MyStack()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.top()# param_4 = obj.empty()

（226）翻轉一棵二叉樹。

示例：

輸入：

4 / 2 7 / / 1 3 6 9

輸出：

4 / 7 2 / / 9 6 3 1

答：

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ def ver(root): if root==None: return if root.left!=None or root.right!=None: root.left,root.right=root.right,root.left ver(root.left) ver(root.right) ver(root) return root

（231）給定一個整數，編寫一個函數來判斷它是否是 2 的冪次方。

示例 1:

輸入: 1輸出: true解釋: 20 = 1

示例 2:

輸入: 16輸出: true解釋: 24 = 16

示例 3:

輸入: 218輸出: false

答：

class Solution(object): def isPowerOfTwo(self, n): """ :type n: int :rtype: bool """ if n<1: return False return bin(n).count(1)==1

答：（看n的二進和n-1的二進&是否為0）

class Solution(object): def isPowerOfTwo(self, n): """ :type n: int :rtype: bool """ if n<1: return False return not(n & (n-1))

(232)使用棧實現隊列的下列操作：

• push(x) -- 將一個元素放入隊列的尾部。
• pop() -- 從隊列首部移除元素。
• peek() -- 返回隊列首部的元素。
• empty() -- 返回隊列是否為空。

示例:

MyQueue queue = new MyQueue();queue.push(1);queue.push(2); queue.peek(); // 返回 1queue.pop(); // 返回 1queue.empty(); // 返回 false

答：

class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.a=[] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: void """ self.a.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ b=self.a[0] del self.a[0] return b def peek(self): """ Get the front element. :rtype: int """ return self.a[0] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ return self.a==[] # Your MyQueue object will be instantiated and called as such:# obj = MyQueue()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.peek()# param_4 = obj.empty()

（234）請判斷一個鏈表是否為迴文鏈表。

示例 1:

輸入: 1->2輸出: false

示例 2:

輸入: 1->2->2->1輸出: true

答：

# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ a=[] while head: a.append(head.val) head=head.next return a==a[::-1]

（242）給定兩個字元串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的一個字母異位詞。

示例 1:

輸入: s = "anagram", t = "nagaram"輸出: true

示例 2:

輸入: s = "rat", t = "car"輸出: false

答：

class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ return sorted(s)==sorted(t)

（258）

給定一個非負整數 num，反覆將各個位上的數字相加，直到結果為一位數。示例:輸入: 38輸出: 2 解釋: 各位相加的過程為：3 + 8 = 11, 1 + 1 = 2。 由於 2 是一位數，所以返回 2。

答：

class Solution(object): def addDigits(self, s): """ :type num: int :rtype: int """ while s>9: s = sum(int(str(s)[i])for i in range(len(str(s)))) return s

（263）

編寫一個程序判斷給定的數是否為丑數。丑數就是只包含質因數 2, 3, 5 的正整數。示例 1:輸入: 6輸出: true解釋: 6 = 2 × 3示例 2:輸入: 8輸出: true解釋: 8 = 2 × 2 × 2示例 3:輸入: 14輸出: false 解釋: 14 不是丑數，因為它包含了另外一個質因數 7。

答：

class Solution(object): def isUgly(self, num): """ :type num: int :rtype: bool """ while num >0 and num%2==0: num /= 2 while num >0 and num%3==0: num /= 3 while num >0 and num%5==0: num /= 5 return True if num == 1.0 else False

(268)給定一個包含 0, 1, 2, ..., n 中 n 個數的序列，找出 0 .. n 中沒有出現在序列中的那個數。

示例 1:

輸入: [3,0,1]輸出: 2

示例 2:

輸入: [9,6,4,2,3,5,7,0,1]輸出: 8

答：(超時)

class Solution(object): def missingNumber(self, n): """ :type nums: List[int] :rtype: int """ for i in range(len(n)+1): if i not in n: return i

答：

class Solution(object): def missingNumber(self, n): """ :type nums: List[int] :rtype: int """ a=sum(n) b=sum(range(len(n)+1)) return b-a

(278)你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由於每個版本都是基於之前的版本開發的，所以錯誤的版本之後的所有版本都是錯的。

假設你有 n 個版本 [1, 2, ..., n]，你想找出導致之後所有版本出錯的第一個錯誤的版本。

你可以通過調用 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。

示例:

調用 isBadVersion(3) -> false調用 isBadVersion(5) -> true調用 isBadVersion(4) -> true所以，4 是第一個錯誤的版本。

答：

# The isBadVersion API is already defined for you.# @param version, an integer# @return a bool# def isBadVersion(version):class Solution(object): def firstBadVersion(self, n): """ :type n: int :rtype: int """ left=0;right=n while(True): mid=(left+right)//2 if isBadVersion(mid)==False and isBadVersion(mid+1)==True: return mid+1 elif isBadVersion(mid)==False and isBadVersion(mid+1)==False: left=mid elif isBadVersion(mid)==True and isBadVersion(mid+1)==True: right=mid

（283）

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。示例:輸入: [0,1,0,3,12]輸出: [1,3,12,0,0]

答：

class Solution(object): def moveZeroes(self, n): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ a=n.count(0) while 0 in n: n.remove(0) n+=[0]*a

（290）

給定一種 pattern(模式) 和一個字元串 str ，判斷 str 是否遵循相同的模式。這裡的遵循指完全匹配，例如， pattern 里的每個字母和字元串 str 中的每個非空單詞之間存在著雙向連接的對應模式。示例1:輸入: pattern = "abba", str = "dog cat cat dog"輸出: true示例 2:輸入:pattern = "abba", str = "dog cat cat fish"輸出: false示例 3:輸入: pattern = "aaaa", str = "dog cat cat dog"輸出: false示例 4:輸入: pattern = "abba", str = "dog dog dog dog"輸出: false

答：

class Solution(object): def wordPattern(self, pattern, str): """ :type pattern: str :type str: str :rtype: bool """ l=str.split() if len(pattern)!=len(l): return False return len(set(zip(pattern,l))) == len(set(pattern)) == len(set(l))

(292)你和你的朋友，兩個人一起玩 Nim遊戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最後一塊石頭的人就是獲勝者。你作為先手。

你們是聰明人，每一步都是最優解。 編寫一個函數，來判斷你是否可以在給定石頭數量的情況下贏得遊戲。

示例:

輸入: 4輸出: false 解釋: 如果堆中有 4 塊石頭，那麼你永遠不會贏得比賽； 因為無論你拿走 1 塊、2 塊 還是 3 塊石頭，最後一塊石頭總是會被你的朋友拿走。

答：

class Solution(object): def canWinNim(self, n): """ :type n: int :rtype: bool """ return n%4!=0

推薦閱讀：