2015年华为校招机试题和代码实现（分解字符串,拼音转数字，去除重复字符并排序，等式变换）

心不留意外尘 2016-04-21

展开全文

http://blog.csdn.net/zhoubin1992/article/details/46461579

再来一套2015年的华为机试题。

第一题(60分)：

按要求分解字符串，输入两个数M，N；M代表输入的M串字符串，N代表输出的每串字符串的位数，不够补0。例如：输入2,8， “abc” ，“123456789”，则输出为“abc00000”,“12345678“,”90000000”
分析思路：
容易题
1.获得字符串的长度length后，判断与要输出位数N的大小，大于N的话，直接printf前N位字符，然后length-=N；
2.再次循环判断与要输出位数N的大小，如果小于N的话，输出length个字符和n-length个0字符。
3.重复循环直到length<0。
代码：

#include <iostream>
using namespace std;

/*********************************
2015届华为校招机试题——分解字符串)
Author:牧之丶  Date：2015年5月25日
Email:bzhou84@163.com
**********************************/
void resolve(char *str,int N){
    int length=strlen(str);             //获得字符串的长度length
    char strtemp[255];  
    while(length>0){                    //循环直到length<0
        if (length>=N)                  //大于N,直接printf前N位字符
        {
            int i;
            for (i=0;i<N;i++)
            {
                strtemp[i]=*str;        
                str++;
            }
            strtemp[i]='\0';            ////记得添加\0  
        } 
        else                            //小于N，输出length个字符和n-length个0字符
        {
            int i;
            for (i=0;i<length;i++)
            {
                strtemp[i]=*str;
                str++;
            }
            for (i=length;i<N;i++)
            {
                strtemp[i]='0';
            }
            strtemp[i]='\0';
        }
        cout<<strtemp<<" ";
        length-=N;
    }
}


int main(){
    int M,N;
    char str[255];
    while (cin>>M>>N)
    {
        for (int i=0;i<M;i++)
        {
            scanf("%s",str);
            resolve(str,N);
        }
    }
    return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

第一题拼音转数字

输入是一个只包含拼音的字符串，请输出对应的数字序列。转换关系如下：
描述：拼音 yi er san si wu liu qi ba jiu
阿拉伯数字 1 2 3 4 5 6 7 8 9
输入字符只包含小写字母，所有字符都可以正好匹配

运行时间限制：无限制
内存限制：无限制
输入：一行字符串，长度小于1000
输出：一行字符（数字）串
样例输入： yiersansi
样例输出： 1234
**思路：简单题，判断首字符即可。
代码：**

/*********************************
2015届华为校招机试题——拼音转数字)
Author:牧之丶  Date：2015年5月25日
Email:bzhou84@163.com
**********************************/
#include<iostream>
using namespace std;

void convert(char *str)
{
    int i;
    int length;
    for(i = 0 ; i < length ; )
    {
        switch(str[i])
        {
        case 'y':
            cout<<"1";
            i += 2;
            break;
        case 'e':
            cout<<"2";
            i += 2;
            break;
        case 's':
            if(str[i + 1] == 'a')
            {
                cout<<"3";
                i += 3;
            }
            else
            {
                cout<<"4";
                i += 2;
            }
            break;
        case 'w':
            cout<<"5";
            i += 2;
            break;
        case 'l':
            cout<<"6";
            i += 3;
            break;
        case 'q':
            cout<<"7";
            i += 2;
            break;
        case 'b':
            cout<<"8";
            i += 2;
            break;
        case 'j':
            cout<<"9";
            i += 3;
            break;
        }
    }
    printf("\n");
}

int main()
{
    char str[255];
    while(cin>>str)
    {
        convert(str);
    }
    return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

第二题：去除重复字符并排序

运行时间限制：无限制
内容限制：无限制
输入：字符串
输出：去除重复字符并排序的字符串
样例输入： aabcdefff
样例输出： abcdef
分析思路：
一、用map实现，map的特征：键不允许重复，比较函数只对元素的键值进行比较，小到大排序
代码：

/*********************************
2015届华为校招机试题——去除重复字符并排序
Author:牧之丶  Date：2015年5月25日
Email:bzhou84@163.com
**********************************/
#include <iostream>
#include <map>
using namespace std;

void fun(char *str){
    map<char,int> m;
    int length=strlen(str);
    for (int i=0;i<length;i++)
    {
        m[str[i]]+=1;
    }
    map<char,int>::iterator it;
    for (it=m.begin();it!=m.end();it++)
    {
        cout<<(*it).first;
    }
    cout<<endl;
}

int main(){
    char str[255];
    while(cin>>str)
    {
        fun(str);
    }
    return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二、非map，也是用hash方法，注意str[i]是字符型作为hash的下标是存的ascii，所以机智的完成了自动排序。
代码：

#include<iostream>
using namespace std;

void fun(char *str)
{
    int hash[256]={0};
    int length=strlen(str);
    for(int i = 0 ; i < length ; ++i)
    {
            hash[str[i]] = 1;
    }
    for(int i = 0 ; i < 256 ; ++i)
    {
        if(hash[i]!=0 )
            putchar(i);
    }
    printf("\n");
}

int main()
{
    char str[255];

    while(cin>>str)
    {
        fun(str);
    }
    return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第三题：等式变换

输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足输入整数的所有整数个数。
输入：正整数，等式右边的数字
输出：使该等式成立的个数
样例输入：5
样例输出：21
自己没有思路，参考了一份详细答案：
代码：
http://blog.csdn.net/feifeiyanfeifeia/article/details/38143419

/********************************************************************************
 *输入一个正整数X，在下面的等式左边的数字之间添加 + 号或者 - 号，使得等式成立。
 *1 2 3 4 5 6 7 8 9 = X
 *比如：
 *12 - 34 + 5 - 67 + 89 = 5
 *1 + 23 + 4 - 5 + 6 - 7 - 8 - 9 = 5
 *请编写程序，统计满足输入整数的所有整数个数。
 *输入： 正整数，等式右边的数字
 *输出： 使该等式成立的个数
 *样例输入：5
 *样例输出：21
 *********************************************************************************/
#include<iostream>
using namespace std;

#define N 8   //数字键空挡个数，这里有9个，所以为8，如果是1 2 3 4，则N=3

/*
*定义结构体数据，后面使用链表结构求解，每个结构体表示一个合法的表达式
*/
typedef struct MidResult  
{
    int Sym[N];//运算符表示，1表示‘+’，0表示仍然空着，-1表示‘-’
    int result;//表达式的计算结果
    int symnum;//符号个数
    struct MidResult* next;
}Node,*List;


/*判断两个表达式是否完全一样*/
bool isEqual(Node* p, Node* q)
{
    if (p == NULL || q == NULL) return false;
    if (p->symnum != q->symnum) return false;//符号个数
    //if (p->result != q->result) return false;
    for (int i = 0; i < N; i++)//符号序列
    {
        if (p->Sym[i] != q->Sym[i]) return false;
    }
    return true;
}

/*查找A数组中cur到n之间的‘+’（1表示）或‘-’（0表示）出现的位置
 *默认没有时返回n;
 */
int findNextSymbol(int *A, int cur,int n)
{
    for (int i = cur; i < n; i++)
    {
        if (A[i] != 0) return i;
    }
    return n;
}

/*将形如... [+/-] s * * * e[+/-] ...的表达式中* * *这些连着的字
*母转为整数，其中s为第一个*的数字，e为最后一个，s到e是连续整数
*/ 
int trans2Num(int s, int e)//s到e之间的串转化为整数
{
    int num = 0;
    for (int i = s; i <= e; i++)
    {
        num = 10 * num + i;
    }
    return num;
}

/*计算某个符号与两边的数形成的表达式的和
其中sum表示运算符号左边表达式的和x表示右边的数的和*/
int caculateSum(int sum, int sym, int x)
{
    if (sym == 1) return sum + x;
    else return sum - x;
}


/*计算结构体元素所表示的完整表达式的和*/
void caculateResult(Node *p)//求表达式和
{
    int num = 0, front = 0;//num为位结果
    int symbol;//记录接下来考察到的符号的结果
    int next = findNextSymbol(p->Sym, 0, N);//找到下一个运算符，则front和next之间为一个整数
    num = trans2Num(1, next + 1);//计算整数的值
    front = next + 1;
    symbol = p->Sym[next];
    int x;
    for (int i = 0; i < p->symnum; i++)//根据符合分割求加数
    {
        next = findNextSymbol(p->Sym, front, N);
        x = trans2Num(front + 1, next + 1);
        num = caculateSum(num, symbol, x);
        front = next + 1;
        symbol = p->Sym[next];
    }

    p->result = num;
}

bool hasElement(List list, Node *p)//计算节点元素是否在链表中，用于去重剪枝
{
    while (list != NULL)
    {
        if (isEqual(list, p)) return true;
        list = list->next;
    }
    return false;
}

int makeNextNode(Node* p, Node* &q,int cur,int sym)//产生下一个需要添加的节点元素，即一个新的完整表达式
{
    q = new Node;
    q->next = NULL;
    q->symnum = p->symnum + 1;
    for (int i = 0; i < N; i++)
    {
        q->Sym[i] = p->Sym[i];
    }
    for (int i = cur; i < N; i++)
    {
        if (q->Sym[i] == 0)
        {
            q->Sym[i] = sym;
            return i;
        }
    }
    return -1;
}

/*本体的最终函数，思路先考察运算符为0个的表达式，接下来扩展出所有运算符为1个的
*表达式，再有1个运算符的表达式扩展为2个的表达式，这个过程中需要查重起到剪枝作用
*以减小搜索空间
*/
int GetTotal(int result)
{
    int total = 0;
    List list = new Node;
    for (int i = 0; i < N; i++)
    {
        list->Sym[i] = 0;
    }
    list->next = NULL;
    list->symnum = 0; 
    caculateResult(list);
    Node *tail = list;
    Node *q;
    Node *tmp;
    int cur;
    while (list != NULL)
    {
        if (list->result == result) total++;
        cur = 0;
        for (int i = 0; i < (N - list->symnum); i++)
        {
            makeNextNode(list, q, cur, 1);//还有剪发，cur不改变
            if (!hasElement(list, q))//剪枝和添加
            {
                caculateResult(q);
                tail->next = q;
                tail = q;
            }
            cur = makeNextNode(list, q, cur, -1)+1;//完成改变
            if (!hasElement(list, q))//剪枝和添加
            {
                caculateResult(q);
                tail->next = q;
                tail = q;
            }
        }
        tmp = list;//删除元素
        list = list->next;
        delete tmp; 
    }
    return total;
}

int main()
{
    cout << GetTotal(5) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181