小锵的博客

题目信息 题目：剑指 Offer 59 - I. 滑动窗口的最大值 时间： 2020-08-10 题目链接：Leetcode tag： 队列 双端队列 滑动窗口 难易程度：困难 题目描述： 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 示例: 123456789101112输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 注意 11. ...

题目信息 题目：剑指 Offer 59 - II. 队列的最大值 时间： 2020-08-09 题目链接：Leetcode tag： 队列 双端队列 难易程度：中等 题目描述： 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 示例1: 1234输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] 示例2: 1234输入: ["MaxQueue","pop_front","max_value"][[],[],[]]输出: [null,-1,-1] 注意 121. 1 <= push_back,pop_front,max_value的总操作数 <= 100002. ...

题目信息 题目： 剑指 Offer 61. 扑克牌中的顺子 时间： 2020-08-08 题目链接：Leetcode tag： 哈希表 排序 难易程度：中等 题目描述： 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。 示例1: 12输入: [1,2,3,4,5]输出: True 示例2: 12输入: [0,0,1,2,5]输出: True 注意 121. 数组长度为 5 2. 数组的数取值为 [0, 13] 解题思路 本题难点 顺子包含’大小王’的特殊情况。 具体思路 集合 Set + 遍历 5 张牌是顺子的 充分条件： 除大小王外，所有牌 无重复 ； 设此 5张牌中最大的牌为 max ，最小的牌为 min（大小王除外），则需满足：max − min < 5 提示 代码 123456789101112131415161718192021222324252627class Solution ...

题目信息 题目： 剑指 Offer 62. 圆圈中最后剩下的数字 时间： 2020-08-07 题目链接：Leetcode tag： 动态规划 迭代 约瑟夫环 难易程度：中等 题目描述： 0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 示例1: 12输入: n = 5, m = 3输出: 3 示例2: 12输入: n = 10, m = 17输出: 2 注意 121. 1 <= n <= 10^52. 1 <= m <= 10^6 解题思路 本题难点 约瑟夫环 N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 具体思路 约塞夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替 下面这个例子是N=8 m=3的例子 ...

题目信息 题目：剑指 Offer 63. 股票的最大利润 时间： 2020-08-06 题目链接：Leetcode tag：动态规划 难易程度：中等 题目描述： 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？ 示例1: 1234输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例2: 123输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 注意 11. 0 <= 数组长度 <= 10^5 解题思路 本题难点 共有 n 天，第 a 天买，第 b 天卖，则需保证 a<b ；可推出交易方案数共有：(n−1)+(n−2)+⋯+2+1=n(n−1)/2种，暴力法的时间复杂度为 O(n^2)。 具体思路 动态规划 状态定义：设动态规划列表 ...

题目信息 题目；剑指 Offer 64. 求1+2+…+n 时间： 2020-08-05 题目链接：Leetcode tag：位运算 限制运算符号 难易程度：中等 题目描述： 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例1: 12输入: n = 3输出: 6 示例2: 12输入: n = 9输出: 45 注意 11. 1 <= n <= 10000 解题思路 本题难点 不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句 具体思路 逻辑运算符： if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true 本题需要实现 “当 n=1 时终止递归” 的需求，可通过 ...

题目信息 题目：剑指 Offer 65. 不用加减乘除做加法 时间： 2020-08-04 题目链接：Leetcode tag： 位运算 限制运算符号 难易程度：中等 题目描述： 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 示例1: 12输入: a = 1, b = 1输出: 2 注意 121. a, b 均可能是负数或 02. 结果不会溢出 32 位整数 解题思路 本题难点 求和不使用 “+”、“-”、“*”、“/” 四则运算符号。 具体思路 位运算 设两数字的二进制形式 a,b ，其求和 s=a+b ，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况： a(i) b(i) 无进位和n(i) 进位和c(i) 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 无进位和 与 异或运算 规律相同 进位 和 与运算 规律相同（并需左移一位） 即可将 s = a+b 转化为： s = 非进位和 n + 进位 c 循环求 n和 c ，直至进位 ...

题目信息 题目：剑指 Offer 66. 构建乘积数组 时间： 2020-08-03 题目链接：Leetcode tag： 限制运算符号 难易程度：简单 题目描述： 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例: 12输入: [1,2,3,4,5]输出: [120,60,40,30,24] 注意 121. 所有元素乘积之和不会溢出 32 位整数2. a.length <= 100000 解题思路 本题难点 不能使用除法，限制运算符号。 具体思路 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] B[i] B[0] = 1 A[1] A[2] … A[n-1] A[n] B[1] = A[0] 1 A[2] … A[n-1] A[n] B[2] = A[0] A[1] 1 … A[n-1] A[n] … … … … ...

题目信息 题目： 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 时间： 2020-08-02 题目链接：Leetcode tag：二叉树 二叉搜索树 递归 迭代 难易程度：简单 题目描述： 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 1234567 6 / \ 2 8 / \ / \0 4 7 9 / \ 3 5 示例1: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例2: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p ...

题目信息 题目： 剑指 Offer 68 - II. 二叉树的最近公共祖先 时间： 2020-08-01 题目链接：Leetcode tag：二叉树 递归 深度优先搜索 难易程度：中等 题目描述： 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 1234567 3 / \ 5 1 / \ / \6 2 0 8 / \ 7 4 示例1: 123输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例2: 123输入: root = [3,5,1,6,2,0,8,null,null,7,4], p ...