剑指offer刷题笔记2023.2.15完结

1.31

二叉树后序遍历：注意返回的边界

65：位运算计算和：巧用进位。需要注意移位运算的限制，考虑复数的情况。

56：在时间O(n)，空间O(1)的前提下查找数组中只出现基数次的两个数。巧用异或运算以及二分的思路

56-2：…6.出现三次怎么统计呢？用位运算，具体可以用数电的知识简化。太神奇了！

39：摩尔投票法。通过票数找出众数。由于题目中众数超过了一半，所以最坏情况下所有其他数也会被抵消。

66：构建乘积数组。画表格从二维的角度思考问题。实际上也是一个优化了空间的背包。只不过是双向。

2.1

比较摆，两道数学题。

14-1:剪绳子 实际上也是一个背包，但是可以用数学直接用公式求最大值

14-2:和为s的序列。双指针维护递推即可

2.2

玩了半个下午，开始刷。

62:约瑟夫环。动态规划。

令dp[i]为剩下i个人时最后留下的人在队列中的位置。

很容易知道，dp[1]=0。

状态转移较为困难，需要讨论方便理解。

首先，我们每次剔除人后将其后面的队列接到队首。如下：

1：若最终留下的人在被剔除人的右边（蓝色），则该轮的位置实际就是下一轮的位置+m（因为反向来看就是前面塞了一块长为m的数列）

2：若最终留下的人在被剔除人的做边（橙色），则(下一轮的位置+m)已经超过总长度。此时对m取余即可得到右边这一块前面的长度，即为本轮位置

综上，所以可以直接用dp[n] = (dp[n-1] + m)%n;

从n=1开始递推。

2.3

29:顺序打印矩阵。

就是一道模拟题。关键在于找到优美遍历的方法以及结束条件。开始的个人想法是统计遍历个数，等于矩阵size时结束，并在每次遍历将矩阵元素设为0。可想而知效率不高。

更好的方法是维护上下左右四个边界，逐次逼近。退出条件是两个边界碰面（a>b）。

。。数组x和y搞混了。傻呗。

31:栈的压入、弹出序列。

印象中在洛谷做过这道题，只需要抓住一种不合法的情况。对于顺序排列的进栈序列ABC，出栈可能只有五种。第六种CAB是不合法的。所以我们的工作只需要判断poped中是否包括这种情况即可。

具体的方法是O(n*n)

呃呃。用模拟栈就好了（想复杂了）但是也要注意，在维护模拟栈时需要考虑空栈的情况。否则直接top()会出内存问题。

20：字符串判断

脑子里最初的想法是用循环遍历，内置一大堆if语句。实际上有限状态机是一个很好的简化思路的方法！如下图。

比较有用的点是学习了map和unordered_map的使用。

67：字符串转数字

算法比较简单，关键在于控制边界。复习一下计算机中数的存储：int32 位，范围为[-2^31,2^31-1]。原因是1000 0000作为负数，做取补码的逆运算后得到还是1000 0000。因此规定它为-2^8。

具体到代码中，比较优雅的判断方式是：前部分等于于MAX_INT/10且最后一位大于7，即为错误。

2.7

59-1：滑动窗口的最大值。本质上不是难题，关键在于利用优先队列priority_queue把时间复杂度优化。学到了优先队列的定义以及插入、取值、删除操作。

59-2：队列的最大值。巧用双端队列即可。主要还是学习工具类deque的使用。back(),pop_back(),front(),pop_front()等

2.8

37：二叉树的生成和解析。下午学累了做了一道二叉树的层序遍历，题目不难，主要是处理字符串有点麻烦。

草，还是字符串的问题。怪不得过不了。string的substr 和find函数很好用。力扣编译器不给我过data.substr(l,r-l)…难绷

2.9

38：字符串的排列组合。关键点在于去重，剪枝。方法是在递归中加入set结构避免考虑重复的字母。注意set.end()和set.insert()等函数的使用。

确实也见识了一种基于原来的字符串递归排列组合的写法。

17:打印从1到最大的n位数。虽然是简单题，但是实际上和前面那道也差不太多。实际上也是递归搜索一个字符串的生成树，并排除掉首字母位1的情况。另一个学到的点是string也可以用push_back和pop_back啊…

2.12

19:一道很典型的动规。主要是没有形成动态规划的思考习惯。在碰到过去的状态可以由前面状态决定的题目时就应该用动规，通过状态转移求解。至于本题，我一开始的思路是通过双指针遍历，随后发现很难兼容各种情况。但是状态转移方程很好地解决了这个问题。

dp[i,j]的意思是加入s[i]和p[j]后仍然是匹配的（但是实际上加入的下标是i-1 和 j-1），而dp[0,0]意为两个空串必然匹配。

基本思路也就是判断字符串p中的* . 及其他，然后推理出相应的转移方程。

注意C++中二维数组的初始化。为避免访问越界，需要先初始化第一行。

初始化需要注意，由于*可以出现0次，所以只能初始化偶数位为true。

是好题啊，可以多看几遍。

60:一开始只想到了暴力解法。但是实际上像类似的题都可以寻找递推关系用动态规划。在本题中，有点像以前高中做过的概率递推。

f(n,x) = ∑f(n-1,x-i)。然后考虑到逆推会导致数组越界，所以采用正推。这也是第一次使用。另外注意一下C++里面的double类型。

注意一个错误点。因为采用了两个数组来迭代，而每次实际上都会前推一个数（如[1,6]和[2,12]）。所以这里遍历色子时直接[0,5]不需要[1,6]。否则会越界。在代码中就是k的那重循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6,1.0/6.0);
        for(int i=2; i<=n; i++){
            vector<double> tmp(5*i+1,0);
            for(int j=0; j<dp.size(); j++){
                for(int k=1;k<=6;k++){
                    tmp[j+k]+=dp[j]/6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

2.13

51:逆序对。这个题在算法课上学过，但是现在没印象了（悲）看到比较大小应该和排序联系起来，而类似这样1:n的比较则用归并比较合适。有了思路就是考验手搓归并排序的能力了。

剑指 Offer 51. 数组中的逆序对 - 力扣（Leetcode）

注意的点是：在递归的遍历中由于使用的是i++所以终止条件是i>=m+1。另外写错的一个点是，为了节省空间我们直接在num数组里面更改，所以比较要采用tmp，而不能用num。（也就是第一个else if）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

    int mergesort(int l,int r,vector<int>& nums){
        if(l>=r) return 0;
        int m = (l+r)/2;
        int ans = mergesort(l,m,nums) + mergesort(m+1,r,nums);
        vector<int> tmp(nums.size());
        for(int i=l; i<=r; i++){
            tmp[i] = nums[i];
        }
        int i = l, j = m+1;
        for(int k = l; k<=r; k++){
            if(i==m+1) nums[k] = tmp[j++];
            else if(j==r+1 || tmp[j]>=tmp[i]) nums[k] = tmp[i++];
            else {
                ans += m-i+1;
                nums[k] = tmp[j++];
            }
        }
        return ans;
    }
};

md还不能在每层递归单独创建tmp…只能传参，要不然超时。

44:序列中某一位的数字。碰到像这样的数字题，大多是通过找规律的方式。建立对问题的规律模型然后迭代求解即可。

倒不算是难题。对本题来说就是找到[0,9],[10,99],[100,999]等数字个数和数字位数的关系。

​ 1 9 9

​ 2 90 180

​ 3 900 2700

需要注意的是，在某个区间获得对应数字的顺序时，需要用n-1。

to_string函数很好用。

2.14

49:丑数。应该是一个数学题。

一开始的思路是有的。因为是质因数，所以大数必然是小数的基础上乘2，3，5得到的。关键在于如何按顺序排列。

关键点在于，大数*2必然是大于小数*2。那么怎么解决重复的问题呢？a*2*3和a*3*2怎么判断？这里用三个指针来代表这个数还需要乘2，3，5。因为我们不管后续如何，总之一个数乘2，3，5得到的后续数是不一样的。每一次根据大小决定放入哪个数。如果出现重复结果(如2*3和3*2)，则将2的指针向后移的同时将3的指针同时向后即可。这样就避免了重复和遗漏。

其实也可以算是一道动态规划的题目。后面的状态都是由前面得到的。

c++ min函数在<algorithm>里面。

2.15

41:数据流的中位数。因为题目没有说数组一定是有序的，所以每次添加时要执行一次排序。复杂度自然是log(n) 和 n，二分查找后移动。

但是类似于这样的题可以采用堆来优化。实际上像中位数都可以用一个大顶堆一个小顶堆来实现。维护的细节就需要练习了。具体要注意的是，两个堆大小相等时，插入操作要先插入大顶堆（小的那一半）然后将堆顶弹出给大的那一半。不相等时（大的那一半更多），则先插入大的那一半再弹出顶端给小的那一半。这样才能保证始终有序。

堆用优先队列实现。

1
2
3
4
5
6
7
8

priority_queue<typename, container, functional>;

//构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
priority_queue<int, vector<int>, less<int>> priQueMaxFirst;
 
//构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue<string, vector<string>, greater<string>> priQueMinFirst

还需要注意的是C++里面的类型转换。

43:1~n中1出现的个数 。看起来很难，实际上就是类似于一个行李箱的滚轮密码锁找规律。只不过需要一点简化公式的灵感。另外还要考虑从0开始的特点。

当然，思考方式上也有可取之处：拆解来看，总的问题就是每一位上能够出现1的次数的和。具体情况则由该数位上的数字大小决定。

分类讨论：

cur上为0：

​ 则该位上出现1的情况是：high*digit，因为cur为0时，只能到high-1时为 1。但是考虑到high全为0也 算，所以实际上是high*digit

cur上为1：

​ 思路和上面大致相同。只不过在它的基础上可以加上xx10到xx1y这些数。 实际上也就是 high*digit+low+1。

cur大于1：

​ 此时就解除限制，(high+1)*digit

推出来之后递推。

有一个点，是在递归时digit可能越界。所以用long表示。