当前位置：首页 > article >正文

最大数字（java）(DFS实现)

article 2025/4/1 3:50:38

1.最大数字 - 蓝桥云课

因为N最大是·10 的17次方，

所以可以利用字符串来处理输入的数字的每一位

并且是从高到低依次处理的

然后通过函数charAt(i)来获取第i位的字符

再减去‘0’就可以将字符转化为整型了

假设每一位数字都是x

然后通过两种操作

加或者减来操作

然后每次操作的话我们先判断加

如果这个数字的第i位还存在的话

那就可以进行加或者减

然后我们开始dfs之前先

判断加多少位，能把第一位变成9

我们尽最大的努力去把每一位都加到9

两种情况

第一种如果加法的次数最多不超过9-x 吧

因为加的次数多了又加到0了

做无用功了，你说对吧

第二种情况如果加法的次数不足以把x加到9

我们

加的次数就是9-x 和n 中的最小值

（9-x）也就是x加到9的次数

t 取（9-x）和 n 的最小值

回溯之前：剩余的加的次数就是n =n -t;

然后就开始dfs()嵌套循环了

开始的时候是

dfs(i,v) i表示当前这个数的位数的下标

v 用来保存操作之后的值

dfs(i+1,v*10+t) 表示进入下一位，便利下一个节点i+1

然后需要保存这一次加法之后的值

然后如果回溯回回来就需要把给加法次数加回来

ok自己写一遍

emm，又出问题了，孩子们



import java.util.Scanner;

/**
 * @author zb
 * date2025/3/26 21:32
 */
public class Main {
    static int n ;
    static int add;
  static   int jian;

  static String num;
  static int max = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
         n = in.nextInt();
         num = ""+n;
        add = in.nextInt();
       jian  = in.nextInt();
//       先从最高为开始操作
        dfs(0,0);

        System.out.println(max);

        in.close();
    }
//代表给第i位操作 ，v 用来保存操作的结果
    private static void dfs(int i, int v) {

        if(i<num.length()){
//            加法操作
//            获取第i位的数字
            int numi = num.charAt(i)-'0';
//            加到9所需要的次数
            int t = 9  - numi;
//            如果加的次数不能让这个数字加到9
          if(add<=t){
//              能加多少算多少
              t = add;
          }
//          减去消耗掉的加法次数
          add = add - t;
//            System.out.println(t+"   "+add);
//          便利叶子节点
          dfs(i+1,v*10 +numi+t);
//     从叶子节点变回来了     回复现场
            add = add+ t;
//            减法 的话一定要把这个数字给变成0
//           也就是减法必须要被这个位置的数字大
//            某一位最大只能变成9
            if(numi-jian<0&&numi!=9){
//                numi  = 9;
//               等于-1也就是变成9
                jian = jian - numi-1;
//                System.out.println("   "+jian);
                dfs(i+1,v*10 +9);
                jian  = jian + numi + 1;
            }



        }else {
//            保存进行操作之后得到的最大值
            max = Math.max(max,v);

        }
    }
}

整体思路没有问题，死于段错误

看了一下题目发现