今天我们一起掌握 leetocode 的 237, 238, 292, 344, 557 题。

1. lc 237 - 删除链表中的节点

  • 题目来源
  • 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。
  • 难度：简单

直观想法，从链表里删除一个节点 node 的最常见方法是修改之前节点的 next 指针，使其指向之后的节点。有以下代码：

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        move = head
        while move:
            if move == node:
                move.next = move.next.next
            move = move.next

因为，我们无法访问我们想要删除的节点 之前 的节点，我们始终不能修改该节点的 next 指针。所以，上面代码不正确。

1.1 解题思路 - 交换值

我们必须将想要删除的节点的值替换为它后面节点中的值，然后删除它之后的节点。这里只能做的事情是交换节点val，和更改引用。

因为我们知道要删除的节点不是列表的末尾，所以我们可以保证这种方法是可行的。

1.2 时间复杂度

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

1.3 代码

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

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

  • 题目来源
  • 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
  • 示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
  • 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
  • 进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
  • 难度：中等

2.1 解题思路 - 左右乘积列表

利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。每个位置乘积对应的左侧所有数字的乘积和右侧所有数字的乘积分别由一个数组储存。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        # 初始化 L，R
        L,R = [1 for _ in range(size)],[1 for _ in range(size)]
        for i in range(1,size):
            L[i] = L[i-1]*nums[i-1]
        for j in range(size-2,-1,-1):
            R[j] = R[j+1]*nums[j+1]
        for z in range(size):
            nums[z] = L[z]*R[z] 
        return nums

复杂度

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。使用了 L 和 R 数组去构造答案，L 和 R 数组的长度为数组 nums 的大小。

2.2 解题思路 - 左右乘积列表

由输出数组不被视为额外空间知，我们可以试着只用输出数组储存L和R中的内容。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        # 初始化 输出空间
        answer = [1 for _ in range(size)] 
        for i in range(1,size):
            answer[i] = answer[i-1] * nums[i-1]
        tmp = 1
        for j in range(size-2,-1,-1):
            tmp = nums[j+1]*tmp
            answer[j] = answer[j]*tmp
        return answer

复杂度

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

3. lc 292 - Nim 游戏

  • 题目来源
  • 你和你的朋友，两个人一起玩 Nim 游戏： 桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
  • 1 <= n <= 2^31 - 1
  • 难度：中等

如果采用动态规划和递归会超时。

3.1 解题思路 - 推理

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。

显然，它以相同的模式不断重复 n=4,8,12,16,…，基本可以看出是 4 的倍数。

3.2 复杂度分析

  • 时间复杂度：O(n)。最差情况下，需要递归遍历树的所有节点。
  • 空间复杂度：O(n)。最差情况下，递归深度达到 N ，系统使用 O(N) 大小的额外空间。

3.3 代码

1
2
3
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n%4 != 0

4. lc 344 - 反转字符串

  • 题目来源
  • 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
  • 难度：简单

4.1 解题思路 - 库函数

s[::-1]表示反转s中的元素

s[:]表示数组中所有子模块

s[:]=s[::-1]表示将原数组反转后赋值给s中每一个对应的位置

s=s[::-1]表示将s反转后赋值给新的对象s（可以通过id函数查看内存地址），与题意原地修改不符。

代码

1
2
3
4
5
6
7
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[::] = s[::-1]
        return s

4.2 解题思路 - 双指针

左右两边双指针，向中间推进，交换两指针指向元素，直到左指针等于或超过右指针。

复杂度

  • 时间复杂度：O(n)。一共执行了 N/2 次的交换。
  • 空间复杂度：O(1)。只使用了常数空间来存放若干变量。

代码

1
2
3
4
5
6
7
8
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s)//2):
            s[i],s[-i-1] = s[-i-1],s[i]

5. lc 557 - 反转字符串中的单词 III

  • 题目来源
  • 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
  • 提示：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
  • 难度：简单

5.1 解题思路 - 使用额外空间

将字符串分割成单词列表，然后把每个单词反转切片，再join。

代码

1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:  
        return ' '.join(word[::-1] for word in s.split(" "))

用map:

1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:  
        return ' '.join(map(lambda x:x[::-1], s.split()))

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)，用了切片就是O(n)，不管什么方法都需要额外的空间取存储split()方法分割后的列表，那么空间复杂度应该是O(n)级别的，尽管反转过程是原地进行的

5.2 解题思路 - 原地解法

此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符…… 如此反复，就可以在原空间上翻转单词。

需要注意的是，原地算法在某些语言（比如 Java, Python, C#, Javascript, Go）中不适用，因为在这些语言中 String 类型是一个不可变的类型。python 报错：'str' object does not support item assignment

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def reverseWords(self, s: str) -> str: 
        tmp = '' # 临时变量储存每个单词 
        res = ''
        for i, ch in enumerate(s):
            print(ch)
            if ch!= ' ':
                tmp += ch
            else: 
                res += tmp[::-1] + ' '
                tmp = '' 
        res += tmp[::-1] 
        return res

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。只用tmp储存单词，但res使用了额外空间存储了返回结果。