华为2019/04/10春招实习生笔试题

前两题比较基础，第三题也不是很难，刚做完，记录一下，04/13更新第三题做法

————————————————————————————————

第一题:

输入的字符串超过8个字符的，按8个截一段，最后不足8个的补0到8个

最后将重新得到的字符串按升序排列

输入描述：输入一个数字N ，N个字符串 ，中间以空格隔开

输出描述：排序后的字符串

例：输入：2  abc 123456789    输出： 12345678 90000000 abc00000

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main() {
    int num;
    while (cin >> num)
    {
        //vector<string> str_array;
        vector<string> str_array_new;
        for (int i = 0; i < num; i++) {
            string str;
            cin >> str;
            //str_array.push_back(str);
            while (str.length() > 8)
            {
                string str_temp(str.begin(), str.begin() + 8);
                str_array_new.push_back(str_temp);
                str.erase(str.begin(),str.begin() + 8);
            }
            while (str.length() < 8)
            {
                str.push_back('0');
            }
            str_array_new.push_back(str); 
        }
        int length = str_array_new.size();
        for (int i = 0;  i < length; i++)
        {
            for (int j = i + 1 ; j < length; j++)
            {
                if (str_array_new[j][0] < str_array_new[i][0]) {
                    string temp = str_array_new[i];
                    str_array_new[i] = str_array_new[j];
                    str_array_new[j] = temp;
                }
            }
        }
        for (int i = 0; i < length; i++)
        {
            cout << str_array_new[i] << ' ';
        }
        cout << endl;
    }

    system("pause");
    return 0;
}

第二题：

题目描述：输入一个字符串，含有括号（大括号，小括号，中括号），数字和字母，数字（n）之后必跟一个括号（测试用例里的括号都是匹配的），代表括号内的字符串重复（n）次。括号里可以有嵌套，即括号里含有括号。现在将输入的字符串逆序展开；

输入描述：字符串，例:abc3(A)

输出描述：字符串，例：AAAcba

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace  std;

int have_kuohao(string str) {
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{')
        {
            return 1;
        }
        
    }
    return 0;
}
int main()
{
    string str;
    while (cin >> str)
    {
        //括号嵌套问题
        //没有括号直接输出
        if (have_kuohao(str) == 0)
        {
            reverse(str.begin(),str.end());
            cout << str << endl;
            continue;
        }
        else
        {
            //
            while (have_kuohao(str))
            {
                int left;
                int right;
                for (int i = 0; i < str.length(); i++)
                {
                    if (str[i] == '(' || str[i] == '[' || str[i] == '{')
                    {
                        left = i;
                    }
                    if (str[i] == ')' || str[i] == ']' || str[i] == '}')
                    {
                        right = i;
                        break;
                    }
                }
                //展开插入
                int times = (int)(str[left - 1] - '0');
                string temp_str(str.begin() + left + 1, str.begin() + right);
                //在右括号后插入
                int insert_end = right;
                for (int i = 0; i < times - 1; i++)
                {
                    for (int j = 0; j < temp_str.length(); j++)
                    {
                        str.insert(str.begin() + insert_end + 1, temp_str[j]);
                        //cout << str << endl;
                        insert_end ++;
                    }
                }
                //删除括号和数字
                str.erase(str.begin() + right);
                str.erase(str.begin() + left);
                str.erase(str.begin() + left - 1 );
            }
            reverse(str.begin(), str.end());
            //倒序输出
            cout << str <<endl;
        }
    }


    system("pause");
    return 0;
}

第三题：时间不够了，没写出来

题目描述：

输入一个N*M矩阵栅格，每个栅格都有一个高程值代表海拔高度，小明从出发点到终点有几条不同路径？每次只能往更高海拔的地方去，走过的地方不能再走，只能前后左右走。

例：输入：

5 4

0 1 0 0

0 2 3 3

0 3 0 0

0 4 5 6

0 7 6 0

0 1 4 1

第一行代表M*N，网格大小

后面是M*N的矩阵

最后一行前两个数字代表 起始坐标，后面两个数字代表 目的坐标（坐标从左上角（0，0）开始）。

输出 ：2

即两条不同路径

解法：

#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;


//建立一个结构体

struct grid {
    int high = 0;
    //flag为0代表未到达过
    int arived_flag = 0;
};
//深度优先遍历搜索函数
int DFT_result(vector<vector<grid>> map,int m,int n, int des_zuobiao[2]) {
    int result = 0;
    int M = map.size();
    int N = map[0].size();
    if (m == des_zuobiao[0] && n == des_zuobiao[1])
    {
        result++;
        return result;
    }
    else
    {
        //当前位置设置为已走过
        map[m][n].arived_flag = 1;
        //判断是否越界,上下左右邻接点
        if (m - 1 >= 0)
        {
            if (map[m - 1][n].arived_flag != 1 && map[m - 1][n].high > map[m][n].high)
            {
                result += DFT_result(map, m - 1, n, des_zuobiao);
            }
        }
        if (m + 1 <= M - 1)
        {
            if (map[m + 1][n].arived_flag != 1 && map[m + 1][n].high > map[m][n].high)
            {
                result += DFT_result(map, m + 1, n, des_zuobiao);
            }
        }
        if (n - 1 >= 0)
        {
            if (map[m][n - 1].arived_flag != 1 && map[m][n - 1].high > map[m][n].high)
            {
                result += DFT_result(map, m, n - 1, des_zuobiao);
            }
        }
        if (n + 1 <= N - 1)
        {
            if (map[m][n + 1].arived_flag != 1 && map[m][n + 1].high > map[m][n].high)
            {
                result += DFT_result(map, m, n + 1, des_zuobiao);
            }
        }
        
    }


    return result;
}
int main(){
    int map_M = 0;
    int map_N = 0;
    cin >> map_M;
    cin >> map_N;

    vector<vector<grid>> map;
    for (int i = 0; i < map_M; i++)
    {
        vector<grid> row;
        for (int j = 0; j < map_N; j++) {
            int high = 0;
            cin >> high;
            grid grid_temp{ high, 0 };
            row.push_back(grid_temp);
            //cin >> map[map_M][map_N];
        }
        map.push_back(row);
    }

    int pre_zuobiao[2];
    int des_zuobiao[2];
    cin >> pre_zuobiao[0];
    cin >> pre_zuobiao[1];
    cin >> des_zuobiao[0];
    cin >> des_zuobiao[1];

    int result = DFT_result(map, pre_zuobiao[0], pre_zuobiao[1], des_zuobiao);
    cout << result << endl;
    system("pause");
}