蓄水池抽样算法（Reservoir Sampling）

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出K个不重复的数据。

int[] result = new int[K];
for (int i = 0; i < K; i++) { // 前 K 个元素直接放入数组中
 	result[i] = pool[i];
}

for (int i = K; i < N; i++) { // K + 1 个元素开始进行概率采样
  int r = random.nextInt(i + 1);
  if (r < K) {
 	 result[r] = pool[i];
  }
}

最大公约数，最小公倍数

求最小公倍数需要最大公约数

// 最小公倍数
private long lcm(long a, long b) {
	return a * b / gcd(a, b);
}
    
// 最大公约数
private long gcd(long x, long y) {
  if (x == 0) return y;
  return gcd(y % x, x);
}

枚举二进制子集

// m => 总状态数
for (int i = 1; i < m; i++) {
    // 枚举状态 i 的二进制子集
    for (int j = i; j > 0; j = (j - 1) & i) {
        // To Do..
    }
}

最长上升子序列（Longest Increasing Subsequence）

// 动态规划 O(n2)
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
    		return 0;
    }
    int[] dp = new int[nums.length];
    // 最小值都为1
    Arrays.fill(dp, 1);

    int max = 0;
    // 遍历前面的所以数字
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
          if (nums[j] < nums[i]) {
            // 当小于当前值时,取最大的数量
            dp[i] = Math.max(dp[i], dp[j] + 1);
            max = Math.max(max, dp[i]);
          }
        }
    }
    return max;
}



    // 二分 贪心 O(n*logn)
    public int lengthOfLIS(int[] nums) {
        int ans = 0;
        // 最长上升子序列（Longest  Increasing Subsequence）
        int[] lis = new int[nums.length];
        int index = 0;
        for (int num : nums) {
            if (index == 0) {
                // 初始化子序列
                lis[index++] = num;
                continue;
            }

            if (num > lis[index - 1]) {
                // 大于直接添加到尾部
                lis[index++] = num;
                continue;
            }


            // 二分找第一个大于当前值的索引
            int left = 0, right = index - 1;
            while (left < right) {
                // 找左边中位数
                int mid = (left + right) / 2;
                if (lis[mid] < num) {
                    // 继续找右边的
                    left = mid + 1;
                } else {
                    // 可能是目标
                    right = mid;
                }
            }

            // 替换掉
            lis[right] = num;
        }

        return index;
    }