算法

public ListNode ReverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode next = null; while(cur!=null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }

反转链表（单链表）

设计LRU缓存结构

最长无重复数组

public String solve (String str) { char[] ans = str.toCharArray(); int len = str.length(); for(int i = 0 ; i < len ;i++) { ans[i] = str.charAt(len-1-i); } return new String(ans); }

翻转字符串

public boolean hasCycle(ListNode head) { if (head == null) return false; //快慢两个指针 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }

判断链表是否有环

环形链表

合并两个有序链表

删除链表的倒数第N节点

相交链表

链表的中间节点

双指针

技巧

输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）；

一个MD5理论上的确是可能对应无数多个原文的，因为MD5是有限多个的而原文可以是无数多个

3.4*10^38

MD5目前最有效的攻击方式就是彩虹表

不同的输入得到的不同的结果（唯一性）；

超损压缩

MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

MD5

把3个8 bit 的二进制数转换成4个6字节的二进制数，而这4个6字节数，都是可见打印字符

BASE64

编码

归纳演绎法

插入排序

选择排序

希尔排序

快速排序

归并排序

堆排序

排序算法

多叉树的延伸

广度优先

全排列

N皇后

问题

路径：也就是已经做出的选择。

选择列表：也就是你当前可以做的选择。

结束条件：也就是到达决策树底层，无法再做选择的条件。

解决一个回溯问题，实际上就是一个决策树的遍历过程

回溯算法

深度优先

弗洛伊德算法（多源最短路径）

迪杰斯特拉算法

Bellman-Ford算法(解决负权边）

图的最短路径

找到一个岛屿、用海水淹没他

岛屿问题

图算法

暴力算法BF算法

哈希值进行比较的RK算法

最长可匹配后缀子串

最长可匹配前缀子串

数组的下标代表了“已匹配前缀的下一个位置“

元素的值则是“最长可匹配前缀子串的下一个位置”

next数组

KMP

字符串匹配

动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算

动态规划的核心问题是穷举

通项公式

递推公式

备忘录

DP table

状态转移方程

重叠子问题

最优子结构

三要素

斐波那契数列

凑零钱问题

最长递增子序列

最小编辑距离

01背包

背包9讲

动态规划

朴素的算法

解决分布式系统中负载均衡的问题，使用Hash算法让固定的一部分请求落到同一台服务器上，这样每台服务器固定处理一部分请求（并维护这些请求的信息），起到负载均衡的作用。

伸缩性很差

新增或者下线服务器机器时候，用户id与服务器的映射关系会大量失效

余数hash

各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置

数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

hash环

虚拟节点机制

数据倾斜

一致性hash

分布式算法

对称

加密算法

算法