Neetcode 刷题记录（Leetcode题解-Python语言）

目录

• 一、Array & Hashing 数组与哈希
• • 217. 存在重复元素
  • 242. 有效的字母异位词
  • 1. 两数之和
  • 49. 字母异位词分组
  • 347. 前 K 个高频元素
  • 238. 除自身以外数组的乘积
  • 36. 有效的数独
• 二、Two Pointers 双指针
• • 125. 验证回文串
  • 167. 两数之和 II - 输入有序数组
  • 15. 三数之和
• 六、Linked List 链表
• • 206. 反转链表
  • 21. 合并两个有序链表
  • 143. 重排链表
  • 19. 删除链表的倒数第 N 个结点
  • 138. 复制带随机指针的链表
  • 2. 两数相加 & 445. 两数相加 II
  • 141. 环形链表
  • 287. 寻找重复数
  • 146. LRU 缓存
• 十八、Bit Manipulation 位运算
• • 136. 只出现一次的数字
  • 191. 位1的个数
  • 338. 比特位计数
  • 190. 颠倒二进制位
  • 268. 丢失的数字
  • 371. 两整数之和
  • 7. 整数反转

---

一、Array & Hashing 数组与哈希 217. 存在重复元素

题目页面

解法一：蛮力解法，从头开始遍历数组中的元素，对于每个元素，都将其与后面的所有元素进行比较，若有重复则返回 True，可知此解法时间复杂度为 O ( n 2 ) O({n^2}) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1)

解法二：排序后遍历，将数组排序之后，重复的元素一定是相邻的，所以很容易比较出来，但排序需要时间开销，所以此解法时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间复杂度为 O ( 1 ) O(1) O(1)

解法三：哈希表，利用哈希表插入与查找都只需要常数时间的特性，把出现过的元素记录在哈希表中，若后面遍历元素时发现其已经在哈希表里了，就返回 True，时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        record = set()
        for num in nums:
            if num in record:
                return True
            else:
                record.add(num)
        return False

---

242. 有效的字母异位词

题目页面

解法一：哈希表，分别把两个字符串中的字符以及字符的出现次数记录在两个哈希表中，然后遍历哈希表看看两个哈希表的键、值是否完全一样，注意Python 中索引不存在的键会报错，要用 get 函数，时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        countS = {}
        countT = {}
        if len(s) != len(t):
            return False
        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        for ch in countS:
            if countS[ch] != countT.get(ch, 0):
                return False
        return True

利用 collections 里面的 Counter 可以一行解决：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

解法二：排序法，对两个字符串进行排序，判断它们是否相等即可，优化了空间但损失了时间，时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

---

1. 两数之和

题目页面

解法一：蛮力解法，从头开始遍历数组中的元素，对于每个元素，都将其与后面的所有元素进行相加，判断它们的和是否等于 target，时间复杂度为 O ( n 2 ) O({n^2}) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1)

解法二：哈希表，把出现过的元素以及对应下标记录在哈希表中，若后面遍历元素 num 时发现 target - num 已经在哈希表里了，就返回 True，时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = dict()
        for i, num in enumerate(nums):
            if target - num in hashmap:
                return [hashmap[target - num], i]
            else:
                hashmap[num] = i

---

49. 字母异位词分组

题目页面

解法一：排序，对每一个字符串都进行排序，可知互为异位词的字符串排序后的结果是一样的，所以可以把该结果作为每一组异位词的标识（key），注意列表不能作为键，所以要转换为字符串或者元组。假设有 m 个字符串，每个字符串的平均长度为 n，排序耗时是 n log ⁡ n nlog n nlogn，总的时间复杂度为 O ( m n log ⁡ n ) O(mnlog n) O(mnlogn)，空间复杂度为 O ( m n ) O(mn) O(mn)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)
        for word in strs:
            ans[str(sorted(word))].append(word)
        return list(ans.values())

解法二：解法一中是将异位词排序后的结果作为标识，这里我们还能将异位词中每个字母出现的次数作为标识（注意将列表转换为字符串或元组），时间复杂度为 O ( m n ) O(mn) O(mn)，空间复杂度为 O ( m n ) O(mn) O(mn)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)
        for word in strs:
            count = [0] * 26
            for ch in word:
                count[ord(ch) - ord('a')] += 1
            ans[tuple(count)].append(word)
        return list(ans.values())

---

347. 前 K 个高频元素

题目页面

解法一：首先对每个元素进行频率统计，耗时 O ( n ) O(n) O(n)，然后对频率进行排序，再输出最大的 K 个，总时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn)，但这不符合题目要求，我们的解法必须优于 O ( n log ⁡ n ) O(nlog n) O(nlogn)

解法二：首先对每个元素进行频率统计，然后将频率加入到最大堆中，这样进行 K 次弹出，即可得到最大的 K 个频率，时间复杂度为 O ( k log ⁡ n ) O(klog n) O(klogn)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        heap = []
        for num, cnt in count.items():
            heapq.heappush(heap, (-cnt, num))
        ans = []
        for _ in range(k):
            ans.append(heapq.heappop(heap)[1])
        return ans

解法三：首先对每个元素进行频率统计，然后借鉴桶排序的思想，可知元素的出现次数最大为数组长度，所以可以构建一个频次数组，下标代表出现次数，而值是一个列表，其中记录了出现次数为该下标的所有元素。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        freq = [[] for _ in range(len(nums) + 1)]
        for num, cnt in count.items():
            freq[cnt].append(num)
        ans = []
        for i in range(len(nums), 0, -1):
            for num in freq[i]:
                ans.append(num)
                if len(ans) == k:
                    return ans

---

238. 除自身以外数组的乘积

题目页面

解法一：最直观的想法，就是求数组的总乘积，然后用总乘积除以每一个位置的结果，就是该位置除自身以外数组的乘积，但是题目禁止用除法，所以不考虑这个解法。

解法二：前缀积 + 后缀积，在每一个位置上，它除自身以外数组的乘积，实际上就是其左边所有元素乘积（前缀积）与其右边所有元素乘积（后缀积）的乘积。所以可以用两个数组分别记录前缀积和后缀积，然后输出数组的第 i 个位置的答案，就是前缀积数组第 i - 1 个位置与后缀积数组第 i + 1 个位置的元素乘积。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)

        prefix = [1] * len(nums)
        prefix[0] = nums[0]
        for i in range(1, len(nums)):
            prefix[i] = prefix[i-1] * nums[i]
        
        postfix = [1] * len(nums)
        postfix[-1] = nums[-1]
        for i in range(len(nums) - 2, -1, -1):
            postfix[i] = postfix[i+1] * nums[i]
        
        ans[0] = postfix[1]
        ans[-1] = prefix[-2]
        for i in range(1, len(nums)-1):
            ans[i] = prefix[i-1] * postfix[i+1] 
        
        return ans

解法三：对解法二进行优化，由于题目说明输出数组不计入空间复杂度，所以可以将前缀积记录在输出数组中，然后在计算后缀积的同时，将其与输出数组对应位置的值相乘，即可得到答案。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)

        prefix = 1
        for i in range(len(nums)):
            ans[i] = prefix
            prefix *= nums[i]
        
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            ans[i] *= postfix
            postfix *= nums[i]
        
        return ans

36. 有效的数独

题目页面

解法：每一行、每一列、以及每一个 3*3 宫都用一个哈希表记录出现过的数字，遍历二维数组，如果不是数字则跳过，如果是数字且出现过，就是无效的数独，否则就将其加入到所在行、列、宫的哈希表中。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(len(board)):
            for c in range(len(board[0])):
                if board[r][c] == '.':
                    continue
                if (board[r][c] in rows[r] or 
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r // 3, c // 3)]):
                    return False
                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True

---

二、Two Pointers 双指针 125. 验证回文串

题目页面

解法一：由于题目只要求考虑字母与数字，所以要忽略所有的其他符号，遍历字符串，isalnum() 为真才加入到 newStr 中，最后判断 newStr 与自身的反转是否相同即可。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ""

        for ch in s:
            if ch.isalnum():
                newStr += ch.lower()
        
        return newStr == newStr[::-1]

解法二：创建一个经过处理的新字符串消耗了空间，用双指针就可以优化空间复杂度。左右指针分别从字符串的左边与右边开始遍历，遇到字母或者数字才进行比较，如果不同就返回 False，直到两个指针相遇，返回 True。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        
        return True

---

167. 两数之和 II - 输入有序数组

题目页面

解法一：最弱的方法，是遍历每个数字，然后将其与后面的所有数字都进行相加，即枚举出所有的两数之和，这样的时间复杂度为 O ( n 2 ) O({n^2}) O(n2)；如果改用哈希表，就跟 两数之和 一样，时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

解法二：注意这题的输入是有序数组，遇到有序就应该想到双指针。解法二就是用双指针分别从两边出发，指针指向的元素之和大了左指针就右移，小了右指针就左移，直到遇到符合目标的和或者两指针相交。注意下标从 1 开始。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum < target:
                left += 1
            elif sum > target:
                right -= 1
            else:
                return [left+1, right+1]

---

15. 三数之和

题目页面

解法：由于题目说明不能出现重复的三元组，所以可以通过排序进行去重，遍历元素下标为 i，如果 i - 1 的元素与 i 是一样的，就跳过 i，否则将其作为三数之一，然后剩下的就是两数之和问题了。可以用哈希表解决，但是消耗了 O ( n ) O(n) O(n) 的空间，使用双指针则可以在 O ( 1 ) O(1) O(1) 空间复杂度下解决问题。同样地，在双指针移动的时候，也应该去重，如果移动的下个位置是重复位置则跳过。总的时间复杂度为 O ( n 2 ) O({n^2}) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(len(nums)):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    ans.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
        return ans

---

六、Linked List 链表 206. 反转链表

题目页面

解法一：迭代法，使用前一个节点 pre 和当前节点 cur。在节点 cur 时，先把下个指针记到 temp，然后 cur 的 next 指针反过来指向 pre，已反向的 cur 变为 pre，然后 cur 向右移一位，直到链表结束。在写法上，可以发现变量是头尾相连的，以此作为记忆。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            temp = cur.next     # 把下个指针记到 temp
            cur.next = pre      # cur 的 next 指针反过来指向 pre
            pre = cur           # 已反向的 cur 变为 pre
            cur = temp          # cur 向右移一位
        return pre	

解法二：递归法，对于链表 [1, 2, 3]，可以将反转 [1, 2, 3] 分解为已经反转了 [2, 3] 后反转 [1]，再将反转 [2, 3] 分解为已经反转了 [3] 后反转 [2]。基本情况就是反转单个节点或者空节点，例如反转 [3]，是无法反转的，直接返回自身。在反转 [2, 3] 时，我们正处于 [2] (head)，反转就是将它 next 的 next 即 [3] 的 next 指向自己，然后 [2] 的 next 指向空（作为表尾）。反转 [1, 2, 3] 也同理。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        newHead = self.reverseList(head.next)  # 下一个节点，反转后的
        head.next.next = head # 将下一个节点的 next 指向自己
        head.next = None  # 自己的 next 指向空，作为队尾
        return newHead  # 返回反转后的下一个节点

---

21. 合并两个有序链表

题目页面

解法：合并两个有序的链表，方法就是新建一个节点 head，迭代进行：如果两个链表都非空，就让新链表指向数值小的节点，然后移动下一位，直到其中一个链表为空，最后把另一个链表作为新链表剩下的部分。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(0)
        cur = head
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return head.next

---

143. 重排链表

题目页面

解法：由于题目要求不能只交换值，且不返回链表，所以不能遍历链表用列表记录值再生成新的链表，只能对链表进行原地操作。观察到重排的方式是左边一个节点接着右边一个节点，问题在于右边节点指针是无法向前的，自然就想到反转链表。先用快慢指针找到中点，然后把链表断开两半并将后半部分链表反转，这样问题就变成了合并两个链表了。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 快慢指针找到中点（两个则是左边那个）
        fast = head
        slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        secondHalf = slow.next
        slow.next = None
        # 反转后半部分
        pre = None
        while secondHalf:
            temp = secondHalf.next
            secondHalf.next = pre
            pre = secondHalf
            secondHalf = temp
        # 从左右两端开始
        left = head
        right = pre
        while right:
            temp1 = left.next
            temp2 = right.next
            left.next = right
            right.next = temp1
            left = temp1
            right = temp2

---

19. 删除链表的倒数第 N 个结点

题目页面

解法：删除链表的倒数第 n 个节点，用双指针法，第一个指针先遍历 n 次，然后两个指针一起遍历，这样当第一个指针遍历完之后，第二个指针正好遍历了（链表长度 - n）次，其位置即为要删除的位置。注意由于可能删除头节点，所以要用 dummyHead。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummyHead = ListNode(0, head)
        fast = dummyHead
        for _ in range(n):
            fast = fast.next
        slow = dummyHead
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummyHead.next

---

138. 复制带随机指针的链表

题目页面

解法一：哈希表，这题的难点在于 random 指针，它有可能指向后面未创建的节点，所以必须先遍历一次链表再分配 random 指针，但是直接分配是不可能的，因为无法表示新链表中的节点，直接赋值的话 random 指针也只是指向旧链表中的节点而已。想要表示某个东西的话，用哈希表是很好的选择。我们先遍历一次链表，创建新节点并且让旧新节点一一对应；然后第二次遍历链表，此时就可以通过这个哈希表找到新节点的 next 和 random 指针在新链表中该指向的节点了。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = {None : None}
        # 第一次遍历
        cur = head
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next
        # 第二次遍历
        cur = head
        while cur:
            copy = oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next
        
        return oldToCopy[head]

---

2. 两数相加 & 445. 两数相加 II

题目页面1

题目页面2

解法：两个链表对应位置相加，对于第一题，数字是逆序存储的，即链表头的数字是最低位，所以相加时会产生进位。使用两个队列，每次弹出队首元素进行相加，两个链表不等长的话短的那个会加0，余数作为结果链表的新节点，而商数除以10后作为进位（下一位的加数之一），最后如果还有一个进位也要考虑到。对于第二题，数字是顺序存储的，使用两个栈即可，注意输出也得是正序，所以链表是从尾部开始生成的，cur 初始为 None，每次 cur被新节点指向，然后 cur 再移动到新节点处，直到最后 cur 即为头节点（相当于反转链表）。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        q1, q2 = [], []
        while l1:
            q1.append(l1.val)
            l1 = l1.next
        while l2:
            q2.append(l2.val)
            l2 = l2.next
        dummyHead = ListNode(0)
        cur = dummyHead
        carry = 0
        while q1 or q2 or carry:
            a = q1.pop(0) if q1 else 0
            b = q2.pop(0) if q2 else 0
            sum = a + b + carry
            carry = sum // 10
            newNode = ListNode(sum % 10)
            cur.next = newNode
            cur = cur.next
        return dummyHead.next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        cur = None
        carry = 0
        while s1 or s2 or carry:
            a = s1.pop() if s1 else 0
            b = s2.pop() if s2 else 0
            sum = a + b + carry
            carry = sum // 10
            newNode = ListNode(sum % 10)
            newNode.next = cur
            cur = newNode
        return cur

---

141. 环形链表

题目页面

解法一：用哈希表记录下每一个节点，然后看看是否有相同节点，有的话就是存在环形，时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

解法二：快慢指针，如果链表是有环的，则当快慢指针都进入环之后，由于快指针比慢指针速度快 1，所以每次移动，它们之间的距离都会被缩小 1，而环最大的长度也不超过链表长度 n，所以它们之间的距离一定能被缩小到 0 的。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

使用快慢指针时要注意：如果初始化两个指针都是 head，则 while 循环中必须先赋值再判断是否相等，而不能先判断相等（因为初始时就是相等的）。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

---

287. 寻找重复数

题目页面

解法一：二分法，这题给定一个包含 n + 1 个整数的数组，其数字都在 1 到 n 之间，只有一个数字是重复的。因此，对于某个数字 x 来说，正常来说小于等于 x 的数字应该有 x 个，例如有1、2、3、4 共 4 个数字小于等于 4，如果大于 4了，则说明 1、2、3、4 其中有一个数字重复了，所以右边界左移，反之左边界右移。时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 1
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2 
            cnt = 0 # 记录小于等于mid的元素个数
            for num in nums:
                if num <= mid:
                    cnt += 1
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

解法二：由于数组取值为 1 - n，而数组共有 n + 1 个数，所以可以把数组中的数作为 next 指针，将其视为链表，重复数相当于带环链表中的入环点，因为它是被两个节点指向的。所以问题转换成了求入环点的问题，使用快慢指针即可，时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        fast = 0
        slow = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        temp = 0
        while True:
            slow = nums[slow]
            temp = nums[temp]
            if slow == temp:
                break
        
        return temp

---

146. LRU 缓存

题目页面

解法：LRU 缓存，因为要求函数 get 和 put 必须以 O ( 1 ) O(1) O(1) 的平均时间复杂度运行，所以基础的数据结构一定是哈希表（常数时间的查询与插入）。但是要实现 LRU（Least Recently Used 最近最少使用） 的功能，每次 put 的时候都要更新（key，value）对的位置，而哈希表是不存在顺序关系的，所以需要借助另一个数据结构，双向链表的帮助。

如图所示，我们可以让哈希表的 value 指向双向链表中的节点，该节点 Node 类存储了 key、value、prev 指针和 next 指针，且双向链表左右两边分别有一个节点 left 和 right，代表了 LRU 和 MRU。get 的时候，如果访问过某个 key、value，就要把它移动到双向链表的最右端（right 的左边），移动的方法是删除节点并将其插入到 right 的左边。put 的时候，如果 key 已经存在，就先删除它，然后统一让 value 指向 Node，Node 也插入到双向链表的最右端表示最近被用过；如果哈希表已经超出容量，就将 LRU （left 的右边一个节点）删除，哈希表和双向链表的内容都要删除。

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None
    
class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {} # 从 key 映射到 Node
        # 初始化双向链表，left 为 LRU，right 为 MRU
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

    # 删除 node
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev
    
    # 在最右边插入 node
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev
        
    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])
        
        if len(self.cache) > self.cap:
            # 如果已经超过容量了，就找到 LRU 然后将其从双向链表和哈希表中去除
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

十八、Bit Manipulation 位运算 136. 只出现一次的数字

题目页面

解法一：由于数组中只有一个数字时只出现一次，其余数字都出现两次，所以可以用一个集合，当数字第一次出现时加入集合，第二次出现时退出集合，那最后集合剩下的数字即为答案。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( n ) O(n) O(n)

解法二：位运算，一个数的二进制的每一位只可能为 1 或者 0，考虑所有出现两次的数字，它们每一位上的 0 都可以忽略（因为 1 或 0 与 0 做异或都得到自己），而剩下的 1 一定是偶数个（因为出现两次），偶数个 1 做异或一定得到 0，所以所有出现两次的数字做异或会得到 0，而只出现一次的数字与 0 做异或得到其本身，即为答案。时间复杂度为 O ( n ) O({n}) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            ans ^= num
        return ans

---

191. 位1的个数

题目页面

解法一：统计位 1 的个数，每次判断最低位是否为 1 ，然后右移即可。判断最低位是否为 1 有两个方法：与 1 进行与运算；对 2 进行取余，相当于判断是奇数还是偶数。右移也有两个方法：位运算右移；除以 2 。时间复杂度为 O ( 1 ) O(1) O(1)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            ans = ans + (n & 1)
            n = n >> 1
        return ans

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            ans += n % 2
            n //= 2
        return ans

解法二：由于中间位可能存在大量的 0，会造成不必要的运算，有没有方法可以直接找到值为 1 的位呢？方法是有的，就是每次让 n 与 n - 1 进行与运算，每次运算都会消去最右边的 1，直到 n 变为 0，运算的次数即为答案。时间复杂度为 O ( 1 ) O(1) O(1)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n = n & (n - 1)
            ans += 1
        return ans

---

338. 比特位计数

题目页面

解法一：逐个数字进行位 1 计数，由上一题可知，每个数字判断最低位是否为 1，然后右移 1 位（相当于除以 2），又因为每个数字都不大于 n，时间复杂度为 O ( log ⁡ n ) O(log n) O(logn)，共有 n 个数字，所以时间复杂度为 O ( n log ⁡ n ) O(nlog n) O(nlogn)，空间复杂度为 O ( n ) O(n) O(n)

解法二：动态规划，通过列举 0 到 8 的二进制位为 1 的数量，可以发现规律：2、3 的最低位重复了 0、1 的模式，而第二位固定为 1；4、5、6、7 的最低两位重复了 0、1、2、3 的模式，而第三位固定为 1。时间复杂度为 O ( n ) O( n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        offset = 1
        for i in range(1, n + 1):
            if offset * 2 == i:
                offset = i
            dp[i] = 1 + dp[i - offset]
        return dp

190. 颠倒二进制位

题目页面

解法一：最直接的思路，还是从二进制的最低位开始，判断其是否为 1，如果是则答案的最高位（对称）也为 1，时间复杂度为 O ( 1 ) O(1) O(1)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            ans <<= 1
            ans = ans + (n & 1)
            n >>= 1
        return ans

另外一种实现代码如下，把 ans 的左移一位放到了赋值中，然后加法用或运算代替：

class Solution:
    def reverseBits(self, n):
        ans = 0
        for i in range(32):
            ans = (ans << 1) | (n & 1)
            n >>= 1
        return ans

解法二：分治，把数字分成两半然后互换，对每一半再进行相同的操作，如图所示

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;

---

268. 丢失的数字

题目页面

这题可以用哈希表记录数字，但是空间复杂度为 O ( n ) O(n) O(n)，不符合题目要求。

解法一：位运算，正常的数组与缺失的数组做异或，相同的数会异或为0，剩下缺失的数。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        ans = len(nums)
        for i in range(len(nums)):
            ans = ans ^ i ^ nums[i]
        return ans

解法二：对数组求和，正常的数组和减去缺失的数组和，差值就是缺失的数。时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum([i for i in range(len(nums)+1)]) - sum(nums)

---

371. 两整数之和

题目页面

解法：由于不能用加法和减法，所以只能想到用位运算。观察到二进制加法中，0 + 0 得 0，1 + 0 或 0 + 1 得 1，1 + 1 得 0 进 1，实际上相当于异或运算，除了两者均为 1 时会产生进位。所以先进行异或运算，然后用与运算判断是否进位，是的话就左移一位，且这里我们不是逐位运算，而是对整个数字进行运算。Python 中由于整数是无限长的，所以需要特别处理。时间复杂度为 O ( 1 ) O(1) O(1)，空间复杂度为 O ( 1 ) O(1) O(1)

MASK1 = 0x100000000  # 2^32
MASK2 = 0x80000000  # 2^31
MASK3 = 0x7FFFFFFF  # 2^31-1

class Solution:
    def getSum(self, a: int, b: int) -> int:
        a %= MASK1
        b %= MASK1
        while b != 0:
            carry = ((a & b) << 1) % MASK1
            a = (a ^ b) % MASK1
            b = carry
        if a & MASK2:  # 负数
            return ~((a ^ MASK2) ^ MASK3)
        else:  # 正数
            return a

---

7. 整数反转

题目页面

解法：思路就是每次用 x 对 10 取余得到最低位，然后加到 ans 上，x 再对 10 取整以去掉最低位，直到 x 等于 0 为止。关键是要判断反转后的数是否越界，以上界为例，方法就是看反转后的数除最低位外的各位的值，是否大于上界相同位的值，若大于就肯定是越界，又或者是除最低位外都相同，但最低位比上界的最低位大，那也是越界。还有要注意的是 Python 中负数的取整和取余，参考这篇博客。时间复杂度为 O ( 1 ) O(1) O(1)，空间复杂度为 O ( 1 ) O(1) O(1)

class Solution:
    def reverse(self, x: int) -> int:
        MAX = 2 ** 31 - 1
        MIN = -(2 ** 31)
        
        ans = 0
        while x:
            digit = x % 10 if x > 0 else -((-x) % 10)
            x = int(x / 10)
            if (ans > MAX // 10) or (ans == MAX // 10 and digit >= MAX % 10):
                return 0
            if (ans < int(MIN / 10)) or (ans == int(MIN / 10) and (-digit) >= (-MIN) % 10):
                return 0
            ans = ans * 10 + digit
        return ans