Python劍指offer打卡-19
文章目錄
- Python劍指offer打卡-19
-
- 漢明距離
- 全排列
- 排序連結清單
- 打家劫舍I
- 打家劫舍II
漢明距離
- 問題描述
問題描述： 兩個整數之間的 漢明距離 指的是這兩個數字對應二進制位不同的位置的數目。 給你兩個整數 x 和 y，計算并傳回它們之間的漢明距離。 解題方法： 兩步走原則： （1）通過異或操作統計bit1的不相同位（異或操作取不同） （2）通過x & (x - 1) 統計bit1的出現次數(轉換為比特位計數) 時間複雜度：(logC)，其中 C 是元素的資料範圍，在本題中logC=log2^31 = 31 空間複雜度：O(1)。 知識點： 與：遇0得0 運算規則：0&0=0; 0&1=0; 1&0=0; 1&1=1; 或：遇1得1 運算規則：0|0=0； 0|1=1； 1|0=1； 1|1=1； 異或：相同為0，不同為1 運算規則：0^0=0； 0^1=1； 1^0=1； 1^1=0 - 代碼
class Solution: def hammingDistance(self, x: int, y: int) -> int: """計算兩個數值之間的漢明距離""" res, cnt = x ^ y, 0 while res: res &= (res - 1) cnt += 1 return cnt
全排列
- 問題描述
問題描述： 給定一個不含重複數字的數組 nums ，傳回其 所有可能的全排列 。你可以 按任意順序 傳回答案。 示例： 輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] - 代碼
class Solution: def permute(self, nums): """數組的全排列""" res = [] def dfs(x): # 回朔滿足 if x == len(nums) - 1: res.append(nums[:]) return dic = set() for i in range(x, len(nums)): if nums[i] in dic: continue dic.add(nums[i]) # 交換位置 nums[i], nums[x] = nums[x], nums[i] dfs(x + 1) nums[i], nums[x] = nums[x], nums[i] dfs(0) return res
排序連結清單
- 問題描述
問題描述： 給你連結清單的頭結點head，請将其按 升序 排列并傳回 排序後的連結清單 。 進階：你可以在O(nlogn) 時間複雜度和常數級空間複雜度下，對連結清單進 行排序嗎？ 示例： 輸入：head = [4,2,1,3] 輸出：[1,2,3,4] 解題方法： 歸并排序 時間複雜度：O(nlogn) 空間複雜度：O(n) -
代碼（解題思路）
快慢指針尋找中點圖解：
Python劍指offer打卡-19Python劍指offer打卡-19 class Solution: def sortList(self, head: ListNode) -> ListNode: """合并排序""" # 隻有一個節點時，各子部分有序 if not head or not head.next: return head # 查找二分有的右節點 slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next head2 = slow.next slow.next = None return self.merge(self.sortList(head), self.sortList(head2)) def merge(self, head1, head2): # 建立臨時借點 dummy = pre = ListNode(0) while head1 and head2: if head1.val <= head2.val: pre.next = head1 head1 = head1.next else: pre.next = head2 head2 = head2.next pre = pre.next # 添加剩餘節點 pre.next = head1 if head1 else head2 return dummy.next -
知識點（歸并排序）
主要思想：
歸并排序方法就是把一組n個數的序列，折半分為兩個序列，然後再将這兩個序列再分，一直分下去，直到分為n個長度為1的序列。然後兩兩按大小歸并。如此反複，直到最後形成包含n個數的一個數組。
時間複雜度計算：
歸并排序總時間=分解時間+子序列排好序時間+合并時間
無論每個序列有多少數都是折中分解，是以分解時間是個常數，可以忽略不計。
則：歸并排序總時間=子序列排好序時間+合并時間
把這個規模為 n 的問題分成兩個規模分别為 n/2 的子問題，每個子問題的時間複雜度就是 T(n/2)，那麼兩個子問題的複雜度就是 2×T(n/2)。 當兩個子問題都得到了解決，即兩個子數組都排好了序，需要将它們合并，一共有 n 個元素，每次都要進行最多 n-1 次的比較，是以合并的複雜度是 O(n)。由此我們得到了遞歸複雜度公式：T(n) = 2×T(n/2) + O(n)。 對于公式求解，不斷地把一個規模為 n 的問題分解成規模為 n/2 的問題，一直分解到規模大小為 1。如果 n 等于 2，隻需要分一次；如果 n 等于 4，需要分 2 次。這裡的次數是按照規模大小的變化分類的。 以此類推，對于規模為 n 的問題，一共要進行 log(n) 層的大小切分。在每一層裡，我們都要進行合并，所涉及到的元素其實就是數組裡的所有元素，是以，每一層的合并複雜度都是 O(n)，是以整體的複雜度就是 O(nlogn)。
原理：
- 将一個序列從中間位置分成兩個序列；
- 在将這兩個子序列按照第一步繼續二分下去；
- 直到所有子序列的長度都為1，也就是不可以再二分截止。這時候再兩兩合并成一個有序序列即可。
動态圖示範：
Python劍指offer打卡-19Python劍指offer打卡-19 歸并排序代碼： Python劍指offer打卡-19Python劍指offer打卡-19 def mergeSort(arr): if len(arr) <= 1: return arr middle = (len(arr)) // 2 left, right = arr[:middle], arr[middle:] return merge(mergeSort(left), mergeSort(right)) def merge(left, right): """ 有序合并 :param left:左有序 :param right: 右有序 :return: 有序合并 """ result = [] while left and right: # 比較插入 if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) # 填補剩餘部分 while left: result.append(left.pop(0)) while right: result.append(right.pop(0)) return result
打家劫舍I
- 問題描述
問題描述： 你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制 約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統 會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ， 一夜之内能夠偷竊到的最高金額。 示例： 輸入：[1,2,3,1] 輸出：4 解釋：偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。 偷竊到的最高金額 = 1 + 3 = 4 。 解題方法： 動态規劃 1. 狀态定義：用 dp[i] 表示前 i 間房屋能偷竊到的最高總金額 2. 轉移方程：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) 3. 初始值：dp[0], dp[1] = nums[0], max(nums[0], nums[1]) 4. 傳回值： dp[n] 一晚上偷竊到最高金額 時間複雜複: O(n) 周遊數組n 空間複雜度：O(1) 滾動數組， 不需要額外的存儲空間 - 代碼（解題思路）
class Solution: def rob(self, nums): """動态規劃""" if not nums: return 0 if len(nums) == 1: return nums[0] first, second = nums[0], max(nums[0], nums[1]) for i in range(2, len(nums)): first, second = second, max(nums[i] + first, second) return second if __name__ == "__main__": obj = Solution() print(obj.rob([1, 2, 3, 1]))
打家劫舍II
- 問題描述
問題描述： 你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這 個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。 同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小 偷闖入，系統會自動報警 。 給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ， 今晚能夠偷竊到的最高金額。 示例： 輸入：nums = [2,3,2] 輸出：3 解釋：你不能先偷竊 1 号房屋（金額 = 2），然後偷竊 3 号房屋（金額 = 2）, 因為他們 是相鄰的。 解題方法： 核心原則就是：第一個和最後一個不能同時搶。 是以：要麼不搶第一個，要麼 不搶最後一個。 注意，不搶第一個的時候，最後一個可搶可不搶；另一種情況同理 取兩種情況中的最大值。是以，可以把環拆成兩個隊列，一個是從0到n-1，另一個 是從1到n，然後傳回兩個結果最大的。 時間複雜度：O(n) 空間複雜度：O(1) 注意： 此處的房屋構成一個環。 - 代碼
class Solution: def rob(self, nums: List[int]) -> int: def robRange(start: int, end: int) -> int: first, second = nums[start], max(nums[start], nums[start + 1]) for i in range(start + 2, end + 1): first, second = second, max(first + nums[i], second) return second if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums[0], nums[1]) return max(robRange(0, len(nums)-2), robRange(1, len(nums) - 1))