精华内容
下载资源
问答
  • 华为机试HJ16:购物单

    万次阅读 多人点赞 2021-07-21 12:49:10
    C++实现——购物单问题

    作者:翟天保Steven
    版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

    题目描述:

    王强今天很开心,公司发给N元的年终奖。王强决定把年终奖用于购物,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

    主件附件
    电脑打印机,扫描仪
    书柜图书
    书桌台灯,文具
    工作椅

    如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多,为了不超出预算,他把每件物品规定了一个重要度,分为 5 等:用整数 1 5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 元的整数倍)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

    设第 j 件物品的价格为 v[j] ,重要度为 w[j] ,共选中了 k 件物品,编号依次为 j 1 , j 2 ,……, j k ,则所求的总和为:

    v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。(其中 * 为乘号)

    请你帮助王强设计一个满足要求的购物单

    输入描述:

    输入的第 1 行,为两个正整数,用一个空格隔开:N m

    (其中 N ( <32000 )表示总钱数, m ( <60 )为希望购买物品的个数。)

    从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数 v p q

    (其中 v 表示该物品的价格( v<10000 ), p 表示该物品的重要度( 1 5 ), q 表示该物品是主件还是附件。如果 q=0 ,表示该物品为主件,如果 q>0 ,表示该物品为附件, q 是所属主件的编号)

    输出描述:

    输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值( <200000 )。

    示例:

    输入:

    1000 5

    800 2 0

    400 5 1

    300 5 1

    400 3 0

    500 2 0

    输出:

    2200

    解题思路:

    这道题是一个动态规划问题,类似于背包问题,即探讨如何装包可以使得最大化利用。

    首先可以将输入的物品信息放置在数组中,有三种物品类型分别是主体、附件1和附件2,如果购买附件则必须买对应的主体,也就是说购买方案中至少有一件是主体;考虑只买主体、买主体+附件1、买主体+附件2、买主体+附件1+附件2这几种情况,选择出针对某一金钱数的所有购买方案中最大化价值的那套方案,将其所得价值作为该金钱数下的最大价值,即dp[N],N为金钱数值。dp[ j-ZJ_Pri[i] ] + ZJ_Imp[i]指放入第i个主体时的价值,这个价值如果高于当前的dp[j],则替换dp[j],这样就起到了动态调整的作用,始终让dp[j]都为目前已遍历方案中的最大价值。

    其中,Pri就是物品价格,Imp是物品价格乘重要度;动态规划下务必采用倒序遍历;之所以除以10,是为了提高计算速度。

    测试代码为牛客网中比较优的一个C++案例,比我自己的实现要简洁明了,该作者昵称:不知道叫什么名字123,清华的大佬果然厉害~推广给大家学习参考。

    测试代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    int max(int m, int n)
    {
        return m>n?m:n;
    }
    int dp[3200];
    int main()
    {
        int N,n,v,p,q;
        cin >> N >> n;
        N = N/10;
     
        int *ZJ_Pri = new int[n+1]();  int *ZJ_Imp = new int[n+1]();
        int *FJ1_Pri = new int[n+1](); int *FJ1_Imp = new int[n+1]();
        int *FJ2_Pri = new int[n+1](); int *FJ2_Imp = new int[n+1]();
     
        for(int i=1; i<=n; i++)
        {
            cin >> v >> p >> q;
            v = v / 10;
            if(q == 0)
            {
                ZJ_Pri[i] = v;
                ZJ_Imp[i] = v * p;
            }
            else if(FJ1_Pri[q] == 0)
            {
                FJ1_Pri[q] = v;
                FJ1_Imp[q] = v * p;
            }
            else
            {
                FJ2_Pri[q] = v;
                FJ2_Imp[q] = v * p;
            }
        }
        for(int i = 1; i <= n; i++)//i---前i个物品
        {
            for(int j = N; j >=1; j--)//j--当前的钱数
            {
     
                if(j >= ZJ_Pri[i])
                    dp[j] = max(dp[j], dp[ j-ZJ_Pri[i] ] + ZJ_Imp[i]);
                if(j >= ZJ_Pri[i] + FJ1_Pri[i])
                    dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ1_Pri[i] ] + ZJ_Imp[i] + FJ1_Imp[i]);
                if(j >= ZJ_Pri[i] + FJ2_Pri[i])
                    dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ2_Pri[i] ] + ZJ_Imp[i] + FJ2_Imp[i]);
                if(j >= ZJ_Pri[i] + FJ1_Pri[i] + FJ2_Pri[i])
                    dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ1_Pri[i]-FJ2_Pri[i] ] + ZJ_Imp[i] + FJ1_Imp[i] + FJ2_Imp[i]);
            }
        }
        cout << dp[N]*10 << endl;
     
        delete[] ZJ_Pri;
        delete[] ZJ_Imp;
        delete[] FJ1_Pri;
        delete[] FJ1_Imp;
        delete[] FJ2_Pri;
        delete[] FJ2_Imp;
     
        return 0;
    }
    展开全文
  • 华为机试HJ61:放苹果

    万次阅读 多人点赞 2021-09-06 15:46:01
    C++实现——放苹果

    作者:翟天保Steven
    版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

    题目描述:

    把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

    数据范围:0<=m<=10,1<=n<=10。

    本题含有多组样例输入。

    输入描述:

    输入两个int整数

    输出描述:

    输出结果,int型

    示例:

    输入:

    7 3
    

    输出:

    8

    解题思路:

    本题用递归和动态规划做。m个苹果放在n个盘子里,允许空盘,用function函数递归获得结果;当m或n小于等于0时,返回0;当m或n等于1时,返回1;当m和n都大于1时,function(m,n)其实可以分为两种情况,一是留一个空盘,即function(m,n-1),二是全满盘,每个盘先放一个苹果,即function(m-n,n),则有function(m,n)=function(m,n-1)+function(m-n,n),进入递归过程;其中当m等于n时,function(m,n)=function(m,n-1)+function(m-n,n)+1,因为此时的function(m-n,n)是function(0,n),而m和n一致时满盘的情况只有一种,就是每个盘子都放一个。综上,解题完毕。

    测试代码:

    #include <iostream>
    
    using namespace std;
    
    int function(int m,int n){
        if(m<=0 || n<=0)
            return 0;
        else if(m==1 || n==1)
            return 1;
        else if(m==n)
            return function(m,n-1)+function(m-n,n)+1;
        else 
            return function(m,n-1)+function(m-n,n);
    }
    
    int main(){
        int m,n;
        while(cin >> m >> n){
            cout << function(m,n) << endl;
        }
        return 0;
    }
    展开全文
  • 华为机试HJ74:参数解析

    万次阅读 多人点赞 2021-09-18 14:29:51
    C++实现——参数解析

    作者:翟天保Steven
    版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

    题目描述:

    在命令行输入如下命令:

    xcopy /s c:\ d:\,

    各个参数如下:

    参数1:命令字xcopy

    参数2:字符串/s

    参数3:字符串c:\

    参数4: 字符串d:\

    请编写一个参数解析程序,实现将命令行各个参数解析出来。

    解析规则:

    1.参数分隔符为空格 
    2.对于用""包含起来的参数,如果中间有空格,不能解析为多个参数。比如在命令行输入xcopy /s "C:\program files" "d:\"时,参数仍然是4个,第3个参数应该是字符串C:\program files,而不是C:\program,注意输出参数时,需要将""去掉,引号不存在嵌套情况。
    3.参数不定长 
    4.输入由用例保证,不会出现不符合要求的输入

    输入描述:

    输入一行字符串,可以有空格

    输出描述:

    输出参数个数,分解后的参数,每个参数都独占一行

    示例:

    输入:

    xcopy /s c:\\ d:\\
    
    

    输出:

    4
    xcopy
    /s
    c:\\
    d:\\

    解题思路:

    本题是个字符串问题。

    首先统计参数个数,每出现一次空格,进行一次计数;当出现"字符时,持续遍历且忽略空格存在,直到再出现"字符结束;字符串完整遍历完,计数再加一,因为参数数量为空格的数量加一。

    输出结果,同统计类似,正常输出,每次出现空格输出一个回车符;当出现"字符时,循环输出直到再出现"字符结束。

    测试代码:

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s;
        while(getline(cin, s))
        {
            int size=s.size();
            int num=0;
            // 统计个数
            for(int i=0;i<size;++i)
            {
                if(s[i]=='"')
                {
                    ++i;
                    while(s[i]!='"')
                    {
                        ++i;
                    }
                }
                else if(s[i]==' ')
                {
                    num++;
                }
            }
            cout<<num+1<<endl;
            // 输出
            for(int i=0;i<size;++i)
            {
                if(s[i]=='"')
                {
                    i++;
                    while(s[i]!='"')
                    {
                        cout<<s[i];
                        i++;
                    }
                }
                else if(s[i]==' ')
                {
                    cout<<endl;
                }
                else{
                    cout<<s[i];
                }
            }
            cout<<endl;
        }
        return 0;
    }
    展开全文
  • 华为机试HJ54:表达式求值

    千次阅读 多人点赞 2021-09-02 10:32:49
    C++实现——表达式求值

    作者:翟天保Steven
    版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

    题目描述:

    给定一个字符串描述的算术表达式,计算出结果值。

    输入字符串长度不超过100,合法的字符包括”+, -, *, /, (, )”,”0-9”,字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。

    输入描述:

    输入算术表达式

    输出描述:

    计算出结果值

    示例:

    输入:

    400+5
    

    输出:

    405

    解题思路:

    本题有两个要点:

    1. 检查表达式合法性。首先利用sheet字典,确保字符串中字符都符合要求;其次判断左右括号数是否一致。
    2. calculate函数实现表达式计算。左右有括号就缩进;先找加减法再找乘除;找到运算符后,左右两侧字符串再调用calculate,进行递归;递归至不再包含运算符后退回,返回数字。递归结束,结果输出。

    测试代码:

    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    vector<char> sheet={'+','-','*','/','(',')','0','1','2','3','4','5','6','7','8','9'};
    
    // 检查合理性
    bool check(string &s)
    {
        int left=0;
        int right=0;
        for(int i=0;i<s.size();++i)
        {
            bool isok=false;
            for(int j=0;j<sheet.size();++j)
            {
                if(s[i]=='(')
                    left++;
                if(s[i]==')')
                    right++;
                if(s[i]==sheet[j])
                    isok=true;
            }
            if(!isok)
                return false;
        }
        if(left!=right)
            return false;
        return true;
    }
    
    // 算术表达式计算
    int calculate(string &s,int start,int end)
    {
        if(s[start]=='('&&s[end-1]==')')
        {
            ++start;
            --end;
        }
        int layer=0,am=0,md=0;
        bool flag=false;
        for(int i=start;i<end;++i)
        {
            if(s[i]=='(')
            {
                ++layer;
                flag=true;
            }
            else if(s[i]==')')
            {
                --layer;
                flag=true;
            }
            else if((s[i]=='+'||s[i]=='-')&&!layer)
                am=i;
            else if((s[i]=='*'||s[i]=='/')&&!layer)
                md=i;
        }
        
        if (am > start) {
            if (s[am] == '+') 
                return calculate(s, start, am) + calculate(s, am+1, end);
            else 
                return calculate(s, start, am) - calculate(s, am+1, end);
        } 
        else if (md > start) 
        {
            if (s[md] == '*') 
                return calculate(s, start, md) * calculate(s, md+1, end);
            else 
                return calculate(s, start, md) / calculate(s, md+1, end);
        }
        else if(flag)
            return calculate(s,start+1,end-1);
        else
            return stoi(s.substr(start,end-start));
    }
    
    int main()
    {
        string str;
        while(cin>>str)
        {
            if(!check(str))
                cout<<-1<<endl;
            else
                cout<<calculate(str, 0, str.size())<<endl;
        }
        return 0;
    }
    展开全文
  • 爆肝3个月为大家带来华为机试108题全解,强烈推荐学生党、就业党收藏
  • 华为机试HJ58:输入n个整数,输出其中最小的k个

    万次阅读 多人点赞 2021-09-06 13:51:09
    C++实现——输入n个整数,输出其中最小的k个
  • 华为机试HJ43:迷宫问题

    万次阅读 多人点赞 2021-08-19 16:16:50
    C++实现——迷宫问题
  • 华为机试HJ81:字符串字符匹配

    万次阅读 多人点赞 2021-09-21 17:04:59
    C++实现——字符串字符匹配
  • 华为机试HJ92:在字符串中找出连续最长的数字串

    万次阅读 多人点赞 2021-10-09 15:21:27
    C++实现——在字符串中找出连续最长的数字串
  • 华为机试HJ55:挑7

    千次阅读 多人点赞 2021-09-02 10:40:49
    C++实现——挑7
  • 华为机试HJ65:查找两个字符串a,b中的最长公共子串

    万次阅读 多人点赞 2021-09-09 12:49:25
    C++实现——查找两个字符串a,b中的最长公共子串
  • 华为机试 经验(血泪史啊)

    万次阅读 热门讨论 2020-02-13 13:47:31
    华为面试经验总结--免单统计
  • 华为机试HJ98:自动售货系统

    万次阅读 多人点赞 2021-10-15 13:26:47
    C++实现——自动售货系统
  • 华为机试HJ77:火车进站

    万次阅读 多人点赞 2021-09-21 16:49:14
    C++实现——火车进站
  • (牛客网)华为机试(一)

    万次阅读 多人点赞 2020-07-12 19:26:31
    华为机试解答 第一题 HJ108求最小公倍数: 直接gcd解决 #include<iostream> using namespace std; int gcd(int a,int b) //求最大公约数函数 { int r; while(b) { r=a%b; a=b; b=r; } return a; } int...
  • 华为机试HJ89:24点运算

    万次阅读 多人点赞 2021-10-08 11:25:50
    C++实现——24点运算
  • 华为机试HJ22:汽水瓶

    万次阅读 多人点赞 2021-07-26 13:09:50
    C++实现——汽水瓶问题
  • 华为机试HJ96:表示数字

    万次阅读 多人点赞 2021-10-14 15:47:39
    C++实现——表示数字
  • 华为机试 & 牛客网

    千次阅读 2021-02-24 20:52:18
    华为机试 & 牛客网 今天在准备华为机试,时间蛮紧的,就在牛客网刷了点题目,好久没练算法了,从网上查了下代码,发现很多版本的解题方法,因为我主要学的是C语言,就只看了C++的解法,下面汇总一下我觉得比较...
  • 华为机试HJ86:求最大连续bit数

    万次阅读 多人点赞 2021-09-26 15:16:01
    C++实现——求最大连续bit数
  • 华为机试HJ53:杨辉三角的变形

    万次阅读 多人点赞 2021-08-29 22:54:54
    C++实现——杨辉三角的变形
  • 华为机试HJ71:字符串通配符

    万次阅读 多人点赞 2021-09-15 10:45:25
    C++实现——字符串通配符
  • 华为机试HJ19:简单错误记录

    万次阅读 多人点赞 2021-07-22 09:46:03
    C++实现——简单错误记录
  • 华为机试技巧

    万次阅读 多人点赞 2019-01-05 17:31:40
    华为机试须知 一、上机考试需要在指定时间登录华为的软件考试平台进行答题,考试时长两个小时。具体操作步骤如下: 1、打开浏览器输入上机考试的网址; 2、输入姓名、邮箱和手机号等个人信息,提交登录; 3、登录后...
  • 题目ID:36884 - 查找组成一个偶数最接近的两个素数 题目描述 任意一个偶数(大于2)都可以由2个素数组成,组成偶数的2个素数有很多种情况,本题目要求输出组成指定偶数的两个素数差值最小的素数对 ...
  • 华为机试HJ66:配置文件恢复

    万次阅读 多人点赞 2021-09-09 14:19:44
    C++实现——配置文件恢复
  • 华为机试HJ28:素数伴侣

    千次阅读 多人点赞 2021-07-27 10:25:07
    C++实现——素数伴侣(匈牙利算法)
  • 华为机试HJ64:MP3光标位置

    万次阅读 多人点赞 2021-09-09 11:21:46
    C++实现——MP3光标位置
  • 华为机试HJ68:成绩排序

    万次阅读 多人点赞 2021-09-12 17:43:47
    C++实现——成绩排序
  • 2021年华为机试

    千次阅读 2021-05-19 22:08:35
    N个人。 难点是理解题目。代码写得有点繁琐。 #include<iostream> #include<map> #include<vector> using namespace std; vector<int> v; vector<bool> flag;... r >

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,317
精华内容 3,726
关键字:

华为机试