剑指offer【10~19】

题目链接:

剑指offer 10-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 终于过了一遍,大多数题目还是很简单的,但是题目具有代表性,涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • 剑指offer【60~68】

    动态规划。令 dp[n][6*n],其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。则 dp[-1][1...6*n] 就是每一种点数的次数。点...

    echobingo
  • Leetcode【319、672】

    灯泡开关。初始时有 n 个灯泡关闭,第 i 轮,每 i 个灯泡切换一次开关。找出 n 轮后有多少个亮着的灯泡。

    echobingo
  • 编码篇-iOS开发中的奇巧小伎

    最近搜集了自己以前的笔记中的一些小知识点,归为这篇文章,都是亲测有效的奇巧小伎,当你使用到时,你会大呼过瘾的。

    進无尽
  • iOS SDWebimage 源码阅读

    简介 SDWebimage是 iOS 的图片加载框架。它支持从网络中下载且缓存图片,并设置图片到对应的 UIImageView 控件或者 UIButton 控...

    赵哥窟
  • 接口测试 | 25 requests + pytest测试实例

    概述 本文主要分享如何将pytest和requests结合一起使用,让大家有个初步的了解。 主要内容有: pytest简介 pytest + requests示...

    苦叶子
  • 接口测试 | 25 requests + pytest测试实例

    概述 本文主要分享如何将pytest和requests结合一起使用,让大家有个初步的了解。 主要内容有: pytest简介 pytest + requests示...

    苦叶子
  • [Leetcode][python]Symmetric Tree/对称二叉树

    其中左子树和右子树对称的条件: 两个节点值相等,或者都为空 左节点的左子树和右节点的右子树对称 左节点的右子树和右节点的左子树对称

    后端技术漫谈
  • 如何写出少bug的代码,你需要这4点建议

    小编推荐:Fundebug专注于 JavaScript、微信小程序、微信小游戏,Node.js 和 Java 线上 bug 实时监控。真的是一个很好用的 bug...

    Fundebug
  • Android实现状态栏和虚拟按键背景颜色的变化实例代码详解

    今天介绍一下,我在项目开发过程中,实现状态栏和虚拟按键背景颜色变化的方法,实现方式是,通过隐藏系统的状态栏和虚拟按键的背景,实现图片和背景显示到状态栏和虚拟按键...

    砸漏

扫码关注云+社区

领取腾讯云代金券