华为机试

发表于 分类于 ， 阅读次数： Waline： 本文字数： 9.8k 阅读时长 ≈ 9 分钟

华为机试

HJ1 字符串最后一个单词的长度

计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）

示例：

输入 hello world

输出 8

思路：

从后往前开始计算，碰到第一个空格时，长度为字符串长度-当前所在的位置-1；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;


int main(){
    string s1="";
    getline(cin,s1);
    int ans = 0;
    for(int i = s1.size()-1; i >= 0; --i){
        if(s1[i] == ' '){
            ans = s1.size() - i - 1;
            break;
        }
        else if(i==0){
            ans = s1.size();
        }
    }
    cout << ans << endl;
    
    return 0;
}

HJ2 计算某字符出现次数

写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）

ABCabc

A

输出：2

思路：

由于不区分大小写，所以将大写转化为小写，统计输出次数。

tolower函数把小写字母转换为小写，非字母字符不做出处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1;
    int res = 0;
    while(getline(cin,s1)){
        char input;
        cin >> input;
        cin.ignore();
        input= tolower(input);//转化为小写
        for(int i=0;i<s1.size();++i){
            if(s1[i]==input|| s1[i]==input-32){
                res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

HJ3 明明的随机数

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（ N≤1000 ），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。现在明明把他已经用计算机生成好的 N 个随机数按照下面的输入描述的格式交给你，请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

当没有新的输入时，说明输入结束。

数据范围： 1≤n≤1000 1≤n≤1000 ，输入的数字大小满足 1≤val≤500 1≤val≤500

3
2
2
1
11
10
20
40
32
67
40
20
89
300
400
15

输出：

1
2
10
15
20
32
40
67
89
300
400

说明：

示例1包含了两个小样例！
输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到1000之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以第一个小样例的输出为：
1
2
第二个小样例的第一个数字为11，也即...(类似上面的解释)...
所以第二个小样例的输出为：
10
15
20
32
40
67
89
300
400

思路：

类似于map,统计，最后遍历一遍输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main(){
    int number,n;
    while(cin>>number){
        int a[1001] = {0};
        while(number--){
            cin>>n;
            a[n]++;
        }
        for(int i = 0;i<1001;++i){
            if(a[i]){
                cout<<i<<endl;
            }
        }
    }
    return 0;
}

HJ4 字符串分隔

•连续输入字符串，请按长度为8拆分每个输入字符串并进行输出；

•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

（注：本题有多组输入）

示例：

输入：

abc
123456789

输出：

abc00000
12345678
90000000

思路：

我们在读取的字符串后面增加7个零，这样我们就可以保证后面的0；在通过substr函数进行提取，这里需要简单介绍下substr函数。

s.substr(pos,len)，返回值是string,包含s中从pos开始的len个字符的拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1;
    while(cin>>s1){
        s1 = s1 + "0000000";    //增加7个0，然后substr函数截取前8个
        while(s1.size()>=8){
            cout<<s1.substr(0,8)<<endl;
            s1 = s1.substr(8);
        }
    }
    return 0;
}

HJ5 进制转换

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

数据范围：保证结果在 1≤n≤231−1 1≤n≤231−1

注意本题有多组输入

示例：

输入：

0xA
0xAA

输出：

10
170

思路：

方法一：

直接用流类格式化输入输出

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main(){
	int a;
	while(cin>>hex>>a)
	cout<<dec<<a<<endl;
}

方法二：

主要就是十进制和十六进制的转换关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    while(cin>>s){
        int bit=0;
        int ans=0;
        for(int i =s.size()-1;i>1;--i){
            if(s[i]>='0'&&s[i]<='9'){
                ans+=(s[i]-'0')*pow(16,bit++);
            }
            else if(s[i]>='A'&&s[i]<='F'){
                ans+=(s[i]-'A'+10)*pow(16,bit++);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

HJ6 质数因子

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

数据范围： 1≤n≤2×109+14 1≤n≤2×109+14

输入描述：

输入一个整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例：

输入：180

输出：2 2 3 3 5

思路：

输出所有质数的因子，那么这个因子最大也就是这个数值开根号，比如25，质数因子就是 5、5；除数从2开始，进行除法计算，除不尽就用3，以此类推，直到除数增加到该数的开根号。

有除数能除的最后数值一定是1，如果不是1，那就是这个数本身就是质因子，只有1和本身可以整数，直接输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(){
    long res;
    long i = 2;
    cin >> res;
    for(i;i<=sqrt(res);i++){
        while(res%i==0){
            cout<<i<<" ";
            res /= i;
        }
    }
    if(res>1){
        cout<<res<<" ";
    }
    return 0;
}

HJ7 取近似值

写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于 0.5 ,向上取整；小于 0.5 ，则向下取整。

数据范围：保证输入的数字在 32 位浮点数范围内

示例：

输入：5.5

输出：6

输入：2.499

输出：2

思路：

直接在输入的数上+0.5，然后通过int取整就可以了

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main(){
    float input;
    cin>>input;
    cout<<int(input+0.5)<<endl;
    return 0;
}

HJ8 合并表记录

数据表记录包含表索引和数值（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

提示:

0 <= index <= 11111111

1 <= value <= 100000

输入描述:

先输入键值对的个数n（1 <= n <= 500） 然后输入成对的index和value值，以空格隔开

输出描述：

输出合并后的键值对（多行）

示例：

输入：

4
0 1
0 2
1 2
3 4

输出：

0 3
1 2
3 4

解题思路：

方法一：

我们用一个数组来存储，对相同索引的数值求和，最后遍历输出数值大与0的即可。（不能完全AC）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main(){
    int num;
    cin>>num;
    int sum[1000]={0};
    int index,value;
    for(int i=0;i<num;i++){
        cin>>index>>value;
        sum[index]+=value;
    }
    for(int i=0;i<1000;i++){
        if(sum[i]!=0){
            cout<<i<<" "<<sum[i]<<endl;
        }
    }
    return 0;
}

方法二：

利用C++的map实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main(){
    map<int,int>sum;
    int n;
    cin>>n;
    int index,value;
    while(n--){
        cin>>index>>value;
        sum[index]+=value;
    }
    for(auto c:sum){
        cout<<c.first<<" "<<c.second<<endl;
    }
    return 0;
}

HJ9 提取不重复的整数

输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。

保证输入的整数最后一位不是 0 。

数据范围： 1≤n≤108 1≤n≤108

示例：

输入：9876673

输出：37689

解题思路：

转化为字符串的方法来解决，这里了解一下string::npos

find函数在找不到指定值得情况下会返回string::npos。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main(){
    string str;
    string str1="";
    cin>>str;
    for(int i=str.size()-1;i>=0;i--){
        if(str1.find(str[i])==string::npos)
            str1+=str[i];
    }
    cout<<str1<<endl;
    return 0;
}

方法二：

使用数组a[10]来更新，每次把a[n%10]来判断是否出现过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int a[10]={0};
    int num=0;
    cin>>n;
    while(n){
        if(a[n%10]==0){
            a[n%10]++;//这一步更新，遇到相同的数会跳过
            num = num*10+n%10;
        }
        n/=10;
    }
    cout<<num<<endl;
    return 0;
}

HJ10 字符个数统计

编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次

例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。

数据范围： 1≤n≤500 1≤n≤500

示例：

输入：abc

输出：3

思路：

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    set<char>s;
    while(getline(cin,str)){
        for(int i=0;i<str.size();i++){
            s.insert(str[i]);
        }
    }
    cout<<s.size()<<endl;
    return 0;
}

HJ11 数字颠倒

输入一个整数，将这个整数以字符串的形式逆序输出

程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001

数据范围： 0≤n≤230−1 0≤n≤230−1

示例：

输入：1516000

输出：0006151

思路：

转化为string,然后翻转

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main(){
    int input;
    cin>>input;
    string res = to_string(input);
    reverse(res.begin(), res.end());
    cout<<res;
    return 0;
}

HJ12 字符串反转

接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

示例：

输入：abcd

输出：dcba

思路：

直接reverse()

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    cin>>str;
    reverse(str.begin(),str.end());
    cout<<str;
    return 0;
}

HJ13 句子逆序

将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”

所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符

数据范围：输入的字符串长度满足 1≤n≤1000 1≤n≤1000

注意本题有多组输入

示例：

输入：I am a boy

输出：boy a am I

思路：

我们定义一个string数组，顺序输入，倒序输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    vector<string> tmp;
    while(cin>>str){
        tmp.push_back(str);
    }
    for(int i=tmp.size()-1;i>0;i--){
        cout<<tmp[i]<<" ";
    }
    cout<<tmp[0]<<endl;
    return 0;
}

HJ14 字符串排序

描述

给定 n 个字符串，请对 n 个字符串按照字典序排列。

数据范围： 1≤n≤1000 1≤n≤1000 ，字符串长度满足 1≤len≤100 1≤len≤100

输入描述：

输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。

输出描述：

数据输出n行，输出结果为按照字典序排列的字符串。

示例：

输入：

9
cap
to
cat
card
two
too
up
boat
boot

输出：

boat
boot
cap
card
cat
to
too
two
up

思路：

直接排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<string> res;
    while(n--){
        string tmp;
        cin>>tmp;
        res.push_back(tmp);
    }
    sort(res.begin(),res.end());
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<endl;
    }
    return 0;
}

HJ15 求int型正整数在内存中存储时1的个数

描述

输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。

数据范围：保证在 32 位整型数字范围内

输入描述：

输入一个整数（int类型）

输出描述：

这个数转换成2进制后，输出1的个数

示例：

输入：5

输出：2

思路：

n&(n-1) 即（0111）&（0110）== 0110 就是 n去除了最后一个1 ；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int count = 0;
        while(n){
            //判断二进制有多少个1
            n &= n-1;
            count++;
        }
        cout<<count<<endl;
    }
    return 0;
}