C/C++教程
面试题打卡——C++版
文章目录
- 跳石板
- 字符串通配符
- 串联字符串的最大长度
- 柱状图中最大的矩形
- 皇位继承顺序
跳石板
小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
题解:
1.定义数组count[m]表示到达m位置时需要跳多少次，初始化数组的值为INT_MAX, count[n]=0
2.遍历count，如果count[i]!=INT_MAX，表示可以从当前位置出发(从第一次开始，跳到这来了)
3.当从 i位置，跳到下一个x位置时，count[x]=fmin(count[x],count[i]+1)
#include <iostream>
#include <vector>
using namespace std;
#include <math.h>
#include <limits.h>
void GetNum(int x, vector<int> &arr)//求下一步的所有值
{
arr.clear();//先清空
for (int i = 2; i <= sqrt(x); i++)//从后往前除，第一个位置就是最大值
{
if (x%i == 0)
{
arr.push_back(i);
if (x / i != i)//另外一半
arr.push_back(x / i);
}
}
}
int main()
{
int n;//出发点
int m;
while (cin >> n)
{
cin >> m;//跳到m位置
vector<int> count(m + 1, INT_MAX);//count[i]表示跳到i位置所需要的步伐数
vector<int> arr;
count[n]=0;
for (int i = n; i <= m; i++)
{
if (count[i] ==INT_MAX)//不能从当前位置出发
continue;
GetNum(i, arr);//获取下一步能到达的位置
for (auto&e : arr)
{
if (e + i <= m)//没有超出范围
count[i + e] = fmin(count[i + e], count[i] + 1);
}
}
if (n == m)
cout << 0 << endl;
else if (count[m] == INT_MAX)
cout << -1 << endl;
else
cout << count[m] << endl;
}
return 0;
}
字符串通配符
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求： 实现如下2个通配符：
*：匹配0个或以上的字符（字符由英文字母和数字0-9组成，下同）
？：匹配1个字符
注意：匹配时不区分大小写。
输入： 通配符表达式； 一组字符串。
题解：
1.设dp[i][j]表示s1的前i个字符和s2的前j个字符是否匹配
2.此时s1的最后一个字符s1[i]有三种情况:为?、为*、为普通字符，接下来分别进行讨论
a.当s1[i]==?时，如果对方s2[j]是字母或者数字时，则表示匹配，即此时需要看两个字符串的前一个位置 dp[i][j]
b.当s1[i]== 时*，此时 * 可以匹配N个字符
当N=0时，当前是否匹配，则需要看s1的前i-1个字符和s2的前j个字符 -> dp[i+1][j+1] = dp[i][j+1]
当N!=0时，则需要判断s2[j]是否是字母或者数字，如果是，表示s1[i]可以和s2[j]进行匹配，此时需要看前面，以s1[i]和s2[j-1]结尾的字符串是否相等，因为此时N可以进行多次匹配
c.当s1[i]为普通字符时，此时则需要判断s1[i]是否与s2[j]相等，如果相等，则判断s[i-1] 与 s[j-1]是否相等
3.进行初始化的时候，dp[0][0]=true表示两个都为空时，同时需要判断s1[i] 是否是连续的*，如果是，则dp[i+1][0]=true -> * 可以为为0
#include <iostream>
using namespace std;
#include <string>
#include <vector>
bool Judge(string &str, int sub)
{
if ((str[sub] >= '0'&&str[sub] <= '9') || (str[sub] >= 'a'&&str[sub] <= 'z') || (str[sub] >= 'A'&&str[sub] <= 'Z'))//*和.可以匹配的字符
return true;
return false;
}
int main()
{
string s1, s2;
while (cin >> s1 >> s2)
{
vector<vector<bool>> dp(s1.size() + 1, vector<bool>(s2.size() + 1, false));
dp[0][0] = true;//两个都是空字符串
for (int i = 0; i < s1.size(); i++)//*连续，则可以一直表示0个字符，即与空串是匹配的
{
if (s1[i] == '*')
dp[i + 1][0] = true;
else
break;
}
for (int i = 0; i<s1.size(); i++)
{
for (int j = 0; j<s2.size(); j++)
{
if (s1[i] == '?')
{
if (Judge(s2, j))
dp[i + 1][j + 1] = dp[i][j];
}
else if (s1[i] == '*')
{
if (dp[i][j + 1] == true)//匹配0个
dp[i + 1][j + 1] = true;
else if (Judge(s2, j))//匹配多个
dp[i + 1][j + 1] = dp[i + 1][j];
}
else//普通字符
{
if (s1[i] == s2[j] || s1[i] - 32 == s2[j] || s1[i] + 32 == s2[j])
dp[i + 1][j + 1] = dp[i][j];
}
}
}
if (dp[s1.size()][s2.size()])
cout << "true" << endl;
else
cout << "false" << endl;
}
return 0;
}
串联字符串的最大长度
给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。请返回所有可行解 s 中最长长度。
题解:
1.利用回溯法，将字符进行组合起来
2.回溯的过程之中，进行剪枝 -> 当组合的字符串中出现重复的字符，则进行剪枝(可以用哈希表，进行是否字符重复判断)
3.当组成的字符串出现新的长度的时候，则保存起来
4.最后返回得到的字符串的长度
class Solution {
public:
bool Judge(string &str)
{
unordered_map<char,int> mp;
for(auto&e:str)
{
if(mp[e]==0)
mp[e]++;
else
return false;//出现多次
}
return true;
}
void _maxLength(string &ret,vector<string>& arr,int sub,string &temp)
{
if(!Judge(temp))//出现重复字符
return ;
if(temp.size()>ret.size())//出现了更长的字符
ret=temp;
for(int i=sub;i<arr.size();i++)
{
string copy(temp);//先保存一份
temp+=arr[i];
_maxLength(ret,arr,i+1,temp);
temp.swap(copy);//回溯处理
}
}
int maxLength(vector<string>& arr) {
//首先得判断是否有重复的字符
//挑选出最长的不含重复字符的最长字符串，返回它的长度
//利用回溯法，进行字符串的拼接，然后进行判断是否出现重复的字符
string ret,temp;
_maxLength(ret,arr,0,temp);
return ret.size();
}
};
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
题解1：暴力法
遍历整个数组，求出以每块木板的长度为矩形高度的面积，算出所有的值来，取其中的最大值
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
//遍历整个数组，求以每一块板为高度的面积
int max=0;
for(int i=0;i<heights.size();i++)
{
int left=i;
int right=i;
while(left>=0&&heights[left]>=heights[i])
left--;
while(right<heights.size()&&heights[right]>=heights[i])
right++;
max=fmax(max,heights[i]*(right-left-1));
}
return max;
}
};
题解2：单调栈法
1.由暴力法可知，需要遍历每块板，然后找到它的左边边界(左边第一块小于当前板的位置)和右边边界(右边第一块长度小于当前板的位置)
2.维护一个单调栈，如果新入的元素大于等于栈顶元素，则将其入栈
3.如果新入的元素小于栈顶元素，则将栈顶元素出栈，此时，新入元素的位置就是右边界，由于是单调递增栈，栈中下一个位置就是左边界
4.由于边界的判定需要，所以栈中保存的是元素的坐标
5.同时，当栈为空或者一些特殊情况非常麻烦，因此在数组的前面和后面分别加上一个0
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
//在前面和后面添加0，解决一些场景下的边界问题
vector<int> copy(heights.begin(),heights.end());
copy.insert(copy.begin(),0);
copy.push_back(0);
int max=0;
for(int i=0;i<copy.size();i++)
{
//新来的元素，小于栈顶元素
while(!st.empty()&©[i]<copy[st.top()])
{
int cur=st.top();
st.pop();
int left=st.top();
max=fmax(max,(i-left-1)*copy[cur]);
}
st.push(i);
}
return max;
}
stack<int> st;
};
皇位继承顺序
一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
题解：
1.给定两个哈希表，一个mp<string,vector>存储具有继承关系的人，mp中key值表示以这个人为父亲，v值表示这个人孩子的集合
另外一个set记录这个人是否已经死了，如果一个人死了，则添加至set集合之中
2.新孩子来了，通过父亲找到对应的集合，将孩子添加进去
3.输出继承顺序，继承顺序是一个前序遍历，在输出的时候，需要判断，这个人是否在死亡集合里面
class ThroneInheritance {
public:
ThroneInheritance(string kingName)
:_king(kingName)
{
_mp[kingName];//第一个人
}
void birth(string parentName, string childName) {//有了一个新的孩子
//得到它父亲的孩子集合,并且将该孩子添加进去
_mp[parentName].push_back(childName);//将该孩子添加进去
_mp.insert(make_pair(childName,vector<string>()));//这个孩子也有可能成为父亲
}
void death(string name) {//死了
_death.insert(name);//死亡的将其进行标记
}
void prevOrder(vector<string>& ret,string name)
{
vector<string> arr=_mp[name];
for(int i=0;i<arr.size();i++)
{
if(_death.find(arr[i])==_death.end())//没有死亡，则添加进去
ret.push_back(arr[i]);
prevOrder(ret,arr[i]);
}
}
vector<string> getInheritanceOrder() {//返回继承顺序列表
vector<string> ret;
if(_death.find(_king)==_death.end())//不在死亡列表之中
ret.push_back(_king);
prevOrder(ret,_king);
return ret;
}
string _king;//保存第一位国王
unordered_map<string,vector<string>> _mp;//记录每个人，和它的孩子
unordered_set<string> _death;//记录这个人是否死亡
};
-
MATLAB 中 A(7)=[];什么意思？-icode9专业技术文章分享11-26
-
UniApp 中如何实现使用输入法时保持页面列表不动的效果？-icode9专业技术文章分享11-26
-
在 UniApp 中怎么实现输入法弹出时禁止页面向上滚动？-icode9专业技术文章分享11-26
-
WebSocket是什么，怎么使用？-icode9专业技术文章分享11-26
-
页面有多个ref 要动态传入怎么实现？-icode9专业技术文章分享11-26
-
在 UniApp 中实现一个底部输入框的常见方法有哪些？-icode9专业技术文章分享11-26
-
RocketMQ入门指南：搭建与使用全流程详解11-26
-
RocketMQ入门教程：轻松搭建与使用指南11-26
-
手写RocketMQ：从入门到实践的简单教程11-26
-
【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版11-25
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
