2020

12/03 Thu

奇数筛，质数筛的一种，比已学的都好

  1. public int countPrimes(int n) {
  2.     if (n < 3) {
  3.         return 0;
  4.     }
  5.     boolean[] f = new boolean[n];
  6.     int len = (int)Math.sqrt(n), count = 1;
  7.     for (int i = 3; i < n; i += 2) {
  8.         if(!f[i]) {
  9.             ++count;
  10.             if (i <= len) {
  11.                 for (int j = i, t; (t = i * j) < n; j +=2) {
  12.                     f[t] = true;
  13.                 }
  14.             }
  15.         }
  16.     }
  17.     return count;
  18. }

12/02 Wed

中位数与所有数的差是最小的
最大字典子序列

  1. public static int[] maxSubsequence(int[] nums, int k) {
  2.     int length = nums.length;
  3.     int[] stack = new int[k];
  4.     // Deque<Integer> st = new LinkedList<Integer>();
  5.     int top = -1;
  6.     int remain = length - k;
  7.     for (int i = 0; i < length; i++) {
  8.         int num = nums[i];
  9.         while (top >= 0 && stack[top] < num && remain > 0) {
  10.             top--;
  11.             remain--;
  12.         }
  13.         if (top < k - 1) {
  14.             stack[++top] = num;
  15.         } else {
  16.             remain--;
  17.         }
  18.     }
  19.     return stack;
  20. }

11/27 Fri

求目标和target，可以把target分成两部分，前半部分暴力，后半部分直接映射检查是否存在。

区间加减运算，可以使用差分+前缀和。一维差分
差分的前缀和就是原数组。

11/26 THU

Leetcode:
自带排序sort：时间复杂度O(nlog(n))，其实在元素范围相同的情况下，除非数组长度大于最大值，否则自带sort还是很还用的。
线性排序

  • 计数排序，基数排序，桶排序
  • 计数排序实现简单，但是会被元素大小卡常
  • 基数排序时间复杂度之和最大元素的位数有关，大大减少时间复杂度
    • 时间复杂度：O(KN)，其中K=最大元素的位数*3
  • 桶排序(以前一直把计数排序当作桶排序)，分桶，
    • 每个桶的长度d=(maxE-minE) / (len(arr) - 1)
    • 桶的数量为bucketSize = (maxE - minE) / d + 1
    • 每个数映射到桶的公式: (num[i] - minE) / d
    • 每个桶单独进行排序，可以是自带sort，也可以进行递归桶排序；
    • 时间复杂度：O(bucketSize * log(bucketSize / d) + bucketSize，比起前两种，常数更小？

Acwing:
前缀和

  • 一维是点变成线，算长度
  • 二维是线变成面，算面积，注意重叠
  • 三维

11/23 MON

leetcode：气球射箭
java中数组排序的比较器，有两种写法，匿名类和lambda，其中lambda有两种，推荐lambda
匿名类：

  1. Arrays.sort(points, new Comparator<int[]>() {
  2.     public int compare(int[] point1, int[] point2) {
  3.                 if (point1[1] > point2[1]) {
  4.                     return 1;
  5.                 } else if (point1[1] == point2[1]) {
  6.                     return 0;
  7.                 } else {
  8.                     return -1;
  9.                 }
  10.             }
  11. });

lambda：

  1. Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);
  2. Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1], p2[1]));

java的比较器有三种返回值
小于 -1 等于 0 大于 1
常见写法：
但是减法运算有可能会溢出
Arrays.sort(arr, (e1, e1) -> e1 - e2);

11/24 TUE

完全二叉树性质：除最后一层，其他层必满，且叶子节点靠左。若左子树深度等于右子树，则左必为满，否则右必满。
总数目肯定在[2h,2h+1-1]内，2的幂运算可以用位运算代替 1 << h

思路1：只算最后一层，上层用公式 (1 << depth) - 1 计算，但是存在重复，计算层数，和计算叶子节点，会重复遍历子树；
思路2：因为总数目在单调递增区间内，考虑二分；如果mid存在，总数目肯定≥mid，否则＜mid；判断是否存在节点12，可以用12=1100(二进制)来确定，因为每层首节点必为偶数，所以最高位必为1，从次高位开始计算，1向右，0向左，最后到达该点，判断是否为空即可。