简单回顾

这次的题比较简单，主打一个帮我们找自信。我本来是能全部 AC 的，可惜的是，时间差了一点，再给我一分钟我就全 AC 了。我基本一道题 20 分钟，最后半小时一直在做第三题。第三题提交了三次，第一次随便提交的，本来感觉不会不想做了，只初始化了 dp 数组，结果还通过了 12.5%。有了一点信心，继续攻克，到最后三分钟才提交，但只过了 62.5%。我没有放弃，继续看代码的逻辑问题，还真看出来了，可是当我提交时，刚好到八点半截止答题了。结束后我又去重做了第三题，果然我最后一次没交上的代码是能 AC 的。哎，太可惜了。没办法，七点准时开始的，但我搞忘了，七点零几分才开始做的题。要是我准时开始的话，说不定就真全 AC 了。中间卡码网还崩了几分钟。不过第三第四题都是我还没刷到的动态规划背包问题，我全是做题时临时自己按照卡尔哥讲的动规五部曲分析的，没想到还都做出来了。一想到这，我觉得自己的算法也还没到无可救药的程度，后面争取坚持多刷刷题，应该还是有希望的哈哈。

接下来上题目和代码，我虽然通过了，但我看自己的运行耗时还是挺长的，我也知道肯定还有很多可以优化的地方。由于时间关系，先把代码放上来，题解和注释都还没写，后面再研究一下更优解再来更新。

1、替换数字

题目描述

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

输入

输入一个字符串 s，s 包含小写字母和数字字符。

输出

打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入

a1b2c3

样例输出

anumberbnumbercnumber

提示

数据范围：

• 1 <= s.length < 10000。

My answer

import java.util.Scanner;
import java.util.StringJoiner;

public class T1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String newstr = changeNumber(s);
        System.out.println(newstr);
    }

    private static String changeNumber(String s) {
        StringJoiner joiner = new StringJoiner("");

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 48 && c <= 57) {
                joiner.add("number");
            } else {
                joiner.add(String.valueOf(c));
            }
        }

        return joiner.toString();
    }
}

2、右旋字符串

描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出

输出共一行，为进行了右旋转操作后的字符串。

样例输入

2
abcdefg

样例输出

fgabcde

提示

数据范围：

• 1 <= k < 10000
• 1 <= s.length < 10000

My answer

import java.util.Scanner;
import java.util.StringJoiner;

public class T2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        String s = scanner.next();

        String str = rotateString(s,k);
        System.out.println(str);
    }

    private static String rotateString(String s, int k) {
        StringJoiner joiner = new StringJoiner("");
        String s1 = s.substring(0, s.length() - k);
        String s2 = s.substring(s.length() - k, s.length());
        joiner.add(s2);
        joiner.add(s1);
        return joiner.toString();
    }
}

3、携带矿石资源

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。

接下来的三行，每行包含 N 个正整数。具体如下：

第二行包含 N 个整数，表示 N 种矿石的重量。

第三行包含 N 个整数，表示 N 种矿石的价格。

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出

输出一个整数，代表获取的最大价值。

样例输入

10 3
1 3 4
15 20 30
2 3 2

样例输出

90

提示

数据范围：

• 1 <= C <= 10000

• 1 <= N <= 10000

• 1 <= w[i], v[i], k[i] <= 10000

My answer

import java.util.Scanner;

public class T3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int capacity = scanner.nextInt();
        int n = scanner.nextInt();

        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }

        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = scanner.nextInt();
        }

        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        int[][] dp = new int[n][capacity+1];

        for (int j = weights[0]; j < capacity + 1; j++) {
            int count = j / weights[0];
            if (count <= numbers[0]) {
                dp[0][j] = count * values[0];
            } else {
                dp[0][j] = numbers[0] * values[0];
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < capacity + 1; j++) {
                if (j < weights[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    int count = j / weights[i];
                    if (count < numbers[i]) {
                        for (int k = 1; k <= count; k++) {
                            dp[i][j] = Math.max(dp[i][j],dp[i-1][j-weights[i]*k]+values[i]*k);
                        }
                    } else {
                        for (int k = 1; k <= numbers[i]; k++) {
                            dp[i][j] = Math.max(dp[i][j],dp[i-1][j-weights[i]*k]+values[i]*k);
                        }
                    }

                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);
                }
            }
        }

        System.out.println(dp[n-1][capacity]);
    }
}

4、爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入

输入共一行，包含两个正整数，分别表示 n，m

输出

输出一个整数，表示爬到楼顶的方法数。

样例输入

3 2

样例输出

3

提示

数据范围：

• 1 <= m < n <= 32

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶

• 1 阶 + 2 阶

• 2 阶 + 1 阶

My answer

import java.util.Scanner;

public class T4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j <= m && j <= i; j++) {
                dp[i] += dp[i-j];
            }
        }
        System.out.println(dp[n]);
    }
}