腾讯
# 1.生成格雷码
生成格雷码_牛客题霸_牛客网 (nowcoder.com) (opens new window)
先理解一下格雷码的定义吧，我拿n为3举例，当n为3时，我们生成的格雷码如下
[000, 001, 011, 010, 110, 111, 101, 100]
任意两个相邻位比如0和1，它们之间只有第三为不同，其他部分相同。
这题其实算是一个规律题吧。如果仔细观察格雷码的结构，我们会有以下发现：
1、除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。
2、最小的重复单元是 0 , 1。
所以，在实现的时候，我们完全可以利用递归，在每一层前面加上0或者1，然后就可以列出所有的格雷码。
public String[] getGray(int n) {
// n位数字它的格雷码长度就是2^n
String[] strings = new String[(int) Math.pow(2,n)];
// 当前n为1时我们返回01
if (n == 1) {
strings[0] = "0";
strings[1] = "1";
return strings;
} else {
// 获取每一位的格雷码
String[] result = getGray(n - 1);
// 遍历我们的result数组
for (int i = 0; i < result.length; i++) {
strings[i] = "0" + result[i];
strings[strings.length-1-i] = "1" + result[i];
}
}
return strings;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 2.构造回文
构造回文__牛客网 (nowcoder.com) (opens new window)
输入输出数据如下：
// 输入
abcda
google
// 输出
2
2
2
3
4
5
6
害，我是菜鸡，不会。。。
看了大佬的题解后，发现这题其实不难，因为回文串是正反顺序都一样，所以我们可以先对源字符串进行逆转，然后求原字符串和反转后的最大公共子序列（可以不连续，因为我们可以删除任意字符），找到最长公共子序列后，我们相减就可以得出最小的编辑长度了。代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 判断是否还有输入
while (sc.hasNext()){
// 原字符串
String s1 = sc.next();
// 反转后的字符串
String s2 = new StringBuffer(s1).reverse().toString();
// 使用dp数组来进行动态规划计算
int[][] dp = new int[s1.length()+1][s1.length()+1];
// 为了方便计算，我们从1开始（因为涉及到-1操作）
for (int i=1;i< dp.length;i++){
for (int j=1;j< dp.length;j++){
// 这个就是核心部分了
// 具体原理就是，当i和j这里两个位置的字符串相同的时候，我们的最长子序列就是上一个（i-1,j-1）的基础上+1
// 当不相同的时候，要么就是 i字符串-1 或者j字符串-1 时的最大子序列
dp[i][j] = s1.charAt(i-1)==s2.charAt(j-1)?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]);
}
}
// 这里我们可以直接用字符串长度减去我们的最大子序列
System.out.println(s1.length()-dp[dp.length-1][dp.length-1]);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 3.字符串移位
算法基础-字符移位__牛客网 (nowcoder.com) (opens new window)
// 输入
AkleBiCeilD
// 输出
kleieilABCD
2
3
4
。。。。这题目转了一圈下来，看到大家好像都或多或少的申请了空间。。看的我都有点懵逼了。。。
这题总感觉有争议，，，我这里就贴一个高赞用户的代码吧。。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
String str = scan.nextLine();
System.out.println(getResult(str));
}
}
public static String getResult(String str){
return str.replaceAll("[A-Z]","")+str.replaceAll("[a-z]","");
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# 4.有趣的数字
有趣的数字__牛客网 (nowcoder.com) (opens new window)
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
输入包含多组测试数据。 对于每组测试数据： N - 本组测试数据有n个数 a1,a2...an - 需要计算的数据 保证: 1<=N<=100000,0<=ai<=INT_MAX.
对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
// 输入
6
45 12 45 32 5 6
// 输出
1 2
2
3
4
5
6
这题不算难，我说一下主要思路吧，第一步我们就需要先进行排序，然后我们还需要使用map来统计每个数字出现的次数， 相差最大的好计算，直接最大值和最小值出现的次数相乘即可，相差最小的要分两个情况，如果出现重复的数组，那么相乘最小的就是 (n*(n-1))/2 n是出现的次数，如果不重复的话，我们就需要从相邻位置一个一个进行比较，直到找出最小的值。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
Arrays.sort(a);
//如果数组中的值全相同，直接两两组合
if(a[0] == a[n-1]){
int tmp = (n*(n-1))/2;
System.out.println(tmp + " " + tmp);
continue;
}
//map用来统计
Map<Integer, Integer> map = new TreeMap<>();
for(int i=0;i<n;i++){
if(map.containsKey(a[i])) {
map.put(a[i], map.get(a[i])+1);
} else {
map.put(a[i], 1);
}
}
//求差最小个数
int minres = 0;
if(map.size() == n){
// 如果map长度为n的话，说明没有重复的
// 我们只需要一个一个进行比对就可以了
int min = Math.abs(a[1]-a[0]);
// 向后进行遍历
for(int i=2;i<n;i++){
int tmp = Math.abs(a[i]-a[i-1]);
if(tmp == min) {
minres++;
} else if(tmp < min){
min = tmp;
minres = 1;
}
}
}else{
//
for(Integer key : map.keySet()){
int val = map.get(key);
if(val > 1){
minres += (val * (val-1))/2;
}
}
}
// 求差最大个数
int maxres = 0;
List<Integer> keyset = new ArrayList<>(map.keySet());
int val1 = map.get(keyset.get(0));
int val2 = map.get(keyset.get(keyset.size()-1));
// 为什这里是之间相乘呢，因为相乘最大的一定是最大的减去最小的，val1和val2就是两个值出现的次数，我们直接相乘即可
maxres = val1 * val2;
System.out.println(minres + " " + maxres);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 5.翻转数列
翻转数列_腾讯笔试题_牛客网 (nowcoder.com) (opens new window)
小Q定义了一种数列称为翻转数列: 给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4..., 每隔m个符号翻转一次, 最初符号为'-';。 例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8. 而n = 4, m = 1, 数列就是: -1, +2, -3, + 4. 小Q现在希望你能帮他算算前n项和为多少。
// 输入
8 2
// 输出
8
2
3
4
这题。。。找数学规律，太难了吧。。。
我们可以观察数列，可以把一组负正出现的数看成一组。所以n个数一共 n/(2m) 组，而每一组求和结果为m*m。于是得到前n项和的公式： Sn=n*m*m/(2m)=m*n/2
代码如下
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextInt();
long m = sc.nextInt();
System.out.println(n*m/2);
}
}
2
3
4
5
6
7
8
9
# 6.纸牌游戏
纸牌游戏_腾讯笔试题_牛客网 (nowcoder.com) (opens new window)
牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。 牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。 他们的得分等于他们抽到的纸牌数字总和。 现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。
输入
3
2 7 4
输出
5
2
3
4
5
这题我其实是想出来了的。。。其实非常简单，因为两个人都是最优策略，所以我们需要先对数组进行排序，然后是牛牛先抽，再是羊羊，他们只需要从大到小轮流抽就可以了
代码如下，我们使用了 Collections.reverseOrder() 方法
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
Integer[] data = new Integer[n];
for (int i=0;i<n;i++){
data[i] =sc.nextInt();
}
// 倒序排序
Arrays.sort(data,Collections.reverseOrder());
int sum =0,flag = 1;
for (int i=0;i<n;i++){
sum+=data[i]*flag;
flag=-flag;
}
System.out.println(sum);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 7.贪吃的小Q
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)
2
输入
3 7
输出
4
2
3
4
我以为这题有啥数学规律，然而并没有。。。只能一个一个算。。。
思路大致就是我们让结果从M到1依次计算，判断当前条件是否恰好满足条件，如果满足，那么就返回答案
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int day = scan.nextInt();
int number = scan.nextInt();
System.out.println(fun(number,day));
}
// 计算第一天吃m时，n天总共需要吃多少个
public static int count(int m,int n) {
int sum = 0;
for (int i=0;i<n;i++){
sum+=m;
m=(m+1)/2;
}
return sum;
}
// 计算结果
static int fun (int m,int n){
// 初始化low和high指针
int low=0,high=m;
// 当low大于high时退出循环
while (low<=high){
// 获取mid
int mid = (low+high)/2;
int tmp;
// 我们把mid放进去计算，如果刚好为m那么恰好满足条件，此时我们可以直接返回mid
if ((tmp = count(mid,n)) == m){
return mid;
} else if (tmp > m){
// 否则如果tmp大于m，说明计算的值太大了，我们需要缩小mid来满足条件
high = mid-1;
} else {
low = mid+1;
}
}
// 这里返回high，改成mid好像没用。。估计是要求最大的，所以我们直接返回high
return high;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 8.小Q的歌单
小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。
每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。
2
3
输入
5
2 3 3 3
输出
9
2
3
4
5
唉，又是一道不会的题。。。
这题需要使用动态规划来求解，这个是一个背包问题。。
import java.util.*;
public class Main{
public static final int ASD = 1000000007;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
// 数据输入
int k=sc.nextInt();
int a=sc.nextInt(), x=sc.nextInt();
int b=sc.nextInt(), y=sc.nextInt();
// 创建DP数组
int[] dp = new int[k+1];
dp[0] = 1;
// 因为长度为A的歌有X首
for(int i=0; i<x ; i++){
// j从k开始，不断计算，直到j小于a为止，这里我们计算出所有的解
for(int j=k; j>=a; j--){
dp[j] = (dp[j] + dp[j-a]) % ASD;
}
}
// 长度为B的歌有Y首
for(int i=0; i<y ; i++){
for(int j=k; j>=b; j--){
dp[j] = (dp[j] + dp[j-b]) % ASD;
}
}
System.out.println(dp[k]);
sc.close();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 9.安排机器
安排机器_腾讯笔试题_牛客网 (nowcoder.com) (opens new window)
小Q的公司最近接到m个任务, 第i个任务需要xi的时间去完成, 难度等级为yi。 小Q拥有n台机器, 每台机器最长工作时间zi, 机器等级wi。 对于一个任务,它只能交由一台机器来完成, 如果安排给它的机器的最长工作时间小于任务需要的时间, 则不能完成,如果完成这个任务将获得200 * xi + 3 * yi收益。
对于一台机器,它一天只能完成一个任务, 如果它的机器等级小于安排给它的任务难度等级, 则不能完成。
小Q想在今天尽可能的去完成任务, 即完成的任务数量最大。如果有多种安排方案,小Q还想找到收益最大的那个方案。小Q需要你来帮助他计算一下。
输入包括N + M + 1行,
输入的第一行为两个正整数n和m(1 <= n, m <= 100000), 表示机器的数量和任务的数量。
接下来n行,每行两个整数zi和wi(0 < zi < 1000, 0 <= wi <= 100), 表示每台机器的最大工作时间和机器等级。
接下来的m行,每行两个整数xi和yi(0 < xi < 1000, 0 <= yi<= 100), 表示每个任务需要的完成时间和任务的难度等级。
2
3
4
输入
1 2
100 3
100 2
100 1
输出
1 20006
2
3
4
5
6
7
这个是一道典型的贪心题，我们可以对机器和任务进行排序，然后每次尽量都用最小的机器来完成任务。所以我们就需要进行排序，这里我们需要自己重写排序方法，优先排时间，时间相同我们就排序难度。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static class Pair {
int time;
int diff;
public Pair(int time, int diff) {
this.time = time;
this.diff = diff;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
// 获取机器数和任务数
int machineNum = sc.nextInt();
int taskNum = sc.nextInt();
// 机器的工作时长和等级
Pair[] machines = new Pair[machineNum];
// 任务时长和等级
Pair[] tasks = new Pair[taskNum];
for (int i = 0; i < machineNum; i++) {
machines[i] = new Pair(sc.nextInt(), sc.nextInt());
}
for (int i = 0; i < taskNum; i++) {
tasks[i] = new Pair(sc.nextInt(), sc.nextInt());
}
// 重写比较逻辑
Comparator<Pair> cmp = (p1, p2) -> {
// 当时间相同的时候，我们比较难度
// 时间不相同我们则比较时间
if (p1.time == p2.time) {
return p2.diff - p1.diff;
} else {
return p2.time - p1.time;
}
};
// 然后我们分别对机器和任务进行排序
Arrays.sort(machines, cmp);
Arrays.sort(tasks, cmp);
System.out.println(machines);
long sum = 0;
int count = 0;
int j = 0;
int[] dp = new int[101];
// 因为我们需要尽可能的去完成任务，所以我们需要优先完成最简单的任务
for (int i = 0; i < taskNum; i++) {
// j表示机器的编号，我们确保机器可以完成任务(这里找出所有的机器)
while (j < machineNum && machines[j].time >= tasks[i].time) {
// 这里我们使用dp来统计每个难度的机器有多少台
dp[machines[j].diff]++;
j++;
}
// 因为要完成这个任务，我们就必须从当前任务的最低难度开始找
for (int k = tasks[i].diff; k < 101; k++) {
// 当当前难度不为0，说明有这台机器可以完成任务
if (dp[k] != 0) {
// 机器数-1
dp[k]--;
// sum表示总收益
sum += 200L * tasks[i].time + 3L * tasks[i].diff;
// count表示可以完成的任务数
count++;
break;
}
}
}
System.out.println(count + " " + sum);
}
sc.close();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# 10.画家小Q
画家小Q_腾讯笔试题_牛客网 (nowcoder.com) (opens new window)
画家小Q又开始他的艺术创作。小Q拿出了一块有NxM像素格的画板, 画板初始状态是空白的,用'X'表示。 小Q有他独特的绘画技巧,每次小Q会选择一条斜线, 如果斜线的方向形如'/',即斜率为1,小Q会选择这条斜线中的一段格子,都涂画为蓝色,用'B'表示;如果对角线的方向形如'',即斜率为-1,小Q会选择这条斜线中的一段格子,都涂画为黄色,用'Y'表示。 如果一个格子既被蓝色涂画过又被黄色涂画过,那么这个格子就会变成绿色,用'G'表示。 小Q已经有想画出的作品的样子, 请你帮他计算一下他最少需要多少次操作完成这幅画。
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数N和M(1 <= N, M <= 50), 表示画板的长宽。
接下来的N行包含N个长度为M的字符串, 其中包含字符'B','Y','G','X',分别表示蓝色,黄色,绿色,空白。整个表示小Q要完成的作品。
2
3
4 4
YXXB
XYGX
XBYY
BXXY
输出
3
说明
XXXX
XXXX
XXXX
XXXX
->
YXXX
XYXX
XXYX
XXXY
->
YXXB
XYBX
XBYX
BXXY
->
YXXB
XYGX
XBYY
BXXY
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String tem = scanner.nextLine();
int n = Integer.parseInt(tem.split(" ")[0]);
int m = Integer.parseInt(tem.split(" ")[1]);
// 使用color来存储信息
char[][] color = new char[n][m];
for (int i = 0; i < n; i++) {
tem = scanner.nextLine();
for (int j = 0; j < tem.length(); j++) {
color[i][j] = tem.charAt(j);
}
}
// 获取最小步数
getMinStep(n, m, color);
scanner.close();
}
/**
* 获取最小步数 每画一个线直到颜色不同为止
* @param n
* @param m
* @param color
*/
private static void getMinStep(int n, int m, char color[][]) {
int step = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (color[i][j] == 'Y') {
dfs_y(i, j, n, m, color); // 画y
step++;
} else if (color[i][j] == 'B') {
dfs_b(i, j, n, m, color); // 画B
step++;
} else if (color[i][j] == 'G') {
dfs_y(i, j, n, m, color); // 先画y
step++;
dfs_b(i, j, n, m, color); // 在画B
step++;
}
}
}
System.out.println(step);
}
/**
* 当前位置画y,是否在后续位置继续画y
*
* @param x
* @param y
*/
private static void dfs_y(int x, int y, int n, int m, char color[][]) {
// 根据要求决定当前位置是否能画y
if (x >= 0 && x < n && y >= 0 && y < m && (color[x][y] == 'Y' || color[x][y] == 'G')) {
if (color[x][y] == 'G') {
color[x][y] = 'B'; // 如果当前位置要求画的是G,那么画了Y之后下一次只能画B
} else {
color[x][y] = 'X'; // 如果当前位置要求画的是Y,那么画了Y之后下一次不需要再画
}
// 是否连笔继续画，Y对应的是画\，即左上或者右下
dfs_y(x - 1, y - 1, n, m, color);
dfs_y(x + 1, y + 1, n, m, color);
}
}
/**
* 当前位置画B,是否在后续位置继续画B
*
* @param x
* @param y
*/
private static void dfs_b(int x, int y, int n, int m, char color[][]) {
// 根据要求决定当前位置是否能画B
if (x >= 0 && x < n && y >= 0 && y < m && (color[x][y] == 'B' || color[x][y] == 'G')) {
if (color[x][y] == 'G') {
color[x][y] = 'Y'; // 如果当前位置要求画的是G,那么画了Y之后下一次只能画Y
} else {
color[x][y] = 'X'; // 如果当前位置要求画的是B,那么画了B之后下一次不需要再画
}
// 是否连笔继续画，B对应的是画/，即左下或者右上
dfs_b(x + 1, y - 1, n, m, color);
dfs_b(x - 1, y + 1, n, m, color);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87