注意

  该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。

  为了节省篇幅，在不影响阅读的前提下，代码中将省略import语句；同时，也不再给出输入和输出样例；过于简单的题也不再文字说明解题思路。

输出字符对应 ASCII 码

  输入一个字符，输出其前一个字符和后一个字符，以及这个字符对应的ASCII码值。

输入格式

  在一行中给出一个字符。

输出格式

  在一行中输出前一个字符、后一个字符，以及这个字符对应的 ASCII 码值，用一个空格分隔。

题解

1
2
3
4
5
6
7
8
public class Main {

    public static void main(String[] args) throws IOException {
        int ch = System.in.read();
        System.out.printf("%d %d %d", ch - 1, ch + 1, ch);
    }

}

嵌套循环格式输出

  输入一个 n（n >= 1），输出形如以下格式的图形，每个数字后面空3格。

1
2
3
4
5
6
0   
0   1   
0   1   2   
0   1   2   3   
.......
0   1   2   .....  n-1

输入格式

  输入一个整数 n。

输出格式

  输出如下格式数据：

1
2
3
4
5
6
0   
0   1   
0   1   2   
0   1   2   3   
.......
0   1   2   .....  n-1

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int line = 0; line != n; ++line) {
            for (int i = 0; i <= line; ++i) {
                System.out.printf("%d   ", i);
            }
            System.out.println();
        }
    }

}

找大写字母

  本题目要求输入一个字符串，然后输出这个字符串中大写字母的个数。

输入格式

  在一行中输入一个字符串。字符串长度不超过 80。

输出格式

  第一行按输入顺序输出这个字符串中所有大写字母。

  第二行输出这些小写字母的个数。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {

    public static void main(String[] args) throws IOException {
        int value;
        int ans = 0;
        while ((value = System.in.read()) != -1 && value != '\n') {
            if (Character.isUpperCase(value)) {
                ++ans;
                System.out.print((char) value);
            }
        }
        if (ans != 0) System.out.printf("\n%d", ans);
    }

}

有趣的三位数

  数字中有很多有趣的三位数，像，大家熟知的水仙花数，其各位数字的立方和等于该数本身。拿153来说，我们有：153 = 13+ 53+ 33。

  本题在上述的表达式上做一些变化，求三位数 ABC 使得 ABC = A1+ B2+ C3。

  本题要求编写程序，输出给定正整数M和N区间内的所有三位数ABC使得 ABC = A1+ B2+ C3。

输入格式

  输入在一行中给出两个正整数 M 和 N（100 <= M <= N <= 999）。

输出格式

  顺序输出 M 和 N 区间内所有符合要求的三位数，每一行输出一个数。若该区间内没有符合要求的三位数，则输出“Not Found”。

题解

  直接打表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] all = {135, 175, 518, 598};
        int m = scanner.nextInt(), n = scanner.nextInt();
        int start = 0, end = 0;
        for (int i = 0; i != all.length; ++i) {
            if (all[i] <= m) start = i;
            if (all[i] <= n) end = i;
        }
        if (end - start == 0) System.out.println("Not Found");
        else {
            for (int i = start; i <= end; ++i) {
                System.out.println(all[i]);
            }
        }
    }

}

计算钱币

  编写程序，读取用户输入的代表总金额的 double 值，打印表示该金额所需的最少纸币张数和硬币个数，打印从最大金额开始。纸币的种类有十元、五元、一元，硬币的种类有五角、一角、贰分、壹分。

  注意：即使不需要某一种类的纸币或硬币，也要打印出来。

题解

  贪心即可，注意如何输入数据即可。

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
public class Main {

    public static void main(String[] args) throws IOException {
        int left = 0, dime = 0, penny = 0;
        boolean end = false;
        // 读取整数部分
        int ch = System.in.read();
        while (Character.isDigit(ch)) {
            left = (left << 1) + (left << 3) + (ch ^ 48);
            ch = System.in.read();
            if (ch == -1 || ch == '\n') end = true;
        }
        if (!end) { // 如果读取时没有遇到结尾，则尝试读取“角”
            ch = System.in.read();
            if (Character.isDigit(ch)) dime = ch - '0';
            else end = true;
        }
        if (!end) { // 如果读取角时没有遇到结尾，则尝试读取“分”
            ch = System.in.read();
            if (Character.isDigit(ch)) penny = ch - '0';
        }
        Integer[] ans = {
                left / 10,
                (left % 10) / 5,
                left % 10 % 5,
                dime / 5,
                dime % 5,
                penny >> 1,
                penny & 1
        };
        System.out.printf("%d 张十元\n%d 张五元\n%d 张一元\n%d 个五角\n%d 个一角\n%d 个贰分\n%d 个壹分", (Object[]) ans);
    }

}

数组元素移动

  完成数组元素的移动功能：假设数组有 n 个元素，输入一个数x，把数组的第 x 个位置的元素先保存起来，然后把 x + 1 到 n 的元素，依次往前移一位，最后将原来的第 x 个位置的元素放在数组的最后。

  重复若干次这样的移动，得到最后的结果。

输入格式

  第一行包括一个整数n（1<=n<=100），表示数组元素的个数。

  第二行输入n个数组元素，均为整数，用空格隔开。

  第三行输入一个数k（1<=k<=100），表示要进行k次移动。

  接下来k行，每行一个数x，表示要移动第x个元素。

输出格式

  输出经过 k 次移动后的数组，每两个元素之间用空格隔开。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<String> list = new ArrayList<>(n);
        for (int i = 0; i != n; ++i) list.add(scanner.next());
        int k = scanner.nextInt();
        for (int i = 0; i != k; ++i) {
            int index = scanner.nextInt() - 1;
            String tmp = list.remove(index);
            list.add(tmp);
        }
        System.out.println(String.join(" ", list));
    }

}

计算矩阵两个对角线之和

  计算一个 n × n 矩阵两个对角线之和。

输入格式

  第一行输入一个整数 n（0 < n <= 10），第二行至第 n + 1 行，每行输入 n 个整数，每行第一个数前没有空格，每行的每个数之间各有一个空格。

输出格式

  输出sum = ?，其中问号表示对角线元素之和。

题解

  注意排除中间两对角线重叠部分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ans = 0;
        for (int y = 0; y != n; ++y) {
            for (int x = 0; x != n; ++x) {
                int value = scanner.nextInt();
                if (x == y) ans += value;
                else if (x == n - y - 1) ans += value;
            }
        }
        System.out.printf("sum = %d", ans);
    }

}

输入一个字符串转换成十进制整数

  输入一个字符串，它可能是 2 ~ 16 进制数中一种进制数的表示，计算它对应的 10 进制数可能的最小值。例如，“151”可以是 6 ~ 16 进制中任何一种进制数的表示。

  对应的 10 进制数可能的最小值就是 67，也就是把它当成 6 进制。

输入格式

  输入一行字符串，仅由 0 ~ 9和 A ~ F 这些字符组成，保证转换后对应的 10 进制数在 int 范围内。

输出格式

  输出一个整数，为字符串对应10进制数可能的最小值。

题解

  使数字的进制尽可能的小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        int dist = 2;
        for (int i = 0; i != input.length(); ++i) {
            char item = input.charAt(i);
            if (Character.isDigit(item)) {
                dist = Math.max(item - '0' + 1, dist);
            } else {
                dist = Math.max(item - 'F' + 16, dist);
            }
        }
        System.out.println(Integer.parseInt(input, dist));
    }

}

缩写期刊名

  科研工作者经常要向不同的期刊投稿。但不同期刊的参考文献的格式往往各不相同。有些期刊要求参考文献所发表的期刊名必须采用缩写形式，否则直接拒稿。现对于给定的期刊名，要求按以下规则缩写：

  1. 长度不超过 4 的单词不必缩写
  2. 长度超过 4 的单词仅取前4个字母，但其后要加“.”
  3. 所有字母都小写

输入格式

  首先输入一个正整数 T，表示测试数据的组数，然后是 T 组测试数据。
  每组测试输入一个包含大小写字母和空格的字符串（长度不超过 85），单词由若干字母构成，单词之间以一个空格间隔。

输出格式

  对于每组测试，在一行上输出缩写后的结果，单词之间以一个空格间隔。

题解

  使用split分割字符串后逐个处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i != n; ++i) {
            String input = scanner.nextLine();
            System.out.println(
                    Arrays.stream(input.split(" "))
                    .map(it -> it.length() > 4 ? it.substring(0, 4) + '.' : it)
                    .map(String::toLowerCase)
                    .collect(Collectors.joining(" "))
            );
        }
    }

}

优美的括号序列

  某日，小明特别无聊，就想找点东西玩，于是他发现括号 () 特别好玩，而且新学会了一项技能，

  将一对小括号 ()，插入到一个括号序列中，其中插入的规则是，左括号 ‘(’ 的位置要小于右括号 ‘)’ 的位置，不要求插入的左右括号相邻，

  例如以下，为了方便区分，我们拿 ab 代表原括号序列

  将 () 插入到 () 中可形成 ()ab (a)b (ab) a()b a(b) ab() 等等序列，其中 a 代表原括号序列的左括号，b 代表原括号序列的右括号。

  小明认为一个括号序列是一个优美的序列当且仅当这个括号序列可以被如下方法构造出来：

  一开始有一个空串，然后执行 0 次或者若干次操作，每次操作将 () 插入到当前的括号序列中。

  根据上面的定义：() , (()) , (()()) 都是优美的括号序列，(()， )(， ())) 都不是优美的括号序列。

输入格式

  多组输入。

  每行输入给定一个仅由 ‘(’、‘)’ 组成的括号序列，长度小于等于 1000。

  题目保证没有空串。

输出格式

  对于每个输入输出一行，若当前的括号序列是优美的，则输出“YES”（不含引号）。

  否则输出“NO”（不含引号）。

题解

  题上说的花哨，实际上就是一个非常简单的括号匹配而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String input = scanner.nextLine();
            int flag = 0;
            for (int i = 0; i != input.length(); ++i) {
                if (input.charAt(i) == '(') ++flag;
                else if (--flag < 0) break;
            }
            System.out.println(flag == 0 ? "YES" : "NO");
        }
    }

}

自行车停放

  有 n 辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g. 停车棚里已经有 3 辆自行车，从左到右编号为：3, 5, 1。现在编号为 2 的第 4 辆自行车要停在 5 号自行车的左边，所以现在停车棚里的自行车编号是：3, 2, 5, 1)。给定 n 辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。

输入格式

  第一行一个整数 n。 第二行一个整数 x。表示第一辆自行车的编号。 以下 n - 1 行，每行 3 个整数 x, y, z。 z = 0 时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的左边。 z = 1 时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的右边。

输出格式

  从左到右输出停车棚里的自行车编号。

题解

  注意最后一个数字后面要有一个空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> list = new ArrayList<>(n);
        list.add(scanner.nextInt());
        for (int i = 1; i != n; ++i) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            int index = list.indexOf(y);
            if (z == 0) list.add(index, x);
            else list.add(index + 1, x);
        }
        list.forEach(it -> System.out.printf("%d ", it));
    }

}

求迷宫最短通道

  递归求解迷宫最短通道的总步长。输入一个迷宫，求从入口通向出口的可行路径中最短的路径长度。为简化问题，迷宫用二维数组int maze[10][10]来存储障碍物的分布，假设迷宫的横向和纵向尺寸的大小是一样的，并由程序运行读入, 若读入迷宫大小的值是 n（3 < n <= 10），则该迷宫横向或纵向尺寸都是 n，规定迷宫最外面的一圈是障碍物，迷宫的入口是maze[1][1]，出口是maze[n-2][n-2]，若maze[i][j] = 1代表该位置是障碍物，若maze[i][j] = 0代表该位置是可以行走的空位（0 <= i <= n - 1, 0 <= j <= n - 1）。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的路径上经历的最短的总步长。要求迷宫中只允许在水平或上下四个方向的空位上行走，走过的位置不能重复走。

输入格式

  输入迷宫大小的整数 n，以及 n 行和 n 列的二维数组（数组元素 1 代表障碍物，0 代表空位）。

输出格式

  若有可行的通道则输出一个整数，代表求出的通道的最短步长；若没有通道则输出“No solution”。

题解

  最短路径问题，可以用 dijk，也可以直接暴力搜索，下面给出 dijk 的写法

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] map = new int[n - 2][n - 2];
        scanner.nextLine();
        scanner.nextLine();
        for (int i = 0; i != map.length; ++i) {
            scanner.nextInt();
            for (int k = 0; k != map[i].length; ++k) {
                map[i][k] = scanner.nextInt();
            }
            scanner.nextInt();
        }
        int ans = bfs(map);
        System.out.print(ans != Integer.MAX_VALUE ? ans : "No solution");
    }

    static int bfs(int[][] map) {
        int[][] record = new int[map.length][map.length];
        for (int[] line : record) {
            Arrays.fill(line, Integer.MAX_VALUE);
        }
        Queue<Location> queue = new PriorityQueue<>();
        queue.add(new Location(0, 0, 0));
        do {
            Location pos = queue.remove();
            if (pos.x == -1 || pos.x == map.length || pos.y == -1 || pos.y == map.length || map[pos.y][pos.x] != 0)
                continue;
            if (pos.count < record[pos.y][pos.x]) record[pos.y][pos.x] = pos.count;
            else continue;
            if (pos.x == map.length - 1 && pos.y == map.length - 1) break;
            ++pos.count;
            queue.add(new Location(pos.x - 1, pos.y, pos.count));
            queue.add(new Location(pos.x + 1, pos.y, pos.count));
            queue.add(new Location(pos.x, pos.y - 1, pos.count));
            queue.add(new Location(pos.x, pos.y + 1, pos.count));
        } while (!queue.isEmpty());
        return record[map.length - 1][map.length - 1];
    }

}

class Location implements Comparable<Location> {

    int x, y, count;

    Location(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }

    @Override
    public int compareTo(Location o) {
        return count - o.count;
    }
}

一步两步

  你要过河，但是没有桥，只有由一排石头堆成的石头路，你一次只能跨一个石头或者两个石头，求你到第 n 个石头有多少种走法。

输入格式

  正整数 n。

输出格式

  可能性的个数。

题解

  非常简单的动态规划问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 1) {
            System.out.print(1);
            return;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i != n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.print(dp[n - 1]);
    }

}

Median Pyramid

  一个 n 层的金字塔，第 i 层有 2i − 1 个方格。

  第 i（1 <= i < n）层第 j 个数是第 i + 1 层的第 j − 1, j, j + 1 三个数的中位数。

  现给出第 n 层的 2n − 1 个数(保证是一个 2n − 1 的排列)，求第一层的数。

Median Pyramid Pic

输入格式

  第一行一个整数 n（2 <= n <= 105）

  第二行 2n − 1 个数表示最底层的数，保证是一个（1, 2, … , 2N−1）的排列。

输出格式

  一个整数表示塔顶的数。

题解

  这道题使用模拟肯定是不行的，因为数据量很大，非常容易超时，所以肯定需要一些“骚套路”。

  那么我们能不能使用二分呢？答案是可以，下面我们就来说如何进行二分。

  由题我们可知答案的范围是[1, 2n - 1]（值得一提的是，PTA 上的测试数据不太严谨，没有答案在边界的情况，所以就算把答案范围视为[0, 2n - 1)同样可以通过判题），于是我们直接在[1, 2n - 1]的范围内二分答案（我们将每次二分的值设为value）。

  二分法只能用于解具有单调性的题目，那么这道题如何体现出来单调性呢？

  我们在每次检查时，将三角形底边上的数小于value的设置为0，大于等于value的设置为1，然后如果三角形顶部的结果为0则说明正确答案小于value，为1说明大于等于value。

  这样一来，这道题就具有了二分所需要的单调性。

  那么又如何快速判断三角形顶部的值是0还是1呢？我们肯定不能进行模拟，如果直接模拟的话还不如从一开始就直接模拟。

  我们不难发现，进行数据01化后，三角形中将只存在两种数字，三个数的中位数必然是数量为 2 的那一个，比如1 0 1的中位数为1，0 0 1的中位数为0。

  然后我们再来看一个例子：

1
2
3
4
5
6
          1
        1 1 0
      1 1 1 0 0
    1 1 1 1 0 0 0
  0 1 1 1 0 1 0 0 0
1 0 1 1 0 1 0 1 0 0 0

  不难发现，当两个相同的数字连接在一起时，这两个数字将一直向上传递（除非是由于被边界切割）并向中间靠拢，最终谁最先顶部，顶部就是谁。

  我们设存在 ? 组相邻的两个数字 0 和 ? 组相邻的数字 1，它们距离底部中心的距离分别为 Zi和 Oi。

  通过类推，我们不难得知，如果存在一个 i 对于所有 j 有Zi< Oj则说明 0 会先于 1 到达顶部，否则就是 1 先到达顶部。

  所以我们从数组中间向两边查找，判断是两个相邻的 0 还是 1 先出现就可以了。

  当然，还存在一种没有任何 0 或 1 是相邻的的情况，比如：

1
2
3
4
5
        1          |          0
      1 0 1        |        0 1 0
    1 0 1 0 1      |      0 1 0 1 0
  1 0 1 0 1 0 1    |    0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1  |  0 1 0 1 0 1 0 1 0

  我们发现，每向上一层（除被切割的位置外）所有数字的上面会变成和自己相反的数字，由于三角形底边数字数量和高度均一定为奇数，所以顶部的数字一定和底部中央的元素相等，所以下标（从 0 开始）为偶数的位置上的数就一定和顶部数字相等，我们使用array[0]就能获得结果。

  知道了二分的方法，我们不难写出代码：

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
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int length = (n << 1) - 1;
        int[] input = new int[length];
        int[] checker = new int[length];
        for (int i = 0; i != length; ++i) input[i] = scanner.nextInt();
        int left = 1, right = length;
        do {
            int mid = (left + right) >> 1;
            if (check(input, checker, mid)) left = mid + 1;
            else right = mid - 1;
        } while (left <= right);
        System.out.println(left - 1);
    }

    static boolean check(int[] input, int[] checker, int value) {
        for (int i = 0; i != input.length; ++i)
            checker[i] = input[i] < value ? 0 : 1;
        int left = (input.length - 1) / 2;
        for (; left != -1; --left) {
            int other = input.length - left - 1;
            if (other == left) continue;
            if (other + 1 == left) {
                if (checker[left] == checker[other])
                    return checker[left] == 1;
            } else {
                if (checker[left] == checker[left + 1])
                    return checker[left] == 1;
                if (checker[other] == checker[other - 1])
                    return checker[other] == 1;
            }
        }
        return checker[0] == 1;
    }

}
创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o