奇安信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;
}