1.从合并两个有序数组谈归并排序
(1).需要额外的一个O(n)的数组去存放结果
(2).两个指针分别遍历两个待合并数组，谁小拿出谁，然后往下走。
递归的归并排序
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
解析
- 右移1位相当于除以2 。
- 核心在于如何将两个有序数组合并成有序的，然后将这个任务递归划分下去。
2.归并排序的思想完成小和问题
(1).左边求完小和，右边求完小和
(2).合起来的小和(如果左边的数小于右边的数)
static int SmallSum(int[] arr,int[] ret,int l,int r){
if(l==r)
return 0;
int mid = l + ((r - l) >> 1);
return SmallSum(arr,ret,l,mid)+SmallSum(arr,ret,mid+1,r)+merge(arr,l,mid,r);
}
public static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
解析：一分一合，左右有序，然后遍历求小和后，还要确保左右合成的新部分有序，逆序对的题亦然。
逆序对代码：
public int merge(int[] arr,int l,int mid,int r){
int p1=l;
int p2=mid+1;
int sum=0;
int[] tmp=new int[r-l+1];
int index=0;
while (p1<=mid && p2<=r){
if(arr[p1]>arr[p2]){
sum+=r-p2+1;
tmp[index++]=arr[p1];
p1++;
}else {
tmp[index++]=arr[p2];
p2++;
}
}
while (p1<=mid){
tmp[index++]=arr[p1];
p1++;
}
while (p2<=r){
tmp[index++]=arr[p2++];
}
for(int i=l;i<=r;i++){
arr[i]=tmp[i-l];
}
return sum;
}
3.栈与队列互相实现
1.栈实现队列：出栈时，先将n-1个元素放在另一个辅助栈中， 然后最后一个元素出栈，再将辅助栈的元素放回来。
2.队列实现栈：用一份辅助队列临时放元素
4.数组实现队列
从end进，start出
元素出队列时start++，当start走到底时，等于0
有元素进队列时end++，当end走到底时，等于0
5.排序的稳定性
稳定的排序：冒泡，插入，归并
不稳定的排序：选择，快排（可以稳定，但是这是论文级别的《0-1 stable sort》），堆排序
6.工程中的排序
综合性的，基础是快排，但是很短的时候用插入排序（代码复杂度极低，常数项很低）
相同值无差异时用快排，相同值有差异时用归并。
7.堆排序（注意两个基本操作，堆插入与堆筛选）
数组中第k个最大的元素（215）
8.桶排序，基数排序跟计数排序（都是稳定的，不基于比较的）
面试题：排序后相邻两数的最大值，要不基于比较的排序，O（N）复杂度的
思路：
N个数，准备N+1个桶 -> 至少有一个空桶 -> 相邻值绝对不会出现在同一个桶里 -> 每个桶记录一下最大值与最小值->则遍历一次桶，最大值就出来了。
9.转圈打印矩阵
宏观思想：
别想着从00开始，如何加加减减的变换，要提到一个更高层面去看：每转一圈，其实都是以左上右下两个对角线围成的矩形的打印。
int printEdge(int[] ret,int index, int[][] arr,int left,int top,int right,int down ){
int first=left;
int i=index;
while (first<=right){
ret[i++]=arr[left][first++] ;
//System.out.print(arr[left][first++]+" ");
}
first=top+1;
while (first<=down){
ret[i++]=arr[first++][right];
// System.out.print(arr[first++][right]+" ");
}
first=right-1;
while (first>=left && down!=top){
ret[i++]=arr[down][first--];
// System.out.print(arr[down][first--]+" ");
}
first=down-1;
while (first>top && left!=right){
ret[i++]=arr[first--][left];
//System.out.print(arr[first--][left]+"");
}
return i;
}
这样子就能沿着对角线，不断打印矩阵
10.Z字形打印矩阵
每次打印一条对角线，不断变化对角线的点即可。
11.反转链表
入门：
//pre指针的使用
public ListNode reverseList(ListNode head) {
ListNode pre=null,cur=head;
while (cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
进阶：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
12.二叉树的三种遍历方式6种代码：
1.前序递归：
public List<Integer> preorderTraversal(TreeNode root) {
if(root!=null){
l.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return l;
}
2.前序非递归
public List<Integer> preorderTraversal(TreeNode root) {
if (root != null) {
s.push(root);
while (!s.isEmpty()) {
TreeNode top = s.pop();
l.add(top.val);
if (top.right != null)
s.push(top.right);
if (top.left != null)
s.push(top.left);
}
}
return l;
}
解析：首先头结点压栈，当栈不为空时，取出栈顶元素，将栈顶元素的右先压，左后压，循环直到栈空，即可保证：自己->左->右的顺序
3.中序递归：
public List<Integer> inorderTraversal(TreeNode root) {
if(root!=null){
inorderTraversal(root.left);
l.add(root.val);
inorderTraversal(root.right);
}
return l;
}
4.中序非递归
public List<Integer> inorderTraversal(TreeNode root) {
if(root!=null){
while (!s.isEmpty() || root!=null){
if(root!=null){
s.push(root);
root=root.left;
}
//当前结点为空，也就是左边没东西了
else{
TreeNode head=s.pop();
l.add(head.val);
root=head.right;
}
}
}
return l;
}
解析：左中右的顺序，所以当左边不为空时，将整个左边压进去，当为空时，弹出栈顶，从栈顶的右边继续走，走不动就弹出栈顶。
5.后序递归
public List<Integer> inorderTraversal(TreeNode root) {
if(root!=null) {
inorderTraversal(root.left);
inorderTraversal(root.right);
l.add(root.val);
}
return l;
}
6.后序非递归
public List<Integer> inorderTraversal5(TreeNode root) {
if (root != null) {
s.push(root);
while (!s.isEmpty()) {
if (root.left != null)
s.push(root.left);
if (root.right != null)
s.push(root.right);
TreeNode head = s.pop();
s1.push(head);
root = head;
}
while (!s1.isEmpty()) {
l.add(s1.pop().val);
}
}
return l;
}
13.后继结点（中序遍历的最后一个）：左->中（自己）->右
因此：
1.如果有右子树 后继则是右子树最左的结点
2.没有右子树，则找哪个结点的左子树是自己（parent指针）
反之：
前驱结点：
1.左子树最右的结点
2.哪个结点的右子树是自己结尾
14.二叉树的序列化与反序列化（思想，以某种遍历方式存成字符串，按一定分隔符进行分割）
15.平衡二叉树（左右高度不大于1）
判断平衡性：
public boolean isBalanced(TreeNode root) {
if(root==null)
return true;
if(!isBalanced(root.left)){
return false;
}
if(!isBalanced(root.right)){
return false;
}
int leftH = getFlagHeigt(root.left);
int rightH = getFlagHeigt(root.right);
if(Math.abs(leftH-rightH)>1)
return false;
else
return true;
}
public int getFlagHeigt(TreeNode root){
if (root!=null){
return Math.max(getFlagHeigt(root.left),getFlagHeigt(root.right))+1;
}
return 0;
}
16.完全二叉树结点个数
if(root == null)
return 0;
if(root!=null) {
int leftH = 0, rightH = 0;
TreeNode head = root.left;
while (head != null) {
leftH++;
head = head.left;
}
head = root.right;
while (head != null) {
rightH++;
head = head.left;
}
if (leftH == rightH) {
//左子树满的
count += (int) Math.pow(2, leftH) - 1 + 1;
if (root.right != null)
countNodes(root.right);
} else if (leftH > rightH) {
//右子树是满的
count += (int) Math.pow(2, rightH) - 1;
if (root.left != null)
countNodes(root.left);
}
}
return count;
解析：左右子树高度
17. 单例模式的线程安全解法
18.数组中的重复数字，不用哈希表的解法（前提：N个数都在0到n-1之间）
将a[i]移动到a[i]这个位置上。
19 不改变原数组并且不使用额外空间：
例：[2,3,5,4,3,2,6,7]
长度为8的数组，数字在1~7之间：
取中间数字4，1~4出现了5次，则重复在这里，以此类推。
--------------------------------------------2020.04.16 12:59更新
20 哈希表等概率随机返回一个key
准备两个表：
记录 A 0 B 1 （value为index）
记录0 A 1 B （value为具体的值）
这样要随机返回时，就可以随机一个数，去表B找对应的value
但是需要注意，删除时会产生洞，导致不连续，因此：
A表：拿最后一条数据，替换删除的数据（主要是替换value）
B表：删除对应的key，更新A表替换的那一条的value
21 布隆过滤器
22 一致性哈希
(找个时间整理一下)
22
-------------------中级班-----------------------
1.LRU结构
1.1双向链表+ 哈希表结构(为了O（1）时间找到某个点)
import java.util.*;
class LRUCache {
HashMap<Integer, Node> map = new HashMap<>();
DoubleList list = new DoubleList();
public LRUCache(int capacity) {
list.capacitry = capacity;
}
public int get(int key) {
Node cur;
if (map.get(key) != null) {
cur = map.get(key);
list.remove(cur);
put(key,cur.val);
return map.get(key).val;
}
else
return -1;
}
public void put(int key, int value) {
Node newNode = new Node(key,value);
list.add(newNode);
}
public class DoubleList{
int capacitry;
int length = 0;
Node head = null;
Node tail = null;
public void add(Node a) {
if (map.get(a.key) != null) {
remove(map.get(a.key));
if (head == null) {
head = tail = a;
map.put(a.key, a);
}
else {
tail.next = a;
a.pre = tail;
tail = a;
map.put(a.key, a);
}
length ++;
} else {
if (length == capacitry)
removeFirst();
if (head == null) {
head = tail = a;
map.put(a.key, a);
length += 1;
}
else {
tail.next = a;
a.pre = tail;
tail = a;
map.put(a.key, a);
length += 1;
}
}
}
public void removeFirst(){
if (head != null){
map.remove(head.key);
head = head.next;
length --;
}
}
public void remove(Node n) {
if (n == head && n == tail) {
head = tail = null;
length--;
}
else {
if (n == head) {
head = head.next;
head.pre = null;
}
else if (n == tail) {
tail = tail.pre;
tail.next = null;
} else {
n.next.pre = n.pre;
n.pre.next = n.next;
}
length--;
}
map.remove(n.key);
}
}
public class Node{
int key;
int val;
Node pre;
Node next;
public Node(int key,int val){
this.key = key;
this.val = val;
this.pre = this.next = null;
}
}
}
2.跳跃游戏
step
curMaxRight 当前可以走到的最右边
nextMaxRight 下一步可以走到的最右边
3.交错子串
动态规划 建立以后一张二维表，将第一行第一列写填好 dp[i][j] =从上或者左任意一下true的情况，第i+j-1位用其中一个串的
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
boolean[][] map = new boolean[s1.length() + 1][s2.length() + 1];
map[0][0] = true;
for (int i = 0; i < s1.length();i++){
if (s1.substring(0,i+1) .equals(s3.substring(0,i+1)) )
map[i+1][0] = true;
else
map[i+1][0] = false;
}
for (int j = 0; j < s2.length();j++){
if (s2.substring(0,j+1).equals(s3.substring(0,j+1)))
map[0][j+1] = true;
else
map[0][j+1] = false;
}
for (int i = 1;i < map.length;i++){
for (int j = 1;j < map[i].length;j++){
if (map[i-1][j] == true && s3.charAt(i+j-1) == s1.charAt(i-1))
map[i][j] = true;
if (map[i][j] == false && map[i][j-1] == true && s3.charAt(i+j-1) == s2.charAt(j-1))
map[i][j] = true;
}
}
// for (int i = 0 ;i < map.length;i++){
// for (int j = 0; j < map[i].length;j++){
// System.out.print(map[i][j] +" ");
// }
// System.out.println();
// }
return map[map.length -1][map[0].length-1];
}
4.丑数(只有2,3,5三种因子)
判断是不是丑数： 一直除 2 3 5 看看最后是不是等于1
第n个丑数：第一个丑数为1 则下一个就是 1*2 1 *3 1 5中较小的那个，于是2的那个走到下一个（2）上
5. 最短无序子数组
从左往右遍历 知道最远的那个排错的数（他后面的都是对的）
从右往左遍历 知道最近的那个排错的数（他前面的都是对的）
于是这两个数之间就是要排序的
6.分割相等数组
[3,2,4,1,4,9,5，10,1,2,2]
每次缺人当前位置能不能作为第一刀，能则继续看第二刀能不能
image.png
如果当前位置能做第一刀 则前一个位置的前缀和一定要在后面出现，也就是后面需要一个 2 * X +cur 的前缀和，若是有，则那个位置的下一个位置 就是下一刀
7.最小不可组成和
例：[3,2,5] min = 2 max = 11
构建一个dp[i][j] 代表 只用前i个数字能否构建出j,
进阶：如果知道一定有1，如何更快？
6,1,4,2,15
1,2,4,6,15
当遍历到2的时候 我一定能组成1 到 3 的所有数
当遍历到4的时候 我一定能组成1到7的所有数
当遍历到6的时候，我一定能组成1到13的所有数
当看到15,？？？13+1 < 15 所以14丢了 答案为14
网友评论