不容易解的题10.5

31.下一个排列

31. 下一个排列 - 力扣（LeetCode）https://leetcode.cn/problems/next-permutation/?envType=list&envId=ZCa7r67M会做就不算难题，如果没做过不知道思路，这道题将会变得很难。

这道题相当于模拟cpp的next_permutation函数，但是请注意如果直接使用库函数将失去刷题的意义！

这道题的思路是：从后向前的寻找，第一次遇见的呈从左到右递增的两个数，注意我这里说的很详细了，是从后向前的寻找，从左到右递增的第一次遇见的两个数字，找到了以后，以这两个数的较大的那个数为终止条件，从后向前的寻找第一个大于第一次寻找到的第一个数字，将这两个数字交换之后，再将本次的终止条件那个数为起始点，一直到该数组的尾部，进行一次反转，即可得到结果。听着有点像绕口令，模拟一下。

给出例子：123456求它的一些下一个排列应该依次为：

123465、123546、123564、123645、123654

对照我上面说的规律，不难看出，完全符合规律。遵循了，排列一步一步的增大，如何保证一步一步增大？那么就是上面说的那样，从后往前的原因在于，数字越高位越大

我们要求的下一个排列，仅仅应该比给你的排列大一点点，不能太大！

所以我们从后向前找，我们把大数尽量和较低位交换，这样不就能保证我们得到的排列不会太大吗

这里解释了为什么是从后向前找，而不是从前向后，也解释了为什么是第一次遇见的递增，这都是在保证交换的数位处在相对较低的位置上。

再来说一说，为什么要找第一次找到的那两个数中，以第二个数为终止，从后向前找大于第一次寻找的第一个数，这也是保证我们要交换的数字尽可能小，那有的人可能要问了，你怎么知道从后向前就一定能够小呢？你看上面的排列规律，是不是这样的？尽量使低位拿大数，高位拿小数，这也是后面我们为什么对后面一段进行反转的原因，还有就是终止条件是大于等于第一次找到的第二个数的下标，就像是对123456求下一个排列一样，第一次找到的是56，而6后面没有数，那么只能把6和5进行交换了，你多模拟几遍就可以知道这些究竟是为什么了！！

然后需要注意的一点就是，如果排列已经是最大，无法增大了，就直接整体反转就可以了，这也是题目的要求

看代码

class Solution {
public:void nextPermutation(vector<int>& nums) {for(int i=nums.size()-1;i>0;i--){if(nums[i]>nums[i-1]){for(int j=nums.size()-1;j>=i;--j){if(nums[j]>nums[i-1]){swap(nums[j],nums[i-1]);reverse(nums.begin()+i,nums.end());return;} }}}reverse(nums.begin(),nums.end());return;}
};

找到了下一个排列直接返回就可以了，如果循环里没有返回证明不能找到比当前更大的排列，还有一点，不要把最后的全部反转排列写在if里面和里层循环for的外面，之前我就是这样想的，以为它进不去里层循环就意味着需要反转了，模拟一次就知道，其实如果当前排列是最大，那么它连if也进不去，自然不会走到整体反转。

---

75.颜色分类

75. 颜色分类 - 力扣（LeetCode）https://leetcode.cn/problems/sort-colors/?envType=list&envId=ZCa7r67M这道题不太难，但也是思路题，题做的少，很容易想不出来。

首先不要用sort排序！

先介绍第一种做法，单指针做法，做法十分简单，循环外部，定义变量s0，它有两个作用一是辅助交换，当循环遍历到0这个数字时，与下标s0的位置做交换，此时它就是起到一个下标交换作用，二是记录上一次循环时候，走到了哪里，也就是下一次循环从哪个地方开始，s0停在哪，说明了s0前面都是0，这时候从该位置起，遍历到1，再进行交换，即可完成排列。

class Solution {
public:void sortColors(vector<int>& nums) {int s0=0;for(int i=0;i<nums.size();++i){if(nums[i]==0){swap(nums[i],nums[s0]);s0++;}}for(int i=0;i<nums.size();++i){if(nums[i]==1){swap(nums[i],nums[s0]);s0++;}}}
};

两次循环搞定，时间是On，其实这个还可以简化第二次循环从s0位置开始遍历，因为前面都是0了

第二种思路是双指针

一个s0记录0的位置，一个s1记录1的位置，但是思路和上一个有一点不同。

我们先正常的去交换1，这是为什么等一下会有解释，正常交换1，就是遍历遇到1，就和下标s1位置交换，而0要特殊处理，因为数字0要被排序到1的前面。

怎么处理？遇到0直接交换，然后不要着急使s0向后指，在该位置判断s0位置是否小于s1，如果是，那么把s1位置和当前遍历位置进行交换，因为s1走在右边，s0此时在它的左边的缘故，此时s1左边都是1，这个时候交换s0下标，一定是把1扔出去了，所以要交换回来，然后再使s0和s1下标各自增加1。

这里官方题解的说法一笔带过，没说是为什么

我在这里的解释是：由于s0和s1都做了交换，所以理应进行两个自增，那如果此时s0在s1的右边或者说和s1重叠呢？这样就没进入s0<s1，这时候还该s1自增吗？

答案是应该的，我们这里保证尽量走在s0的前面，这不是闲的

我的理解是：首先如果1需要交换时候，我们只是写了直接交换，如果s1一直在s0左边，那么我们还要接着扩充它的判断，多写代码。

第二点：题意要求我们把0放前面，所以s0下标理应走在s1的左边，这样看着更加合理。

第三点：一直保持s1走在前面，逻辑具有规律性，利于代码书写和思维理解。

class Solution {
public:void sortColors(vector<int>& nums) {int s0=0,s1=0;for(int i=0;i<nums.size();++i){if(nums[i]==1){swap(nums[i],nums[s1]);s1++;}if(nums[i]==0){swap(nums[i],nums[s0]);if(s0<s1&&nums[i]==1)swap(nums[i],nums[s1]);s1++,s0++;}}}
};

以上仅是个人理解，如果不是强行控制s1走前面，而是在两个判断里都写出来s0或者s1走在前面需要如何的调整，那我觉得应该也是可以的，虽然我没有试过。无非就是给对方扔出来了，需要再交换回去呗。

官方题解，这里第二个写的是else if我认为写if更好，因为此时遍历可能是i指向1而s1指向0，我们可以再判断一次防止s1主动把0扔了出去，理论上可以这样理解，但是当然模拟一下知道，这肯定是不可能的，这样的代码只可能是s0把1扔出去，因为i遍历的数字如果是0，第一个if走不进去，而且刻意调整了s1向前走，所以s1指不到之前的0位置。

还有就是，第二个if里的num【i】==1可以不用写，上面我们也解释了为什么扔出的一定是1，可以看前面，我这样写这两句，完全是让代码思路更加吻合常规思想，就是这样理所当然地写。

第三种方法也是双指针

这个双指针是移动0和2而不是0和1。思路有差别，2需要放在后面，所以需要s2在后面开始走

class Solution {
public:void sortColors(vector<int>& nums) {int s0=0,s3=nums.size()-1;for(int i=0;i<=s3;i++){while(i<s3&&nums[i]==2){swap(nums[i],nums[s3]);s3--;}if(nums[i]==0){swap(nums[i],nums[s0]);s0++;}}}
};//这里的s3就是s2的意思

首先需要注意的就是为什么第一个判断部分用while而不是if，这里外层循环是用i<=s3

我先说一下这个点，用s3来控制下标为什么不用nums.size？

i走到s3之后就没必要往后走了，因为s3的后面都是有序
其实不仅仅是这样，如果i向后走会出现错误的，i走到了s3后面，这时i极有可能指向2，那么就把此时s3指向的垃圾数调回去了！

然后再说为什么使用while做第一部分判断，这里其实你可以用if跑一下试试，有用例过不去，我们此时用的s3做判断，每进一次判断，s3才有可能做出减少1的举动，但是不要忘记外层循环i一直再做自增。遇到案例{2，1，2}这样的数据，第一个判断如果用if，而第二个if永远进不去，因为这个数据里没有0，那会导致下一次外层循环i++之后，i指向了1，那么数组下标为0的数据虽然是2，但是永远无法被调整位置，所以很显然，这个while的原因正是要在当前i这个位置是2，而当前s3也是2的时候，再进行一步调整，充分地去利用i这个位置，把更多的2跳到后面，避免略过2，这里就是和上一种双指针完全不同的思路。那为什么第一种你不需要while循环去那么尽力的找数字，也可以找到全部的0和1然后排序呢？我想应该是因为上一种方法，两个指针都指向前面，这里指针是对着走的，同时兼顾后面数据和交换，和前面数字和i交换，肯定比同一侧的数字和i交换情况复杂一些。

然后解释一下为什么前面说了不能让i走向后面已经排完序的2的位置，而外层循环还要让i走到小于等于s3呢？这是要兼顾一种特殊测试用例{2，0，1}交换数据后成了{1，0，2}，s3此时指向中间位置下标，然后i++
如果这时没有等于，那么直接跳出循环了

总之这第三种双指针思路需要注意的细节十分的多，虽然代码也短，但是我更倾向于学习第二种双指针的解法，这种还可以稍微好理解一些，而且需要细节少于这种。

---

43.字符串相乘

43. 字符串相乘 - 力扣（LeetCode）https://leetcode.cn/problems/multiply-strings/?envType=list&envId=ZCa7r67M不要使用竖式模拟的方法，之前看了一些竖式模拟，需要串位来模拟乘积后相加的情景，很麻烦，也不好理解，建议的方法只有一个：数组存储。

用数组存储，从后向前的遍历数字，第一个数的最后一位分别乘上第二个数字的各个位，得到的结果也分别写在数组对应的两个数字下标和的位置，为什么这么写？这是有讲究的后面再说。

我们这道题结合代码看

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0")return "0";int m=num1.size(),n=num2.size();vector<int>a(m+n-1,0);for(int i=m-1;i>=0;--i){for(int j=n-1;j>=0;--j){a[i+j]+=(num1[i]-'0')*(num2[j]-'0');}}for(int i=a.size()-1;i>0;i--){a[i-1]+=a[i]/10;a[i]%=10;}string ss="";int i=a[0]==0?1:0;for(;i<a.size();++i)ss+=to_string(a[i]);return ss;}
};

第一点需要注意0乘以任何数字都得0，而如果不写这个判断那么如果一方为0，则结果是“”，一个空字符串，而不是字符串0，这里需要额外判断。

然后是，开辟数组多大合适？

虽然说一个m位的数和一个n位的数相乘可能得到一个m+n或者m+n-1位的数
但是只开一个m+n-1的数组也是可以的，这样如果得到结果是m+n位数的话
多出来的一位会都挤在数组第一个数据里，但是两位最大也就是99所以不需要担心会太大。
这里为什么这么写呢？因为做的时候发现如果开m+n的数组，在出现m+n-1的位数结果时候，最后一个位置会多出一个0
如果开m+n的数组，赋值时候应该是向i+j+1位置赋值，如果结果是m+n位数那么正好存的下，如果少一位，则判断前导0情况就可以了
官方题解给出的是开，m+n空间，然后去判断是否出现前导0，也就是相加和为m+n-1位的情况，我们这里的题解直接开m+n-1，就不用判断了。

然后就是往数组里填数，会的人会觉得很简单，没什么要说的，但是我还是要说一说，这里易错点是什么，数组填数采用的是+=而不是=

数组的位置是+=，它存两个数字的不同下标乘积，那么肯定有一些时候会存在一个位置上，比如说
123和456的3*5和2*6的下标和都是在一个位置
这说明了什么？
这道题的思路我们是把乘积放在数组内，同一个下标就相当于模拟竖式乘积时，对应的那个位置
也就是说2*6得到的答案不对应3*6，而是3*5，这是在模拟竖式算术时的错位和行为，得到答案后，遍历数组把每个位置多余10的部分取模然后多出部分加在上一位，再转换为字符串就可以了

也就是说这里的+=既实现了竖式乘积的错位，也实现了竖式相加的那一个步骤。

而填数之后的各个取模操作是为了模拟相加的产生的进位。

---

都看到这里了如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注！