剑指offer【10~19】

作者: 牛奶芝麻 | 来源:发表于2019-12-16 16:26 被阅读0次

题目链接：

剑指offer 10-19

10.1 斐波那契数列
 10.2 矩形覆盖
 10.3 跳台阶
 10.4 变态跳台阶
 11. 旋转数组的最小数字
 12. 矩阵中的路径
 13. 机器人的运动范围
 14. 剪绳子
 15. 二进制中 1 的个数
 16. 数值的整数次方
 17. 打印从 1 到最大的 n 位数
 18.1 在 O(1) 时间内删除链表节点
 18.2 删除链表中重复的结点
 19. 正则表达式匹配

Python 实现：

10.1 斐波那契数列

只需要两个变量记录前两个状态即可，不需要递归和大小为 n 的数组保存。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0 or  n == 1:
            return n
        pre1, pre2, ans = 0, 1, 0  # pre1 和 pre2 分别记录前两个状态
        for i in range(2, n + 1):
            ans = pre1 + pre2
            pre1 = pre2
            pre2 = ans
        return ans

10.2 矩形覆盖

实际上就是斐波那契数列。注意 f(1) = 1，f(2) = 2

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 2:
            return number
        pre1, pre2, ans = 1, 2, 0
        for i in range(3, number + 1):
            ans = pre1 + pre2
            pre1 = pre2
            pre2 = ans
        return ans

10.3 跳台阶

实际上就是斐波那契数列，代码和 10.2 一模一样。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number <= 2:
            return number
        pre1, pre2, ans = 1, 2, 0
        for i in range(3, number + 1):
            ans = pre1 + pre2
            pre1 = pre2
            pre2 = ans
        return ans

10.4 变态跳台阶

f(n) = f(n-1) + f(n-2) + ... + f(0)，其中 f(i) 表示从第 i 层跳到第 n 层的跳法。化简的 f(n) = 2 * f(n-1)，故为公比为 2 的等比数列，总跳法为 2 ^ (n-1)。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2 ** (number - 1)

11. 旋转数组的最小数字

二分查找，每次 mid 和上界 hi 去比较。注意数组可以有重复，如 [3,3,3,1,2,3] 这种，判断一下等号应该放在哪个条件上。

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        lo, hi = 0, len(rotateArray) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if rotateArray[mid] >= rotateArray[hi]:  # 非递减，所以取等号
                lo = mid + 1
            elif rotateArray[mid] < rotateArray[hi]:
                hi = mid
        return rotateArray[lo]

12. 矩阵中的路径

DFS 回溯法。注意如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索（上下左右）结束之后，需要将 b 的原来状态改回来，并搜索 c。

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        def judgePath(i, j, path):
            if not path:
                return True
            tmp = matrix2[i][j]  # 先用 tmp 记录 matrix[2] 的状态
            matrix2[i][j] = None
            for p in pos:
                if 0<=i+p[0]<rows and 0<=j+p[1]<cols and matrix2[i+p[0]][j+p[1]] != None and matrix2[i+p[0]][j+p[1]]==path[0]:
                    if judgePath(i+p[0], j+p[1], path[1:]):
                        return True
            matrix2[i][j] = tmp  # 将 matrix[2] 位置的状态改回来
            return False
        
        if not path:
            return True
        matrix2 = [[''] * cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                matrix2[i][j] = matrix[i*cols+j]
        pos = [[-1,0], [1,0], [0,-1], [0,1]]  # 上下左右 
        for i in range(rows):
            for j in range(cols):
                if matrix2[i][j] == path[0]:
                    if judgePath(i, j, path[1:]):
                        return True
        return False

13. 机器人的运动范围

DFS 回溯法。先构造矩阵，将能到达的坐标置为 1，不能到达的坐标置为 0，就可以将此题转化为从 (0, 0) 点开始求连通面积问题。和 Leetcode 【DFS】695. Max Area of Island 类似。注意这题和上面 12 题的区别在于探索到一个点，回溯过程不需要改回去原来的状态。

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # 转化为从 (0, 0) 点开始求连通面积问题
        def count(i, j):
            ans = 1
            matrix[i][j] = 0  # 不需要改回去
            for p in pos:
                if 0<=i+p[0]<rows and 0<=j+p[1]<cols and matrix[i+p[0]][j+p[1]]==1:
                    ans += count(i+p[0], j+p[1])
            return ans
        
        # write code here
        if threshold < 0:
            return 0
        matrix = [[0] * cols for _ in range(rows)]
        for i in range(rows):  # 将能到达的坐标位置改为 1
            for j in range(cols):
                if sum([int(num) for num in list(str(i))]) + sum([int(num) for num in list(str(j))]) <= threshold:
                    matrix[i][j] = 1
        pos = [[-1,0], [1,0], [0,-1], [0,1]]
        return count(0, 0)

14. 剪绳子

找规律，含有越多因子 3 的乘积越大。

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3: return n - 1
        div, mod = divmod(n, 3)
        if mod == 0: return 3 ** div
        if mod == 1: return 3 ** (div - 1) * 4
        if mod == 2: return 3 ** div * 2

15. 二进制中 1 的个数

刚开始写的代码如下，但是出错了。因为下面代码无法处理负整数的情况。比如 n = -3，-3 的补码是 101，>> 1 变成 110，110 表示 -2，再 >> 1 会变成 111，111 表示 -1，之后会陷入死循环，一直是 -1）

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        cnt = 0
        while n:
            if n & 1:
                cnt += 1
            n = n >> 1  # 除以 2
        return cnt

发现新大陆之使用 n & (n-1)，可以去除 n 的位级表示中最低的那一位 1。正确的代码如下。注意：while 判断条件是 n & 0xffffffff，因为 Python 的整数类型是没有范围限制的，比如 -1 会表示成 11111111...(都是符号位)1，n & (n-1)每次只会消掉末尾的一个 1，所以如果不加 & 0xffffffff，还是会无限循环。但是 C++ 和 Java 就可以不用加，因为它们对整数的定义就是 int 为 4 个字节（最大数就是 0xffffffff），不会死循环。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        cnt = 0
        while n & 0xffffffff:  # python 对整数没有取值范围限制，因此对负数会无限循环
            cnt += 1
            n = n & (n - 1)  # 删去末尾的 1
        return cnt

16. 数值的整数次方

快速幂算法，注意负指数的处理。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        isNegative = False
        if exponent < 0:  # 将指数转化为正数
            isNegative = True
            exponent *= -1
        ans = 1
        while exponent:
            if exponent & 1:
                ans *= base
            base *= base
            exponent >>= 1
        return ans if isNegative == False else (1 / ans)  # 负指数是 ans 的倒数

17. 打印从 1 到最大的 n 位数

因为可能 n 很大，因此数字要用数组存储。可以使用 DFS 回溯法构造每个数字，打印出来。回溯深度为 n，每一个位置有 0~9 这10种算符选择。

# -*- coding:utf-8 -*-
class Solution:
    def print1toN(self, n):
        # write code here
        def search(k):  # k 为深度
            if k == n:
                printNum()
                return
            for i in range(10):  # 算符种数
                nlist[k] = str(i) 
                search(k + 1)

        def printNum():  # 打印结果
            ans, flag = "", True
            for ch in nlist:
                if ch == '0' and flag:  # 去除前导 0
                    continue
                else:
                    flag = False
                    ans += ch
            if ans:  # 不为 ""
                print(ans, end=" ")

        nlist = ['0'] * n  # 字符列表存储各个数字
        search(0)  # 回溯法构造每个数字

Solution().print1toN(3)  # 结果为 1 2 3 ... 999

18.1 在 O(1) 时间内删除链表节点

分两种情况：（1）删除的结点是尾结点；（2）删除的结点不是尾结点。

① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 None，时间复杂度为 O(N)。

综上，如果进行 N 次操作，那么大约需要操作节点的次数为 O(1) * (N-1) + O(N) * 1 ，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。因此该算法的平均时间复杂度为 [O(1) * (N-1) + O(N) * 1] / N = O(1)。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNone(self, phead, delnode):  # delnode 为要删除的结点的指针
        # write code here
        if not phead or not delnode:  # 都为空
            return phead
        if delnode.next:  # 待删除的结点不是尾结点，O(1)
            last = delnode.next
            delnode.val = last.val
            delnode.next = last.next
        else:  # 待删除的结点是尾结点
            if phead == delnode:  # 只有一个结点 
                phead = None
            else:
                pre = phead  # O(n) 
                while pre.next != delnode:
                    pre = pre.next
                pre.next = None  # 令倒数第二个结点的下一个结点指向 None  
        return phead

18.2 删除链表中重复的结点

方法1：使用三个指针，每次进行交换和移动。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead:
            return None
        dummy = ListNode(-1)  # 头节点
        dummy.next = pHead
        pHead = dummy
        # pre为cur的前一个结点，便于删除操作，cur指向相同元素的第一个结点，last为工作指针
        pre, cur, last = pHead, pHead.next, pHead.next.next
        isDup = False  # 标记某一段是否有重复
        while last:
            if cur.val == last.val and isDup == False:  # last 往后移即可
                isDup = True
            elif cur.val != last.val and isDup == True:  # 有重复
                pre.next = last
                cur = last
                isDup = False
            elif cur.val != last.val and isDup == False:  # 无重复
                pre = cur
                cur = last
            last = last.next
        if isDup == True:  # [1,1] or [1,2,2] 这种
            pre.next = None  # [1,2,2]
        return pHead.next  # 注意去掉头部的空结点

方法2：递归，比较好理解。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        cur = pHead.next
        if pHead.val != cur.val:   # [1,2,3,3,4]
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead
        else:  # [1,1,1,1,2]
            while cur and pHead.val == cur.val:
                cur = cur.next
            return self.deleteDuplication(cur)

19. 正则表达式匹配

递归。分为四种情况：

s 和 p 均为空：返回 True
s 不为空，p 为空：返回 Fasle
s 为空，p 不为空：
（1）如果 p 的第二个字符为 *：，递归调用返回 match(s, p[2:])
（2）否则返回 False
s 不为空，p 不为空：
（1）如果 p 的第二个字符为 *：如果 s[0] 和 p[0] 匹配，递归调用返回 mathc(s, p[2:]) || match(s[1:], p)；否则递归调用返回 match(s, p[2:])
（2）否则：如果 s[0] 和 p[0] 匹配，递归调用返回 mathc(s[1:], p[1:])；否则返回 False

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if not s and not pattern:  # 均为空
            return True
        if s and not pattern:  # s 不为空，pattern 为空
            return False
        if not s and pattern:  # s 为空，pattern 不为空
            if len(pattern) > 1 and pattern[1] == '*': # pattern 的第二个字符为 *
                return self.match(s, pattern[2:])
            else:
                return False
        if s and pattern:  # s 不为空，pattern 不为空
            if len(pattern) > 1 and pattern[1] == '*':  # pattern 的第二个字符为 *
                if s[0] == pattern[0] or pattern[0] == '.':
                    # 前者为 "ab" -> "a*ab" 这种，后者为 ab" -> "a*b" 这种 
                    return self.match(s, pattern[2:]) or self.match(s[1:], pattern) 
                else:  # "ab" -> "c*ab" 这种
                    return self.match(s, pattern[2:])
            else:  # pattern 的第二个字符不为 *
                if s[0] == pattern[0] or pattern[0] == '.':  # "ab" -> "ab" 这种
                    return self.match(s[1:], pattern[1:])
                else:
                    return False

剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。这里做一个总结：

剑指offer【03~09】
剑指offer【10~19】
剑指offer【20~29】
剑指offer【30~39】
剑指offer【40~49】
剑指offer【50~59】
剑指offer【60~68】