牛客网算法一

发表于

最近几天一直在牛客网上进行算法试题测试，在博客做下简单的记录。

原题地址

侵权删

题一：黑白卡片题

题目简介：

牛牛有n张卡片排成一个序列.每张卡片一面是黑色的,另一面是白色的。初始状态的时候有些卡片是黑色朝上,有些卡片是白色朝上。牛牛现在想要把一些卡片翻过来,得到一种交替排列的形式,即每对相邻卡片的颜色都是不一样的。牛牛想知道最少需要翻转多少张卡片可以变成交替排列的形式。

输入描述:
1
输入包括一个字符串S,字符串长度length(3 ≤ length ≤ 50),其中只包含'W'和'B'两种字符串,分别表示白色和黑色。整个字符串表示卡片序列的初始状态。
输出描述:
1
输出一个整数,表示牛牛最多需要翻转的次数

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class wb {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String line = input.next();
            int b = 0, w = 0;//w为WBWBWB序列需要翻次数，b为BWBWBWB序列需要翻次数
            for (int i = 0, len = line.length(); i < len; i++) {
                char c = line.charAt(i);
                //判断位置
                //奇数位置
                if ((i & 1) == 0) {
                    if (c == 'W') b++;
                    else w++;
                } else {
                    if (c == 'B') b++;
                    else w++;
                }
            }
            System.out.println(Math.min(b, w));
        }
    }
}

代码说明:

代码中的 i&1 用来判断 i 奇偶，基本就是遍历所有的元素。因为整个排序片段只有 2 种情况，所有只需要获取 2 种情况下所得结果再进行比较得到最小值，就是最终结果。

题目二：黑化的牛牛

题目简介：

牛牛变得黑化了,想要摧毁掉地球。但他忘记了开启地球毁灭器的密码。牛牛手里有一个字符串S,牛牛还记得从S中去掉一个字符就恰好是正确的密码,请你帮牛牛求出他最多需要尝试多少次密码。

如样例所示S = “ABA”,3个可能的密码是”BA”, “AA”, “AB”.

当S = “A”, 牛牛唯一可以尝试的密码是一个空的密码,所以输出1.

输入描述:
1
输入包括一个字符串S,字符串长度length(1 ≤ length ≤ 50),其中都是从'A'到'Z'的大写字母。
输出描述:
1
输出一个整数,表示牛牛最多需要尝试的密码次数。

代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.HashSet;
import java.util.Scanner;
public class Niuniuaaba {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            //方法一：
//            String s = input.next();
//            if (s.length() == 0) {
//                return;
//            } else if (s.length() == 1) {
//                System.out.print(s.length() + "");
//            } else {
//                char[] chas = s.toCharArray();
//                int re = 0;
//                for (int i = 1; i < chas.length; i++) {
//                    if (chas[i - 1] == chas[i]) {
//                        re++;
//                    }
//                }
//                System.out.print(chas.length - re + "");
//            }
            //方法二
            String s2 = input.next();
            if (s2.length() == 0) {
                return;
            } else if (s2.length() == 1) {
                System.out.print(s2.length() + "");
            } else {
                StringBuffer s3 = new StringBuffer(s2);
                HashSet<String> hashSet = new HashSet<>();
                for (int i = 0; i < s2.length(); i++) {
                    s3.deleteCharAt(i);
                    boolean add = hashSet.add(s3.toString());
                    s3.insert(i, s2.charAt(i));
                }
                System.out.print(hashSet.size() + "");
            }
        }
    }
}

代码说明:

本代码未做字符串‘A-Z’的判断;

方法一：这里根据只要遇到 2 个相同元素,就只有可能会出现一个秘密组, re(代码重复秘密组)就 +1 ,而如果没有重复组，最多尝试的秘密组其实就是依次去掉字符串中的每个个元素所得,即 chas.lenth ,所以最终解为 chas.length - re.

方法二：这里根据了 java Hashset 的定义去运算. HashSet 中不能添加同一个元素，所以,遍历所以字符串,依次去掉一个字符串组成新字符串加入 hashSet 中，最终 hashSet 的长度就为答案.

题目三：膨胀的牛牛

题目简介：

牛牛以草料为食。牛牛有一天依次遇到n堆被施展了魔法的草料,牛牛只要遇到一堆跟他当前相同大小的草料,它就会把草料吃完,而使自己的大小膨胀一倍。一开始牛牛的大小的是A,然后给出牛牛依次遇到的n堆草料的大小。请计算牛牛最后的大小。

输入描述:
1
2
输入包括两行,第一行包含两个整数n和A(1 ≤ n ≤ 200, 1 ≤ A ≤ 1,000,000,000)
第二行包括n个整数,表示牛牛依次遇到的草料堆大小a_i(1 ≤ a_i ≤ 1,000,000,000)
输出描述:
1
输出一个整数,表示牛牛最后的大小。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();//所有整数
        int a = input.nextInt();//牛牛初始大小
        int[] a_i=new int[num];
        for(int i = 0;i < num; i++){
            a_i[i] = input.nextInt();
        }
        
        for(int j=0 ;j<num;j++){
            if(a==a_i[j]){
                a*=2;
            }
        }
        
        System.out.print(a);
    }
}

题目四：序列交换

题目简介：

牛牛有一个长度为n的整数序列s,羊羊要在牛牛的序列中选择不同的两个位置,然后交换这两个位置上的元素。现在需要求出羊羊交换后可以得到的不同的序列个数。(注意被交换的两元素值可能相同)。

如序列{1, 47},输出1.羊羊必须交换仅有的两个元素,得到序列{47, 1}。羊羊必须交换,不能保留原有的序列。

{1, 2, 1},输出3.羊羊通过交换可以得到{2, 1, 1},{1, 1, 2},{1, 2, 1}这三个序列。

输入描述:
1
2
输入包括两行,第一行为一个整数n(2 ≤ n ≤ 50),即序列的长度。
第二行n个整数,表示序列的每个元素a_i(1 ≤ a_i ≤ 50),以空格分割。
输出描述:
1
输出一个整数,表示羊羊可以得到的不同的序列个数

代码说明：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = 0;//输入总数
        int sum = 0;
        int i, j;
        boolean hasSame = false;//相同判断
        num = sc.nextInt();
        int[] test = new int[num];
        for (i = 0; i < num; i++) {
            test[i] = sc.nextInt();
        }
        if (num == 2) {
            System.out.print(1 + "");
            return;
        }
        for (i = 0; i < num; i++) {
            for (j = i + 1; j < num; j++) {
                if (test[i] != test[j]) {
                    sum++;
                } else {
                    hasSame = true;
                }
            }
        }
        if (hasSame) {
            System.out.print(sum + 1 + "");
        } else {
            System.out.print(sum + "");
        }
    }
}

代码说明:

根据交换条件，只要交换的 2 个数字不一样，交换出来的数组肯定为新的一列数组,因此sum在这种情况下每次 +1,而当有 2 个数字一样的时候，在最后结果需要再 +1,因为相同的数字在同等的情况下只允许出现同一个情况,所以不管有多少组重复数字，都只需要最终 +1.当然,这里也可以运用 HashSet 的方式来解决,跟问题二中描述类似.

问题五：丑陋的字符串

问题简介：

牛牛喜欢字符串,但是他讨厌丑陋的字符串。对于牛牛来说,一个字符串的丑陋值是字符串中相同连续字符对的个数。比如字符串“ABABAABBB”的丑陋值是3,因为有一对”AA”和两对重叠的”BB”。现在给出一个字符串,字符串中包含字符’A’、’B’和’?’。牛牛现在可以把字符串中的问号改为’A’或者’B’。牛牛现在想让字符串的丑陋值最小,希望你能帮帮他。

输入描述:
1
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包含'A','B','?'三种字符。
输出描述:
1
输出一个整数,表示最小的丑陋值

代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] chars;
        while (sc.hasNext()) {
            String s = sc.next();
            int count = 0;
            if (s.length() == 1) {
                System.out.print(0 + "");
                return;
            } else {
                //去除最前面的所有？
                int j = 0;
                while (j != s.length() && s.charAt(j) == '?') {
                    j++;
                }
                if (j == s.length()) {
                    System.out.print(0 + "");
                } else {
                    s = s.substring(j, s.length());
                    chars = s.toCharArray();
                    for (int i = 1; i < chars.length; i++) {
                        if ('?' == chars[i]) {
                            if (chars[i - 1] == 'A') {
                                chars[i] = 'B';
                            } else {
                                chars[i] = 'A';
                            }
                        } else {
                            if (chars[i - 1] == chars[i]) {
                                count++;
                            }
                        }
                    }
                    System.out.print(count + "");
                }
            }
        }
    }
}

代码说明：

因为只需要判断连续 2 位字符串是否相同，就可以判断到底有多少组丑陋值,按照顺时针方向,首先去除在开头所有的 ?,在依次判断接下来的字符串中是否包有 ?,有就把 ? 改成跟前一个字符不同的字符,再循环判断,最终可以得到所以的丑陋值 count.

题目六：庆祝 61

题目简介：

牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。

如样例所示:

当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解

输入描述:
1
2
输入包括两行,第一行为一个正整数n(3 ≤ n ≤ 20)
第二行为n个整数h_i(80 ≤ h_i ≤ 140),表示每个小朋友的身高。
输出描述:
1
输出一个整数,表示满足条件下的相邻小朋友身高差的最大值。

代码：

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
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] m = new int[n];
        for (int i = 0; i < n; i++) {
            m[i] = sc.nextInt();
        }
        Arrays.sort(m);
        int max = Math.max(m[1] - m[0], m[n - 1] - m[n - 2]);
        for (int j = 0; j < n - 2; j++) {
            max = Math.max(m[j + 2] - m[j], max);
        }
        System.out.print(max);
    }
}

代码说明：

首先该想到序号间隔越小差值也越小. 所以应该按顺序左右插入,这样形成一种金子塔型, 这样序号差值最大就只有2了,如有 1,2,3,4,5,6.7.应该排成7,5,3,1,2,4,6或1,3,5,7,6,4,2.(不是自己的思路，看到一个大神的思路,侵权删)

先排序，把所以的数字根据升降排序列好,根据金字塔型,最顶端数字为最大数或者最小数，左侧一列为与顶端数字位置相差为2的数字(m[j+2])，右侧则为相差1的数字(m[j+1]),而算出最大身高差,可以看出,只需要计算金字塔左侧和右侧每个相邻数字之差中的最大值就可以获得.

说明：上面所有代码段本人都亲自敲过，并且在牛客网都可以通过。