滴滴笔试 09.17 已更正第一题

第一题

正整数，没有前导0
可以被3整除
?是需要猜测的位置，相邻的数字不能相同
输出可能的最小数。
一定存在一个 ?

输入：?12?0?9??
输出：212101902

之前 81%的代码的问题在于，数组赋值的时候，需要初始化为 -1，而不是默认的 0，否则，如果两个 "?" 相连 & 没有较好处理，第一个 "?" 会以为后面存在 0 而不能选择 0.

补充，这个题可以用贪心的方法来解决，只需要考虑下最后一个问号的处理就好了。不需要DFS。

    static boolean find;
    static int n;
    static int[] ret; // 记录最终结果
    public static void main4(String s) {
        n = s.length();
        int cnt = 0;
        find = false;
        int arr[] = new int[n];
        ret = new int[n];
        Arrays.fill(arr， -1); // 出错的原因


        List<Integer> l = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(Character.isDigit(s.charAt(i))){
                cnt += s.charAt(i) - '0'; // 记录和
                arr[i] = s.charAt(i) - '0';  // 记录值
            }else{
                l.add(i); // 记录 ？ 位置
            }
        }
        if(n == 1){ // 长度1，且一定有？，直接返回3
            System.out.println(3);
            return ;
        }
        dfs(arr, 0, l, cnt%3);
        StringBuilder sb = new StringBuilder();
        for(int i: ret){
            sb.append(i);
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int arr[], int idx, List<Integer> list, int sumv) {
        if(find) return; // 已经找到，直接返回
        if(idx == list.size()){  // 已经查看完所有的？，进行处理
            if(sumv % 3 == 0){ 
                find = true;
                for(int i  = 0; i < arr.length; i++) ret[i] = arr[i];
            }
            return;
        }
        int arrIdx = list.get(idx); // 当前的 ？
        for(int i = 0; i < 10; i++){
            if(arrIdx == 0){
                if(i == 0) continue; // 如果 ？在开头 & i = 0
            }else if(arr[arrIdx-1] == i) continue;

            if(arrIdx != n-1 && arr[arrIdx+1] == i) continue;
            arr[arrIdx] = i;
            dfs(arr, idx+1, list, sumv + i);
        }
    }

贪心，参考思路吧，没有验证。

    public static String TanXin(String s) {
        n = s.length();
        if (n == 1) return "3";
        int cnt = 0;
        int arr[] = new int[n];
        Arrays.fill(arr, -1);
        int numOfWenHao = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != '?') {
                cnt += s.charAt(i) - '0';
                arr[i] = s.charAt(i) - '0';
            }else{
                numOfWenHao++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '?') {
                Set<Integer> set = new HashSet<>(3); // 不能使用的值
                if(i == 0) set.add(0); // 头部
                if(i != 0) set.add(arr[i-1]); // 后部
                if(i != n-1) set.add(arr[i+1]); // 前部
                for(int j = 0; j < 10; j++){
                    // 1. 剩余 ? 个数 > 1，直接取可行的数中最小的
                    // 2. 剩余 ? 个数 = 1，还需要满足全部模3为0.
                    if((numOfWenHao != 1 && !set.contains(j)) ||
                        (numOfWenHao == 1 && !set.contains(j) && (j + cnt) % 3 == 0)){
                            arr[i] = j;
                            cnt += j;
                            numOfWenHao--;
                            break;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(i);
        }
        return sb.toString();
    }

第二题

题目：
栅栏被按顺序编号为1到1000000000。每个栅栏要刷 p 次 A 油漆和 q 次 B 油漆。

第一行有三个正整数n,p,q(1<=n<=100000,1<=p,q<=n)，代表刷漆的次数，以及两个参数 p 和 q。

第二到四行给出了一个大小为3*n的矩阵，第 i 列的三个数从上到下记为l,r,t(1<=l,r<=1000000000,1<=t<=2)，代表第i次刷漆将编号在 l 到 r 之间的栅栏刷了一遍 t号油漆。

问，最后有多少个栅栏满足条件。

输入：
5 2 2
1 1 2 3 2
3 5 4 5 4
1 2 1 1 2

输出：
3

方法：
差分数组+离散化

   public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int p = sc.nextInt(), q = sc.nextInt();
        int arr[][] = new int[n][3];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < n; j++){
                arr[j][i] = sc.nextInt();
            }
        }
        Map<Integer, Integer> m1 = new HashMap<>();
        Map<Integer, Integer> m2 = new HashMap<>();
        for(int i = 0; i < n; i++){
            if(arr[i][2] == 1){
                m1.put(arr[i][0], m1.getOrDefault(arr[i][0], 0) + 1);
                m1.put(arr[i][1]+1, m1.getOrDefault(arr[i][1]+1, 0) - 1);
            }else{
                m2.put(arr[i][0], m2.getOrDefault(arr[i][0], 0) + 1);
                m2.put(arr[i][1]+1, m2.getOrDefault(arr[i][1]+1, 0) - 1);
            }
        }

        List<int[]> l1 = getOk(m1, p); // 获取满足条件的 A 燃料所处的区间
        List<int[]> l2 = getOk(m2, q); // 获取满足条件的 B 燃料所处的区间
        System.out.println(func(l1, l2)); // 两个区间重叠部分
    }


    public static int func(List<int[]> l1, List<int[]> l2){
        // 查看两个区间重叠的个数
        int i = 0, j = 0;
        int a = l1.size(), b = l2.size();
        int cnt = 0;
        while(i < a && j < b){
            int arr1[] = l1.get(i);
            int arr2[] = l2.get(j);
            cnt += Math.max(Math.min(arr1[1], arr2[1]) - Math.max(arr1[0], arr2[0]) + 1, 0);
            if(arr1[1] >= arr2[1]){
                j++;
            }else{
                i++;
            }
        }
        return cnt;
    }

    public static List<int[]> getOk(Map<Integer, Integer> map, int p){
        List<Integer> keys = new ArrayList<>(map.keySet());
        List<int[]> ret = new ArrayList<>();
        if(keys.isEmpty()) return ret;

        keys.sort((a, b) -> a - b);

        int pre = keys.get(0); // 可行区间的左侧索引
        int cnt = map.get(pre); // 粉刷数目
        int len = 0; // 可行区间的长度
        for(int i = 1; i < keys.size(); i++){
            int idx = keys.get(i);
            if(cnt >= p){ // 之前的区间达到 p 值，更新长度
                len = idx - pre;
            }else{ // [idx-1] 位置没有达到 p 值
                if(len > 0){ // 保存区间
                    ret.add(new int[]{pre, pre + len-1});
                }
                pre = idx; // 更新起始点
                len = 0;  // 更新长度
            }
            cnt += map.get(idx); // 更新当前点的粉刷数
        }
        if(len > 0){  // p == 1 时需要多个判断
            ret.add(new int[]{pre, pre + len-1});
        }

        return ret;
    }