Java算法题
Xplorist Lv6
  2022-01-01 22:15:00 2022-01-01 22:15      

Java算法题

reference-site-list

steps

  • x

content

HJ1-字符串最后一个单词的长度

  • 题目
    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
    HJ1 字符串最后一个单词的长度
    题目
    题解(296)
    讨论(2k)
    排行
    较难  通过率：30.47%  时间限制：1秒  空间限制：32M
    知识点
    字符串
    warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

    描述
    计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。
    （注：字符串末尾不以空格为结尾）
    输入描述：
    输入一行，代表要计算的字符串，非空，长度小于5000。

    输出描述：
    输出一个整数，表示输入字符串最后一个单词的长度。

    示例1
    输入：
    hello nowcoder
    复制
    输出：
    8
    复制
    说明：
    最后一个单词为nowcoder，长度为8
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        String str = "";
        if (scanner.hasNextLine()) {
            str += scanner.nextLine();
        }
        scanner.close();
        String[] arr = str.split(" ");
        int length = arr[arr.length - 1].length();
        System.out.println(length);
    }
}

HJ2-计算某字符出现次数

  • 题目

    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
    HJ2 计算某字符出现次数
    题目
    题解(305)
    讨论(1k)
    排行
    较难  通过率：28.78%  时间限制：1秒  空间限制：32M
    知识点
    字符串
    哈希
    warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。


    描述
    写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）

    数据范围： 
    输入描述：
    第一行输入一个由字母和数字以及空格组成的字符串，第二行输入一个字符。

    输出描述：
    输出输入字符串中含有该字符的个数。（不区分大小写字母）

    示例1
    输入：
    ABCabc
    A
    复制
    输出：
    2

  • 代码

    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
    import java.util.Locale;
    import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            test();
        }

        public static void test() {
            Scanner scanner = new Scanner(System.in);
            String str1 = "";
            String str2 = "";
            if (scanner.hasNextLine()) {
                str1 += scanner.nextLine();
            }
            if (scanner.hasNextLine()) {
                str2 += scanner.nextLine();
            }
            String[] strings = str1.split("");
            String str2Temp = str2.toLowerCase(Locale.ROOT);
            int count = 0;
            for (int i = 0; i < strings.length; i++) {
                if (strings[i].toLowerCase(Locale.ROOT).equals(str2Temp)) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }

HJ3-明明的随机数

  • 题目
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
HJ3 明明的随机数
题目
题解(253)
讨论(1k)
排行
较难  通过率：20.47%  时间限制：1秒  空间限制：32M
知识点
数组
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（ N≤1000 ），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。


注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

当没有新的输入时，说明输入结束。

数据范围：  ，输入的数字大小满足 
输入描述：
注意：输入可能有多组数据(用于不同的调查)。每组数据都包括多行，第一行先输入随机整数的个数 N ，接下来的 N 行再输入相应个数的整数。具体格式请看下面的"示例"。

输出描述：
返回多行，处理后的结果

示例1
输入：
3
2
2
1
11
10
20
40
32
67
40
20
89
300
400
15
复制
输出：
1
2
10
15
20
32
40
67
89
300
400
复制
说明：
示例1包含了两个小样例！！  
输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到1000之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以第一个小样例的输出为：
1
2
第二个小样例的第一个数字为11，也即...(类似上面的解释)...
所以第二个小样例的输出为：
10
15
20
32
40
67
89
300
400
  • 代码
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int[] nums = new int[sum];
        int count = 0;
        while (scanner.hasNextLine()) {
            if (sum == 0) {
                count = 0;
                sum = Integer.parseInt(scanner.nextLine());
                nums = new int[sum];
            } else {
                nums[count] = Integer.parseInt(scanner.nextLine());
                count++;
                sum--;
            }
            if (sum == 0 && count != 0) {
                List<Integer> list = sort(nums);
                for (Integer item : list) {
                    System.out.println(item);
                }
            }
        }
        scanner.close();
    }

    // 去重，排序
    public static List<Integer> sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int item = arr[i];
            if (!list.contains(item)) {
                list.add(item);
            }
        }
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int vi = list.get(i);
                int vj = list.get(j);
                if (vi > vj) {
                    list.set(i, vj);
                    list.set(j, vi);
                }
            }
        }
        return list;
    }
}

HJ4-字符串分隔

  • 题目
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
HJ4 字符串分隔
题目
题解(304)
讨论(1k)
排行
较难  通过率：26.98%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
•连续输入字符串，请按长度为8拆分每个输入字符串并进行输出；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
（注：本题有多组输入）
输入描述：
连续输入字符串(输入多次,每个字符串长度小于等于100)

输出描述：
依次输出所有分割后的长度为8的新字符串

示例1
输入：
abc
123456789
复制
输出：
abc00000
12345678
90000000
  • 代码
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        int num = str.length();
        if (num < 8) {
            System.out.print(str);
            for (int i = 0; i < 8 - num; i++) {
                System.out.print("0");
            }
            System.out.println();
        } else if (num == 8) {
            System.out.println(str);
        } else {
            String strTemp1 = str.substring(0, 8);
            process(strTemp1);
            String strTemp2 = str.substring(8);
            process(strTemp2);
        }
    }
}

HJ5-进制转换

  • 题目
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
HJ5 进制转换
题目
题解(226)
讨论(1k)
排行
中等  通过率：31.28%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

数据范围：保证结果在 

注意本题有多组输入
输入描述：
输入一个十六进制的数值字符串。注意：一个用例会同时有多组输入数据，请参考帖子https://www.nowcoder.com/discuss/276处理多组输入的问题。

输出描述：
输出该数值的十进制字符串。不同组的测试用例用\n隔开。

示例1
输入：
0xA
0xAA
复制
输出：
10
170
  • 代码
    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.Locale;
    import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            test();
        }

        public static void test() {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextLine()) {
                String str = scanner.nextLine();
                process(str);
            }
            scanner.close();
        }

        public static void process(String str) {
            String[] strArr = str.replace("0x", "").split("");
            int num = 0;
            for (int i = 0; i < strArr.length; i++) {
                String item = strArr[strArr.length - 1 - i];
                if (item.matches("\\d")) {
                    num += Integer.parseInt(item) * square(16, i);
                } else if (item.toUpperCase(Locale.ROOT).matches("[A-F]")) {
                    num += AFtoInt(item) * square(16, i);
                }
            }
            System.out.println(num);
        }

        public static int square(int num, int times) {
            int result = 1;
            for (int i = 0; i < times; i++) {
                result = result * num;
            }
            return result;
        }

        public static int AFtoInt(String s) {
            char ch = s.charAt(0);
            return 10 + (ch - 'A');
        }
    }

HJ6-质数因子

  • 题目
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
HJ6 质数因子
题目
题解(207)
讨论(1k)
排行
中等  通过率：26.35%  时间限制：2秒  空间限制：32M
知识点
排序
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）


数据范围： 
输入描述：
输入一个整数

输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例1
输入：
180
复制
输出：
2 2 3 3 5
  • 代码
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            int num = Integer.parseInt(str);
            process(num);
        }
        scanner.close();
    }

    public static void process(int num) {
        int primary = 2;
        while (num != 1) {
            if (num % primary == 0) {
                num = num / primary;
                System.out.print(primary + " ");
            } else {
                if (primary == 2) {
                    primary++;
                } else {
                    primary += 2;
                }
            }
        }
    }
}

HJ7-取近似值

  • 题目
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
HJ7 取近似值
题目
题解(182)
讨论(1k)
排行
入门  通过率：48.04%  时间限制：1秒  空间限制：32M
知识点
基础数学
语法题
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于 0.5 ,向上取整；小于 0.5 ，则向下取整。

数据范围：保证输入的数字在 32 位浮点数范围内
输入描述：
输入一个正浮点数值

输出描述：
输出该数值的近似整数值

示例1
输入：
5.5
复制
输出：
6
复制
说明：
0.5>=0.5，所以5.5需要向上取整为6   
示例2
输入：
2.499
复制
输出：
2
复制
说明：
0.499<0.5，2.499向下取整为2
  • 代码
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        int index = str.indexOf(".");
        if (index != -1) {
            String str1 = str.substring(0, index);
            String str2 = str.substring(index + 1);
            int num = Integer.parseInt(str1);
            int num1 = Integer.parseInt(str2.substring(0, 1));
            if (num1 >= 5) {
                System.out.println(num + 1);
            } else {
                System.out.println(num);
            }
        }
    }
}

HJ8-合并表记录

  • 题目
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
HJ8 合并表记录
题目
题解(194)
讨论(1k)
排行
中等  通过率：33.70%  时间限制：1秒  空间限制：32M
知识点
集合
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
数据表记录包含表索引和数值（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。


提示:
0 <= index <= 11111111
1 <= value <= 100000

输入描述：
先输入键值对的个数n（1 <= n <= 500）
然后输入成对的index和value值，以空格隔开

输出描述：
输出合并后的键值对（多行）

示例1
输入：
4
0 1
0 2
1 2
3 4
复制
输出：
0 3
1 2
3 4
复制
示例2
输入：
3
0 1
0 2
8 9
复制
输出：
0 3
8 9
  • 代码
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.*;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                sum = Integer.parseInt(str);
                arr = new String[sum];
                count = 0;
            } else {
                arr[count] = str;
                sum--;
                count++;
            }
            if (sum == 0 && count != 0) {
                process(arr);
            }
        }
    }

    public static void process(String[] arr) {
        int[][] numArr = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            numArr[i] = new int[2];
            String str = arr[i];
            String[] strings = str.split(" ");
            numArr[i][0] = Integer.parseInt(strings[0].trim());
            numArr[i][1] = Integer.parseInt(strings[1].trim());
        }
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < numArr.length; i++) {
            int item = numArr[i][0];
            if (!list.contains(item)) {
                list.add(item);
            }
        }
        sort(list);
        for (int i = 0; i < list.size(); i++) {
            int vi = list.get(i);
            int sum = 0;
            for (int j = 0; j < numArr.length; j++) {
                int vj0 = numArr[j][0];
                int vj1 = numArr[j][1];
                if (vi == vj0) {
                    sum += vj1;
                }
            }
            System.out.println(vi + " " + sum);
        }
    }

    public static void sort(List<Integer> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int vi = list.get(i);
                int vj = list.get(j);
                if (vi > vj) {
                    list.set(i, vj);
                    list.set(j, vi);
                }
            }
        }
    }
}

HJ9-提取不重复的整数

  • 题目
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
HJ9 提取不重复的整数
题目
题解(235)
讨论(1k)
排行
中等  通过率：41.64%  时间限制：1秒  空间限制：32M
知识点
数组
位运算
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。
保证输入的整数最后一位不是 0 。

数据范围： 
输入描述：
输入一个int型整数

输出描述：
按照从右向左的阅读顺序，返回一个不含重复数字的新的整数

示例1
输入：
9876673
复制
输出：
37689
  • 代码
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        str = reverse(str);
        deduplicate(str);
    }

    public static String reverse(String str) {
        StringBuilder temp = new StringBuilder();
        int length = str.length();
        for (int i = 0; i < length; i++) {
            temp.append(str.charAt(length - 1 - i));
        }
        return temp.toString();
    }

    public static void deduplicate(String str) {
        List<String> list = new ArrayList<>();
        String[] strings = str.split("");
        for (int i = 0; i < strings.length; i++) {
            String item = strings[i];
            if (!list.contains(item)) {
                list.add(item);
            }
        }
        for (String item : list) {
            System.out.print(item);
        }
    }
}
  • 结果
1
2
3
4
运行时间：34ms
超过57.70% 用Java提交的代码
占用内存：10720KB
超过19.91%用Java提交的代码

HJ10-字符个数统计

  • 题目
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
HJ10 字符个数统计
题目
题解(199)
讨论(1k)
排行
中等  通过率：44.69%  时间限制：1秒  空间限制：32M
知识点
字符串
哈希
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。

数据范围： 
输入描述：
输入一行没有空格的字符串。

输出描述：
输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。

示例1
输入：
abc
复制
输出：
3
复制
示例2
输入：
aaa
复制
输出：
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        char[] chars = str.toCharArray();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            char item = chars[i];
            if (!list.contains(item) && item >= 0 && item <= 127) {
                list.add(item);
            }
        }
        System.out.println(list.size());
    }
}
  • 结果
1
2
3
4
运行时间：42ms
超过36.67% 用Java提交的代码
占用内存：10964KB
超过5.91%用Java提交的代码

HJ11-数字颠倒

题目

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
HJ11 数字颠倒
题目
题解(155)
讨论(1k)
排行
简单  通过率：56.64%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001


数据范围： 
输入描述：
输入一个int整数

输出描述：
将这个整数以字符串的形式逆序输出

示例1
输入：
1516000
复制
输出：
0006151
复制
示例2
输入：
0
复制
输出：
0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        String[] arr = str.split("");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[arr.length - 1 - i]);
        }
    }
}

结果

1
2
3
4
运行时间：39ms
超过40.04% 用Java提交的代码
占用内存：10868KB
超过8.17%用Java提交的代码

HJ12-字符串反转

  • 题目
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
HJ12 字符串反转
题目
题解(140)
讨论(893)
排行
简单  通过率：56.97%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

输入描述：
输入一行，为一个只包含小写字母的字符串。

输出描述：
输出该字符串反转后的字符串。

示例1
输入：
abcd
复制
输出：
dcba
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        for (int i = 0; i < str.length(); i++) {
            System.out.print(str.charAt(str.length() - 1 - i));
        }
    }
}
  • 结果
1
2
3
4
运行时间：52ms
超过21.41% 用Java提交的代码
占用内存：11420KB
超过5.44%用Java提交的代码

HJ13-句子逆序

  • 题目
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
HJ13 句子逆序
题目
题解(165)
讨论(1k)
排行
较难  通过率：37.76%  时间限制：1秒  空间限制：32M
知识点
数组
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符

数据范围：输入的字符串长度满足 

注意本题有多组输入
输入描述：
输入一个英文语句，每个单词用空格隔开。保证输入只包含空格和字母。

输出描述：
得到逆序的句子

示例1
输入：
I am a boy
复制
输出：
boy a am I
复制
示例2
输入：
nowcoder
复制
输出：
nowcoder
  • 代码
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        List<String> list = new ArrayList<>();
        String[] arr = str.split(" ");
        for (int i = 0; i < arr.length; i++) {
            int index = arr.length - 1 - i;
            list.add(arr[index]);
        }
        for (String item : list) {
            System.out.print(item + "");
        }
    }
}
  • 结果
1
2
3
4
运行时间：44ms
超过36.56% 用Java提交的代码
占用内存：10912KB
超过11.74%用Java提交的代码

HJ14-字符串排序

  • 题目
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
HJ14 字符串排序
题目
题解(157)
讨论(947)
排行
中等  通过率：39.36%  时间限制：1秒  空间限制：32M
知识点
字符串
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
给定 n 个字符串，请对 n 个字符串按照字典序排列。

数据范围：  ，字符串长度满足 
输入描述：
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述：
数据输出n行，输出结果为按照字典序排列的字符串。
示例1
输入：
9
cap
to
cat
card
two
too
up
boat
boot
复制
输出：
boat
boot
cap
card
cat
to
too
two
up
  • 代码
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
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        String[] arr = null;
        int sum = 0;
        int count = 0;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                sum = Integer.parseInt(str);
                count = 0;
                arr = new String[sum];
            } else {
                arr[count] = str;
                sum--;
                count++;
            }
            if (sum == 0 && count != 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                String si = arr[i];
                String sj = arr[j];
                if (compare(si, sj) > 0) {
                    arr[i] = sj;
                    arr[j] = si;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static int compare(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int length = 0;
        if (chars1.length < chars2.length) {
            length = chars1.length;
        } else {
            length = chars2.length;
        }
        for (int i = 0; i < length; i++) {
            char ch1 = chars1[i];
            char ch2 = chars2[i];
            if (ch1 < ch2) {
                return -1;
            } else if (ch1 > ch2) {
                return 1;
            }
        }
        if (chars1.length < chars2.length) {
            return -1;
        } else {
            return 1;
        }
    }
}
  • 结果
1
2
3
4
运行时间：167ms
超过10.24% 用Java提交的代码
占用内存：18060KB
超过23.60%用Java提交的代码

HJ15-求int型正整数在内存中存储时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
HJ15 求int型正整数在内存中存储时1的个数
题目
题解(197)
讨论(1k)
排行
入门  通过率：54.95%  时间限制：1秒  空间限制：32M
知识点
位运算
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。

数据范围：保证在 32 位整型数字范围内
输入描述：
 输入一个整数（int类型）

输出描述：
 这个数转换成2进制后，输出1的个数

示例1
输入：
5
复制
输出：
2
复制
示例2
输入：
0
复制
输出：
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            process(str);
        }
        scanner.close();
    }

    public static void process(String str) {
        int num = Integer.parseInt(str);
        int count = 0;
        while (num != 0) {
            if (num % 2 != 0) {
                count++;
            }
            num = num / 2;
        }
        System.out.println(count);
    }
}
  • 结果
1
2
3
4
运行时间：39ms
超过43.10% 用Java提交的代码
占用内存：10800KB
超过12.65%用Java提交的代码

HJ16-购物单

  • 题目
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
HJ16 购物单
题目
题解(60)
讨论(412)
排行
中等  通过率：20.12%  时间限制：1秒  空间限制：32M
知识点
动态规划
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
    设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
    请你帮助王强设计一个满足要求的购物单。
 


输入描述：
输入的第 1 行，为两个正整数，用一个空格隔开：N m

（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）


从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q


（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 



输出描述：
 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
示例1
输入：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
复制
输出：
2200
  • 代码
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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
import java.util.*;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                String[] strings = str.split(" ");
                sum = Integer.parseInt(strings[1]) + 1;
                count = 0;
                arr = new String[sum];
            }
            arr[count] = str;
            sum--;
            count++;
            if (sum == 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        String str0 = arr[0];
        String[] strings0 = str0.split(" ");
        int moneyMax = Integer.parseInt(strings0[0]);
        List<Goods> list = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            String item = arr[i];
            String[] strings = item.split(" ");
            int price = Integer.parseInt(strings[0]);
            int worth = Integer.parseInt(strings[1]);
            if (price <= moneyMax) {
                int num = price * worth;
                Goods goods = new Goods();
                goods.id = i;
                goods.price = price;
                goods.worth = worth;
                goods.pid = Integer.parseInt(strings[2]);
                goods.num = num;
                list.add(goods);
            }
        }
        sort(list);
        getMax(list, moneyMax);
    }

    public static void getMax(List<Goods> list, int moneyMax) {
        int num = findScale(list, moneyMax);
        int numMax = 0;
        combine(list, num, moneyMax, numMax);
    }

    // 排序
    public static void sort(List<Goods> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                Goods gi = list.get(i);
                Goods gj = list.get(j);
                if (gi.price > gj.price) {
                    list.set(i, gj);
                    list.set(j, gi);
                }
            }
        }
    }

    // 寻找至多几件物品（原理：最小的n个数相加都大于最大钱，则n件物品一定不满足要求）
    public static int findScale(List<Main.Goods> list, int moneyMax) {
        int num = 0;
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            int temp = sum + list.get(i).price;
            if (temp <= moneyMax) {
                sum = temp;
                num = i + 1;
            } else {
                break;
            }
        }
        return num;
    }

    // 分组
    public static void combine(List<Goods> list, int num, int moneyMax, int numMax) {
        // 从至多个数num开始找起组合，不满足条件就继续往下递减
        // 找出个数为num的所有组合
        List<List<Integer>> comboList = findCombine(list, num);
        for (List<Integer> combo : comboList) {
            int sumMoney = 0;
            int sumNum = 0;
            for (Integer index : combo) {
                Goods goods = list.get(index);
                // pid > 0时为从件，等于0时为主件
                int pid = goods.pid;
                if (pid > 0 && !comboContains(list, combo, pid)) {
                    // 只有从件，没有主件，为错误组合
                    sumNum = 0; // 不符合条件，归0
                    break;
                }
                sumMoney += goods.price;
                sumNum += goods.num;
                if (sumMoney > moneyMax) {
                    sumNum = 0; // 不符合条件，归0
                    break;
                }
            }
            if (sumNum > 0 && sumNum > numMax) {
                numMax = sumNum;
            }
        }

        if (num > 1) {
            int maxNumInN = findMaxNumInN(list, num - 1);
            if (numMax < maxNumInN) {
                comboList = null;
                // 当前深度求得的最大值小于(num - 1)个数组合的最大值，继续往下递减
                combine(list, num - 1, moneyMax, numMax);
            } else {
                System.out.println(numMax);
            }
        } else {
            System.out.println(numMax);
        }
    }

    // 求个数为n的最大分数
    public static int findMaxNumInN(List<Goods> list, int num) {
        int sum = 0;
        // 按照分数排序
        List<Goods> numList = sortByNum(list);
        int size = numList.size();
        for (int i = 0; i < num; i++) {
            sum += numList.get(size - (1 + i)).num;
        }
        return sum;
    }

    // 按照分数排序
    public static List<Goods> sortByNum(List<Goods> list) {
        List<Goods> temp = new ArrayList<>();
        // 遍历，重新组装list，实现深拷贝
        for (Goods item : list) {
            Goods obj = new Goods();
            obj.id = item.id;
            obj.price = item.price;
            obj.worth = item.worth;
            obj.pid = item.pid;
            obj.num = item.num;
            temp.add(obj);
        }
        for (int i = 0; i < temp.size() - 1; i++) {
            for (int j = i + 1; j < temp.size(); j++) {
                Goods gi = temp.get(i);
                Goods gj = temp.get(j);
                if (gi.num > gj.num) {
                    temp.set(i, gj);
                    temp.set(j, gi);
                }
            }
        }
        return temp;
    }

    // 遍历combo中是否有该pid的id的对象
    public static boolean comboContains(List<Goods> list, List<Integer> combo, int pid) {
        for (Integer index : combo) {
            Goods goods = list.get(index);
            if (goods.id == pid) {
                return true;
            }
        }
        return false;
    }

    // 找出个数为num的所有组合
    public static List<List<Integer>> findCombine(List<Goods> list, int num) {
        // 生成根节点数组
        int size = list.size();
        Node[] roots = new Node[size - num + 1];
        // 满足深度为num，所以范围是[0, list.size() - num]的闭区间
        for (int i = 0; i < roots.length; i++) {
            Node node = new Node();
            node.index = i;
            node.pid = -1;
            roots[i] = node;
            // 从根节点出发生成深度为num的树
            generateTree(node, 1, num, size);
        }

        // 遍历树，将所有组合保存到list中
        List<List<Integer>> comboList = new ArrayList<>();
        for (Node node : roots) {
            List<Integer> combo = new ArrayList<>();
            recurseTree(node, combo, comboList);
        }
        return comboList;
    }

    // 递归生成树
    public static void generateTree(Node node, int cur, int deep, int listSize) {
        // 找node的子节点
        int index = node.index;
        if (cur < deep && index + 1 < listSize) {
            for (int i = index + 1; i <= listSize - (deep - cur); i++) {
                Node child = new Node();
                child.index = i;
                child.pid = index;
                node.children.add(child);
                generateTree(child, cur + 1, deep, listSize);
            }
        }
    }

    // 递归遍历树
    public static void recurseTree(Node node, List<Integer> combo, List<List<Integer>> comboList) {
        List<Integer> temp = deepCopy(combo); // 深拷贝，缓存当前层级的结果,深拷贝是为了不影响上层的结果
        int index = node.index;
        temp.add(index);
        List<Node> children = node.children;
        if (children.size() > 0) {
            for (Node child : children) {
                recurseTree(child, temp, comboList);
            }
        } else {
            comboList.add(temp);
        }
    }

    // 深拷贝
    public static List<Integer> deepCopy(List<Integer> combo) {
        List<Integer> list = new ArrayList<>();
        for (Integer item : combo) {
            int val = item;
            list.add(val);
        }
        return list;
    }

    static class Goods {
        public int id;
        public int price;
        public int worth;
        public int pid;
        public int num;
    }

    static class Node {
        public int index;
        public int pid;
        public List<Node> children = new ArrayList<>();
    }
}
  • 结果
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
执行出错
请检查是否存在数组越界等非法访问情况
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Main$Node.<init>(Main.java:259)
at Main.generateTree(Main.java:214)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.findCombine(Main.java:196)
at Main.combine(Main.java:96)
at Main.getMax(Main.java:59)
at Main.process(Main.java:53)
at Main.test(Main.java:25)
at Main.main(Main.java:5)
8/12 组用例通过
运行时间
1435ms
占用内存
80016KB
  • 用例输入
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
14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0
  • 预期输出
1
59350
  • 测试用例代码
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
String str = "14000 25\n"
        + "100 3 0\n"
        + "400 5 0\n"
        + "1300 5 1\n"
        + "1400 2 2\n"
        + "500 2 0\n"
        + "800 2 0\n"
        + "1400 5 0\n"
        + "300 5 0\n"
        + "1400 3 0\n"
        + "500 2 0\n"
        + "1800 4 0\n"
        + "440 5 10\n"
        + "1340 5 10\n"
        + "1430 3 0\n"
        + "500 2 0\n"
        + "800 2 0\n"
        + "1400 5 0\n"
        + "300 4 0\n"
        + "1400 3 0\n"
        + "500 2 0\n"
        + "1800 2 0\n"
        + "400 5 20\n"
        + "1310 5 20\n"
        + "1400 3 0\n"
        + "500 2 0\n";
String[] arr = str.split("\n");
process(arr);
  • 实际输出
1
59350

网上找的代码，跑通了，但是不是很理解原理

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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //test();
        String str = "14000 25\n"
                + "100 3 0\n"
                + "400 5 0\n"
                + "1300 5 1\n"
                + "1400 2 2\n"
                + "500 2 0\n"
                + "800 2 0\n"
                + "1400 5 0\n"
                + "300 5 0\n"
                + "1400 3 0\n"
                + "500 2 0\n"
                + "1800 4 0\n"
                + "440 5 10\n"
                + "1340 5 10\n"
                + "1430 3 0\n"
                + "500 2 0\n"
                + "800 2 0\n"
                + "1400 5 0\n"
                + "300 4 0\n"
                + "1400 3 0\n"
                + "500 2 0\n"
                + "1800 2 0\n"
                + "400 5 20\n"
                + "1310 5 20\n"
                + "1400 3 0\n"
                + "500 2 0\n";
        String[] arr = str.split("\n");
        process(arr);
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                String[] strings = str.split(" ");
                sum = Integer.parseInt(strings[1]) + 1;
                count = 0;
                arr = new String[sum];
            }
            arr[count] = str;
            sum--;
            count++;
            if (sum == 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        int n = 0;
        Goods[] goodsArray = new Goods[arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            String[] strArray = arr[i].split(" ");
            if (i == 0) {
                n = Integer.parseInt(strArray[0])/10;
                continue;
            }
            int master = Integer.parseInt(strArray[2]);
            int price = Integer.parseInt(strArray[0])/10;
            int value = Integer.parseInt(strArray[1]);
            Goods tmp = new Goods(master, price, value, new ArrayList<>());
            goodsArray[i - 1] = tmp;
        }
        for (Goods goods : goodsArray) {
            if (goods.master > 0) {
                goodsArray[goods.master - 1].list.add(goods);
            }
        }
        System.out.println(shopDp(goodsArray, n) * 10);
    }

    static class Goods {
        Goods(int master, int price, int value, List<Goods> list) {
            this.master = master;
            this.price = price;
            this.value = value;
            this.list = list;
        }
        int master;
        int value;
        int price;
        List<Goods> list;
    }

    private static int shopDp(Goods[] goods, int n) {
        int[] dp = new int[n + 1];
        for (Goods item : goods) {
            if (item.master > 0) {
                continue;
            }
            // 主件和依赖的的同价格下最大价值
            int[] tmp = new int[n + 1];
            tmp[item.price] = item.price * item.value;
            for (Goods child : item.list) {
                // 最大价值不超过n，max(i) = n - child.price
                for (int i = n - child.price; i >= 0; i--) {
                    if (tmp[i] > 0) {
                        int price = child.price + i;
                        tmp[price] = Math.max(tmp[i] + child.price * child.value, tmp[price]);
                    }
                }
            }
            // dp
            for (int i = n; i >= 0; i--) {
                if (dp[i] == 0 && i != 0) {
                    continue;
                }
                // 选择购买不能超过n，max(j) = n-i
                for (int j = n - i; j >= 0; j--) {
                    if (tmp[j] != 0) {
                        dp[i + j] = Math.max(dp[i] + tmp[j], dp[i + j]);
                    }
                }
            }
        }
        int ret = -1;
        for (int i = n; i >= 0; i--) {
            if (dp[i] != 0) {
                ret = Math.max(ret, dp[i]);
            }
        }
        return ret;
    }
}
  • 本文标题：Java算法题
  • 本文作者：Xplorist
  • 创建时间：2022-01-01 22:15:00
  • 本文链接：https://xplorist.tech/2022/01/01/7fd991b892f3/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论