AI 助理
备案控制台
开发者社区 人工智能 文章 正文

《剑指offer》题解——week5

2023-02-25 57
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《剑指offer》题解——week5
❤ 作者主页： 欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于 Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得 关注、 点赞、 收藏、 评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

一、剑指 Offer 44. 数字序列中某一位的数字

1. 题目描述

在这里插入图片描述

2. 思路分析

解题思路：

  1. 将 $101112...$ 中的每一位称为 数位，记为 $n$;
  2. 将 $10, 11, 12, ...$ 称为 数字 ，记为 $num$;
  3. 数字 $10$ 是一个两位数，称此数字的 位数 为 2，记为 $digit$；

  4. 每 $digit$ 位数的起始数字（即：1，10，100，...），记为 $start$。

    通过推算可以发现：
    位数递推公式： $digit = digit + 1$
    起始数字递推公式： $start = start \times 10$
    数位数量计算公式： $count = 9 \times start \times digit$

算法流程：

  1. 确定 $n$ 所在 数字 的 位数 ，记为 $digit$ :

循环执行 $n$ 减去 一位数、两位数、... 的数位数量 $count$ ，直至 $n \leq count$ 时跳出。
由于 $n$ 已经减去了一位数、两位数、...、$(digit−1)$ 位数的 数位数量 $count$ ，因而此时的 $n$是从起始数字 $start$ 开始计数的。

  1. 确定 $n$ 所在的 数字 ，记为 $num$ :

所求数位 在从数字 $start$ 开始的第 $[(n - 1) / digit]$ 个数字中（ $start$ 为第 0 个数字）。

  1. 确定 $n$ 是 $num$ 中的哪一数位，并返回结果。

所求数位为数字 $num$ 的第 $[(n - 1) \% digit]$ 位（ 数字的首个数位为第 0 位）。

3. 代码实现

class Solution {
public:
    int findNthDigit(int n) {
        long long start = 1, count = 9, digit = 1;
        while (n > count) {
            n -= count;
            digit ++;
            start *= 10;
            count = 9 * start * digit;
        }
        long long num = start + (n - 1) / digit;
        long long  index = (n - 1) % digit;
        string s = to_string(num);
        int ans = s[index] - '0';
        return ans;
    }
};

 
 

二、剑指 Offer 45. 把数组排成最小的数

1. 题目描述

在这里插入图片描述

2. 思路分析

此题求拼接起来的最小数字，本质上是一个排序问题。设数组 $nums$ 中任意两数字的字符串为 $x$ 和 $y$ ，则规定 排序判断规则 为：

  • 若拼接字符串 $x+y>y+x$ ，则 $x$ “大于” $y$ ；
  • 若拼接字符串 $x+y<y+x$ ，则 $x$ “小于” $y$ ；
$x$ “小于” $y$ 代表：排序完成后，数组中 $x$ 应在 $y$ 左边；“大于” 则反之。

算法流程：

  1. 初始化： 定义字符串列表$str$， 保存各数字的字符串格式；
  2. 列表排序： 使用“排序判断规则”，对$str$执行排序；
  3. 返回值： 拼接$str$中的所有字符串，并返回。

3. 代码实现

class Solution {
public:

    static bool cmp(string a, string b) {
        return a + b < b + a;
    }

    string minNumber(vector<int>& nums) {
        vector<string> str;
        for (auto num : nums) str.push_back(to_string(num));
        sort(str.begin(), str.end(), cmp);
        string res;
        for (auto  num : str) res += num;
        return res;
    }
};

 
 

三、剑指 Offer 46. 把数字翻译成字符串

1. 题目描述

在这里插入图片描述

2. 思路分析

动态规划：

  1. 状态定义： 设动态规划列表$dp$，$dp[i]$表示以 $x_i$ 为结尾的数字的翻译方案数量。
  2. 转移方程： 若$x_i$ 和 $x_{i - 1}$ 组成的两位数字可以被翻译，则dp[i] = dp[i - 1] + dp[i - 2]；否则dp[i] = dp[i - 1]。
可被翻译的两位数的区间：当 $x_{i - 1} = 0$时，组成的两位数是无法被翻译的（例如00，01，……），因此区间为 $[10, 25]$。
  1. 初始化： $dp[0] = dp[1] = 1$，即 “无数字” 和 “第 1位数字” 的翻译方法数量均为 1 。
无数字情况 $dp[0]=1$ ？
当 $num$ 第 1,2 位的组成的数字 $∈[10,25]$ 时，显然应有 2 种翻译方法，即 $dp[2]=dp[1]+dp[0]=2$ ，而显然$dp[1]=1$ ，因此推出 $dp[0]=1$ 。
  1. 返回值： $dp[n]$，即数字的翻译方案数量。

3. 代码实现

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i ++ ) {
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (t >= 10 && t <= 25) f[i] = f[i - 1] + f[i - 2];
            else f[i] = f[i - 1];
        }
        return f[n];
    }
};

 
 

四、剑指 Offer 47. 礼物的最大价值

1. 题目描述

在这里插入图片描述

2. 思路分析

动态规划：

  1. 状态定义： 设动态规划矩阵 $dp$ ，$dp(i,j)$ 代表从棋盘的左上角 $(1,1)$ 开始，到达单元格 $(i - 1,j - 1)$时能拿到礼物的最大累计价值。
  2. 转移方程： $f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1]$
  3. 初始化： 下标$i$、$j$都从1开始；
  4. 返回值： $dp[n][m]$，$m$,$n$ 分别为矩阵的行高和列宽，即返回 $dp$ 矩阵右下角元素。

3. 代码实现

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
        return f[n][m];
    }
};

 
 

五、剑指 Offer 48. 最长不含重复字符的子字符串

1. 题目描述

在这里插入图片描述

2. 思路分析

双指针 + 哈希表：
定义两个指针$i$,$j$$(i <= j)$, 表示当前扫描到的子串是$[i,j]$（闭区间）。扫描过程中维护一个哈希表unorderes_map<char, int> hash， 表示$[i,j]$中每个字符出现的个数。

线性扫描，每次循环的流程如下：

  1. 指针$j$向后移一位，同时将哈希表中$s[j]$ 的计数加一：hash[s[j]] ++;
  2. 假设$j$移动前的区间$[i,j]$中没有重复字符，则$j$移动后，只有$s[j]$可能出现2次。因此我们不断向后移动$i$，直至区间$[i,j]$中$s[j]$的个数等于1为止。

3. 代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            hash[s[i]] ++;
            while (hash[s[i]] > 1) hash[s[j ++]] --;
            res = max(res, i - j + 1);
        }
        return res;
    }
};

 
 

六、剑指 Offer 49. 丑数

1. 题目描述

在这里插入图片描述

2. 思路分析

丑数的递推性质： 丑数只包含因子 2, 3, 5 ，因此有 “ 丑数 = 某较小丑数 × 某因子” （例如：10 = 5 x 2）。

设已知长度为 $n$ 的丑数序列 $x_1$,$x_2$, ....$x_n$，求第 $n + 1$ 个丑数 $x_{n + 1}$。根据递推性质，丑数 $x_{n + 1}$ 只可能是一下三种情况其中之一（索引$a$, $b$, $c$为未知数）：
$$ x_{n + 1} =\begin{cases} x_a \times 2 ，& a∈[1,n] \\ x_b \times 3 ，& b∈[1,n] \\ x_c \times 5 ，& c∈[1,n] \end{cases}$$

丑数递推公式： 若索引 $a,b,c$ 满足以上条件，则下个丑数 $x_{n+1}$ 为以下三种情况中的 最小值 :

即    $x_{n+1}$ = min($x_a$ $\times$ 2, $x_b$ $\times$ 3, $x_c$ $\times$ 5)

动态规划：

  1. 状态定义： 设动态规划列表$dp$，$dp[i]$代表第 $i + 1$ 个丑数；

  2. 状态方程： 每轮计算 $dp[i]$后，需要更新索引 $a, b, c$的值，使其始终满足方程条件。实现方法：分别独立判断 $dp[i]$ 和 $dp[a] \times 2, dp[b] \times 3, dp[c] \times 5$ 的大小关系，若相等则将对应索引 $a, b, c$ 加 1；

    $dp[i] = min(dp[a] \times 2, dp[b] \times 3, dp[c] \times 5)$
  3. 初始化： $dp[0] = 1$，即第一个丑数为 1；
  4. 返回值： $dp[n - 1]$，即返回第 $n$ 个丑数。

3. 代码实现

class Solution {
public:
    int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int dp[n];
        dp[0] = 1;
        for (int i = 1; i < n; i ++ ) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n2, n3), n5);
            if (dp[i] == n2) a ++;
            if (dp[i] == n3) b ++;
            if (dp[i] == n5) c ++;
        }
        return dp[n - 1];
    }
};

 
 

七、剑指 Offer 50. 第一个只出现一次的字符

1. 题目描述

在这里插入图片描述

2. 思路分析

哈希表：

  1. 遍历字符串 $s$，使用哈希表 unordered_map<char, int> hash 统计各字符出现的次数；
  2. 再遍历字符串 $s$，在哈希表中找到首个 ”次数为1的字符“，并返回。

3. 代码实现

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, int> hash;
        for (auto c : s) hash[c] ++;
        char res = ' ';
        for (auto c : s) {
            if (hash[c] == 1) {
                res = c;
                break;
            }
        }
        return res;
    }
};

 
 

八、剑指 Offer 51. 数组中的逆序对

1. 题目描述

在这里插入图片描述

2. 思路分析

「归并排序」 与 「逆序对」 是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

  • 分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
  • 治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；

算法流程：
merge_sort() 归并排序与逆序对统计：

  1. 终止条件： 当 $l \geq r$ 时，代表子数组长度为 1 ，此时终止划分；
  2. 递归划分： 计算数组中点 $mid$ ，递归划分左子数组 merge_sort(l, mid) 和右子数组 merge_sort(mid + 1, r) ；

  3. 合并与逆序对统计：

    1. 暂存数组 $nums$ 闭区间 $[l,r]$ 内的元素至辅助数组 $tmp$ ；

    2. 循环合并： 设置双指针 $i , j$ 分别指向左 / 右子数组的首元素；

      • 左子数组和右子数组还可以合并的条件是： i <= mid && j <= r
      • 当 $tmp[i] \leq tmp[j]$ 时： 添加左子数组当前元素 $tmp[i]$ ，并执行 $i = i + 1$；
      • 否则（即 $tmp[i] > tmp[j]$）时： 添加右子数组当前元素 $tmp[j]$ ，并执行 $j = j + 1$ ；此时构成 $mid - i + 1$ 个 「逆序对」，统计添加至 $res$ ；
  4. 返回值： 返回直至目前的逆序对总数 $res$ 。

3. 代码实现

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size() - 1);
    }

    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;

        int mid = (l + r) / 2;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);

        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) 
            if (nums[i] <= nums[j]) temp.push_back(nums[i ++ ]);
            else {
                temp.push_back(nums[j ++ ]);
                res += mid - i + 1;
            }
        while (i <= mid) temp.push_back(nums[i ++ ]);
        while (j <= r) temp.push_back(nums[j ++ ]);

        int k = l;
        for (auto x  : temp) nums[k ++ ] = x;

        return res;
    }

};

 
 

九、剑指 Offer 52. 两个链表的第一个公共节点

1. 题目描述

在这里插入图片描述

2. 思路分析

双指针：
设「第一个公共节点」为 $node$ ，「链表 $headA$」的节点数量为 $a$ ，「链表 $headB$」的节点数量为 $b$，「两链表的公共尾部」的节点数量为 $c$ ，则有：

  • 头节点 $headA$ 到 $node$ 前，共有 $a - c$ 个节点；
  • 头节点 $headB$ 到 $node$ 前，共有 $b - c$ 个节点；

算法流程：

  1. 考虑构建两个节点指针 $p$​ , $q$ 分别指向两链表头节点 $headA$, $headB$ ，做如下操作：

    • 指针 $p$ 先遍历完链表 $headA$，再开始遍历链表 $headB$ ，当走到 $node$ 时，共走步数为：

    $a + (b - c)$

    • 指针 $q$ 先遍历完链表 $headB$，再开始遍历链表 $headA$ ，当走到 $node$ 时，共走步数为：

    $b + (a - c)$

  2. 即 $a+(b−c)=b+(a−c)$，此时指针 $p$ , $q$ 重合，并有两种情况：

    • 若两链表 有 公共尾部 (即 $c > 0$ ) ：指针 $p$ , $q$ 同时指向「第一个公共节点」$node$ 。
    • 若两链表 无 公共尾部 (即 $c = 0$ ) ：指针 $p$ , $q$ 同时指向 $null$。
  3. 返回值：直接返回指针$p$即可。

3. 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};

 
 

十、剑指 Offer 53 - I. 在排序数组中查找数字 I

1. 题目描述

在这里插入图片描述

2. 思路分析

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 $target$ 的下标，但这个方法的时间复杂度为 $O(n)$，没有利用到数组升序排列的条件。
由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 $target$ 在数组中出现的次数，其实我们要找的就是数组中 「第一个等于 $target$ 的位置」（记为 $left$）和 「最后一个等于 $target$ 的位置」（记为 $right$）。当 $target$ 在数组中存在时，$target$ 在数组中出现的次数为 $right- left + 1$ 。

3. 代码实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid =  (l + r) / 2;
            if (nums[mid] >=target) r = mid;
            else l = mid + 1;
        }
        int left = l;
        if (nums[r] !=target) return 0;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (nums[mid] <=target) l = mid;
            else r = mid - 1;
        }
        int right = r;
        return right - left + 1;
    }
};

创作不易，如果有帮助到你，请给文章==点个赞和收藏==，让更多的人看到！！！
==关注博主==不迷路，内容持续更新中。

文章标签：
Java
搜索推荐
索引
算法
zwy_coding
目录
相关文章
aliyun7652621635-14532
|
2月前
|
机器人
【题解】—— LeetCode一周小结37
LeetCode每日一道一周小结37
aliyun7652621635-14532
25 9
aliyun7652621635-14532
|
2月前
|
人工智能 BI
【题解】—— LeetCode一周小结38
LeetCode每日一道一周小结38
aliyun7652621635-14532
21 1
aliyun7652621635-14532
|
2月前
|
算法
【题解】—— LeetCode一周小结36
LeetCode每日一道一周小结36
aliyun7652621635-14532
31 12
aliyun1792367740-35101
|
1月前
|
测试技术
AcWing 2867. 回文日期（每日一题）
AcWing 2867. 回文日期（每日一题）
aliyun1792367740-35101
28 0
aliyun7652621635-14532
|
3月前
|
人工智能 BI
【题解】—— LeetCode一周小结31
LeetCode每日一道一周小结31
aliyun7652621635-14532
42 4
aliyun7652621635-14532
|
3月前
【题解】—— LeetCode一周小结33
LeetCode每日一道一周小结33
aliyun7652621635-14532
16 0
aliyun7652621635-14532
|
5月前
|
机器学习/深度学习
【题解】—— LeetCode一周小结22
LeetCode每日一道一周小结22
aliyun7652621635-14532
40 7
aliyun7652621635-14532
|
6月前
|
存储 测试技术 索引
【题解】—— LeetCode一周小结21
LeetCode每日一道一周小结21
aliyun7652621635-14532
100 8
aliyun7652621635-14532
|
6月前
|
机器学习/深度学习 算法
【题解】—— LeetCode一周小结10
【题解】—— LeetCode一周小结10
aliyun7652621635-14532
26 1
aliyun7652621635-14532
|
6月前
|
存储 人工智能 算法
【题解】—— LeetCode一周小结11
【题解】—— LeetCode一周小结11
aliyun7652621635-14532
32 1