bilibili哔哩哔哩校招笔试编程题 求因数最小和

这样写为啥不对呢  有一个用例死活过不了  质数也排除了
public class Test{
    public static void main(String args[]){
        long num1;
        long num2;
        List<Long> sumList=new ArrayList<>();
        Scanner input=new Scanner(System.in);
        long n;

        n=input.nextInt();
        for(int i=1;i<n;i++){
            if(n%i==0){
                num1=i;
                num2=n/i;
                sumList.add(num1+num2);
            }
        }
        Collections.sort(sumList);
        if(sumList.size()==1){
            System.out.println(sumList.get(0)-1);
        }else{
            System.out.println(sumList.get(0));
        }
    }
}
先用循环求了因数  然后用一个list存入每一对因数的和   然后从小到大排序  输出第一个元素
质数的话  如果list只有一个元素  说明只有1和它本身的和  输出第一个元素减去1就好
但是为什么有个用例过不了呀。。。求指点


#bilibili笔试#
全部评论
import java.util.*; class Main{     public static void main(String[] args){         Scanner sc= new Scanner(System.in);         int n = sc.nextInt();         int[] dp = new int[n+1];         dp[0] = 0;         dp[1] = 1;         for(int i = 2;i<n+1;++i){             dp[i] = i;         }         for(int i = 2;i<dp.length;++i){             for(int j = i/2;j>=1;--j){                 if(i%j==0){                     dp[i] = Math.min(dp[i],j+dp[i/j]);                 }             }         }         System.out.println(dp[dp.length-1]);     } } 简单dp
2 回复 分享
发布于 2022-09-01 20:33 浙江
完全因数分解是最小的,直接完全因数分解就好了
2 回复 分享
发布于 2022-09-01 20:47 北京
你也是java岗么 为啥咱题目不一样
1 回复 分享
发布于 2022-09-01 21:05 江西
开始还以为它给的数字用int存不下 就用了long  结果还是不行
点赞 回复 分享
发布于 2022-09-01 20:22 山西
可以有超过两个因数
点赞 回复 分享
发布于 2022-09-01 20:26 浙江
直接回溯
点赞 回复 分享
发布于 2022-09-01 20:28 广东
谢谢各位了 没考虑到每组可以有多个因数
点赞 回复 分享
发布于 2022-09-01 20:29 山西

相关推荐

点赞 2 评论
分享
牛客网
牛客企业服务