首页 > 华为八月份机试题总结2-0811-测试代码补充
头像
lw_hnu
发布于 2021-08-13 11:24
+ 关注

华为八月份机试题总结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;
}




全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐