[TOC]
快速幂（迭代）
public double myPow(double x, int n) {
long N = Math.abs((long)n);
double ans = 1;
while(N > 0){
if((N & 1) == 1){
ans *= x;
}
x *= x;
N /= 2;
}
return n >= 0 ? ans : 1 / ans;
}
快速幂（递归）
public double dfs(double x, long n){
if(n == 0){
return 1;
}
double y = dfs(x, n / 2);
return (n & 1) == 1 ? y * y * x : y * y;
}
public double myPow(double x, int n) {
long N = Math.abs((long)n);
return n < 0 ? 1 / dfs(x, N) : dfs(x, N);
}
快速乘（实际运用需要考虑溢出）
public long quickAdd(int x, int n) {
long N = Math.abs((long) n);
long ans = 0;
while(N > 0){
if((N & 1) == 1){
ans += x;
}
x += x;
N /= 2;
}
return n < 0 ? -ans : ans;
}
一个长度为k的窗口，求最大的一个窗口
public int[] maxSumOfOneSubarray(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[1];
int win = 0, maxWin = 0;
for (int i = 0; i < n; i++) {
win += nums[i];
if (i >= k - 1) {
if (win > maxWin) {
maxWin = win;
ans[0] = i - k + 1;
}
win -= nums[i - k + 1];
}
}
return ans;
}
三个长度为k的窗口，互不重叠，求三个窗口的最大值（需要反复理解）
其实本质相当于一个长度为3 * k的大窗口遍历整个数组。
首先，win3需要知道win1和win2什么时候是最优解，当win3 + max(win1 + win2)为最大时，更新对应下标。
其次，win2需要知道win1什么时候是最优解，当win2 + max(win)为最大的时候，更新对应下标。
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int win1 = 0, win2 = 0, win3 = 0;
int maxWin1 = 0, maxWin12 = 0, maxWin123 = 0;
int maxWin1Index = 0, maxWin12Index0 = 0, maxWin12Index1 = 0;
int[] ans = new int[3];
for(int i = k * 2 ; i < n; i++){
win1 += nums[i - k * 2];
win2 += nums[i - k];
win3 += nums[i];
if(i >= k * 3 - 1){
if(win1 > maxWin1){
maxWin1 = win1;
maxWin1Index = i - 3 * k + 1;
}
if(maxWin1 + win2 > maxWin12){
maxWin12 = maxWin1 + win2;
maxWin12Index0 = maxWin1Index;
maxWin12Index1 = i - 2 * k + 1;
}
if(maxWin12 + win3 > maxWin123){
maxWin123 = maxWin12 + win3;
ans[0] = maxWin12Index0;
ans[1] = maxWin12Index1;
ans[2] = i - k + 1;
}
win1 -= nums[i - 3 * k + 1];
win2 -= nums[i - 2 * k + 1];
win3 -= nums[i - 1 * k + 1];
}
}
return ans;
}
字典序的下一个排列（lc.31）
首先，如果是完全逆序的数组，那么这个值一定是最大的，直接逆序即可，如果不完全逆序，则说明它还有更大的下一个排列。
逆序意味着最大，所以改动点必不可能在逆序中，改动逆序子序列意味着这个排列是比当前小的。
所以先找到最右侧的第一个升序，此处为改动点1。（比如127431，2为改动点1）
其次找到改动点1之后，找离他右侧最远的大于它的改动点2，因为越右这个数影响越小。（比如127431，3为改动点2）
交换这两个改动点的值。（比如127431，交换完为137421）
最后由于交换完可能乱序，将改动点1之后所有的值逆序排序。
public void nextPermutation(int[] nums) {
int n = nums.length;
int one = -1, two = -1;
for(int i = n - 2; i >= 0; i--){
if(nums[i + 1] > nums[i]){
one = i;
break;
}
}
if(one == -1){
reverse(nums, 0, n - 1);
return;
}
for(int i = one + 1; i < n; i++){
if(nums[i] > nums[one]){
two = i;
}
}
swap(nums, one, two);
reverse(nums, one + 1, n - 1);
}
public void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public void reverse(int[] arr, int i, int j){
while(i < j){
swap(arr, i++, j--);
}
}
最长重复子数组（lc.718）
DP省时间，滑窗省空间。
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[][] dp = new int[n + 1][m + 1];
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(nums1[j - 1] == nums2[i - 1]){
dp[i][j] = 1 + dp[i - 1][j - 1];
ans = Math.max(ans, dp[i][j]);
}
}
}
return ans;
}
判断有向图有无环(lc.207)
关键在于vis数组，0代表未访问，1代表正在搜索，2代表搜索完。
如果当前搜索到的节点的邻接点为1，那说明有环。
另外，在图问题中，要考虑对重复路径进行记忆化搜索，保存每个节点的最优解。
class Solution {
List<List<Integer>> edges;
int[] vis;
boolean valid;
public boolean canFinish(int numCourses, int[][] prerequisites) {
this.edges = new ArrayList();
this.vis = new int[numCourses];
this.valid = true;
for(int i = 0; i < numCourses; i++){
edges.add(new ArrayList());
}
for(int[] line : prerequisites){
edges.get(line[1]).add(line[0]);
}
for(int i = 0; i < numCourses && valid; i++){
if(vis[i] == 0){
dfs(i);
}
}
return valid;
}
public void dfs(int course){
vis[course] = 1;
for(int next : edges.get(course)){
if(vis[next] == 1){
valid = false;
return;
}else if(vis[next] == 0){
dfs(next);
if(!valid){
return;
}
}
}
vis[course] = 2;
}
}
LIS
传统DP时间O(n^2)，不比比。
优化贪心+二分时间O(nlogn)：
对于一个最长的上升序列，它的上升幅度应该尽量的小，因此希望每次在上升子序列后面加上的值尽可能小。
用数组d[i]表示长度为i的子序列末尾的最小值，数组有序。
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int maxLen = 0;
for(int num : nums){
int low = 0, high = maxLen - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(dp[mid] < num){
low = mid + 1;
}else{
high = mid - 1;
}
}
dp[low] = num;
maxLen = Math.max(maxLen, low + 1);
}
return maxLen;
}
}
螺旋矩阵（lc.54）
顺时针方向，可以不用direction数组。访问过则修改，越界或访问过就改方向。
很好的模板题，顺时针方向变化也可以不用directions数组优化一下。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
List<Integer> ans = new LinkedList();
int x = 0, y = 0, dx = 0, dy = 1;
for(int i = 0; i < m * n; i++){
ans.add(matrix[x][y]);
matrix[x][y] = 101;
if(x + dx < 0 || x + dx >= m || y + dy < 0 || y + dy >= n || matrix[x + dx][y + dy] == 101){
int tmp = dx;
dx = dy;
dy = -tmp;
}
x += dx;
y += dy;
}
return ans;
}
}
并查集
class U {
int[] fa, rank;
U(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
rank = new int[n];
Arrays.fill(rank, 1);
}
public int find(int x) {
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
public void merge(int i, int j) {
int x = find(i), y = find(j), r1 = rank[x], r2 = rank[y];
if (r1 <= r2) {
fa[x] = y;
} else {
fa[y] = x;
}
if (r1 == r2 && x != y) {
rank[y]++;
}
}
}
二叉树的前序遍历和二叉树的中序遍历
List<Integer> ans = new ArrayList();
Deque<TreeNode> q = new LinkedList();
while(q.size() != 0 || root != null){
//从起点无限向左走
while(root != null){
q.addLast(root);
ans.add(root.val); //add在这就是前序
root = root.left;
}
//无路可走，取出头部
root = q.pollLast();
ans.add(root.val); //add在这就是中序
//以该头部right为新起点
root = root.right;
}
return ans;
二叉树的后序遍历
List<Integer> ans = new ArrayList();
Deque<TreeNode> q = new LinkedList();
TreeNode pre = null;
while(q.size() != 0 || root != null){
while(root != null){
q.addLast(root);
root = root.left;
}
root = q.pollLast();
//后序需要特别处理
//如果右侧为空或者右侧访问过了，就是答案
if(root.right == null || root.right == pre){
ans.add(root.val);
pre = root;
root = null;
}else{ //如果右侧不为空并且没访问过，那得把刚刚poll出来的root再放回去继续遍历
q.addLast(root);
root = root.right;
}
}
return ans;
手撕优先队列
class PQ<T> {
Object[] value;
int size;
int capacity;
Comparator comparator;
PQ(int capacity, Comparator<T> comparator) {
this.size = 0;
this.capacity = capacity;
this.value = new Object[capacity];
this.comparator = comparator;
}
public void add(T v) {
if (size == capacity) {
capacity *= 1.5;
value = Arrays.copyOf(value, capacity);
}
value[size++] = v;
int idx = size - 1;
int fa = (idx - 1) / 2;
while (comparator.compare(value[idx], value[fa]) < 0) {
swap(value, idx, fa);
idx = fa;
fa = (idx - 1) / 2;
}
}
public T poll() {
T ret = (T) value[0];
value[0] = value[--size];
updateFromTop(0);
return ret;
}
public void updateFromTop(int i) {
int left = i * 2 + 1, right = i * 2 + 2, small = i;
if (left < size && comparator.compare(value[left], value[small]) < 0) {
small = left;
}
if (right < size && comparator.compare(value[right], value[small]) < 0) {
small = right;
}
if (small != i) {
swap(value, i, small);
updateFromTop(small);
}
}
public boolean isEmpty() {
return size == 0;
}
private void swap(Object[] arr, int i, int j) {
Object tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
