Leetcode(快慢指针习题思路总结,持续更新。。。)

发布于:2024-11-29 ⋅ 阅读:(26) ⋅ 点赞:(0)

这种模式,有一个非常出门的名字,叫龟兔赛跑。这种算法的两个指针的在数组上(或是链表上,序列上)的移动速度不一样。快的一个指针肯定会追上慢的一个(可以想象成跑道上面跑得快的人套圈跑得慢的人)

讲解题目

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。
def hasCycle(self, head: ListNode) -> bool:
    if not head or not head.next:
        return False
        
    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
        
    return True

习题1

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。
def middleNode(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

习题2

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19
输出:true
解释:
1 ** 2 + 9 ** 2 = 82
8 ** 2 + 2 ** 2 = 68
6 ** 2 + 8 ** 2 = 100
1 ** 2 + 0 ** 2 + 0 ** 2 = 1

示例 2:

输入:n = 2
输出:false
def isHappy(self, n: int) -> bool:
        
    def get_squre_sum(n):
        num_sum = 0
        while n > 0:
            num = n % 10
            num_sum += num ** 2
            n = n // 10
        return num_sum

    res = []
    while n != 1 and n not in res:
        res.append(n)
        n = get_squre_sum(n)
    return n == 1