百度秋招笔试三道编程题（2021-09-07)

逃离我推掉我的手 2022-09-10 11:28 216阅读 0赞

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

【2021-09-04】美团秋招笔试五道编程题（附题目）  
【2021-09-03】贝壳秋招笔试四道编程题（前三道ac）  
【2021-09-01】阿里巴巴秋招笔试两道编程题  
【2021-09-01】华为秋招机试三道编程题（附题目，后两题AC）  
【2021-08-29】美团秋招笔试四道编程题  
【2021-08-29】字节跳动秋招笔试四道编程题  
【2021-08-26】腾讯音乐秋招笔试编程三道题  
【2021-08-25】华为秋招机试三道编程题  
【2021-08-23】阿里巴巴秋招笔试两道编程题  
【2021-08-22】腾讯秋招笔试五道编程题  
【2021-08-22】美团秋招笔试五道编程题（待更新）  
【2021-08-21】网易秋招机试四道编程题（待更新）  
【2021-08-14】荣耀秋招机试三道编程题（已更新）  
【2021-08-18】华为秋招机试三道编程题（已更新）  
【2021-08-18】阿里秋招笔试两道编程题  
【2021-08-15】美团秋招笔试五道编程题（已更新）  
【2021-08-12】携程秋招笔试三道编程题  
【2021-08-11】华为秋招机试三道编程题(已更新)  
【2021-08-09】阿里巴巴秋招笔试两道编程题  
【2021-08-08】拼多多秋招笔试四道编程题  
【2021-08-08】美团秋招笔试五道编程题  
【2021-08-08】好未来秋招三道编程题  
【2021-08-07】网易互娱秋招笔试三道编程题  
【2021-08-04】华为秋招两道编程题

### 文章目录 ###

*  第一道：像素图扩大
 *   *  题目描述
     *  参考代码
 *  第二道：完美数（100%）
 *   *  题目描述
     *  参考代码：
 *  第三道：子序列（100%）
 *   *  题目描述
     *  参考代码

# 第一道：像素图扩大 #

## 题目描述 ##

把一个由0和1构成的正方形矩阵扩成原先的k倍，比如【1】会扩成两行两列的【1】矩阵。

思路就是扩大后的数组下标除以扩大倍数K填充扩大后的矩阵元素，构成新的矩阵。

## 参考代码 ##

import java.util.Scanner;
    
    public class Main { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            int K = in.nextInt();
    
            int[][] dp = new int[N][N];
            for (int i = 0; i < N; i++) { 
                for (int j = 0; j < N; j++) { 
                    dp[i][j] = in.nextInt();
                }
            }
    
            for (int i = 0; i < N * K; i++) { 
                for (int j = 0; j < N * K; j++) { 
                    int x = i / K;
                    int y = j / K;
                    System.out.print(dp[x][y] + " ");
                }
                System.out.println();
            }
        }
    }

# 第二道：完美数（100%） #

## 题目描述 ##

对于一个十进制正整数x，如果x的每一位数字只可能是1，2，3中的其中一个，则称x是完美数。如:123，1，3321 都是完美数，而5,1234则不是。

牛牛想写一个函数f(n)，使得其返回最大的不大于n的完美数，请你帮助牛牛实现这个函数。

**输入描述**  
第一行一个正整数T表示单组测试数据的组数。接下来T行每行一个正整数n。  
1<T≤10^5  
1<n≤10^18

4
    213
    3244
    22
    100

**输出描述**  
对于每组输入的n，输出f(n)的值。

213
    3233
    22
    33
    
    解释:
    f(213)=213
    f(3244)=3233
    f(22)=22
    f(100)=33

## 参考代码： ##

import java.util.Scanner;
    
    public class Main { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            int n = Integer.parseInt(in.nextLine());
            for (int i = 0; i < n; i++) { 
                String str = in.nextLine();
                int[] nums = new int[str.length()];
                for (int k = 0; k < str.length(); k++) { 
                    nums[k] = str.charAt(k) - '0';
                }
                boolean flag = false;
                for (int k = 0; k < nums.length; k++) { 
                    if (flag) { 
                        nums[k] = 3;
                    } else if (nums[k] >= 1 && nums[k] <= 3) { 
                        continue;
                    } else if (nums[k] > 3) { 
                        flag = true;
                        nums[k] = 3;
                    } else { 
                        if (!flag) { 
                            int temp = k - 1;
                            while (temp != 0 && nums[temp] == 1) { 
                                temp--;
                            }
                            nums[temp]--;
                            temp++;
                            for (; temp < k; temp++) { 
                                nums[temp] = 3;
                            }
                            flag = true;
                        }
                        nums[k] = 3;
                    }
                }
    
                int idx = 0;
                for (; idx < nums.length; idx++) { 
                    if (nums[idx] != 0) { 
                        break;
                    }
                }
                StringBuilder sbuilder = new StringBuilder();
                for (; idx < nums.length; idx++) { 
                    sbuilder .append(nums[idx]);
                }
                System.out.println(sbuilder );
            }
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：子序列（100%） #

## 题目描述 ##

在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列，如对于字符串"abc"，“ab” 和 "ac” 都是其子序列，而"cb"和"ca"不是。

牛牛有一个长度为n的仅由小写字母组成的字符串s，牛牛想知道 s有多少子序列恰好包含k种字母?

**输入描述**  
第一行输入两个正整数n和k。  
第二行输入一个长度为n的仅包含小写字母的字符串s。(1≤n<105,1<k≤26)

6 5
    eecbad

**输出描述**  
由于答案可能会很大，因此你只需要输出子序列个数对10°主7取模的结果即可。

**解释**  
显然有两个子序列"ecbad"满足要求，同时s自己也满足要求，因此答案为3

## 参考代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1e5 + 5;
    long long dp[26];
    const long long mod = 1e9 + 7;
    char s[N];
    long long qpow(long long a, long long b)
    { 
        long long res = 1;
        while (b)
        { 
            if (b & 1)
            { 
                res = res * a % mod;
            }
            b /= 2;
            a = a * a % mod;
        }
        return res;
    }
    int v[30],w[30];
    int main()
    { 
        int n, k;
        scanf("%d%d", &n, &k);
        scanf("%s", s + 1);
        map<char, int> mp;
        for (int i = 1; i <= n; i++)
            mp[s[i]]++;
        for (char i = 'a'; i <= 'z'; i++)
        { 
            v[i - 'a'] = qpow(2, mp[i]) - 1;
            w[i - 'a'] = 1;
        }
        dp[0] = 1;
        for (int i = 0; i < 26; i++)
        { 
            for (int j = k; j >= 1; j--)
            { 
                if (j >= w[i])
                { 
                    dp[j] = (dp[j] + dp[j - w[i]] * v[i]) % mod;
                }
            }
        }
    
        cout << dp[k] << endl;
        return 0;
    }
    /** 作者：nuoyanli 链接：https://www.nowcoder.com/discuss/735052?type=post&order=create&pos=&page=0&ncTraceId=&channel=-1&source_id=search_post_nctrack 来源：牛客网 **/

> 关注TechGuide，大厂笔经面经闪电速递！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/cdda75214f0a4a089132b044d29b3e6c.png