[数据结构与算法]LeetCode（中）

滑动窗口衍生

绳子覆盖问题

定右二分向左查找O(N*logN)

class D {
    // 长度为L的绳子最多覆盖几个点，请保证arr有序
    public static int maxPoint(int[] arr, int L) {
        int res = 1;
        for (int i = 0; i < arr.length; i++) {
            int nearest = nearestIndex(arr, i, arr[i] - L);
            res = Math.max(res, i - nearest + 1);
        }
        return res;
    }

    // 在arr[0..R]范围上，找满足>=value的最左位置
    public static int nearestIndex(int[] arr, int R, int value) {
        int L = 0;
        int index = R;
        while (L < R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] == value) {
                return index;
            } else if (arr[mid] > value) {
                index = mid;//右侧更新前记录
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }
}

定左向右延申O(N)

• 优化原因：左侧向右运动时，右侧动态测试能到达最右位置。避免了每次要寻找。

class D {
    static int Left=0;
    static int right=0;//指向第一个不能到达的元素
    static int[] arr;
    static int len;
    public static int maxNum(int[] array,int L){
        if (array==null||array.length==0||L==0)return 0;
        arr=array;
        len=L;
        int max=0;
        for (;Left<arr.length;Left++){
            int n=maxN();
            max=Math.max(max,n);
        }
        return max;
    }
    public static int maxN(){
        while (right<arr.length&&arr[Left]+len>=arr[right]){
            right++;
        }
        return right-Left;
    }
}

打表法

• 出现和倍数相关的问题时，可以考虑通过一般方法解题后的结果是否存在某种特殊的规律，通过直观的答案直接进行代码的书写，不需要关注本质含义。

整体装袋

一般思路

    public static int num(int apple){
        if (apple%8==0)return apple/8;
        int n8=apple/8;
        int m=apple%8;
        while (m<24&&n8>=0){
            if (m%6==0)return n8+m/6;
            --n8;
            m+=8;
        }
        return -1;
    }

打表代码

18前无规律，18后单为-1，双为一个值，每增加8个就增加1

public static int daBiao(int apple){
    if (apple<18)return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1
          : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
    if (apple%2==1)return -1;
    return (apple-18)/8+3;
}

幂次方吃草

一般思路

    public static String winner(int N) {
        if (N <= 4) return N == 0 || N == 2 ? "羊羊" : "牛牛";
        int eatTest = 1;
        while (eatTest <= N) {
            if (winner(N - eatTest).equals("羊羊")) return "牛牛";
            eatTest *= 4;
        }
        return "羊羊";
    }

打表代码

public static String win(int N){
    return (N)%5==0||(N)%5==2?"羊羊":"牛牛";
}

数据预处理

• 每次计算时出现重复的动作，我们就将这些操作在计算之前进行直接处理，在我们需要时直接进行数据的获取。

最小染色数

一般思路

    public static int minPrint(String s) {
        char[] arr = s.toCharArray();
        int N = arr.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int num = 0;
            if (i == 0) {
                for (int j = i; j < N; j++) {
                    if (arr[j] == 'R')
                        num++;
                }
                min = Math.min(num, min);
            } else if (i == N - 1) {
                for (int j = N - 1; j >= 0; j--) {
                    if (arr[j] == 'G') {
                        num++;
                    }
                }
                min = Math.min(num, min);
            } else {
                for (int j = 0; j < i; j++) {
                    if (arr[j] == 'G') {
                        num++;
                    }
                }
                for (int j = i; j < N; j++) {
                    if (arr[j] == 'R') {
                        num++;
                    }
                }
                min = Math.min(num, min);
            }
        }
        return min;
    }

预处理

    public static int minP(String s) {
        char[] arr = s.toCharArray();
        int N = arr.length;
        int[] Gmun = new int[N];
        Gmun[0] = arr[0] == 'G' ? 1 : 0;
        for (int i = 1; i < N; i++) {
            Gmun[i] = Gmun[i - 1] + (arr[i] == 'G' ? 1 : 0);
        }
        int[] Rmun = new int[N];

        Rmun[N - 1] = arr[N-1] == 'R' ? 1 : 0;
        for (int i = N - 2; i >= 0; i--) {
            Rmun[i] = Rmun[i + 1] + (arr[i] == 'R' ? 1 : 0);
        }

        int min = Math.min(Gmun[N-1],Rmun[0]);
        for (int i = 0; i < N-1; i++) {
            min = Math.min(min, Gmun[i] + Rmun[i+1]);
        }
        return min;
    }