leetcode marathon 8.28 复习

快慢指针-本地存储

83. 删除排序链表中的重复元素

本地存储-快慢指针

慢指针负责存储连接，快指针负责向前走，进行探索

最后一定要记得截取到slow指针的位置!！！！！！！

def deleteDuplicates(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 快慢指针
    # 慢指针负责存储
    # 快指针负责找到
    slow = head
    fast = head
    while fast != None:
        if fast.val!=slow.val:
            slow.next=fast
            slow=fast
        fast=fast.next
    if slow != None:
        slow.next = None  # 记得最后要截取到slow指针！！！！！！！！！！！！
    return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

27. 移除元素

快慢指针+本地存储

非val的数全部本地存储

def removeElement(nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """
    slow = 0
    for fast in range(len(nums)):
        if nums[fast]!=val:
            nums[slow]=nums[fast]
            slow+=1
    return slow
1
2
3
4
5
6
7
8
9
10
11
12

283. 移动零

依然是快慢指针-本地存储

前面把所有非0数存储上，然后后面全赋值成0即可

千万别钻牛角尖！！ 不是0的数存储，最后全赋值成0就行

千万别想着交换

def moveZeroes(nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    slow=0
    for fast in range(len(nums)):
        if nums[fast]!=0:
            nums[slow]=nums[fast]
            slow+=1
    nums[slow:len(nums)]=0
1
2
3
4
5
6
7
8
9
10
11

贪心算法

55. 跳跃游戏

贪心+找到当前选择内 跳到最远的

因为 最远的那个 一定能覆盖其他选择

跳跃游戏是一个贪心问题！！！！！！

我们立足于0点就知道要选择2号

# 跳跃游戏本质是一个贪心问题
# 我们要选择跳的最远的就行！！！

def canJump(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """

    far=0   # 立足于当前点最远能跳多远
    index=0 # 当前点的位置
    while True:
        # 更新far
        far=index+nums[index]
        # 如果最远能到达最后一个点:则成功
        if far>=len(nums)-1:
            return True
        # 选择最有潜力的点
             #0 1 2 3
        # eg: 3 1 4 2
        max=far
        maxi=-1
        for i in range(index+1,far+1):
            if nums[i]+i>max:
                max=nums[i]+i
                maxi=i
        # 什么时候会失败:
        # 当没有最有潜力的点
        if maxi==-1:
            return False
        # 此时 max 是能 跳到最远的位置，maxi是 当前的节点
        # 更新index
        index=maxi






if __name__ == '__main__':
    nums=[3,2,1,0,4]
    print(canJump(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

45. 跳跃游戏 II

依然是贪心问题，选择跳的最远的

要问为什么 因为跳的最远的 一定更是次数 且跳的最远的相比其他点 并没有丢失任何可能性

一样的代码

# 跳跃游戏本质是一个贪心问题
# 我们要选择跳的最远的就行！！！

def jump(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    n=0
    far=0   # 立足于当前点最远能跳多远
    index=0 # 当前点的位置
    while True:
        # 更新far
        far=index+nums[index]
        # 如果最远能到达最后一个点:则成功
        if far>=len(nums)-1:
            n+=1
            break
        # 选择最有潜力的点
             #0 1 2 3
        # eg: 3 1 4 2
        max=far
        maxi=-1
        for i in range(index+1,far+1):
            if nums[i]+i>max:
                max=nums[i]+i
                maxi=i
        # 什么时候会失败:
        # 当没有最有潜力的点
        if maxi==-1:
            return -1
        n+=1
        # 此时 max 是能 跳到最远的位置，maxi是 当前的节点
        # 更新index
        index=maxi


    return n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

292. Nim 游戏

贪心 如下面的逻辑

面对4的倍数时必输

# 这个问题要反着想
# 谁最后面对4颗的时候谁输，所以我要想办法让对手面对4颗
# 也就是5-7时，我能让对手面对4颗
# 也就是面对8颗时,必输...

# ...
# 也就是面对4的倍数时必输
# 所以只要n不是4的倍数，我就能让对手面对4的倍数
1
2
3
4
5
6
7
8

def canWinNim(self, n):
    """
    :type n: int
    :rtype: bool
    """
    # 先理清这个逻辑
    # 这个问题要反着想
    # 谁最后面对4颗的时候谁输，所以我要想办法让对手面对4颗
    # 也就是5-7时，我能让对手面对4颗
    # 也就是面对8颗时,必输...

    # ...
    # 也就是面对4的倍数时必输
    # 所以只要n不是4的倍数，我就能让对手面对4的倍数

    if n%4==0:
        return False
    return True

if __name__ == '__main__':
    pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

877. 石子游戏 - 力扣（LeetCode） (leetcode-cn.com)

贪心 先手必赢

先手可以一直控制自己拿下标全为奇数或者全为偶数的石子，所以只要提前计算好偶数下标与奇数下标各自的总和，选大的那一方拿就必胜

def stoneGame(self, piles):
    """
    :type piles: List[int]
    :rtype: bool
    """
    # 有两个条件很重要
    # 偶数堆石子，总数为奇数个
    # 也就是 偶数总数 奇数总数 总有一个更高
    # 而在先手的情况下，可以控制对手只能选奇数 或者偶数
    # 也就是必胜的
    return True
1
2
3
4
5
6
7
8
9
10
11

319. 灯泡开关

规律

# 灯刚开始是关着的
# 因此一个灯被按了奇数次开关是开着的
# 所以一个灯会被按多少次开关呢，我们要看它的因子
# 比如 4=1*4=2*2  也就是第1，2，4 轮会被按
# 比如总共按16轮 16个灯
# 1= 1*1 灭
# 2=1*2 亮
# ...
# 会发现能被开方的 就是灭着的灯
# 而<=n的数有多少能被开方？
# eg n=10<4*4
        #>3*3
        #>2*2
        #>1*1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

return int(math.sqrt(n))
1

42. 接雨水

双指针 移动最小的那边

提升短板

雨水i = min(l_max,r_max)-height[i]

# 接雨水的核心解法 就是 双指针 从两头
# 并且移动小的那边
# 在本题中 每一个格子乘的水为 min(max_left,max_right)-num
# 所以对于左右指针走到的点
# 对于左指针左边的点 其左边最大已经确定了，如果它还小于 此时的max_right,说明它一定比自己真正的max_rigth小
1
2
3
4
5

def trap(height):
    """
    :type height: List[int]
    :rtype: int
    """
    r_max=0
    l_max=0
    left=len(height)-1
    right=0
    res=0
    while right < left:
        l_max=max(l_max,height[left])
        r_max=max(r_max,height[right])

        if l_max<r_max:
            res+=l_max-height[left]
            left+=1
        else:
            res+=r_max-height[right]
            right-=1
    return res
if __name__ == '__main__':
    print(max(0,0))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

11. 盛最多水的容器

双指针 分别从两边移动

双指针 移动较小的那边 只有移动较小的那边，提升短板，才有雨水变大的可能

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    left=0
    right=len(height)-1

    max_res=0

    while left < right:
        if (right-left)*min(height[left],height[right]) > max_res:
            max_res=(right-left)*min(height[left],height[right])
        # 只有移动 最小的那边，才有雨水变大的可能！！
        if height[left] < height[right]:
            left+=1
        else:
            right-=1
    return max_res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树

144. 二叉树的前序遍历

二叉树遍历

遍历！！

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res=[]
        def dfs(node):
            if node==None:
                return 
            res.append(node.val)
            dfs(node.left)

            dfs(node.right)
        dfs(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树 我们需要想清楚 根节点需要干什么，同时选出用什么遍历