华为OD机试--恢复数字序列--带答案

古城微笑少年丶 2023-10-14 09:18 1阅读 0赞

[2023华为OD统一考试（A+B卷）题库清单-带答案（持续更新）][2023_OD_A_B_-]or[2023年华为OD真题机考题库大全-带答案（持续更新）][2023_OD_-]

> ## 题目描述 ##
> 
> 对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。 现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。
> 
> ## 输入描述 ##
> 
> 输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。
> 
> ## 输出描述 ##
> 
> 输出一个数字，为序列中最小的数字。
> 
> ## 样例 ##
> 
> **输入**
> 
> 19801211 5 -->8
> 
> 1611231145 5 -->12
> 
> 8088456888789199 8 -->84
> 
> 111002011304101065 6 -->101
> 
> **输出**
> 
>   
> 8

public class RecoverySequence {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long num = sc.nextLong();
            long len = sc.nextInt();
            long min = minNum(num,len);
            System.out.println(min);
        }
        public static long minNum(long num, long len){
            List<Long> nums = new ArrayList<>();
            List<Long> begin = new ArrayList<>();
            while (num > 0){
                long digit = num % 10;
                nums.add(digit);
                begin.add(digit);
                num = num / 10;
            }
            //序列值范围 19801211 5 -->8    1611231145 5 -->12    8088456888789199 8 -->84 111002011304101065 6 -->101
            long minRange = nums.size()/len;
            long maxRange = (long) Math.ceil(Double.valueOf(nums.size())/len);
            //boolean区分起始值跟终值
            minRange = range(minRange,true);
            maxRange = range(maxRange,false);
            int count = 0;
            Boolean con = true;
            List<Long> value = new ArrayList<>();
            for (long i = minRange; i < maxRange; i++){
                long t = i;
                while (t > 0){
                    //将整数值一个个拆分出来
                    Long digit = t % 10;
                    value.add(digit);
                    t = t / 10;
                }
                //分拆
                for (int j = 0; j < value.size(); j++){
                    //满足则删除，计数+1，且list列表长度为0
                    if (nums.contains(value.get(j))){
                        nums.remove(value.get(j));
                    }else {
                        //初始化恢复
                        con = false;
                        nums = new ArrayList<>(begin);
                        //恢复到开始连续的伪序列号位置
                        i = i - count;
                        count = 0;
                        break;
                    }
                }
                if (con){
                    count++;
                }else if (!con){
                    con = true;
                }
                value = new ArrayList<>();
                //满足连续的正整数序列
                if (count == len && nums.size() == 0){
                    return (i-count + 1);
                }
            }
            return count;
        }
    
        /**
         * 定义循环的区间范围（位数）
         * @param value
         * @param b
         * @return
         */
        public static long range(long value ,Boolean b){
            if (b){
                value =  (long) Math.pow(10,value -1);
            }else {
                value =  (long) Math.pow(10,value);
            }
            return value;
        }
    
    }

[2023_OD_A_B_-]: https://blog.csdn.net/weixin_42450130/article/details/131750502
[2023_OD_-]: https://blog.csdn.net/weixin_42450130/article/details/131719081