小红书实习笔试java第二题_java小红书实习

是在是太菜了 笔试只写出了一道题 而且通过率才27 无语子
第一个题不说了 是我基础问题 需要用到BigDecimal 套了一个炉石传说的背景 在笔试时候看了好久源码 也没想起来怎么写

第三个题没看 就结束了

这里记录一下第二个题 第一反应就是01背包问题 但是太紧张了 最后用的hashMap做的 今天重新想了一下 写了出来

题目大概是这样的：背景是博主旧的账号引流 我精简一下题干大概是这样的

特殊的01背包 想要求到达价值n的 拿取物品最少数 但是这个物品可以取或者不取 或者取一半 比如 1 2 3 4 10 target为8 返回2 解释:可以3全拿 10拿一半 这种情况最少

今天写出代码来了

package org.example;

import java.util.Arrays;

    public class Main {
        public static int minItemsForValue(int n, int[] values, int target) {
            int[]dp = new int[target + 1];
            Arrays.fill(dp,Integer.MAX_VALUE);
            dp[0] = 0;//背包初始化代表没拿物品  价值为0的最小次数
            for (int i = 0; i < n; i++) {
                for (int j = target; j >= values[i]/2; j--) {
                    //分情况  反正目的就是获得一个当前物品i 在价值j时候的最小物品数目
                    if(j >= values[i]){
                        if(dp[j-values[i]]!= Integer.MAX_VALUE&&dp[j-values[i]/2]!=Integer.MAX_VALUE)
                            dp[j] = Math.min(Math.min(dp[j],dp[j-values[i]/2]+1),dp[j-values[i]]+1);
                        else if(dp[j-values[i]]!= Integer.MAX_VALUE)
                            dp[j] = Math.min(dp[j],dp[j-values[i]]+1);
                        else if(dp[j-values[i]/2]!= Integer.MAX_VALUE)
                            dp[j] = Math.min(dp[j],dp[j-values[i]/2]+1);
                    }else{
                        if(dp[j-values[i]/2] != Integer.MAX_VALUE){
                            dp[j] = Math.min(dp[j],dp[j-values[i]/2]+1);
                        }
                    }
                }
            }
            if(dp[target] == Integer.MAX_VALUE){
                return -1;
            }
            return dp[target];
        }

        
        public static void main(String[] args) {
            int n = 5; // 物品数量
            int[] values = {1, 2, 3, 4,10}; // 每个物品的价值
            int target = 8; // 目标价值
            System.out.println(minItemsForValue(n, values, target)); // 输出最少物品数
        }
}
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