Huawei written test algorithm summary
- 2020-06-19 11:19:51
- OfStack
This paper shares four algorithm questions for huawei 2014 written test for your reference. The specific content is as follows
1. Enter a string of lowercase letters (a~z) on the keyboard. Write a string filter. If more than one character is the same in the string, filter out the character that is not the first time.
For example, the string "abacacde" filters to "abcde".
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);
[Input] pInputStr: Input string
lInputLen: Enter the length of the string
[Output] pOutputStr: Output string, space has been opened, as long as the input string;
[Note] Only the function algorithm needs to be completed, and no input or output of IO is needed in the middle
The sample
Input: "deefd" Output: "def"
Input: "afafafaf" Output: "af"
Input: "pppppppp" Output: "p"
main function has been hidden, here reserved for the user's test entry, here to test your implementation function, you can call printf printout
Currently you can use other methods of testing, as long as the final program is executed correctly, the function implementation can be modified, but do not change the function prototype.
1 must ensure that the compilation run is not affected
////////////////////////////////////////////////////////////////////////// Huawei's first 1 The topic 19:19-19:36 17 minutes
#include <iostream>
#include <cassert>
using namespace std;
bool g_flag[26];
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr)
{
assert(pInputStr != NULL);
int i = 0;
if (pInputStr == NULL || lInputLen <= 1)
{
return;
}
const char *p = pInputStr;
while(*p != '\0')
{
if (g_flag[(*p - 'a')])
{
p++;
}else{
pOutputStr[i++] = *p;
g_flag[*p - 'a'] = 1;
p++;
}
}
pOutputStr[i] = '\0';
}
int main()
{
memset(g_flag,0,sizeof(g_flag));
char input[] = "abacacde";
char *output = new char[strlen(input) + 1];
stringFilter(input,strlen(input),output);
cout<<output<<endl;
delete output;
return 0;
}
2. Enter a string of lowercase letters (a~z) on the keyboard. Please write a string compression program, the string in the continuous presence of repeated letters compression, and output the compressed string.
Compression rules:
1. Compress only characters that appear continuously and repeatedly. For example, the string "abcbc" is still "abcbc" because there are no consecutive repeating characters.
2. The format of compressed field is "number of character repetitions + character". For example, the string "xxxyyyyyyz" becomes "3x6yz" when compressed.
Required functions:
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
[Input] pInputStr: Input string
lInputLen: Enter the length of the string
[Output] pOutputStr: Output string, the space has been opened, as long as the input string;
[Note] Only the function algorithm needs to be completed, and no input or output of IO is needed in the middle
The sample
Input: "cccddecc" Output: "3c2de2c"
Input: "adef" Output: "adef"
Input: "pppppppp" Output: "8p"
////////////////////////////////////////////////////////////////////////// Huawei's first 2 The topic 19:40 - 20:10 In the middle of delay 3 minutes
#include <iostream>
#include <cassert>
using namespace std;
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr)
{
const char *p = pInputStr;
int num = 1;
int i = 0;
p++;
while(*p != NULL)
{
while(*p == *(p-1)&& *p != NULL)
{
num++;
p++;
}
if (num > 1)
{
int size = 0;
int temp = num;
while(num) // Calculation of digits
{
size++;
num /= 10;
}
num = 1;
for (int j = size; j > 0; j--)
{
pOutputStr[i+j-1] = '0'+ temp%10;
temp /= 10;
}
i +=size;
pOutputStr[i++] = *(p-1);
p++;
}else{
pOutputStr[i++] = *(p-1);
p++;
}
}
pOutputStr[i] = '\0';
}
int main()
{
char input[] = "cccddecc";
char *output = new char[strlen(input) + 1];
stringZip(input,strlen(input),output);
cout<<output<<endl;
return 0;
} 3. Input the plus and minus operation expressions of positive integers less than 100 through the keyboard, please write a program to output the operation result string.
The input string is formatted as: operand 1 operator operand 2, separated by a space.
Additional Notes:
1, the operand is a positive integer, do not need to consider the calculation result overflow situation.
2. If the input formula is formatted incorrectly, the output result is "0".
Required functions:
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);
[Input] pInputStr: Input string
lInputLen: Enter the length of the string
pOutputStr: Output string, space has been opened, as long as the input string;
[Note] Only the functional algorithm of this function needs to be completed, and no input or output of IO is needed in the middle
The sample
Input: "4 + 7" Output: "11"
Input: "4-7" Output: "-3"
Input: "9 ++ 7" Output: "0" Note: Format error
////////////////////////////////////////////////////////////////////////// Huawei's first 3 The topic 20:29 - 20:40
#include <iostream>
using namespace std;
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr)
{
const char *input = pInputStr;
char *output = pOutputStr;
int sum = 0;
int operator1 = 0;
int operator2 = 0;
char *temp = new char[5];
char *ope = temp;
while(*input != ' ') // Get operands 1
{
sum = sum*10 + (*input++ - '0');
}
input++;
operator1 = sum;
sum = 0;
while(*input != ' ')
{
*temp++ = *input++;
}
input++;
*temp = '\0';
if (strlen(ope) > 1 )
{
*output++ = '0';
*output = '\0';
return;
}
while(*input != '\0') // Get operands 2
{
sum = sum*10 + (*input++ - '0');
}
operator2 = sum;
sum = 0;
switch (*ope)
{
case '+':itoa(operator1+operator2,pOutputStr,10);
break;
case '-':itoa(operator1-operator2,pOutputStr,10);
break;
default:
*output++ = '0';
*output = '\0';
return;
}
}
int main()
{
char input[] = "4 - 7";
char output[] = " ";
arithmetic(input,strlen(input),output);
cout<<output<<endl;
return 0;
} 4. Input 1 to 50 Numbers and find the sum of the smallest and largest Numbers
// huawei 2014 In machine exam 1 Input: 1--50 Number. Find the sum of the smallest number and the largest number
// Input is separated by commas
#include<stdio.h>
#define N 50
void sort(int a[],int n);
int main(void)
{
char str[100];
int a[N]={0};
gets(str); // The main points of 1 : Dynamic input 1--50 Number of integers, can not determine the number, can only use the string input, and then separate out
int i=0;
int j=0;
int sign=1;
while(str[i]!='\0')
{
if(str[i]!=',') // Input at half Angle
{
if(str[i] == '-') // The main points of :2 : Has a negative integer input
{
// i++; // Easy wrong points 1
sign=-1;
}
else if(str[i]!='\0') // Don't have to else And then the minus sign will also subtract '. 0'
{
a[j]=a[j]*10 + str[i]-'0'; // The main points of 3 : The input can be multiple digits
}
}
i++;
if(str[i]==',' || str[i]=='\0') // The judgment is in i Since it
{
a[j]=a[j]*sign; // Easy wrong points 2
sign=1; //// Easy wrong points 3
j++; //j is a Number of arrays The scope of 0 to j-1
}
}
sort(a,j);
printf("Max number + Min number = %d",a[0]+a[j-1]);
return 0;
}
void sort(int a[],int n) // Selection sort
{
int i,j;
int k;
int temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[k]>a[j])
k=j;
}
if(i!=k)
{
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
for(i=0;i<n;i++)
printf("%-5d",a[i]);
puts("");
}