❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于 Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

一、剑指 Offer 59 - I. 滑动窗口的最大值

1. 题目描述

在这里插入图片描述

2. 思路分析

窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决本问题。遍历数组时，每轮保证单调队列 $deque$ ：

$deque$ 内仅包含窗口内的元素 $\Rightarrow$ 每轮窗口滑动移除了元素 $nums[i - 1]$ ，需将 dequedeque 内的对应元素一起删除。
$deque$ 内的元素非严格递减 $\Rightarrow$ 每轮窗口滑动添加了元素 $nums[j + 1]$ ，需将 $deque$ 内所有 $< nums[j + 1]$ 的元素删除。

算法流程：

初始化： 双端队列 $deque$，结果集合 $res$；
滑动窗口：
1. 若 deque.front() <= i - k，说明在插入新的元素时队头不能继续留在队列中，则将队首元素出队；
2. 删除 $deque$ 内所有 $nums[i]$ $<$ 队头的元素，以保持 $deque$ 递减；
3. 将 $i$ 添加至 $deque$ 尾部；
4. 若已经形成窗口（即 $i >= k - 1$），则将窗口最大值（即队首元素 $deque$）添加至列表 $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 张牌中最大的牌为 $max$，最小的牌为 $min$（大小王除外）, 则需满足 max - min < 5；

算法流程：

初始化： 先对数组进行排序；
判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 $nums[i] = nums[i + 1]$ 是否成立来判重。
获取最大 / 最小的牌： 排序后，数组末素 se$nums[4]$ 为最大牌；元素 $nums[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$
我们每次将删除元素的后一个元素放在最前面方便计数:

删除 $2$ → $[3, 4, 0, 1]$
删除 $0$ → $[1, 3, 4]$
删除 $4$ → $[1, 3]$
删除 $1$ → $[3]$

尝试反推：
如何从最后剩下的元素的索引 $0$ 反推至第一轮该元素的索引呢？

第四轮反推，补上 $m$ 个位置，然后模上当时的数组大小 2，位置是 (0 + 3) % 2 = 1。
第三轮反推，补上 $m$ 个位置，然后模上当时的数组大小 3，位置是 (1 + 3) % 3 = 1。
第二轮反推，补上 $m$ 个位置，然后模上当时的数组大小 4，位置是 (1 + 3) % 4 = 0。
第一轮反推，补上 $m$ 个位置，然后模上当时的数组大小 5，位置是 (0 + 3) % 5 = 3。
所以最后剩下的数字的下标就是 3。因为数组是从 $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. 思路分析

遍历数组：
我们只需要在最低点的时候买入股票就最好了，因此只要用一个变量 $cost$ 来记录最低价格，我们就可以假设股票是在这一天购买的。那么在第 $i$ 天卖出股票能得到的利润是 $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. 思路分析

解题思路： 递归
最直接的方法就是用递归， $sum(n) =n + sum(n - 1)$，但是要注意终止条件，由于求的是 $1 + 2 + ... + n$的和，所以需要在 $n = 0$ 的时候跳出递归，由于题目要求不能使用 $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$ 与进位 $c$ 的计算公式如下:
$$ \begin{cases} n=a⊕b & 非进位和：异或运算\\ c=a\&b<<1 & 进位：与运算 + 左移一位 \end{cases}$$

（和 $s$ ）=（非进位和 $n$ ）+（进位 $c$ ）。即可将 $s = a + b$ 转化为：$s=a+b⇒s=n+c$

若数字 $a$ 和 $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[i]$ 的定义，可列表格，如下图所示。
根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果。
在这里插入图片描述
算法流程：

初始化： 数组 $B$，其中 $B[0] = 1$；辅助变量 $tmp = 1$；
计算 $B[i]$ 的 下三角 各元素的乘积，直接乘入 $B[i]$；
计算 $B[i]$ 的 上三角 各元素的乘积，记为$tmp$，并乘入 $B[i]$；
返回 $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. 思路分析

算法流程：

首部空格： 删除之即可；
符号位： 三种情况，即 “+”， “-”， “无符号”；新建一个变量保存符号位，返回前判断正负即可；
数字字符：
1. 字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减即可；
2. 数字拼接： 若从左向右遍历数字，设当前位字符为 $c$ ，当前位数字为 $x$ ，数字结果为 $res$ ，则数字拼接公式为： $res = res * 10 + x - '0'$;
数组越界问题： 题目要求返回的数值范围应在 $[-2^{31}, 2^{31} - 1]$ ，因此需要考虑数字越界问题。而由于题目指出环境只能存储 32 位大小的有符号整数，因此判断数字越界时，要始终保持 $res$ 在 $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$ 在节点 $root$ 的左 / 右子树中，或者 $p = root$，则称 $root$ 是 $p$ 的祖先。

最近公共祖先的定义： 设节点 $root$ 为节点 $p,q$ 的某公共祖先，若其左子节点 $root->left$ 和右子节点 $root->right$ 都不是 $p,q$ 的公共祖先，则称 $root$ 是 “最近的公共祖先” 。

根据以上定义，若 $root$ 是 $p,q$ 的 最近公共祖先 ，则只可能为以下情况之一：

$p$ 和 $q$ 在 $root$ 的子树中，且分列 $root$ 的异侧（即分别在左、右子树中）；
$p = root$，且 $q$ 在 $root$ 的左或右子树中；
$q=root$，且 $p$ 在 $root$ 的左或右子树中；

算法流程：

循环搜索： 当节点 $root$ 为空时跳出；
1. 当 $p, q$ 都在 $root$ 的 右子树 中，则遍历至 $root->right$ ；
2. 否则，当 $p, q$ 都在 $root$ 的 左子树 中，则遍历至 $root->left$ ；
3. 否则，说明找到了 最近公共祖先 ，跳出。
返回值： 返回最近公共祖先 $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$ 或 $q$ 时返回。从底至顶回溯，当节点 $p, q$ 在节点 $root$ 的异侧时，节点 $root$ 即为最近公共祖先，则向上返回 $root$ 。

算法流程：

终止条件：
1. 当越过叶节点，则直接返回 $null$ ；
2. 当 $root$ 等于 $p, q$ ，则直接返回 $root$ ；
递推工作：
1. 开启递归左子节点，返回值记为 $left$ ；
2. 开启递归右子节点，返回值记为 $right$ ；
返回值： 根据 leftleft 和 rightright ，可展开为四种情况：
1. 当 $left$ 和 $right$ 同时为空 ：说明 $root$ 的左 / 右子树中都不包含 $p,q$ ，返回 $null$ ；
2. 当 $left$ 和 $right$ 同时不为空 ：说明 $p, q$ 分列在 $root$ 的异侧（分别在左 / 右子树），因此 $root$ 为最近公共祖先，返回 $root$ ；
3. 当 $left$ 为空，$right$ 不为空 ：$p,q$ 都不在 $root$ 的左子树中，直接返回 $right$ 。具体可分为两种情况：
  1. $p,q$ 其中一个在 $root$ 的 右子树 中，此时 $right$ 指向 $p$（假设为 $p$ ）；
  2. $p,q$ 两节点都在 $root$ 的 右子树 中，此时的 $right$ 指向 最近公共祖先节点 ；
4. 当 $left$ 不为空， $right$ 为空：与情况 $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)$ 加入到队列 $queue$;
终止条件： 当 $queue$ 为空，代表已遍历完所有可达解。
迭代过程：
1. 单元格出队： 当队首单元格的坐标出队，作为当前搜索的单元格；
2. 判断是否跳出：若行列索引越界 或者 数位和超出目标值 $k$ 或者当前元素已访问过，则直接 $continue$，否则 $res$ 加 1；
3. 标记当前单元格： 当单元格索引 $(i, j)$ 存入到 $st$中，代表此单元格 已被访问过；
4. 单元格入队：将下一个合法的单元格的索引加入队列中；
返回值： 直接返回 $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)$ ；本题难点为实现查找最大值 max_value() 的 $O(1)$ 时间复杂度。
假设队列中存储 $N$ 个元素，从中获取最大值需要遍历队列，时间复杂度为 $O(N)$ ，单从算法上无优化空间。

考虑利用 数据结构 来实现，即经常使用的 “空间换时间” 。考虑构建一个递减列表来保存队列 所有递减的元素 ，递减链表随着入队和出队操作实时更新，这样队列最大元素就始终对应递减列表的首元素，实现了获取最大值 $O(1)$ 时间复杂度。

为了实现此递减列表，需要使用 双向队列 ，假设队列已经有若干元素：

当执行入队 push_back() 时：若入队一个比队列某些元素更大的数字 $x$ ，则为了保持此列表递减，需要将双向队列 尾部所有小于 $x$ 的元素弹出。
当执行出队 pop_front() 时：若出队的元素是最大元素，则双向队列需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。

使用双向队列原因：维护递减列表需要元素队首弹出、队尾插入、队尾弹出操作皆为 $O(1)$ 时间复杂度。

算法流程：

初始化队列 queue，双向队列 deque；
最大值 max_value() ：
1. 当双向队列 deque 为空，则返回 $-1$ ；
2. 否则，返回 deque 首元素；
入队 push_back() ：
1. 将元素 $value$ 入队 $queue$ ；
2. 将双向队列中队尾所有小于 $value$ 的元素弹出（以保持 $deque$ 非单调递减），并将元素 $value$ 入队 $deque$ ；
出队 pop_front() ：
1. 若队列 queue 为空，则直接返回 $-1$ ；
2. 否则，将 $queue$ 首元素出队；
3. 若 $deque$ 首元素和 $queue$ 首元素相等，则将 $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

一、剑指 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. 题目描述

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. 代码实现

热门文章

最新文章

相关电子书