type
status
date
slug
summary
tags
category
icon
password
一些常用的算法整体总结
数组：
1.二分查找
- [left,right]
- [left,right)
- 边界[left,right]
2.双指针（移除元素）
数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖
3.滑动窗口（调节子序列的起始和终止位置）
用队列模拟或者直接用数值模拟
4.循环不变量写多重循环
链表：
1.虚拟头节点（删除节点）
2.双指针
（删除链表的倒数第N个节点）
（环形链表）
3.双向链表＋哈希表（LRU）
哈希表：来快速判断元素是否出现在集合里（众数）
两个key映射到一个value上就叫哈希碰撞（拉链法，线性探测法）
字符串：可以反转整体再反转局部
二叉树：
最大深度和最小深度（都可以用层序遍历来做）
无法自身判定是否符合条件的时候，多考虑父子关系：
难题：
1.二叉树的最近公共祖先（从上往下考虑，遇见符合的return）
2.删除二叉树的节点（考虑删除的节点子情况）
贪心：
在考虑两个区间值的时候，要用双指针
跳跃游戏2
动态规划：
1.不同路径2：需要考虑到初始化障碍之后都不能前进
2.不同的二叉搜索树：从头节点看左右节点，即是Dp[1]=dp[0]*dp[0]
01背包问题：
模板：dp[j]代表背包j所能包含物品i最大的价值
遍历：先物品后背包，且背包遍历时从后至前的，不然前面的物品会多次使用dp[j]=max(dp[j],dp[j-weight[i]+value[i]])//普通公式
dp[j]=max(dp[j],dp[j-nums[i]+nums[i])//计算无价值
dp[i]+=dp[j-nums[i]];//计算有几种方法,dp[0]=1(背包）
完全背包问题：
1.排列问题：先背包后物品，所有物品都需要遍历一次
2.组合问题：先物品后背包，不需要重复遍历
题目：单词拆分，确定dp[j],在确定（i-j),最后得知dp[i]是true
- 作者:Camellia
- 链接:https://qiudehao.life/article/f496359b-199b-4604-8e8a-a00845a0b94c
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章