华为八月份机试题总结2-0811-测试代码补充
对题目进行了详细的描述，并提供了输入输出示例，参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习，offer拿到手软！！！
/*
0811-1:搭积木
当长宽都大于等于上一个积木时才可以搭到上一个积木上，此外数组还可以左右翻转。（与leetcode354相似，不过添加了翻转，增加了难度）
求最多能搭多少层
输入：
[[5,4], [6,3], [6,7], [6,6], [4,6]]
输出：
4
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin, s);
vector<vector<int>> nums;
while(s.size()>2)
{
int pos = s.find(']');
string temp = s.substr(2, pos-2);
s = s.substr(pos+2);
pos = temp.find(',');
int a = stoi(temp.substr(0, pos));
temp = temp.substr(pos+1);
int b = stoi(temp);
if(a<b) swap(a, b);//此行代码解决数组可左右翻转的问题，和后面的排序一起构成一个贪心的思想吧，我也不知道怎么证明这样就对
vector<int> v_temp;
v_temp.push_back(a);
v_temp.push_back(b);
nums.push_back(v_temp);
}
//将数组的第一维从大到小排序，如果第一维相等，则按第二维从大到小排序
auto cmp=[](vector<int> a, vector<int> b){
if(a[0] == b[0]) return a[1]>b[1];
else return a[0] >b[0];
};
sort(nums.begin(), nums.end(), cmp);
//动态规划求最长的递减子序列
int count = 1;
vector<int> dp(nums.size(), 1);//切记dp[i]表示[0,i]范围内包含nums[i]的最长递减子序列。注意该最长子序列并不一定是[0,i]范围内的最长递减子序列
for(int i=1; i<nums.size(); i++)
{
for(int j=i-1; j>=0; j--)
{
if(nums[i][1] <= nums[j][1])
{
dp[i] = max(dp[i], dp[j]+1);
}
}
count = max(dp[i], count); //这里也是根据dp[i]的定义，所以要取最大值
}
cout<<count<<endl;
return 0;
} /*
0811-2:接物品（接雨水的plus版本）
重复字母可以压缩（aaa=>a3）(为小写字母)，重复的连续字符串也可以压缩并转大写(abcabc=>ABC2)(为大写字母)
不过还要满足以下几个条件
如果只有两个连续的重复字符不压缩
重复连续字符串的优先级高于重复字符
重复连续子串的长度越长，优先级越高
输入："aaaabcaabcaabcaabc"
输出：aaAABC4
1
*/
#include<bits/stdc++.h>
using namespace std;
using namespace std;
//将小写字母转为大写
string CharUP(string &s)
{
for(size_t i = 0; i < s.size(); i++)
{
if(s[i] >= 'a' && s[i] <= 'z')
s[i] -= 32;
}
return s;
}
//判断连续子串的所哟字母是否都相等
bool isSame(string s)
{
for(int i=1; i<s.size(); i++)
{
if(s[0] != s[i]) return false;
}
return true;
}
int main()
{
// string s = "aaaabcabcabcabc";
string s = "aaaabcaabcaabcaabc";
int n = s.size();
vector<int> cnt = vector<int>(n, 0);
for(int l = s.size()/2; l > 1; l--) //最长的可能重复子串为l/2，依次递减
{
for(int i = 0; i < s.size(); i++)
{
string sTmp = s.substr(i, l);//用于匹配的重复子串
if(isSame(sTmp)) continue;
int pos = i+l;
int cnt = 1;
while(pos < s.size()) //看有几个连续的重复子串
{
if(sTmp != s.substr(pos, l)) break;
cnt++;
pos += l;
}
if(cnt != 1)
{
if(isupper(sTmp[0])) //处理变为大写字母的字符串中还有重复的字符串
{
// cout<<"s="<<s<<endl;
string s_t = s.substr(i+sTmp.size()*cnt);
// cout<<"s_t="<<s_t<<endl;
int cnt_update = cnt * stoi(s_t);
s = s.substr(0,i) + sTmp + to_string(cnt_update) + s.substr(i+cnt*l+1);
}
else
{
s = s.substr(0,i) + CharUP(sTmp) + to_string(cnt) + s.substr(i+cnt*l);
}
}
}
}
//处理单个字符
for(size_t i = 0; i < s.size(); i++)
{
if(s[i] >= 'a' && s[i] <= 'z')
{
int j = 0;
int cnt = 0;
while((i+1+j) < s.size() && s[i+1+j] >= '0' && s[i+1+j] <= '9')
j++;
string sCnt = s.substr(i+1, j);
cnt = atoi(sCnt.c_str());
if(s[i] == s[i+1+j])
cnt++;
if(cnt == 1 || cnt == 0)
continue;
sCnt = to_string(cnt);
if((i+2+j) < s.size())
s = s.substr(0,i+1) + sCnt + s.substr(i+2+j);
else
s = s.substr(0,i+1) + sCnt;
}
}
cout << s << endl;
return 0;
} /*
0811-3:接物品（接雨水的plus版本）
只有物品（有宽度）能放进坑里才行
输入：第一行（物品的宽度），第二行（坑的宽度），第三行（坑的深度）
2
4
0,-2,-2,-3,0
输出：
1
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int w_obj, n;
cin>>w_obj;
cin>>n;
string s;
cin>>s;
vector<int> nums;
while(true)
{
int a;
if(s.size()==1)
{
a = stoi(s);
nums.push_back(a);
break;
}
else
{
int pos = s.find(',');
a = stoi(s.substr(0, pos));
nums.push_back(a);
s = s.substr(pos+1);
}
}
//接下来求每个深度对应的最大宽度就可以了
//当宽度满足要求时，最大深度的相反数就为可以放的最多的物品
int res = 0;
for(int i=0; i<nums.size(); i++)
{
int w=1;
for(int k=i-1; k>=0; k--)//往左边找
{
if(nums[k] <= nums[i]) w++;
}
for(int k = i+1; k<nums.size(); k++)//往右边找
{
if(nums[k] <= nums[i]) w++;
}
if(w >= w_obj) res = max(res, -nums[i]); //和接雨水关键的不同就在于这一步，这个负深度就很巧妙，完美避开了正深度
}
cout<<res<<endl;
return 0;
} 
投递字节跳动等公司10个岗位 >