算法学习day42-2

算法学习day42-2

算法题----一位道友的题

题目代码实现

口述：

(因为他是面试还是笔试来着忘了，我leetcode上也没找到，所以题目目前只有口述,不过这道题很有意思)

​ 给你一些0-9中的数字叫做幸运数字，然后给一个目标数，返回小于等于该数字的最大的全部由幸运数字构成的数字，比如幸运数字为3，5，7 那么777的结果就是777，857的结果也是777，762的结果就是757，745的结果就是737，312的结果就是77。

package practice111;

import com.sun.org.apache.bcel.internal.generic.LNEG;

import java.util.*;


public class Main {
    public static void main(String[] args) {
        // 已测试案例：
        // 幸运数3,5,7    下的  777、857、762、745、312
        // 幸运数6，8,9   下的  966663666
        // 幸运数2,3      下的 2222221
        // 幸运数1,7,8,9  下的 780087
        // (前导0案例：)
        // 幸运数0,4,5,8  下的 10000
        // 幸运数0        下的 10000
        // (没有的情况，就为空)
        // 幸运数4        下的 2
        // 幸运数为空      下的 任何数
        // 幸运数为任何    下的 目标数为空字符串或空
        Main m = new Main();
        char[] s = new char[]{'0','6'};
        String number = "1000000000000000000000000000000000";

        String str = m.maxNumber(s, number);
        System.out.println(str);
    }

    
    public String maxNumber(char[] luck,String number){
        if(luck == null || luck.length == 0 || number == null){
            return "";
        }
        // 特殊情况：幸运数只有0，那么结果只能取0.
        if(luck.length == 1 && luck[0] == '0'){
            return "0";
        }

        // numbers数组存储number这个数的每一个位上的值(位是指个位、十位等)
        char[] numbers = number.toCharArray();
        // 先将luck排序，保证由低到高
        Arrays.sort(luck);
        int[] flag = new int[numbers.length];// 记录每一位取的幸运数的坐标
        Arrays.fill(flag,-1);
        boolean min = true;// 记录前一位是否连续取最低位

        // 遍历numbers中的每一位，从高到底，贪心取值。
        for(int i = 0;i < numbers.length;i++){
            // 情况1：当前位的值小于最小的幸运数
            if(numbers[i] < luck[0]){
                
                if(i == 0 || min){
                    flag[0] = -1;// 情况2 的(1)情况 需要
                    fuZhi(1,luck.length - 1,flag,numbers.length);
                    break;
                }

                // (2) 有尽头，则前面一定有一个取的幸运数是坐标0以上。找到遇到的前面的第一个不是0的
                //     将其坐标减一(这里值flag)，然后后面的位全部取最大幸运数的坐标即可。
                int index = i - 1;
                while(flag[index] == 0){
                    index--;
                }
                flag[index]--;
                fuZhi(index + 1,luck.length - 1,flag,numbers.length);
                break;
            }

            // 遍历顺序由高到低
            for(int j = luck.length - 1;j >= 0;j--){
                // 情况2：当前这一位大于某一个幸运数，当前位取这个幸运数，然后之后的位直接取最大的幸运数即可。
                //       这里需要注意最小幸运数为0的这种情况，这种情况可能使开头有前导0,具体的处理方式在result
                //       中处理，还要注意这里如果0是中间走到这里的话，其实是不需要处理的。
                if(numbers[i] > luck[j]){
                    flag[i] = j;
                    fuZhi(i+1,luck.length - 1,flag,numbers.length);

                    return result(flag,luck);
                }

                // 情况3：
                if(numbers[i] == luck[j]){
                    // 记录
                    flag[i] = j;

                    if(j != 0){// 这个判断和情况1 中有关哈,相当于标记一个特殊情况。
                        min = false;
                    }

                    break;
                }
            }
        }

        return result(flag,luck);
    }
    // 该方法用于给flag后面的位赋值(主要是重复的有点多，所以弄一个方法)
    public void fuZhi(int index,int maxValue,int[] flag,int numberL){
        for(int i = index;i < numberL;i++){
            flag[i] = maxValue;
        }
    }
    // 该方法用于拼接结果
    public String result(int[] flag,char[] luck){
        StringBuffer str = new StringBuffer();

        for(int i = 0;i < flag.length;i++){
            if(i == 0 && (flag[i] == -1 || (flag[0] == 0 && luck[0] == '0'))){
                continue;
            }
            str.append(luck[flag[i]]);
        }

        return str.toString();
    }
}

PS：自言自语：早上周赛，昨天晚上双周赛，所以现在才弄出来，这道题都是昨天还是前天的了，不过因为条件限制没得，然后也是口述，所以考虑情况比较多，最后觉得应该问题不大才发出来，还是当打卡吧，春招找工作不易，加油。