题解——week7"/>
《剑指offer》题解——week7
❤ 作者主页:Java技术一点通的博客
❀ 个人介绍:大家好,我是Java技术一点通!( ̄▽ ̄)~*
❀ 微信公众号:Java技术一点通
🍊 记得点赞、收藏、评论⭐️⭐️⭐️
📣 认真学习! ! !🎉🎉
文章目录
- 一、剑指 Offer 59 - I. 滑动窗口的最大值
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 二、剑指 Offer 60. n个骰子的点数
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、剑指 Offer 61. 扑克牌中的顺子
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、剑指 Offer 62. 圆圈中最后剩下的数字
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 五、剑指 Offer 63. 股票的最大利润
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、剑指 Offer 64. 求1+2+…+n
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 七、剑指 Offer 65. 不用加减乘除做加法
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 八、剑指 Offer 66. 构建乘积数组
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 九、剑指 Offer 67. 把字符串转换成整数
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 十、剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 十一、剑指 Offer 68 - II. 二叉树的最近公共祖先
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 十二、面试题13. 机器人的运动范围
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 十三、面试题59 - II. 队列的最大值
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
一、剑指 Offer 59 - I. 滑动窗口的最大值
1. 题目描述
2. 思路分析
窗口对应的数据结构为 双端队列 ,本题使用 单调队列 即可解决本问题。遍历数组时,每轮保证单调队列 d e q u e deque deque :
- d e q u e deque deque 内 仅包含窗口内的元素 ⇒ \Rightarrow ⇒ 每轮窗口滑动移除了元素 n u m s [ i − 1 ] nums[i - 1] nums[i−1] ,需将 dequedeque 内的对应元素一起删除。
- d e q u e deque deque 内的元素 非严格递减 ⇒ \Rightarrow ⇒ 每轮窗口滑动添加了元素 n u m s [ j + 1 ] nums[j + 1] nums[j+1] ,需将 d e q u e deque deque 内所有 < n u m s [ j + 1 ] < nums[j + 1] <nums[j+1] 的元素删除。
算法流程:
- 初始化: 双端队列 d e q u e deque deque,结果集合 r e s res res;
- 滑动窗口:
- 若
deque.front() <= i - k
,说明在插入新的元素时队头不能继续留在队列中,则将队首元素出队; - 删除 d e q u e deque deque 内所有 n u m s [ i ] nums[i] nums[i] < < < 队头的元素,以保持 d e q u e deque deque 递减;
- 将 i i i 添加至 d e q u e deque deque 尾部;
- 若已经形成窗口(即 i > = k − 1 i >= k - 1 i>=k−1),则将窗口最大值(即队首元素 d e q u e deque deque)添加至列表 r e s res res;
- 若
- 返回值: 返回结果列表 r e s res res;
3. 代码实现
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;deque<int> q;for (int i = 0; i < nums.size(); i ++ ) {while (q.size() && q.front() <= i - k) q.pop_front();while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();q.push_back(i);if (i >= k - 1) res.push_back(nums[q.front()]);}return res;}
};
二、剑指 Offer 60. n个骰子的点数
1. 题目描述
2. 思路分析
3. 代码实现
三、剑指 Offer 61. 扑克牌中的顺子
1. 题目描述
2. 思路分析
根据题意,此 5 张牌是顺子的 条件 如下:
- 除大小王外, 所有牌 无重复;
- 设此 5 张牌中最大的牌为 m a x max max,最小的牌为 m i n min min(大小王除外), 则需满足
max - min < 5
;
算法流程:
- 初始化: 先对数组进行排序;
- 判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断 n u m s [ i ] = n u m s [ i + 1 ] nums[i] = nums[i + 1] nums[i]=nums[i+1] 是否成立来判重。
- 获取最大 / 最小的牌: 排序后,数组末素 se n u m s [ 4 ] nums[4] nums[4] 为最大牌;元素 n u m s [ k ] nums[k] nums[k] 为最小牌,其中 k k k 为大小王的数量。
3. 代码实现
class Solution {
public:bool isStraight(vector<int>& nums) {int k = 0;sort(nums.begin(), nums.end());for (int i = 0; i < 4; i ++ ) {if (nums[i] == 0) k ++;else if (nums[i] == nums[i + 1]) return false;}return nums[4] - nums[k] < 5;}
};
四、剑指 Offer 62. 圆圈中最后剩下的数字
1. 题目描述
2. 思路分析
本题是著名的约瑟夫环问题,用数学解法。
假设有一圈数字 [ 0 , 1 , 2 , 3 , 4 ] , m = 3 [0, 1, 2, 3, 4],m = 3 [0,1,2,3,4],m=3
我们每次将删除元素的后一个元素放在最前面方便计数:
- 删除 2 2 2 → [ 3 , 4 , 0 , 1 ] [3, 4, 0, 1] [3,4,0,1]
- 删除 0 0 0 → [ 1 , 3 , 4 ] [1, 3, 4] [1,3,4]
- 删除 4 4 4 → [ 1 , 3 ] [1, 3] [1,3]
- 删除 1 1 1 → [ 3 ] [3] [3]
尝试反推:
如何从最后剩下的元素的索引 0 0 0 反推至第一轮该元素的索引呢?
第四轮反推,补上 m m m 个位置,然后模上当时的数组大小 2,位置是 (0 + 3) % 2 = 1
。
第三轮反推,补上 m m m 个位置,然后模上当时的数组大小 3,位置是 (1 + 3) % 3 = 1
。
第二轮反推,补上 m m m 个位置,然后模上当时的数组大小 4,位置是 (1 + 3) % 4 = 0
。
第一轮反推,补上 m m m 个位置,然后模上当时的数组大小 5,位置是 (0 + 3) % 5 = 3
。
所以最后剩下的数字的下标就是 3
。因为数组是从 0 0 0 开始的,所以最终的答案就是 3
。
反推的公式: (当前index + m) % 上一轮剩余数字的个数
。
3. 代码实现
class Solution {
public:int lastRemaining(int n, int m) {int res = 0;for (int i = 2; i <= n; i ++ ) {res = (res + m) % i;}return res;}
};
五、剑指 Offer 63. 股票的最大利润
1. 题目描述
2. 思路分析
遍历数组:
我们只需要在最低点的时候买入股票就最好了,因此只要用一个变量 c o s t cost cost 来记录最低价格,我们就可以假设股票是在这一天购买的。那么在第 i i i 天卖出股票能得到的利润是 p r i c e s [ i ] − c o s t prices[i] - cost prices[i]−cost。
3. 代码实现
class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0, cost = INT_MAX;for (int price : prices) {cost = min(cost, price);res = max(res, price - cost);}return res;}
};
六、剑指 Offer 64. 求1+2+…+n
1. 题目描述
2. 思路分析
解题思路: 递归
最直接的方法就是用递归, s u m ( n ) = n + s u m ( n − 1 ) sum(n) =n + sum(n - 1) sum(n)=n+sum(n−1),但是要注意终止条件,由于求的是 1 + 2 + . . . + n 1 + 2 + ... + n 1+2+...+n的和,所以需要在 n = 0 n = 0 n=0 的时候跳出递归,由于题目要求不能使用 i f , w h i l e if, while if,while 等分支进行判断,可以考虑利用 && 短路运算来终止条件。
3. 代码实现
class Solution {
public:int sumNums(int n) {int res = n;n > 0 && (res += sumNums(n - 1));return res;}
};
七、剑指 Offer 65. 不用加减乘除做加法
1. 题目描述
2. 思路分析
解题思路:
本题考察对位运算的灵活使用,即使用 位运算 实现加法。
通过观察发现,无进位和 与 异或运算 规律相同,进位 和 与运算 规律相同(并需左移一位)。因此,无进位和 n n n 与进位 c c c 的计算公式如下:
{ n = a ⊕ b 非进位和:异或运算 c = a & b < < 1 进位:与运算 + 左移一位 \begin{cases} n=a⊕b & 非进位和:异或运算\\ c=a\&b<<1 & 进位:与运算 + 左移一位 \end{cases} {n=a⊕bc=a&b<<1非进位和:异或运算进位:与运算+左移一位
(和 s s s )=(非进位和 n n n )+(进位 c c c )。即可将 s = a + b s = a + b s=a+b 转化为: s = a + b ⇒ s = n + c s=a+b⇒s=n+c s=a+b⇒s=n+c
若数字 a a a 和 b b b 中有负数,则变成了减法,如何处理?
在计算机系统中,数值一律用 补码 来表示和存储。补码的优势: 加法、减法可以统一处理(CPU只有加法器)。因此,以上方法 同时适用于正数和负数的加法 。
3. 代码实现
class Solution {
public:int add(int a, int b) {while (b) {int sum = a ^ b;int carry = (unsigned int)(a & b) << 1; // C++中负数不支持左移位,因为结果是不定的a = sum;b = carry;}return a;}
};
八、剑指 Offer 66. 构建乘积数组
1. 题目描述
2. 思路分析
解题思路:
本题的难点在于 不能使用除法 ,即需要 只用乘法 生成数组 B B B 。根据题目对 B [ i ] B[i] B[i] 的定义,可列表格,如下图所示。
根据表格的主对角线(全为 1 ),可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积,即可 不使用除法 就获得结果。
算法流程:
- 初始化: 数组 B B B,其中 B [ 0 ] = 1 B[0] = 1 B[0]=1;辅助变量 t m p = 1 tmp = 1 tmp=1;
- 计算 B [ i ] B[i] B[i] 的 下三角 各元素的乘积,直接乘入 B [ i ] B[i] B[i];
- 计算 B [ i ] B[i] B[i] 的 上三角 各元素的乘积,记为 t m p tmp tmp, 并乘入 B [ i ] B[i] B[i];
- 返回 B B B。
3. 代码实现
class Solution {
public:vector<int> constructArr(vector<int>& a) {int n = a.size();if (n == 0) return {};vector<int> b(n, 1);b[0] = 1;int tmp = 1;for (int i = 1; i < n; i ++ ) {b[i] = b[i - 1] * a[i - 1];}for (int i = n - 2; i >= 0; i -- ) {tmp *= a[i + 1];b[i] *= tmp;}return b;}
};
九、剑指 Offer 67. 把字符串转换成整数
1. 题目描述
2. 思路分析
算法流程:
- 首部空格: 删除之即可;
- 符号位: 三种情况,即 “+”, “-”, “无符号”;新建一个变量保存符号位,返回前判断正负即可;
- 数字字符:
- 字符转数字: “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减即可;
- 数字拼接: 若从左向右遍历数字,设当前位字符为 c c c ,当前位数字为 x x x ,数字结果为 r e s res res ,则数字拼接公式为: r e s = r e s ∗ 10 + x − ′ 0 ′ res = res * 10 + x - '0' res=res∗10+x−′0′;
- 数组越界问题: 题目要求返回的数值范围应在 [ − 2 31 , 2 31 − 1 ] [-2^{31}, 2^{31} - 1] [−231,231−1] ,因此需要考虑数字越界问题。而由于题目指出 环境只能存储 32 位大小的有符号整数 ,因此判断数字越界时,要始终保持 r e s res res 在 i n t int int 类型的取值范围内。
3. 代码实现
class Solution {
public:int strToInt(string str) {int k = 0;while (k < str.size() && str[k] == ' ') k ++;if (k == str.size()) return 0;int minus = 1;if (str[k] == '-') minus = -1, k ++;else if (str[k] == '+') k ++;long long res = 0;while (k < str.size() && str[k] >= '0' && str[k] <= '9') {res = res * 10 + str[k] - '0';k ++;if (res > INT_MAX) break;}res *= minus;if (res > INT_MAX) res = INT_MAX;if (res < INT_MIN) res = INT_MIN;return res;}
};
十、剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
1. 题目描述
2. 思路分析
解题思路:
祖先的定义: 若节点 p p p 在节点 r o o t root root 的左 / 右子树中, 或者 p = r o o t p = root p=root,则称 r o o t root root 是 p p p 的祖先。
最近公共祖先的定义: 设节点 r o o t root root 为节点 p , q p,q p,q 的某公共祖先,若其左子节点 r o o t − > l e f t root->left root−>left 和右子节点 r o o t − > r i g h t root->right root−>right 都不是 p , q p,q p,q 的公共祖先,则称 r o o t root root 是 “最近的公共祖先” 。
根据以上定义,若 r o o t root root 是 p , q p,q p,q 的 最近公共祖先 ,则只可能为以下情况之一:
- p p p 和 q q q 在 r o o t root root 的子树中,且分列 r o o t root root 的 异侧(即分别在左、右子树中);
- p = r o o t p = root p=root,且 q q q 在 r o o t root root 的左或右子树中;
- q = r o o t q=root q=root,且 p p p 在 r o o t root root 的左或右子树中;
算法流程:
- 循环搜索: 当节点 r o o t root root 为空时跳出;
- 当 p , q p, q p,q 都在 r o o t root root 的 右子树 中,则遍历至 r o o t − > r i g h t root->right root−>right ;
- 否则,当 p , q p, q p,q 都在 r o o t root root 的 左子树 中,则遍历至 r o o t − > l e f t root->left root−>left ;
- 否则,说明找到了 最近公共祖先 ,跳出。
- 返回值: 返回最近公共祖先 r o o t root root。
3. 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while (root != NULL) {if (root->val < p->val && root->val < q->val)root = root->right;else if (root->val > p->val && root->val > q->val)root = root->left;else break;}return root;}
};
十一、剑指 Offer 68 - II. 二叉树的最近公共祖先
1. 题目描述
2. 思路分析
考虑通过递归对二叉树进行先序遍历,当遇到节点 p p p 或 q q q 时返回。从底至顶回溯,当节点 p , q p, q p,q 在节点 r o o t root root 的异侧时,节点 r o o t root root 即为最近公共祖先,则向上返回 r o o t root root 。
算法流程:
- 终止条件:
- 当越过叶节点,则直接返回 n u l l null null ;
- 当 r o o t root root 等于 p , q p, q p,q ,则直接返回 r o o t root root ;
- 递推工作:
- 开启递归左子节点,返回值记为 l e f t left left ;
- 开启递归右子节点,返回值记为 r i g h t right right ;
- 返回值: 根据 leftleft 和 rightright ,可展开为四种情况:
- 当 l e f t left left 和 r i g h t right right 同时为空 :说明 r o o t root root 的左 / 右子树中都不包含 p , q p,q p,q ,返回 n u l l null null ;
- 当 l e f t left left 和 r i g h t right right 同时不为空 :说明 p , q p, q p,q 分列在 r o o t root root 的 异侧 (分别在 左 / 右子树),因此 r o o t root root 为最近公共祖先,返回 r o o t root root ;
- 当 l e f t left left 为空 , r i g h t right right 不为空 : p , q p,q p,q 都不在 r o o t root root 的左子树中,直接返回 r i g h t right right 。具体可分为两种情况:
- p , q p,q p,q 其中一个在 r o o t root root 的 右子树 中,此时 r i g h t right right 指向 p p p(假设为 p p p );
- p , q p,q p,q 两节点都在 r o o t root root 的 右子树 中,此时的 r i g h t right right 指向 最近公共祖先节点 ;
- 当 l e f t left left 不为空 , r i g h t right right 为空 :与情况 3. 3. 3. 同理;
观察发现, 情况 1. 可合并至 3. 和 4. 内。
3. 代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == NULL || root == p || root == q) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if (left == NULL) return right;if (right == NULL) return left;return root;}
};
十二、面试题13. 机器人的运动范围
1. 题目描述
2. 思路分析
算法流程:
- 初始化: 将机器人初始点 ( 0 , 0 ) (0, 0) (0,0) 加入到队列 q u e u e queue queue;
- 终止条件: 当 q u e u e queue queue 为空,代表已遍历完所有可达解。
- 迭代过程:
- 单元格出队: 当队首单元格的坐标出队,作为当前搜索的单元格;
- 判断是否跳出:若行列索引越界 或者 数位和超出目标值 k k k 或者当前元素已访问过,则直接 c o n t i n u e continue continue,否则 r e s res res 加 1;
- 标记当前单元格: 当单元格索引 ( i , j ) (i, j) (i,j) 存入到 s t st st中,代表此单元格 已被访问过;
- **单元格入队:**将下一个合法的单元格的索引加入队列中;
- 返回值: 直接返回 r e s res res即可。
3. 代码实现
class Solution {
public:int get_sum(pair<int, int> p) {int s = 0;while (p.first) {s += p.first % 10;p.first /= 10;}while (p.second) {s += p.second % 10;p.second /= 10;}return s;}int movingCount(int m, int n, int k) {if (!m || !n) return 0;queue<pair<int, int>> q;vector<vector<bool>> st(m, vector<bool>(n, false));int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int res = 0;q.push({0, 0});while (q.size()) {auto t = q.front();q.pop();if (st[t.first][t.second] || get_sum(t) > k) continue;res ++;st[t.first][t.second] = true;for (int i = 0; i < 4; i ++ ) {int x = t.first + dx[i], y = t.second + dy[i];if (x >= 0 && x < m && y >= 0 && y < n) q.push({x, y});}}return res;}
};
十三、面试题59 - II. 队列的最大值
1. 题目描述
2. 思路分析
解题思路:
对于普通队列,入队 push_back() 和出队 pop_front() 的时间复杂度均为 O ( 1 ) O(1) O(1) ;本题难点为实现查找最大值 max_value() 的 O ( 1 ) O(1) O(1) 时间复杂度。
假设队列中存储 N N N 个元素,从中获取最大值需要遍历队列,时间复杂度为 O ( N ) O(N) O(N) ,单从算法上无优化空间。
考虑利用 数据结构 来实现,即经常使用的 “空间换时间” 。考虑构建一个递减列表来保存队列 所有递减的元素 ,递减链表随着入队和出队操作实时更新,这样队列最大元素就始终对应递减列表的首元素,实现了获取最大值 O ( 1 ) O(1) O(1) 时间复杂度。
为了实现此递减列表,需要使用 双向队列 ,假设队列已经有若干元素:
- 当执行入队
push_back()
时: 若入队一个比队列某些元素更大的数字 x x x ,则为了保持此列表递减,需要将双向队列 尾部所有小于 x x x 的元素 弹出。 - 当执行出队
pop_front()
时: 若出队的元素是最大元素,则 双向队列 需要同时 将首元素出队 ,以保持队列和双向队列的元素一致性。
使用双向队列原因:维护递减列表需要元素队首弹出、队尾插入、队尾弹出操作皆为 O ( 1 ) O(1) O(1) 时间复杂度。
算法流程:
- 初始化队列
queue
,双向队列deque
; - 最大值 max_value() :
- 当双向队列
deque
为空,则返回 − 1 -1 −1 ; - 否则,返回
deque
首元素;
- 当双向队列
- 入队 push_back() :
- 将元素 v a l u e value value 入队 q u e u e queue queue ;
- 将双向队列中队尾 所有 小于 v a l u e value value 的元素弹出(以保持 d e q u e deque deque 非单调递减),并将元素 v a l u e value value 入队 d e q u e deque deque ;
- 出队 pop_front() :
- 若队列
queue
为空,则直接返回 − 1 -1 −1 ; - 否则,将 q u e u e queue queue 首元素出队;
- 若 d e q u e deque deque 首元素和 q u e u e queue queue 首元素 相等 ,则将 d e q u e deque deque 首元素出队(以保持两队列 元素一致 ) ;
- 若队列
设计双向队列为 单调不增 的原因:若队列
queue
中存在两个 值相同的最大元素 ,此时queue
和deque
同时弹出一个最大元素,而queue
中还有一个此最大元素;即采用单调递减将导致两队列中的元素不一致。
3. 代码实现
class MaxQueue {
public:queue<int> que;deque<int> deq;MaxQueue() {}int max_value() {return deq.empty() ? -1 : deq.front();}void push_back(int value) {que.push(value);while (!deq.empty() && deq.back() < value)deq.pop_back();deq.push_back(value);}int pop_front() {if (que.empty()) return -1;int val = que.front();if (val == deq.front())deq.pop_front();que.pop();return val;}
};/*** Your MaxQueue object will be instantiated and called as such:* MaxQueue* obj = new MaxQueue();* int param_1 = obj->max_value();* obj->push_back(value);* int param_3 = obj->pop_front();*/
创作不易,如果有帮助到你,请给文章点个赞和收藏,让更多的人看到!!!
关注博主不迷路,内容持续更新中。
更多推荐
《剑指offer》题解——week7
发布评论