🧊foril

🧊foril

力扣刷题笔记（二）

2021-05-13

阅读时间：20分钟

7. 整数反转　　

题目　　

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。　　

如果反转后整数超过 32 位的有符号整数的范围 [ $−2^{31}$ , $2^{31} − 1$ ] ，就返回 0。　　

假设环境不允许存储 64 位整数（有符号或无符号）。　　

思路　

这是一道简单题，之所以放在这里，是因为其中题解提供的一些思路很值得学习，并且在其中我遇到的一些小问题也很值得记录下来以便以后回忆。

不借助栈的“弹出”和“推入”

首先这个题第一思路是需要借助栈翻转，但作为数字，我们可以不使用栈就对其数字加以翻转。这是值得记录回忆的小技巧之一。

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

其次需要判断反转后的数字是否溢出，因为我们只能使用32位整型，所以不能使用rev*10+digit >　Integer.MAX_VALUE这样的语句来判断，但我们可以反其道而行，对Integer.MAX_VALUE除10来判断，这里题解中有一个值得学习的推导思路：

考虑 x>0 的情况，记 $INT\_MAX=2^{31}-1=2147483647$ ，由于

\begin{aligned} \textit{INT\_MAX}&=\lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor\cdot10+(\textit{INT\_MAX}\bmod10)\\ &=\lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor\cdot10+7 \end{aligned}

则不等式 $rev⋅10+digit≤INT\_MAX$

等价于

\textit{rev}\cdot10+\textit{digit}\le\lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor\cdot10+7

移项得

(\textit{rev}-\lfloor\dfrac{\textit{INT\_MAX}}{10}\rfloor)\cdot10\le7-\textit{digit}

讨论该不等式成立的条件：

若 $rev>\lfloor\cfrac{{INT\_MAX}}{10}\rfloor$ ，由于 ${digit}\ge0$ ，不等式不成立。

若 $rev=\lfloor\cfrac{{INT\_MAX}}{10}\rfloor$ ，当且仅当 ${digit}\le7$ 时，不等式成立。

若 $rev<\lfloor\cfrac{{INT\_MAX}}{10}\rfloor$ ，由于 ${digit}\le9$ ，不等式成立。

注意：这里需要注意如果 $rev=\lfloor\cfrac{{INT\_MAX}}{10}\rfloor$ 时仍然能够推入数字，说明 x 和 $INT\_MAX$ 的位数相同，digit 为 x 的首位，因为 $x<0$ ，所以 $digit\le2$ ，因此判定条件可简化为：当且仅当 $rev\le\lfloor\cfrac{{INT\_MAX}}{10}\rfloor$ 时，不等式成立。

x<0 的情况类似.

综上所述，判断不等式

-2^{31}\le\textit{rev}\cdot10+\textit{digit}\le2^{31}-1

是否成立，可改为判断不等式

\lfloor\cfrac{-2^{31}}{10}\rfloor\le\textit{rev}\le\lfloor\dfrac{2^{31}-1}{10}\rfloor

是否成立，若不成立则返回 0。

解决了边界问题这个重点问题，剩余的部分就很简单了，需要判断结尾的0以及开头的-，在这里就不详细分析了。

1310. 子数组异或查询　

题目　　

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

思路

最初写了一个最简单的遍历想解决问题，设arr的长度为n，queries的长度为m，这样时间复杂度为 $O(mn)$ ，结果运行超时，我开始思考怎么解决问题。

后来看到题解“前缀异或”，突然想到，异或和加减有很多相似的性质，看到异或，又看到连续数组，应该想到利用前缀和的思想，异或这东西不是有x^x=0这种好用的性质吗，题目要求的是对arr中间一段进行异或，那不是就可以后面的结果异或抵消前面的结果嘛。
这里有一个示意可以方便理解。

--------
^
---
=
   -----

这样只需要遍历一遍arr，得到arr.size()个结果保存起来，剩下的就是做异或相抵消得问题了。
上代码：

class Solution {
	public:
		vector<int> xorQueries(vector<int>& arr, vector<vector<int> >& queries) {
			int len = arr.size();
			vector<int> rec(len+1, 0);
			//遍历arr得到arr个结果（第一个0作为初始值，作为最左值之前的结果）
			for(int i=0; i<len; i++) {
				rec[i+1] = (rec[i]^arr[i]);
			}
			vector<int> res;
			//右下标异或左下标之前的结果作抵消
			for(vector<int> lr: queries) {
				res.push_back(rec[lr[1]+1]^rec[lr[0]]);
			}
			return res;
		}
};

62. 不同路径　

题目　　

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路

方法1：数学法

这个题一看到最初的思路是数学法，利用组合数 $C_{m+n-2}^{m-1}$ 。可以理解为一共有m+n-2个空，往其中填入m-1个黑棋，剩下的全部填入白棋，便得到了最终的结果，但实际写出来发现存在的问题是如果先计算分母极容易溢出。
如果使用的语言有关于组合数的API直接调用即可，如果没有，可以考虑

for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }

(来自力扣官方题解)

最初纠结这样一个一个分数会不会产生分数，后来看到网友的评论突然想明白了。

方法2：动态规划

不多说废话，具体动态规划的要点可以查看我的另一篇博客专题：动态规划。
这一题通过一个二维数组记录到对应点的最多方法。

上代码：

int uniquePaths(int m, int n) {
    int dp[m][n];   //二维数组
    memset(dp,0,sizeof(dp));    //初始化（因为是memset针对字节，所以一般只能初始化为0）
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i == 0 || j==0){
                dp[i][j] = 1;   //边界值（初始化）
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; //状态转换方程
            }
        }
    }
    return dp[m-1][n-1];
}

406. 根据身高重建队列　

题目　　

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

思路

方法一：从高到低考虑

这个题一开始上手没有找到其中的窍门，感觉类似的题目的关键就是能够找到一个窍门，或者说一个隐藏的属性。
这个题 ki 记录的是前面有多少身高大于等于 hi 的人数，言下的意思是前面如果放的是比他身高小的人，是没有任何影响的。那我们只要按照一定顺序填入队列就可以得到实际的位置。
官方题解的原话是：

如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

第 0, ... , i-10, ... ,i−1 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮；

而第 i+1, ... ,i+1, ... ,n−1 个人还没有被放入队列中，但他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高。

所以我们要先找到大个的相对位置，把大个的放进队列里，这样其他人的位置不会影响到更大个的人的位置。同时，相同个子的人需要先放入前面人少的人，也就是得到了一个排序的方法：先按第一列从大到小排序，第一列相同的按第二列从小到大排序。

//排序
sort(people.begin(), people.end() , [](const vector<int> & a, const vector<int> & b) {
    if(a[0] == b[0]) return a[1]<b[1];
    return a[0]>b[0];
});

那么，对示例[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]来说，排序后的结果应该是：

7,0
7,1
6,1
5,0
5,2
4,4

这也就是我们填入的顺序，每填入一个当前最小个的人，根据它前面的人数ki，把他放在第ki个位置，之后的全部往后移。最后全部填入，就是最终的顺序。
这样频繁插入移动，在java中考虑使用 LinkedList 。

代码：

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    //第零列从大到小
    //第一列从小到大哦
    int len = people.size();
    sort(people.begin(), people.end() , [](const vector<int> & a, const vector<int> & b) {
        if(a[0] == b[0]) return a[1]<b[1];
        return a[0]>b[0];
    });

    //排好序后开始放位置
    vector<vector<int>> list(len);
    for(int i = 0; i<len; i++) {
        int pos = people[i][1];
        for(int j = len-2; j>=pos; j--) {
            //往后窜
            list[j+1] = list[j];
        }
        list[pos] = people[i];
    }
    return list;
}

PS:
后来发现往后窜的步骤可以通过 insert。

for (const vector<int>& person: people) {
    ans.insert(ans.begin() + person[1], person);
}

方法二：从低到高考虑

同上，在排好序的队列中，个小的人是影响不到个高的人的 ki 的，所以我们可以按身高从低到高往队列中插入，前面只要留够 ki 个 “空座” 给之后个更高的人。对于相同身高的人，需要先排入 ki 大的人。

这里需要注意的是排序方法和方法一刚好相反。

对示例[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]，排序后的结果应该是：

4,4
5,2
5,0
6,1
7,1
7,0

有了这个顺序，便遵循 留空 -> 插入 的原则找到位置即可。

代码：

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
        return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
    });
    int n = people.size();
    vector<vector<int>> ans(n);
    for (const vector<int>& person: people) {
        int spaces = person[1] + 1;
        for (int i = 0; i < n; ++i) {
            if (ans[i].empty()) {
                --spaces;
                if (!spaces) {
                    ans[i] = person;
                    break;
                }
            }
        }
    }
    return ans;
}

96. 不同的二叉搜索树

题目　　

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
输入：n = 3
输出：5

思路

如果了解过卡塔兰数的话，可以直接得到

C_{n+1} = \frac{2(2n+1)}{n+2}C_n

令h(0)=1,h(1)=1，卡塔兰数满足递归式： h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;

以这个题作为背景的话，实际意义就是 n 个数对应分别以 1 到 n 作为根节点，也就是左孩子分别有 0 个到 n-1 个节点这n种情况的数量之和。

664. 奇怪的打印机

题目　　

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由同一个字符组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：
输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：
输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

思路

之前在动态规划专题中，提到过很多字符串最优问题都是使用动态规划解决的。
这个题一上手，并没有找到解决的方法，主要问题是找不到状态转换方程，在查看题解后，发现题解将一个区间的最优问题转化为小区间的最优问题求和的最小值。后来从评论区明白这是一类叫 “区间DP” 的问题。

什么是区间DP？

区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过 合并小区间的最优解进而得出整个大区间上最优解 的DP算法。
既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。

朴素区间DP（ $N^3$ ）转移方程：

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

有了这些背景知识，就可以得到本题的基本思路。

动态规划的基本要素：

保存：dp[i][j]保存下标从i到j的最小打印次数
状态转移方程：

dp[i][j] = \begin{cases} dp[i][j-1] &,s[i]==s[j]\\ min_{k=i}^{j-1} dp[i][k] + dp[k+1][j]&,s[i]!=s[j] \end{cases}

初始化：dp[i][i] = 1
遍历顺序：i从大到小；j从小到大
结果：dp[0][n-1]

这就是做一道动态规划最重要的步骤了，这一题还有一个主要要理解的难点就是如何使用区间DP。
上代码：

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        int dp[n][n];
        //初始化
        for(int i = 0;i<n;i++){
            dp[i][i] = 1;
        }
        //状态转移方程
        for(int i = n-1;i>=0;i--){
            for(int j = i+1;j<n;j++){
                if(s[i] == s[j]){
                    dp[i][j] = dp[i][j-1];
                }else{
                    int minR = INT_MAX;
                    for(int k = i;k<j;k++){
                        minR = min(minR, dp[i][k] + dp[k+1][j]);
                    }
                    dp[i][j] = minR;
                }
            }
        }
        //结果
        return dp[0][n-1];
    }
};

39. 组合总和

题目　　

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。解集不能包含重复的组合。

思路

这个题是在刷回溯专题时遇到的。接下来几个题都有很典型的回溯算法的结构。

class Solution {
private:
    vector<vector<int>> res;    //存放结果
    void bt(vector<int>& v,int index, int already,int target, vector<int>& candidates){
        if(already>target){ //出口条件（不合格，舍弃）
            return;
        }
        if(already==target){//出口条件（是结果，加入结果数组）
            res.push_back(v);
            return;
        }else{
            //继续往下试探
            for(int i = index;i<candidates.size();i++){ //尝试不同的数字作为下一个候选

                v.push_back(candidates[i]); //第一部分，把当前数字加入结果往下试探

                bt(v, i, already+candidates[i], target, candidates);    //递归试探过程

                v.pop_back();   //试探结束后，为了使用下一个数字，要把当前数字所做的改变全部复原
            }
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> v;
        bt(v, 0, 0, target, candidates);    //进入
        return res;
    }
};

🧊foril

🧊foril

力扣刷题笔记（二）

7. 整数反转

题目

思路

不借助栈的“弹出”和“推入”

1310. 子数组异或查询

题目

思路

62. 不同路径

题目

思路

方法1：数学法

方法2：动态规划

406. 根据身高重建队列

题目

思路

方法一： 从高到低考虑

方法二： 从低到高考虑

96. 不同的二叉搜索树

题目

思路

664. 奇怪的打印机

题目

思路

什么是区间DP？

39. 组合总和

题目

思路

7. 整数反转　　

题目　　

思路　

1310. 子数组异或查询　

题目　　

62. 不同路径　

题目　　

406. 根据身高重建队列　

题目　　

方法一：从高到低考虑

方法二：从低到高考虑

题目　　

题目　　

题目　　