奇安信2021秋招面试题
选择题：
int array[5] = {7,8,3,2,6};
int p = (int *)(array+1);
int *m=(int)(&array +1);
printf("%d %d %d\n",(array+1),(p+1),(m-1)) ;
输出结果：
Answer: 8 3 6
只分析最后一个
array指向数组的首地址，也是数组中第一个元素的地址，array+1指向第二元素的地址。&array，表示指向地址的地址，&array+1指向一个和array相同元素的下一个地址，因为array大小为5sizeof(int)，所以&array+1的地址为array[0]+sizeof(int)或者array+5sizeof(int)。
编程题：
1.在一棵魔法森林中，每棵树都有攀比心里，每当魔法师指定一棵树时，指定的树高度不变，其他树的高度都会加1，知道所有树的高度都一样高时，所有树才会停止生长。魔法师当然不希望所所有的树疯狂生长，问魔法师知道需要操作多少次才能使得森立中的树停止生长.
用例输入/输出：
第一行输入一个数n，表示树的个数，第二行输入n个数，分别表示每棵树的高度 。
没课树的高度ai满足，
输出一行一个数，表示使得树停止生长最少操作的次数。
input
3
1 2 3
output：
3
input：
4
5 2 3 7
output:
9
Analysis:
每次先找到森林中最大的值和最小的值，指定最大的，其他的树的高度均加上高树和最低树的差值d1，每轮结束至少有一个新的相等的树增加（森林中高度相等树的数量可能不会增加），并且新增加高度相等的树高度会一致相等（因为原来高度相等的树，只要不是深林中最高的，就不会导致其中一棵树被指定，另外其他树高度增加），因此证明该方法收敛。又因为每一轮中操作都是向着森林高度中高度相等的方向的走，可以等价于每一步都是最优的，因此也保证了最终结果的操作次数最少。
代码实现：
#include<iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<long long> input;
long long temp;
for(int i = 0;i < n;i++)
{
cin>>temp;
input.push_back(temp);
}
int minI,maxI;
long long res = 0;
while(1)
{
if(input[0] > input[1])
{
maxI = 0;
minI = 1;
}
else
{
maxI = 1;
minI = 0;
}
for(int i = 2;i<n;i++)
{
if(input[i] > input[maxI])
maxI = i;
if(input[i] < input[minI])
minI = i;
}
if(input[maxI]== input[minI])
break;
else{
long long minvalue = input[minI];
res += input[maxI] - minvalue;
//cout<<"A"<<endl;
//更新除最高树之外的其他树
for(int j = 0;j < n;j++)
{
if(maxI!=j)
{
input[j] += input[maxI] - minvalue;
}
}
}
}
cout<<res<<endl;
} 2.字符串替换，一个字符串中由0~9组成，接了下来有n组像（number1,number）的数据，每次将字符串中的数字number1替换成number2。注意查找效率。
样例输入
第一行输入一个只包含0~9的字符串，第二张输入一个整数n,接下来n行每行输入两个整数。
0285289430826
2
0 2
2 3
样例输出
输出替换后的字符串
3385389433836
Analysis：
思路1：对每次数组都遍历整个字符串进行替换，时间复杂度为O(n*t),t为字符串的长度。
思路2：因为n组数字替换，前面的数字替换很多会被后面的数字替换，因此希望确定0~9最终的对应的数字后在遍历整个字符换进行替换，应为只有0~9十个数，因此使用一个数组模拟一个hash表。根据下标关系和数字关系的隐形下标作为hash函数，这样在替换整个字符串的时候，确定要替换的数字也可以实现快速查找。时间复杂度为O(max(n,t)),t为字符串的长度。
实现：
#include <iostream>
#include <vector>
#include "algorithm"
using namespace std;
int main(){
string str;
cin>>str;
int n;
cin>>n;
char data[n][2];
vector<int> numbers(10,-1);
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
for(int j = 0;j < 10;j++)
{
if(numbers[j] == a)
{
numbers[j] = b;
}
if(numbers[a] == -1)
numbers[a] = b;
}
}
for(int i=0;i<str.length();i++){
if(numbers[str[i] - '0']!= -1){
str[i] = numbers[str[i] - '0']+'0';
}
}
cout<<str;
return 0;
}
