4.10字节跳动2022春招研发笔试第6场-后端方向题目

文章目录

• 编译环境
• 一、涨潮
• • 1.题目
  • 2.输入输出说明
  • 3.题解
• 二、跳格子
• • 1.题目
  • 2.输入输出说明
  • 3.题解
• 三、装网球
• • 1.题目
  • 2.输入输出说明
  • 3.题解
• 四、集卡片
• • 1.题目
  • 2.输入输出说明
  • 3.题解
• 总结
• 参考链接

---

编译环境

1.gcc 8.1.0
2.Visual Studio Code 1.63.2

---

一、涨潮 1.题目

给一个矩形海滩，元素为0代表海洋，元素为1代表陆地，矩阵外都是陆地，陆地只和上下左右四个方向相邻，和两块海洋相邻的陆地在下一轮会被淹没，求下一轮矩阵中陆地和海洋的情况。

2.输入输出说明

第一行输入t，表示有t块矩形沙滩。

第二行输入m和n，表示沙滩的行数和列数
接下来m行字符串，表示沙滩每行中0和1的情况

输出为m行字符串，表示下一轮矩阵每行的0和1情况

输入样例:
1
4 4
1011
0000
0000
0000
输出样例：
0001
0000
0000
0000

3.题解

#include 
#include 
#include 
using namespace std;
//广度优先搜索
vector<int> direction{-1,0,1,0,-1};
void bfs(vector<vector<char>>& beach){
    int m = beach.size();
    int n = beach[0].size();
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(beach[i][j] == '1'){
                int count = 0;
                for(int k = 0; k < 4; k++){
                    int x = i + direction[k];
                    int y = j + direction[k + 1];
                    if(x >= 0 && x < m && y >= 0 && y < n && beach[x][y] == '0'){
                        count++;
                    }
                }
                if(count >= 2){
                    beach[i][j] = '2';
                }
            }
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(beach[i][j] == '2'){
                beach[i][j] = '0';
            }
        }
    }
}

int main(){
    int t;
    cin >> t;
    while(t-- > 0){
        int m,n;
        cin >> m >> n;
        vector<vector<char>> beach(m, vector<char>(n,'0'));
        string s;
        int i = 0;
        //处理输入
        while(m-- > 0){
            cin >> s;
            for(int j = 0; j < n; j++){
                beach[i][j] = s[j];
            }
            i++;
        }
        //处理沙滩矩阵
        bfs(beach);
        //处理输出
        for(size_t i = 0; i < beach.size(); i++){
            for(size_t j = 0; j < beach[0].size(); j++){
                s[j] = beach[i][j];
            }
            cout << s << endl;
        }
    }
    return 0;
}

二、跳格子 1.题目

有n个格子，最初位于第一个格子，格子中的能量值代表你能在该位置跳跃到的最远距离，判断能否跳跃到最后一个格子。

力扣原题：https://leetcode-cn.com/problems/jump-game/

2.输入输出说明

第一行输入n表示格子的个数，第二行输入为n个格子的能量值，输出TRUE或FALSE

输入样例1：
5
2 3 1 1 4
输出样例1：
TRUE

输入样例2：
5
3 2 1 0 4
输出样例2：
FALSE

3.题解

#include 
#include 
#include 
using namespace std;
//贪心算法
//保存当前位置能跳到的最大距离
bool canJump(vector<int>& energy, int size){
    int MaxDistance = 0;
    for(int i = 0; i < size; i++){
        if(i > MaxDistance){
            return false;
        }
        MaxDistance = max(MaxDistance, i + energy[i]);
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    vector<int> energy(n,0);
    for(int i = 0; i < n; i++){
        cin >> energy[i];
    }
    if(canJump(energy, n)){
        cout << "TRUE" << endl;
    }else{
        cout << "FALSE" << endl;
    }
    return 0;
}

三、装网球 1.题目

把编号为1-k的网球顺序任意放到n个球筒中，球筒可以从两侧装入球，给出n个球筒中的球的情况，求是否按照编号正确装入。

2.输入输出说明

第一行输入t，表示判断t次
第二行输入n，表示有n个球筒
接下来n行，每行的第一个数字m，表示这个球筒中含有的球数，剩下m个数字表示球的编号。

输出为t个数字，1表示正确装入，0表示错误。

输入样例：
2
2
3 2 1 3
2 4 5
2
5 6 2 1 4 8
4 3 9 5 7
输出样例：
1
0

3.题解

#include 
#include 
using namespace std;
//因为按编号顺序从球筒两侧放入球，
//所以球筒中的球号有三种可能：
//1.球号递减
//2.球号递增
//3.球号先递减后递增
//算法中模拟先递减后递增，不满足条件则装入错误。

bool IsPutCorrect(vector<vector<int>>& bucket){
    int n = bucket.size();
    for(int i = 0; i < n; i++){
        int j = 1;
        int m = bucket[i].size();
        while(j < m && bucket[i][j] < bucket[i][j - 1]){
            j++;
        }
        while(j < m && bucket[i][j] > bucket[i][j -  1]){
            j++;
        }
        if(j < m){
            return false;
        }
    }
    return true;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n;
        vector<vector<int>> bucket(n);
        for(int i = 0; i < n; i++){
            cin >> m;
            vector<int> temp(m,0);
            for(int j = 0; j < m; j++){
                cin >> temp[j];
            }
            bucket.push_back(temp);
        }
        cout << IsPutCorrect(bucket) << endl;
    }
    return 0;
}

四、集卡片 1.题目

有10张数字为0-9的数字卡片，每个卡包有三张数字卡，求最少购买几个卡包能够集齐0-9所有卡片？能集齐的话输出最少购买的卡包数量，否则输出-1。

2.输入输出说明

输入为字符串，输出为一个数字，表示最少购买卡包数量。

输入样例：000 111 222 456 678 891
输出样例：5

3.题解

#include 
#include 
#include 
#include 
using namespace std;
//状压dp
#define INF 0x3f3f3f3f
int main()
{
    string s;
    getline(cin, s);
    int status[200] = {0};
    int statu = 0, cnt = 0;
    int dp[1024];
    memset(dp,INF,sizeof(dp));
    dp[0] = 0;
    for (size_t i = 0; i < s.size(); i++)
    {
        //遍历字符串，将每个卡包的状态记录下来
        if (s[i] == ' ')
        {
            status[cnt++] = statu;
            statu = 0;
            continue;
        }
        statu |= (1 << (s[i] - '0'));
        //注意是与运算，数字相同的话只记录一个数字
    }
    status[cnt++] = statu;
    for (int i = 0; i < cnt; i++)
    {
        //当目前只有前i个卡包时合成1-1023这些状态最少需要几个卡包
        for (int j = 1; j < 1024; j++)
        {
            dp[j] = min(dp[j & (1023 ^ status[i])] + 1, dp[j]);
            //异或后再与的功能是
            //当能通过当前卡包直接组成j状态时dp[j]=1,
            //当不能直接组成j状态时寻找缺失的状态,
            //若缺失的状态存在，就在其需要的最少卡包上加1，并和当前能组成状态j的情况取最小值
            //否则是INF
        }
    }
    if (dp[1023] == INF)
    {
        //如果1023这个状态无法合成，就返回-1
        cout << -1 << endl;
    }
    else
    {
        //否则返回合成1023这个状态所需的最小卡包数
        cout << dp[1023] << endl;
    }
    return 0;
}

总结

第1题 广度优先搜索
第2题 贪心算法
第3题 找波峰
第4题 状态压缩动态规划

参考链接

1.https://leetcode-cn.com/circle/discuss/lR2rwk/
2.https://www.nowcoder.com/discuss/927679?type=post&order=recall&pos=&page=2&ncTraceId=&channel=-1&source_id=search_post_nctrack&gio_id=95B914AE287CCE11DA0CE0F1BCDF4C2B-1649902122833
3.https://www.bilibili.com/video/BV1Z4411x7Kw?spm_id_from=333.337.search-card.all.click
4.https://www.luogu.com.cn/problem/P1896