- 博客(102)
- 收藏
- 关注
RSS订阅原创 【剑指offer】41.数据流中的中位数
这种解法虽然可以通过，但是执行时间过长，如下图，因此不是最优解。添加数字：堆的插入和弹出操作，时间复杂度为。查找中位数：获取堆顶元素的时间复杂度为。个元素，那么时间复杂度为。因此，总的时间复杂度为。...
2022-08-17 23:48:43
175
原创 【剑指offer】38.字符串的排列
假设字符串的长度为$N$，则一共有$N\times(N-1)\times(N-2)\times...\times2\times1$种排列方案，也就是递归函数要执行多少次，此处的时间复杂度为$O(N!)$，在保存每次排列结果时回调用函数`join()`，其时间复杂度为$O(N)$，因此总的时间复杂度为$O(N!\times N)$。......
2022-07-15 02:30:57
109
原创 【剑指offer】37.序列化二叉树
假设二叉树有$N$个节点，那么最坏的情形下，存在$N+1$个`null`，因此时间复杂度为$O(2N+1)$，即时间复杂度为$O(N)$。
2022-07-15 01:02:35
152
原创 【剑指offer】36.二叉搜索树与双向链表
本题利用中序遍历+深度优先搜索解决。参考：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/根据上述思路，代码如下：时间复杂度分析假设二叉搜索树有NNN个节点，中序遍历需要遍历所有节点，因此时间复杂度为O(N)O(N)O(N)。...
2022-07-07 02:47:16
177
原创 【剑指offer】34.二叉树中和为某一值的路径
本题使用深度优先搜索+路径记录的方法解决。参考：根据上述思路，代码如下：时间复杂度分析假设二叉树的节点数量为NNN，深度优先搜索需要遍历二叉树的所有节点，因此时间复杂度为O(N)O(N)O(N)。...
2022-07-06 23:50:57
174
原创 【剑指offer】57.和为s的两个数字
参考：https://www.bilibili.com/video/BV1zL4y1n7tG?spm_id_from=333.337.search-card.all.click&vd_source=e0510cf9e4de2d7c94df0a249e260c4c根据上述思路，代码如下：时间复杂度分析假设数组中有NNN个元素，双指针共同线性遍历整个数组，因此时间复杂度为O(N)O(N)O(N)。...
2022-07-05 02:35:45
100
原创 【剑指offer】33.二叉搜索树的后序遍历序列
本题采用递归分治的方法解决。具体思路参考：根据上述思路，代码如下：时间复杂度分析假设二叉搜索树有NNN个节点，每轮函数都要确定出一个根节点，因此有NNN轮，最差情况下，当树表现为一个链表，每轮递归都要遍历树的所有节点，因此时间复杂度为O[(N−1)+...+2+1]=O(N(N−1)2)O[(N-1)+...+2+1]=O(\frac{N(N-1)}{2})O[(N−1)+...+2+1]=O(2N(N−1))，即时间复杂度为O(N2)O(N^2)O(N2)。...
2022-07-05 01:58:41
165
原创 【剑指offer】39.数组中出现次数超过一半的数字
本题直观上的一个解法就是使用哈希表，其键为数组中的元素，其值为各元素出现的次数。找出出现次数超过数组长度一半的那个元素。代码如下：时间复杂度分析假设数组中的元素数量为NNN，那么时间复杂度为O(N)O(N)O(N)。摩尔投票法，参考：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-c
2022-07-01 02:24:04
189
原创 【剑指offer】52.两个链表的第一个公共节点
两个链表相交之后，一定不会再分开，因为这里的链表是单链表，next指针只会指向一个节点。既然如此，我们可以从后往前寻找第一个公共的节点。代码如下：时间复杂度分析假设链表A的节点有MMM个，链表B的节点有NNN个，公共节点有LLL个，代码中第一个循环的时间复杂度为O(M)O(M)O(M)，第二个循环的时间复杂度为O(N)O(N)O(N)，第三个循环的时间复杂度为O(L)O(L)O(L)，总的时间复杂度为O(M+N+L)O(M+N+L)O(M+N+L)，令n=M+N+Ln=M+N+Ln=M+N+L，因此时间
2022-07-01 00:46:09
77
原创 【剑指offer】31.栈的压入、弹出序列
参考：https://www.bilibili.com/video/BV1Qh411Z7bu?spm_id_from=333.337.search-card.all.click&vd_source=e0510cf9e4de2d7c94df0a249e260c4c代码如下：时间复杂度分析假设压入序列中有NNN个元素，每个元素最多有1次压入操作和1次弹出操作，因此时间复杂度最坏为O(2N)O(2N)O(2N)，即O(N)O(N)O(N)。...
2022-06-30 01:03:36
117
原创 【剑指offer】29.顺时针打印矩阵
参考：https://www.bilibili.com/video/BV1sV411h7ss/?spm_id_from=333.788&vd_source=e0510cf9e4de2d7c94df0a249e260c4c代码如下：** 时间复杂度分析**假设矩阵的尺寸为M∗NM*NM∗N，因为矩阵中每个元素都会被打印，因此时间复杂度为O(MN)O(MN)O(MN)。......
2022-06-29 01:28:59
125
原创 【剑指offer】25.合并两个排序的链表
参考：https://www.bilibili.com/video/BV12y4y1B7vR?spm_id_from=333.337.search-card.all.click&vd_source=e0510cf9e4de2d7c94df0a249e260c4c代码如下：时间复杂度分析假设链表l1有mmm个节点，链表l2有nnn个节点，因为合并链表需要遍历链表l1和链表l2，因此时间复杂度为O(m+n)O(m+n)O(m+n)。...
2022-06-29 00:34:30
103
原创 【剑指offer】22.链表中倒数第k个节点
将链表的节点保存在数组中，返回索引为的节点，即为链表中倒数第k个节点。时间复杂度分析假设链表中有nnn个节点，本方法需要遍历链表中每个节点，因此时间复杂度为O(n)O(n)O(n)。使用快慢指针。时间复杂度分析假设链表中有nnn个节点，快指针先走kkk个节点，然后再走n−kn-kn−k个节点，总共走了nnn个节点，因此时间复杂度为O(n)O(n)O(n)。...
2022-06-28 02:11:18
83
原创 【剑指offer】21.调整数组顺序使奇数位于偶数前面
遍历数组，分别将奇数和偶数保存到两个列表中，再拼接在一起。代码如下：时间复杂度分析假设数组numsnumsnums中有nnn个数字，本方法中采用循环遍历数组中每个元素，因此时间复杂度为O(n)O(n)O(n)。采用双指针分别寻找数组的奇数和偶数，再互换。可参考：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/mian-shi-ti-21-diao
2022-06-28 00:56:24
82
原创 【剑指offer】20.表示数值的字符串
本题参考：https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/jian-zhi-offer-20-biao-shi-shu-zhi-de-zi-060v/采用遍历字符串判断的方法，步骤如下：1.首先定义4个标志位，即： 1.1 ，表示之前是否存在数字0−90-90−9 1.2 ，表示之前是否存在eee或者EEE 1.3 ，表示之前是否存在+++或者−-− 1.4 ，表示之前是否存在小数点...2.
2022-06-27 23:49:03
162
原创 【剑指offer】19.正则表达式匹配
本题采用动态规划的方法解决，难点在于弄清楚各种讨论的情况。参考：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/本题代码如下：时间复杂度分析本方法中有2次循环，第一次的时间复杂度为O(n/2)O(n/2)O(n/2)，第二次中还有一层循环，其时间复杂度为O(mn)O(mn)O(mn)，总的时间复杂度为O(mn
2022-06-24 00:56:33
184
原创 【剑指offer】18.删除链表的节点
本题不是很复杂，直接上代码。时间复杂度分析假设链表中有nnn个节点，最好的情况下，待删除的是头节点，时间复杂度为O(1)O(1)O(1)，最差的情况下，待删除的是最后一个节点，需要遍历链表，时间复杂度为O(n)O(n)O(n)。...
2022-06-22 00:48:19
84
原创 【剑指offer】17.打印从1到最大的n位数
假设n=1n=1n=1，打印[1,2,...,9][1,2,...,9][1,2,...,9]假设n=2n=2n=2，打印[1,2,...,99][1,2,...,99][1,2,...,99]假设n=3n=3n=3，打印[1,2,...,999][1,2,...,999][1,2,...,999]…以此类推最大的数字maxmaxmax与nnn之间的关系为max=10n−1max=10^n-1max=10n−1根据题意，可写如下代码：提交之后，顺利通过。看了评论区，说这题的本意是考察大数问题
2022-06-21 23:10:30
115
原创 【剑指offer】16.数值的整数次方
一开始的写法是：提交之后，也是可以通过的，但是这个题目肯定不是考这个的。然后的写法是：提交之后，显示“超出时间限制”。这种方法的时间复杂度是O(n)O(n)O(n)，而题目中提示−231≤n≤231-2^{31} \leq n \leq 2^{31}−231≤n≤231，所以当nnn很大时，这种方法是有可能超出时间限制的，因此不是本题的解法。参考https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-s
2022-06-21 00:51:38
81
原创 【剑指offer】15.二进制中1的个数
本题考察位运算。假设二进制数为101110111011，令其和111进行与运算，即1011&11011\&11011&1，此时后者相当于000100010001，即1011&00011011\&00011011&0001，结果为000100010001，即111。假设二进制数为101010101010，令其和111进行与运算，即1010&11010\&11010&1，结果为000。总结：将二进制数和111进行与运算，如果二进制数最后一位数字为000，那么与运算的结果为000，如果二进制数最后一位数字为
2022-06-18 02:15:01
52
原创 【剑指offer】14-II.剪绳子
本题与【剑指offer】14-I.剪绳子几乎一致，不同的地方是：1.答案需要取模1e9+7；2.n的范围不再是2≤n≤582 \leq n \leq 582≤n≤58，而是2≤n≤10002 \leq n \leq 10002≤n≤1000。可见，本题的计算结果大，耗时更久，如果继续采用【剑指offer】14-I.剪绳子中的做法，很有可能会超时，从而报错。然而我还是试了一下，将【剑指offer】14-I.剪绳子的代码输入进去，正常通过了，但是的确比较耗时（1060ms），所以本题肯定有更优的解法。更
2022-06-17 01:08:45
102
原创 【剑指offer】14-I.剪绳子
分析本题采用动态规划的方法来解决。假设f(n)f(n)f(n)表示长度为nnn的绳子被剪之后的最大乘积。将绳子剪断1次，设第1段的长度为jjj，那么第2段的长度为n−jn-jn−j，这里有j=1,2,...,n−1j=1,2,...,n-1j=1,2,...,n−1。对于第2段绳子，我们有两种处理方法：1.如果第2段绳子不剪，那么第2段绳子的最大乘积为n−jn-jn−j；2.如果第2段绳子剪断，那么第2段绳子的最大乘积为f(n−j)f(n-j)f(n−j)。因此，长度为nnn的绳子被剪之后的最大乘
2022-06-16 23:53:05
96
1
原创 【剑指offer】13.机器人的运动范围
本题与【剑指offer】12.矩阵中的路径有相似之处，均可采用深度优先搜索（DFS）和回溯的方法来解决。本题参考思路：https://www.bilibili.com/video/BV1fD4y197vW/?spm_id_from=333.788&vd_source=e0510cf9e4de2d7c94df0a249e260c4c代码如下：时间复杂度分析此题的时间复杂度与KKK的大小有关。最好的情况下，只访问1个格子（K=0K=0K=0），此时的时间复杂度为O(1)O(1)O(1)；最差的情况下，所
2022-06-16 00:53:21
70
原创 【剑指offer】12.矩阵中的路径
本题使用深度优先搜索+剪枝的方法来解决，具体思路参考：时间复杂度分析假设矩阵board的大小为M∗NM*NM∗N，单词word的长度为KKK。最差情况下，矩阵中MNMNMN个元素都会搜索单词中的KKK个字符，这个时间复杂度为O(MN)O(MN)O(MN)，而每个字符有333个搜索方向，其时间复杂度为O(3K)O(3^K)O(3K)，故总的时间复杂度为O(3kMN)O(3^kMN)O(3kMN)。......
2022-06-14 23:57:32
54
原创 【剑指offer】07.重建二叉树
本题需要利用分治思想进行解答，具体思路参考评论区大佬。代码如下：时间复杂度分析假设二叉树有NNN个节点。初始化哈希表dic需要遍历inorder，其时间复杂度为O(N)O(N)O(N)；递归共建立NNN个节点，每层递归中的根节点建立、搜索操作的时间复杂度为O(1)O(1)O(1)；因此总的时间复杂度为O(N)O(N)O(N)。......
2022-06-10 01:50:03
124
原创 【剑指offer】42.连续子数组的最大和
Python3本题采用动态规划的方法求解。参考评论区大佬的思路动态规划解析状态定义：设动态规划列表dpdpdp，dp[i]dp[i]dp[i]表示以元素nums[i]nums[i]nums[i]为结尾的连续子数组的最大和。转移方程： - 当dp[i−1]>0dp[i-1]>0dp[i−1]>0时，dp[i]=dp[i−1]+nums[i]dp[i] = dp[i-1] + nums[i]dp[i]=dp[i−1]+nums[i]
2022-06-09 22:49:33
55
原创 【剑指offer】63.股票的最大利润
Python3直接采用暴力解法，建立矩阵，其行和列均为输入的价格数组，逐元素计算差值，返回矩阵最大值。代码如下：class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 dp = [] for i in range(len(prices)): tmp = []
2022-05-25 23:43:49
137
原创 【剑指offer】10-II.青蛙跳台阶问题
Python3先简单列举一些台阶级数，看看有无数学规律： 当台阶为0级时，有1种跳法； 当台阶为1级时，有1种跳法； 当台阶为2级时，有2种跳法； 当台阶为3级时，有3种跳法； … 当台阶为7级时，有21种跳法； … 当台阶为n级时，有?种跳法。好像看不出有什么规律。换个思路： 我们假设台阶的级数为nnn，青蛙有F(n)F(n)F(n)种跳法。无论如何，青蛙的最后一跳，要么是跳1级台阶，要么是跳2级台阶。可以知道： 1.当最后一跳跳了1级台阶，那么之前跳了n−1
2022-05-25 00:37:22
123
原创 【剑指offer】10-I.斐波那契数列
Python3本题最开始的想法是直接使用递归来处理，于是有如下代码：class Solution: def fib(self, n: int) -> int: if n == 0: return 0 if n == 1: return 1 return (self.fib(n-1) + self.fib(n-2)) % 1000000007但是提交之后，显示超出时间限制，答案错误。分析了一下：从时间的角度来看，这种做法有大量的重复计算，增加了耗时；从空间的角度来看，重
2022-05-24 23:43:04
107
原创 【剑指offer】28.对称的二叉树
Python3# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def isMirror(self, A: TreeNode, B: TreeNode) -> bool: # 判断二叉
2022-05-24 02:29:37
47
原创 【剑指offer】27.二叉树的镜像
Python3方法1 利用辅助队列遍历二叉树的每个节点，交换其左右子节点# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None"""解题思路：利用辅助队列遍历二叉树的所有节点，并交换每个节点的左右子节点"""class Solu
2022-05-24 01:15:15
118
原创 【剑指offer】26.树的子结构
Python3# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None"""解题思路：此题需要采用递归的方法进行判断"""class Solution: # 第二步：再看这个函数 def isContain(sel
2022-05-23 23:52:23
50
原创 【剑指offer】32-III.从上到下打印二叉树
Python3本题是在题32-II基础上的延伸，可与【剑指offer】32-II.从上到下打印二叉树比较着看。方法1 BFS搜索+双端队列
2022-05-18 23:06:15
171
原创 【剑指offer】32-II.从上到下打印二叉树
Python3本题是在题32-I基础上的延伸，可与【剑指offer】32-I.从上到下打印二叉树比较着分析。# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def levelOrder(se
2022-05-17 01:41:16
194
原创 【剑指offer】32-I.从上到下打印二叉树
Python3题目要求从上到下、同一层从左到右打印二叉树，这属于二叉树的广度优先搜索（BFS，也称为宽度优先搜索），其基本过程是从根节点开始，沿着二叉树的宽度遍历二叉树的节点，如果所有节点均被访问，那算法终止，一般采用队列来辅助实现广度优先搜索。本题算法流程：特殊情形：如果二叉树的根节点为空，那直接返回空列表[]初始化定义数组array，用于保存二叉树的打印结果，初始化array=[]定义队列queue，其包含根节点root，即queue=[root]BFS循环：当队列queue
2022-05-15 22:35:14
187
原创 【剑指offer】50.第一个只出现一次的字符
Python3在字符串s中找出第一个只出现一次的字符，首先想到使用哈希表统计每个字符出现的次数，然后返回第一个次数为1的字符。一开始写的代码如下：class Solution: def firstUniqChar(self, s: str) -> str: hash_map = {} # 定义一个哈希表 for ch in s: # ch 表示字符串s中的字符 hash_map[ch] = [] for ch in s: hash_map[ch].append(ch
2022-05-13 01:22:01
99
原创 【剑指offer】11.旋转数组的最小数字
Python3方法1 直接使用min()函数"""解题思路：旋转数组那终究也是数组，直接使用min()函数返回数组的最小值即可"""class Solution: def minArray(self, numbers: List[int]) -> int: return min(numbers)但本题题意写的这么复杂，肯定不是为了考核min()函数，所以要考虑其他方法。方法2 哈希表"""解题思路：由于原来是一个升序排列的数组，将最开始的若干个元素搬到数组的末尾，那最小元素
2022-05-13 00:13:00
78
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人