Leetcode模拟过程类题型

Leetcode模拟过程类题型

此类问题，没有特定的模板，没有特定的算法，你需要做的是找规律，或者单纯的根据题意模拟一段过程

目录

67. 二进制求和

1487. 保证文件名唯一

31. 下一个排列

448. 找到所有数组中消失的数字

面试题67. 把字符串转换成整数

面试题31. 栈的压入、弹出序列 

面试题17. 打印从1到最大的n位数

矩阵原地运算

48. 旋转图像

54. 螺旋矩阵

面试题45. 把数组排成最小的数

面试题43. 1～n整数中1出现的次数 

面试题44. 数字序列中某一位的数字

面试题61. 扑克牌中的顺子

 

面试题62. 圆圈中最后剩下的数字

面试题58 - II. 左旋转字符串

面试题58 - I. 翻转单词顺序

面试题39. 数组中出现次数超过一半的数字

---

1488. 避免洪水泛滥

/ 

218. 天际线问题

非常好的一道题目，逻辑参考：/

 

class Solution {
public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int,int>> h;multiset<int> m;//堆，自动排序vector<vector<int>> res;//1、将每一个建筑分成“两个部分”，例如:[2,9,10]可以转换成[2，-10][9,10]，我们用负值来表示左边界，这也是很关键的一步，我们将前段点和后端点分开储存for(const auto& b:buildings){h.push_back({b[0], -b[2]});h.push_back({b[1], b[2]});}//2、根据x值对分段进行排序sort(h.begin(),h.end());int prev = 0, cur = 0;m.insert(0);//3、遍历for (auto i:h){if (i.second < 0) m.insert(-i.second);  //左端点，高度入堆ase(m.find(i.second));         //右端点，高度出堆cur = *m.rbegin();                      //当前最大高度高度if (cur != prev) {                      //当前最大高度不等于最大高度perv表示这是一个转折点res.push_back({i.first, cur});      //添加坐标prev = cur;                         //更新最大高度}}return res;
// /}
};

 

67. 二进制求和

/

 

class Solution {
public:string addBinary(string a, string b) {//模拟过程题目pty()&&pty()) return "";pty()) return b;pty()) return a;int index1 = a.size() - 1;int index2 = b.size() - 1;int delta = 0;stack<int>Res;while(index1>=0&&index2>=0){// cout<<a[index1]<<" "<<b[index2]<<endl;if(a[index1] == '1'&&b[index2] == '1') {if(delta == 1) {Res.push(1);delta = 1;}else {Res.push(0);delta = 1;}}else if( (a[index1] == '1'&&b[index2] == '0')||(a[index1] == '0'&&b[index2] == '1') ){if(delta == 1) {Res.push(0);delta = 1;}else {Res.push(1);delta = 0;}                } else if(a[index1] == '0'&&b[index2] == '0'){if(delta == 1) {Res.push(1);delta = 0;}else {Res.push(0);delta = 0;}     }index1--,index2--;} while(index1>=0) {if(a[index1] == '1') {if(delta == 1) {Res.push(0);delta = 1;}else {Res.push(1);delta = 0;}}else {if(delta == 1) {Res.push(1);delta = 0;}else {Res.push(0);delta = 0;}}index1--;}while(index2>=0) {if(b[index2] == '1') {if(delta == 1) {Res.push(0);delta = 1;}else {Res.push(1);delta = 0;}}else {if(delta == 1) {Res.push(1);delta = 0;}else {Res.push(0);delta = 0;}}index2--;}if(delta == 1) Res.push(1);string Str = "";while(Res.size()) {// cout<&p()<<endl;Str += to_p());Res.pop();}return Str;}
};

前置补零：

class Solution {
public:string addBinary(string a, string b) {//模拟过程题目pty()&&pty()) return "";pty()) return b;pty()) return a;//补0操作，短的部分前置补领int i = a.size() - b.size();if(i<0) i = -1*i;if(a.size()>b.size()) while(i>0){b = "0"+b;i--;}else if(a.size()<b.size()) while(i>0){a = "0"+a;i--;}int index = a.size() - 1;int delta = 0;stack<int>Res;while(index>=0){if(a[index] == '1'&&b[index] == '1') {if(delta == 1) {Res.push(1);delta = 1;}else {Res.push(0);delta = 1;}}else if( (a[index] == '1'&&b[index] == '0')||(a[index] == '0'&&b[index] == '1') ){if(delta == 1) {Res.push(0);delta = 1;}else {Res.push(1);delta = 0;}                } else if(a[index] == '0'&&b[index] == '0'){if(delta == 1) {Res.push(1);delta = 0;}else {Res.push(0);delta = 0;}     }index--;} if(delta == 1) Res.push(1);string Str = "";while(Res.size()) {Str += to_p());Res.pop();}return Str;}
};

 

1487. 保证文件名唯一

/

先审题，保存一个清晰的思路，再动手结题，利用Hash表，key为字符串，value保存再次出现同名文件名后，最小下标应该是多少。

class Solution {
public:vector<string> getFolderNames(vector<string>& names) {int size = names.size();if(size == 0) return {};vector<string>Res;unordered_map<string,int>M;for(int i = 0;i<size;++i){if(M.find(names[i]) == M.end())//没找见{M[names[i]] = 1;Res.push_back(names[i]);}else{string temp = names[i] + '(' + to_string(M[names[i]]) + ')';if(M.find(temp) == M.end()) {M[names[i]]++;M[temp]++;}else {while(M.find(temp) != M.end()) {M[names[i]]++;temp = names[i] + '(' + to_string(M[names[i]]) + ')';}M[temp]++;M[names[i]]++;}Res.push_back(temp);}}return Res;}
};

 

31. 下一个排列

找规律，如何找到第一个比原数组大的值

class Solution {
public:void nextPermutation(vector<int>& nums) {pty()) return;int right = nums.size() - 1;while(right>=1){if(nums[right - 1]<nums[right]) break;else right--;}if(right == 0)//整体单调递减，最大值状态{vector<int> Temp(nums.rbegin(),d());nums = Temp;}else{int Move = right-1;int Change = nums[Move];//要交换的数值//找到后半部分第一个大于Change的值，交换while(right<nums.size()){if(Change>=nums[right]) break;right++;}            swap(nums[Move],nums[right - 1]);//反转后半部分int begin = Move+1,end = nums.size() - 1;while(begin<=end){swap(nums[begin],nums[end]);end--;begin++;}}return;}};

448. 找到所有数组中消失的数字

/

Hash表当然是无所畏惧了， 遍历一遍，把出现过的内容标记，然后遍历hash表，看看谁没有出现，直接记录

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {if(!nums.size()) return {};vector<int>Res;unordered_map<int,int>M;int size = nums.size();for(auto item:nums) M[item]++;for(int i = 1;i<=size;++i) if(M[i] == 0) Res.push_back(i);return Res;}
};

原地操作:

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {if(nums.size()) return{};vector<int>Res;for(int i = 0;i<nums.size();++i){int newIndex = abs(nums[i])-1;//新的索引if(newIndex>=0&&newIndex<nums.size()&&nums[newIndex]>0)  nums[newIndex] *= -1;}for(int i = 0;i<nums.size();++i){if(nums[i]>0) Res.push_back(i+1);}     return Res;   }
};

面试题67. 把字符串转换成整数

/

本题要注意很多的细节问题。

也有需要的特殊案例：

那么根据题意，我们从头开始，不断提出空格，知道遇到第一个不是空格的内容

然后从该内容开始，判断是否为正负号或者数字，如果都不是，那么直接返回0

如果是，那么保留正负号，继续往下遍历，一旦遇到非数字的内容，直接return掉即可

但是本题要考虑大数问题，所以我们在循环中增加判断，一旦越界直接break；

string和int相互转换常用接口：

string 变成 int ：atoi()函数

int变成string：to_string()函数

判断是否为数字：isdigit(char);

本题核心代码：

        for(int i = begin;i<str.size();++i) {if(str[i]>='0'&&str[i]<='9') Num = Num*10+str[i]-'0';}

这是典型的字符串变数字的方法。 

class Solution {
public:int strToInt(string str) {pty()) return 0;//除去收尾多余内容int begin = 0;for(auto item:str) {if(item == ' ') begin++; else  break; }if(!(str[begin] == '+'||str[begin] == '-'||(str[begin]>='0'&&str[begin]<='9'))) return 0;//内容转化开始long sign = 1,Num = 0;//此处必须是long，而且不能是unsignedif(str[begin] == '-') {begin++;sign = -1;}else if(str[begin] == '+') {begin++;sign = 1;}for(int i = begin;i<str.size();++i) {if(str[i]>='0'&&str[i]<='9') Num = Num*10+str[i]-'0';else  break;if(Num>INT_MAX) return sign == 1?INT_MAX:INT_MIN;}return Num*sign;}
};

 

 

面试题31. 栈的压入、弹出序列 

/

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> Temp;//压入测试int index = 0;for(int i = 0;i<pushed.size();++i){Temp.push(pushed[i]);while(Temp.size()&&p() == popped[index]){index++;Temp.pop();}}return index == popped.size()?true:false;}
};

压入元素，对比栈顶和第一个出栈的元素是否相等（），相等，出栈（ temp.pop()），移动指针（++point）

如果不相等继续压入元素，并且每次压入一个都要比一次

 

面试题17. 打印从1到最大的n位数

 /

本题由于性质问题，不太可能出现在机考中，面试中倒是有可能

暴力解法：

class Solution {
public:vector<int> printNumbers(int n) {vector<int> Res;if(n<=0) return Res;int end = 1;for(int j = 0;j<n;++j) end *= 10;// cout<<end<<endl;for(int i = 1;i<end;++i){Res.push_back(i);}return Res;}
};

本题的核心就是考查大数问题，我们需要做的是在字符串上模拟数字加法 

大数解法：

本题是用字符串实现加减法

class Solution {
public:vector<int> printNumbers(int n) {int m = pow(10, n) - 1;vector<int> res(m);for(int i = 0; i < m; i++){res[i] = i + 1;}return res;}void printNumbers2(int n) {string s = "0";while(s.size() <= n){cout << s << endl;s = add(s);}}string& add(string &s){int i = s.size()-1;while(i >= 0 && s[i] == '9'){s[i--] = '0';}if(i < 0){s = "1" + s;}else{s[i] = s[i] + 1;}return s;}
};// 作者：Echoooo
// 链接：/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

参考解法：/

/

 

 

面试题14- II. 剪绳子 II

/

矩阵原地运算

48. 旋转图像

/

本题还是需要观察一下，才能入手的

不能整行的换，下面是本题代码思路的示意图：

两个两个换，才能整个完成选择

class Solution {
public:void rotate(vector<vector<int>>& matrix) {pty()) return;int row = matrix.size(),col = matrix[0].size();//从外到内进行替换int BeginR = 0,EndR = row-1;int BeginC = 0,EndC = col-1;while(BeginR<EndR){//换四个角//顶行和左列for(int i = EndR,j = BeginC;i>BeginR,j<EndC;--i,++j){swap(matrix[BeginR][j],matrix[i][BeginC]);//第一行和第一列交换}//左列和底行for(int i = EndR,j = EndC;i>BeginR,j>BeginC;--i,--j){swap(matrix[i][BeginC],matrix[EndR][j]);//第一行和第一列交换}  //左列和底行for(int i = EndR-1,j = BeginC+1;i>=BeginR,j<=EndC;--i,++j){swap(matrix[EndR][j],matrix[i][EndC]);//第一行和第一列交换} //收缩     BeginR++;EndR--;BeginC++;EndC--;  cout<<BeginR<<""<<endl; }}
};

54. 螺旋矩阵

/

面试题29. 顺时针打印矩阵  /

本题没有任何花里胡哨的技巧等，就是单纯的模拟整个过程，思路要清晰

 

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {pty()) return{};int m = matrix.size(),n = matrix[0].size();int Rbegin = 0,Rend = m-1;int Cbegin = 0,Cend = n-1;vector<int> Res;while(Rbegin!=Rend||Cbegin!=Cend){//第一行for(int i = Cbegin;i <= Cend;++i) if( (i>=0&&i<n&&Rbegin<m)&&matrix[Rbegin][i] != INT_MIN)//固定行{Res.push_back(matrix[Rbegin][i]);matrix[Rbegin][i] = INT_MIN;}//右侧for(int i = Rbegin;i<= Rend;++i) if((i>=0&&i<m&&Cend>=0)&&matrix[i][Cend] != INT_MIN)//固定列{Res.push_back(matrix[i][Cend]);matrix[i][Cend] = INT_MIN;}if(Cbegin!=Cend) Cend--;if(Rbegin!=Rend) Rbegin++;//下侧for(int i = Cend;i>=Cbegin;--i) if((i>=0&&i<n&&Rend>=0)&&matrix[Rend][i] != INT_MIN)//固定行{Res.push_back(matrix[Rend][i]);matrix[Rend][i] = INT_MIN;}if(Rbegin!=Rend) Rend--;//左侧for(int i = Rend;i>=Rbegin;--i) if((i>=0&&i<m&&Cbegin<m)&&matrix[i][Cbegin] != INT_MIN)//固定列{Res.push_back(matrix[i][Cbegin]);matrix[i][Cbegin] = INT_MIN;}if(Cbegin!=Cend) Cbegin++;}// cout<<"Rbegin"<<Rbegin<<endl;// cout<<"Rend"<<Rend<<endl;// cout<<"Cbegin"<<Cbegin<<endl;// cout<<"Cend"<<Cend<<endl;if(matrix[Rbegin][Cbegin] != INT_MIN)Res.push_back(matrix[Rbegin][Cbegin]);return Res;}
};

 

面试题45. 把数组排成最小的数

/

这是一道排序题

x+y>y+x，那么我们选择x+y这个组合就好了

class Solution {
public:string minNumber(vector<int>& nums) {vector<string> strs;string res;for(auto num:nums)strs.push_back(to_string(num));sort(strs.begin(),d(),[](const string &a,const string &b){return a+b<b+a;});for(auto str:strs)res+=str;return res;}
};

 当然了，我们也是可以从大到小排列

class Solution {
public:string minNumber(vector<int>& nums) {vector<string> strs;string res;for(auto num:nums)strs.push_back(to_string(num));sort(strs.begin(),d(),[](const string &a,const string &b){return a+b>b+a;});for(auto str:strs)res+=str;return res;}
};
// 北冥有鱼

输出的就是 

算法参考：/

 

 

面试题43. 1～n整数中1出现的次数 

/

算法参考：/

233. 数字 1 的个数 /

这是一道单纯的找规律问题

class Solution {
public:
int countDigitOne(int n)
{int countr = 0;for (long long i = 1; i <= n; i *= 10) {long long divider = i * 10;countr += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);}return countr;
}// 作者：LeetCode
// 链接：/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
};

 

 

面试题44. 数字序列中某一位的数字

/

400. 第N个数字 /

本题也是一道找规律的题目：

 

算法参考：/

class Solution {
public:int findNthDigit(int n) {//（1）先看看是几位数(156是两位数)long base = 9,Digits = 1;//Digits表示目前的数字在哪儿个区while(n-base*Digits>0){n -= base*Digits;base *= 10;Digits++;}//（2）找具体的值long number = 1;//起步位置for (int i = 1;i < Digits;i++)number *= 10;int dig = n % Digits;// Digits表示所在的区 if (dig == 0)dig = Digits;//如果能整除的话要减去1// cout<<dig<<endl;// cout<<n<<endl;number += (dig == Digits)? n/Digits - 1:n/Digits;cout<<number<<endl;//（3）for (int i=dig;i<Digits;i++) number /= 10;return number%10;}
};

先看看目标值在哪儿个区间

        long base = 9,Digits = 1;//Digits表示目前的数字在哪儿个区while(n-base*Digits>0){n -= base*Digits;base *= 10;Digits++;}

9第一个区间长度

180第二个区间长度

270第三个区间长度

我们看看我们要找的位数是在哪儿个区间长度，比如156

现在在第二个区间，区间号码：Digits

从第二个区间的首部算起，找第156-9 = 147个数字

第一步完成

 

下面我们找第147位数字，原来的值是多少，显然是为

        long number = 1;//起步位置for (int i = 1;i < Digits;i++)number *= 10;

以156为例，就是起步是10

10——99这180个中的第147个，因为Digits为2，所以直接147/Digits，数字都是两个两个一组，看看147在第几组

但是此处要考虑特殊情况比如找第11个数字，11-9 = 2,2/2 = 1；本来原数组是10，现在找到11了

所以先取余，看看到底是多少，不行就-1

        int dig = n % Digits;// Digits表示所在的区 if (dig == 0)dig = Digits;//如果能整除的话要减去1// cout<<dig<<endl;// cout<<n<<endl;number += (dig == Digits)? n/Digits - 1:n/Digits;

现在我们也找到了要找的原始数据了

是83，那么147到底是那儿一位呢？

147对Digits取余，如果是0，那么就是最后一位，不然就是第一位

        for (int i=dig;i<Digits;i++) number /= 10;return number%10;

难度颇高

面试题61. 扑克牌中的顺子

/

本题比较单纯

class Solution {
public:bool isStraight(vector<int>& nums) {sort(nums.begin(),d());int ZeroSize = 0;//大小王的个数for(int i = 0;i<nums.size();++i){if(nums[i] == 0) ZeroSize++;}int Pre = (ZeroSize == 0)?nums[0]:nums[ZeroSize];for(int i = ZeroSize+1;i<nums.size();++i){int Next = nums[i];int Dleta = Next - Pre;// cout<<Pre<<"  "<<Next<<"   "<<ZeroSize<<endl;Pre = Next;if(Dleta>1) ZeroSize = ZeroSize-Dleta+1; if(Dleta == 0||ZeroSize < 0) return false;}return true;}
};

 

面试题62. 圆圈中最后剩下的数字

/

/

/

 

面试题58 - II. 左旋转字符串

/

class Solution {
public:string reverseLeftWords(string s, int n) {pty()) return "";int begin = 0;n = n%s.size();string Part1 = s.substr(0,n);while(n){n--;begin++;}cout<<Part1<<endl;string Part2 = s.substr(begin,s.size()-n);return Part2+Part1;}
};

本题为字符串的拼接，找到旋转点，断开字符串，然后收尾拼接即可

面试题58 - I. 翻转单词顺序

合理运用栈的性质，先进后出，我们在提出了前后多余的空格后，将内容压入栈中，然后再一次输出，字符之间增加空格即可

class Solution {
public:string reverseWords(string s) {int size = s.size();// cout<<size<<endl;if(size == 0) return s;// 找起点和终点int begin = 0,end = size-1;while(begin<size-1&&s[begin] == ' ') begin++;while(end>=0&&s[end] == ' ') end--;// cout<<begin<<end<<endl;if(begin>end) return "";stack<string> Temp;int point = begin;while(point<=end){string n = "";while(point<=end&&s[point] != ' ') {n+=s[point];point++;}if(n!="") Temp.push(n);// cout<<s[point]<<endl;// point++;while(point<=end&&s[point] == ' ') point++;}//拼接// cout<<Temp.size()<<endl;string Res;while(Temp.size()-1){string item = p();Temp.pop();Res += item + ' ';}Res += p();return Res;}
};

面试题39. 数组中出现次数超过一半的数字

/

169. 多数元素 /

机考直接Hash表秒杀，但是笔试的时候，怎么算才是最优？

class Solution {
public:int majorityElement(vector<int>& nums) {if(!nums.size()) return 0;unordered_map<int, int> Map;int MAX = 0,index = 0;for(auto item:nums){Map[item]++;if( Map[item]>MAX ){MAX = Map[item];index = item;}}return index;}
};

排序，超过一半，那么中位数一定是该数字

class Solution {
public:int majorityElement(vector<int>& nums) {if(!nums.size()) return 0;sort(nums.begin(),d());return nums[nums.size()/2];}
};

使用莫尔投票法(Boyer-Moore)：

算法参考：/

/

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = -1;int count = 0;for (int num : nums) {if (num == candidate)++count;else if (--count < 0) {candidate = num;count = 1;}}return candidate;}
};作者：LeetCode-Solution
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

5437. 不同整数的最少数目

/

合理运用hash表和vector数组 

class Solution {
public:int findLeastNumOfUniqueInts(vector<int>& arr, int k) {pty()) return 0;unordered_map<int,int>M;for(auto item:arr) M[item]++;//记录出现次数vector<int>Time;//创建一个保存出现次数的数组for(auto item:M) Time.push_back(item.second);int res = M.size();//多少个数字sort(Time.begin(),d());//对出现次数进行排序for(auto item:Time){//拿出相应的个数if(item<=k) {k -= item;res--;}//本次拿走该数字后，k>=0,那么数字种类就要减1else if(item>k) break;//本次拿走多少，都不会改变数字种类}return res;}
};