小李飛刀:做題第七彈!
寫在前面的話
做做做題,慢慢上手了就覺得刷題速度變快了,果然還是有點笨~
希望最後一竅快點通吧~
開始做題
第一題
難度:簡單
給定一個大小為 n 的陣列,找到其中的眾數。眾數是指在陣列中出現次數大於 ⌊ n/2 ⌋
的元素。
你可以假設陣列是非空的,並且給定的陣列總是存在眾數。給定一個大小為 n 的陣列,找到其中的眾數。眾數是指在陣列中出現次數大於 ⌊ n/2 ⌋
的元素。
你可以假設陣列是非空的,並且給定的陣列總是存在眾數。
我的題解:
class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ value = nums[0] count = 0 for i in nums: if value == i: count = count + 1 else: if count == 0: value = i count = 1 continue count =count - 1 return value
我的思路:
這題參考了評論的題解,做了兩次,明白了來龍去脈。
中心思想就是:按順序遍歷數字,存在不同的數字就抵消相應的count,存在相同數字則增加,最後總能獲取到唯一一個不會被抵消全部的數字,就是眾數了。
第二題
難度:簡單
給定一個非空整數陣列,除了某個元素只出現一次以外,其餘每個元素均出現兩次。找出那個只出現了一次的元素。
說明:
你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎?
我的題解:
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ a = 0 for num in nums: a = a ^ num return a
我的思路:
異或
,兩個相同的數字的計算結果為0,最後剩餘的則為唯一值
第三題
難度:簡單
給定一個排序連結串列,刪除所有重複的元素,使得每個元素只出現一次。
我的題解:
# 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 """ a = head if not a: return a while head.next: if head.next.val == head.val and head.next.next == None: head.next = None elif head.next.val == head.val and head.next.next: head.next = head.next.next else: head = head.next return a
我的思路:
當存在前後節點一致的時候,則前一個節點的next指向後一個節點的next,跳過即可。
其他:
因為連結串列的結構指向的是記憶體,遍歷完之後指向最後的節點,所以需要一個 a
指向頭結點。
第四題
難度:簡單
給定兩個二叉樹,編寫一個函式來檢驗它們是否相同。
如果兩個樹在結構上相同,並且節點具有相同的值,則認為它們是相同的。
我的題解:
# 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: if p.val == q.val: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) else: return False else: return False
我的思路:
遞迴
,主要是判斷兩個節點的值是否一致,一致的前提下,判斷向下的左右節點及更向下是否一致。
第五題
難度:簡單
給定兩個有序整數陣列 nums1 和 nums2,將 nums2 合併到 nums1 中,使得 num1 成為一個有序陣列。
說明:
- 初始化 nums1 和 nums2 的元素數量分別為 m 和 n。
- 你可以假設 nums1 有足夠的空間(空間大小大於或等於 m + n)來儲存 nums2 中的元素。
我的題解:
class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]
我的思路:
因為nums1[m+n]為空的部分,所以我們可以從後向前寫,判斷兩個陣列的值,更大的數字不斷向後挪,挪到一定程度的時候,剩餘部分則為更長的陣列的剩餘未判斷部分。
第六題
難度:簡單
給定一個二叉樹,找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明 : 葉子節點是指沒有子節點的節點。
我的題解:
# 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 maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 if root.right is None and root.left is None: return 1 return max(self.maxDepth(root.right),self.maxDepth(root.left))+1
我的思路:
遞迴
圖上為呼叫棧的情況,不斷向下尋找更遠的根節點。
- 基線判斷為:節點是否為空
- 遞迴判斷為:節點不為空且左節點或右節點還有值
總結
最近在看 《演算法圖解》
,感覺對 遞迴
理解更深一點,但學習之後重要的是實踐,還是要多做題。