今天我们一起掌握 leetocode 的 136,141,142 题。

1. lc 136 - 只出现一次的数字

  • 题目来源
  • 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
  • 难度：简单

本题如果没有说明，可以采用哈希表和排序。哈希表会开辟额外空间，而排序的时间复杂度是O(nlogn)。下面给一个排序的代码。

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        nums.append(float('inf'))
        size = len(nums)
         
        for i in range(size//2): 
            if nums[2*i] != nums[2*i+1]: 
                return nums[2*i]

1.1 解题思路 - 异或运算 + 动态规划

异或运算有下面3个性质，前2个性质有助于我们理解异或运算的运算方式，第三个性质有助于解题：

由第三个性质可知，所有数位都参与到异或运算时，重复的数位将会等于0。最终运算结果等于出现一次数位的值。由这个规律，我们可以利用动态规划解题。

1.2 复杂度：

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

1.3 代码

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        tmp = 0
        for i in range(len(nums)): 
            tmp ^= nums[i]
        return tmp 
``` 

```

2. lc 141 - 环形链表

  • 题目来源
  • 给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。
  • 难度：简单

2.1 解题思路 - 快慢指针

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，慢指针每次只移动一步，而快指针每次移动两步。初始时，快指针和慢指针都在位置 head。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

2.2 时间复杂度

  • 时间复杂度： O(n)。 其中 N 是链表中的节点数。
    • 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
    • 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
  • 空间复杂度： O(1)。 我们只使用了两个指针的额外空间。

2.3 代码

1
2
3
4
5
6
7
8
9
class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while slow and fast and fast.next: # 注意不要忘记检查fast.next的存在
            slow, fast = slow.next, fast.next.next 
            if slow is fast:
                return True
            
        return False

3. lc 142 - 环形链表 II

  • 题目来源
  • 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。说明：不允许修改给定的链表。
  • 进阶：你是否可以使用 O(1) 空间解决此题？
  • 难度：中等

3.1 解题思路 - 快慢指针

还是依据lc 141的解题思路，一快一慢两个指针在链表上移动。但在何处是环的起始点呢？请看下面图解（注意，下面我们设定快指针比慢指针快1倍）。

由此可知，只要第一次相遇后，将慢指针重新设定在head，并且快慢指针以相同速度移动，直到两者相遇，相遇点便是环起始点。

3.2 时间复杂度

  • 时间复杂度：O(n) 其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离h + k不会超过链表的总长度；随后寻找入环点时，走过的距离2h + k，n=1时，等于链表的总长度，n>1时，超过链表的总长度。
  • 空间复杂度：O(1)

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while slow and fast and fast.next:
            slow,fast = slow.next,fast.next.next
            if slow is fast:
                slow = head # 重新设定慢指针位置
                while slow is not fast: 
                    slow,fast = slow.next,fast.next
                return slow
        return None