# 水塘抽样

Leetcode 382

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

## Random Pick Index

Leetcode 398

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

# 线段树

## Count of Smaller Numbers After Self

Leetcode 315

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

# 子串和满足条件的最短长度

## Minimum Size Subarray Sum

Leetcode 209

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

## 上一题数组中包含正负，找和为target的最小长度

Leetcode 862

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Example 2:

Example 3:

# 快排相关

## 快排优化

• 基准随机化算法

• 将前后中间三个数取中值作为标兵元素

• 在数组大小等于一定范围的时候，改为插入排序，防止排序退化
• 将相等的数字聚集到一起，然后跳过此处的排序

# 牛顿法

Leetcode 69

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Example 2:

# 快速幂

## Pow(x, n)

Leetcode 50

Implement pow(x, n), which calculates x raised to the power n (xn).

# 全排列相关

Leetcode 60

## 字母全排列

1. 从最后向前找相邻的两个元素是的i < ii
2. 然后再从最后向前找一个元素使得i < j
3. i和j交换，然后将ii之后的元素reverse排序

nextPermutation的头文件是algorithm

M=
| |A |B |C |
|—-|:–:|:–:|:–:|
|A |B,C |C |A |
|B |A,C |C |C |
|C |A |A |A,B |

S={A,B,C}