第一讲 基础算法

包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。

快速排序
分治算法： 1 分成子问题 —————— 2 递归处理子问题 —————— 3 子问题合并

public void quick_sort(int[] a, int l, int r) {
    if (l >= r) return; // 区间内元素为1个或0个

    int x = a[l], i = l - 1, j = r + 1; // 向两边扩了一下(i, j在两侧)
    while (i < j) {
        while (a[ ++ i] < x);
        while (a[ -- j] > x);
        if (i < j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    quick_sort(a, l, j); // 边界是j
    quick_sort(a, j + 1, r);
}

第k个数

思路：只选一边来递归，因为只用前k个
时间复杂度 O = n + 1/2n + 1/4n + ... = n(1 + 1/2 + 1/4 + ..) <= 2n

public static int quick_select(int[] a, int k, int l, int r) {
    if (l == r) return a[l];
    int x = a[l], i = l - 1, j = r + 1;
    while (i < j) {
        while (a[ ++ i] < x);
        while (a[ -- j] > x);
        if (i < j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    int sl = j - l + 1; // 统计从小排后的个数
    if (k <= sl) return quick_select(a, k, l, j);
    else return quick_select(a, k - sl, j + 1, r);

}

归并排序

也是分治思路：先递归排，后排序

public static void merge_sort(int[] a, int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid); // 先递归
    merge_sort(a, mid + 1, r);

    int[] tmp = new int[a.length]; // 再使用辅助数组合并
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k ++] = a[i ++ ];
        else tmp[k ++ ] = a[j ++ ];
    }
    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++];
    for (i = l, k = 0; i <= r; i ++ , k ++ ) {
        a[i] = tmp[k];
    }
}

逆序对的数量

两个序列都是有序的
一旦a[i] > a[j] 那么i之后的所有数都比a[j]大，那么计算逆序对的数量是 mid - i + 1

public static int merge_sort(int[] a, int l, int r) {
    int res = 0;
    if (l >= r) return res;
    int mid = l + r >> 1;
    res += merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);

    int[] tmp = new int[a.length];
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ];
        else {
            res += mid - i + 1;
            tmp[k ++ ] = a[ j ++ ];
        }
    }
    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++ ];
    for (i = l, k = 0; i <= r; i ++ , k ++ ) a[i] = tmp[k];
    return res;
}

数的范围

考察二分法
二分法的题目大多数是单调性，但适用于90%两段性，分界点左右两段分别满足不同的条件

俩模板，根据l和r的更新方式选择

public static int[] rangeOfNumber(int[] a, int x) {
    int[] res = new int[2];
    Arrays.fill(res, -1);

    int l = 0,r = a.length - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }


    if (l <= r && a[l] != x) return res;
    res[0] = l;
    l = 0;
    r = a.length - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    res[1] = l;
    return res;
}

数的三次方根

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double x = sc.nextDouble();
    double l = -10000, r = 10000;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid < x) l = mid;
        else r = mid;
    }
    System.out.printf("%.6f",l);
}

数的算数平方根

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double x = sc.nextDouble();
    double l = 0, r = Math.max(1, r);
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid < x) l = mid;
        else r = mid;
    }
    System.out.printf("%.6f",l); 精度为4位小数 1e6  5位小数 1e7
}

最长连续不重复子序列

连续子序列就是子数组 —— 可采用滑动窗口求解,用双指针来维护一个闭区间[left, right]

滑动窗口问题：可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度，是查找满足一定条件的连续区间的性质（长度等）的问题， “请找到满足 xx 的最 xx的区间（子串、子数组）的 xx ”这类问题都可以使用该方法进行解决。” 一般在线性结构里，如数组链表栈字符串等

普遍的模板

int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}
//对应上面的例题，中间的while条件需要自己去修改，原理是一样的，遇到不符合的条件，就调整窗口大小

本题代码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i ++ ) {
        a[i] = sc.nextInt();
    }
    HashSet<Integer> set = new HashSet<>();
    int l = 0, r = 0, length = 0;
    while (r < n) {
        while (set.contains(a[r])) {
            set.remove(a[l ++ ]);
        }
        set.add(a[r ++ ]);
        length = Math.max(length, r - l);

    }
    System.out.println(length);
}

数组元素的目标和

因为A和B都是升序的数组，所以可以使用两个指针，i从a0，j从bm往里走
涉及到索引自加自减的，一定要检查是否越界

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[n];
    int [] b = new int[m];
    for (int i = 0; i < n; i ++ ) a[i] = sc.nextInt();
    for (int i = 0; i < m; i ++ ) b[i] = sc.nextInt();

    for (int i = 0, j = m - 1; i < n; i ++ ) {
        while (j >= 0 && a[i] + b[j] > x) j -- ;
        if (j >= 0 && a[i] + b[j] == x) {
            System.out.println(i + " " + j);
            break;
        }
    }
}

判断子序列

双指针 + 贪心

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] a = new int[n];
    int[] b = new int[m];
    for (int i = 0; i < n; i ++ ) a[i] = sc.nextInt();
    for (int i = 0; i < m; i ++ ) b[i] = sc.nextInt();

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] == b[j]) i ++ ;
        j ++ ;
    }
    if (i == n) {
        System.out.println("Yes");
    } else System.out.println("No");
}

二进制中1的个数

采用lowbit来实现，每次减去一个lowbit，看减到0，能有几次操作
lowbit可以提取出一个数的最后一个1及后面的所有位。 x = (1010) lowbit(x) = 10[都是二进制表示]

public static void main(String[] args) {
    Scanner sc =  new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 0; i < n; i ++ ) {
        int x = sc.nextInt();
        System.out.print(countOne(x) + " ");
    }
}
public static int countOne(int x) {
    int res = 0;
    while (x != 0) {
        x -= lowBit(x);
        res ++ ;
    }
    return res;
}

public static int lowBit(int x) {
    return x & (-x);
}

区间和

离散化：因为涉及到的下标只有n + 2m个————很稀疏————而且查询只用相对大小关系，所以保序映射

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] a = new int[n + 2 * m + 1]; // 保存离散后的数值
    int[] s = new int[n + 2 * m + 1]; // 前缀和数组
    List<Integer> alls = new ArrayList<>(); // 存放所有需要映射的下标
    int[][] add = new int[n][2];
    int[][] query = new int[m][2];
    for (int i = 0; i < n; i ++ ) {
        int x = sc.nextInt();
        int c = sc.nextInt();
        alls.add(x);
        add[i][0] = x;
        add[i][1] = c;
    }

    for (int i = 0; i < m; i ++ ) {
        int l = sc.nextInt();
        int r = sc.nextInt();
        alls.add(l);
        alls.add(r);
        query[i][0] = l;
        query[i][1] = r;
    }

    alls = new ArrayList<>(new HashSet<>(alls));
    Collections.sort(alls);

    // 处理add部分
    for (int[] item : add) {
        int x = find(alls, item[0]);
        a[x] += item[1];
    }

    // 处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

    //
    for (int[] item : query) {
        int l = find(alls, item[0]);
        int r = find(alls, item[1]);
        System.out.println(s[r] - s[l - 1]);
    }


}

public static int find(List<Integer> alls, int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (alls.get(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 因为计算前缀和需要从1开始
}

区间合并
计数只需要维护右端点

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] intervals = new int[n][2];
    for (int i = 0; i < n; i ++ ) {
        intervals[i][0] = sc.nextInt();
        intervals[i][1] = sc.nextInt();
    }

    Arrays.sort(intervals, (a, b) ->(a[0] - b[0]));
    int end = Integer.MIN_VALUE;
    int res = 0;
    for (int[] seg : intervals) {
        if (seg[0] > end) {
            res ++ ;
            end = seg[1];
        } else {
            end = Math.max(end, seg[1]);
        }
    }
    System.out.println(res);


}

如果需要保存区间

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] intervals = new int[n][2];
    for (int i = 0; i < n; i ++ ) {
        intervals[i][0] = sc.nextInt();
        intervals[i][1] = sc.nextInt();
    }

    Arrays.sort(intervals, (a, b) ->(a[0] - b[0]));
    int start = Integer.MIN_VALUE, end = Integer.MIN_VALUE;
    int res = 0;
    for (int[] seg : intervals) {
        if (seg[0] > end) {
            if (start != Integer.MIN_VALUE) res.add(new int[]{start, end});
            start = seg[0];
            end = seg[1];
        } else {
            end = Math.max(end, seg[1]);
        }
    }
    if (start != Integer.MIN_VALUE) res.add(new int[]{start, end});
    return res;
}