算法
2023-05-09 15:00:33 0 举报AI智能生成
朴素算法（非人工智能）脑图
作者其他创作
大纲/内容
技巧
反转链表（单链表）
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 int maxLength (int[] arr) {
Queue<Integer> queue = new LinkedList<>();
int res = 0;
for (int c : arr) {
while (queue.contains(c)) {
queue.poll();
}
queue.add(c);
res = Math.max(res, queue.size());
}
return res;
}
翻转字符串
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节点
相交链表
链表的中间节点
编码
MD5
输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）；
不同的输入得到的不同的结果（唯一性）；
一个MD5理论上的确是可能对应无数多个原文的，因为MD5是有限多个的而原文可以是无数多个
3.4*10^38
MD5目前最有效的攻击方式就是彩虹表
超损压缩
MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
BASE64
把3个8 bit 的二进制数转换成4个6字节的二进制数，而这4个6字节数，都是可见打印字符
朴素的算法
归纳演绎法
排序算法
插入排序
选择排序
希尔排序
快速排序
归并排序
堆排序
图算法
多叉树的延伸
图的最短路径
广度优先
深度优先
回溯算法
问题
全排列
N皇后
解决一个回溯问题，实际上就是一个决策树的遍历过程
路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。
弗洛伊德算法（多源最短路径）
迪杰斯特拉算法
Bellman-Ford算法(解决负权边）
问题
岛屿问题
找到一个岛屿、用海水淹没他
字符串匹配
暴力算法BF算法
哈希值进行比较的RK算法
KMP
最长可匹配后缀子串
最长可匹配前缀子串
next数组
数组的下标代表了“已匹配前缀的下一个位置“
元素的值则是“最长可匹配前缀子串的下一个位置”
动态规划
动态规划的核心问题是穷举
动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算
三要素
状态转移方程
递推公式
通项公式
备忘录
DP table
重叠子问题
最优子结构
问题
斐波那契数列
凑零钱问题
最长递增子序列
最小编辑距离
背包9讲
01背包
分布式算法
一致性hash
解决分布式系统中负载均衡的问题，使用Hash算法让固定的一部分请求落到同一台服务器上，这样每台服务器固定处理一部分请求（并维护这些请求的信息），起到负载均衡的作用。
余数hash
伸缩性很差
新增或者下线服务器机器时候，用户id与服务器的映射关系会大量失效
hash环
各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置
数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
数据倾斜
虚拟节点机制
加密算法
对称
0 条评论
下一页
