Harry's Blog
博客
分类
标签
归档
友链
关于
博客
分类
标签
归档
友链
关于
Harry 的个人空间
博客
分类
标签
归档
关于
算法(8): LRU 策略
LeetCode No.146 LRU缓存机制 LRU(Least Recent Used)策略:优先淘汰最近最少使用的数据,常用于缓存淘汰机制,如Linux系统的内存淘汰、Redis的缓存淘汰等。 基于哈希表和双向链表实现LRU核心思路是,利用双向链表存储键值对,哈希表存储键在链表中对应的节点指针,如下图所示 这样的好处是使访问和更新操作时间复杂度都在O(1)。 PUT操作 判断哈希表中k...
2023-03-19
算法
算法
阅读全文
算法(7): 动态规划
动态规划的关键思想在于将问题转换成较小的子问题,然后根据子问题的结果总结出一个状态转移方程,最后得到整个问题的解 7.1 打家劫舍LeetCode No.198 问题描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非...
2023-03-19
算法
算法
阅读全文
算法(6): 贪心算法
分治的思想为将大问题分解为子问题,子问题再分解为更小的子问题,直到不能再拆分,然后再合并子问题的结果,通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述:给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路:根据二叉搜索树的特点,左子树的所有节点值均小于根节点,右子树的所有节点值均大于根节点,同时对于每一...
2023-03-19
算法
算法
阅读全文
算法(5): 分治/归并
分治的思想为将大问题分解为子问题,子问题再分解为更小的子问题,直到不能再拆分,然后再合并子问题的结果,通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述:给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路:根据二叉搜索树的特点,左子树的所有节点值均小于根节点,右子树的所有节点值均大于根节点,同时对于每一...
2023-03-19
算法
算法
阅读全文
算法(4): 搜索
3.1 深度优先DFS 问题1:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。Input: “23”Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] 思路:深度优先搜索,从根节点到每个叶子节点的所有路径即结果,深度为子串的长度...
2023-03-19
算法
算法
阅读全文
算法(3): 二分查找
二分查找是一种在有序列表中查找元素的高效方法,时间复杂度(logN),二分查找思路和时间都比较简单,但是实际问题中的细节不可忽视。 3.1 搜索插入位置LeetCode No.35 问题描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置,你可以假设数组中无重复元素。 思路:按照二分查找法,定义low,high两个指...
2023-03-19
算法
算法
阅读全文
算法(2): 排序
2.1 快速排序 题目描述:实现快速排序 思路:采用交换法,选第一个数为基准数pivot,在pl <= pr的前提下,指针pl从基准数+1的位置向右走,直到碰到比pivot大的数,指针pr从最右边向左走,直到碰到比pivot小的数,交换arr[pl], arr[pr],循环结束时pr = pl - 1,将基准数和pr交换。递归调用对基准数位置两边的区间调整。 示...
2023-03-19
算法
算法
阅读全文
算法(1): 双指针
双指针通常用在有序数组,链表的数据结构上,根据题目条件移动对应的指针。比如判断子串、链表是否有环的问题。 1.1 最长子串LeetCode No.524 题目描述:给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串输入:s = “abpcpl...
2023-03-19
算法
算法
阅读全文