Clay_Guo的博客

LRU算法 原理LRU（Leasted Recently Used）缓存机制可以通过哈希表和辅助双向链表实现 双向链表按照被使用的顺序存储了键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。 哈希表存储数据的键映射到其在双向链表中的位置。 逻辑： 针对get操作： 先判断哈希表cache中是否存在该key 如果不存在则直接返回-1 如果存在，则将通过哈希表找到对应的结点并将该结点删除（removeNode）并在开头添加一个结点(（addToHead)，其中删除和添加操作只需要修改指针，因此时间复杂度为O(1)满足题目要求 针对put操作： 判断哈希表cache中是否存在该key 如果不存在该key则 先以该key、value为键值对构建一个双向链表node 将该结点node添加到链表的开头（addToHead) 然后在哈希表中添加键key和值node 将self.size+1，并判断当前size大小是否超过capacity 如果没有超过则不进行任何操作 如果超过了，则需要进行淘汰，将双线链表的末尾的结点删除并将其对应的key从哈希表中删除 如果存 ...

哈希表用途：用于快速判断一个元素是否出现在集合里 可以做到O(1)的时间复杂度 哈希函数哈希碰撞将两个元素都映射到索引相同的位置，这一现象叫做哈希碰撞。 解决办法 拉链法 线性探测法 练习题242、有效的字母异位词 Python便捷解法： 1234class Solution: def isAnagram(self, s: str, t: str) -> bool: from collections import Counter return Counter(s)==Counter(t) 两个数组的交集12345class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) set2 = set(nums2) return list(set1&set2) 202、快乐数1234567891011121314151617c ...

常见设计模式总结工厂模式单例模式

链表链表的定义链表是一种通过指针串联在一起的数据结构，每个节点由两个部分组成，一个是数据域，一个是指针域（存放指向下一个地址的指针），最后一个节点的指针域为空NULL。 链表的入口节点被称为链表的头结点，即head 首先定义单个结点的结构 12345class ListNode: def __init__(self, val): self.val = val self.next = None 单个结点中，包含了一个结点值和下一个结点的指针域 整体代码如下： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051class ListNode: def __init__(self, val): self.val = val self.next = Noneclass MyLinkedList: def __init__(self): self.size = 0 ...

LinkedList底层源码分析LinkedList集合底层数据结构是双链表，查询慢，增删快，但如果操作的是首尾元素，速度也是极快的。 特有的API 底层原理LinkedList底层是双向链表结构 节点对象Node的定义如下 核心步骤如下： 刚开始创建的时候，底层创建了两个变量：一个记录头结点first，一个记录尾结点last，默认都为null 添加第一个元素时候，底层创建一个结点对象，first和last都记录这个结点的地址值 添加第二个元素时候，底层创建一个结点对象，第一个结点会记录第二个结点的地址值，last会记录新结点的地址值。 源代码流程：

ArrayList底层源码分析 底层原理 创建使用ArrayList<>()创建空对象的时候，会在底层创建一个长度为0的数组。该数组的名称为elementData，定义变量size size变量有两层含义 ① 表示元素的个数，也就是集合的长度 ② 表示下一个元素的存入位置 添加第一个元素之后，size++，同时底层会创建一个新的长度为DEFAULT_CAPACITY=10的数组 扩容机制1： 当存满的时候，会创建一个新的数组，新数组的长度是原来的1.5倍，也就是长度为15。再把所有的元素拷贝到新数组中。如果继续添加数据，这个长度为15的数组也满了，那就会继续按照相同的方式扩容1.5倍。 扩容时机2： 当使用例如addAll()这样的方法一次性添加多个数据，扩容1.5倍的方法不够用时，则以扩容的实际大小为准。 成员变量： 123456789private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {
...

单调栈通常针对一维数组的问题，如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置，就可以使用单调栈，时间复杂度为O(n) 单调栈的本质是空间换时间， 遍历的过程中需要使用一个栈记录右边第一个比当前元素高的值。优点是整个数组只需要遍历一次。 使用单调栈需要明确的几点： 单调栈中存放的元素是什么？ 单调栈里的元素是递增还是递减？ 单调栈中的元素可以是递增的也可以是递减的，具体需要看题目的需求。 单调栈中存放的元素最好是下标，这样具有更好的泛型 练习题739、每日温度 使用单调栈的方式从前往后进行遍历； 栈中的元素从栈底到栈顶对应下标的值是递减的，直到找到一个比栈顶元素大的值，然后出栈。 栈中存放的是元素的下标，如果出现一个新的元素比栈中元素都要大的时候，就对栈中元素进行循环遍历，将其对应的res值修改为当前元素的下标和栈中存放的值的差值，这就是最终结果，到最后一个元素的时候，因为初始化结果列表中元素值都是0，故不需要进行修改。 初始化答案res为全0的列表，这样可以防止后面的元素没有下一个更大的元素，当然这一点要根据题目的要求来，因为有些题目会赋值为-1。 123456 ...

统计已测试设备 12345678910class Solution: def countTestedDevices(self, batteryPercentages: List[int]) -> int: res = 0 for i in range(len(batteryPercentages)): if batteryPercentages[i] > 0: res += 1 for j in range(i + 1, len(batteryPercentages)): batteryPercentages[j] = max(0, batteryPercentages[j] - 1) # print(batteryPercentages) return res 双模幂运算 12345678class Solution: def getGoodIndices(self ...

程序员面试宝典作者 Clay_Guo 零、前言 本文档是基于本人在2020秋招以及2021秋招过程中的面试经验，希望可以帮助到有需要的人进行面试的准备，当然由于本人能力有限，文档部分如果不正确的地方也请不领赐教。联系邮箱：guoyinzhi@foxmail.com 一、自我介绍自我介绍保持在三分钟左右即可，简洁明了，让面试官知道你自己的长处在哪，可以适当的说一些项目经历。 运维开发（SRE）工程师自我介绍中文面试官你好，我叫xxx，我的本科的专业是软件工程，在校期间我学过的课程有C语言，数据结构，操作系统，计算机网络，数据库、设计模式、java 、java-web，C#等课程。我个人大二大三课余时间学习过系统（主要是Red Hat操作系统）和网络相关的知识，然后考了RHCE的证书。平时的话也会倒腾自己在阿里云上租的一台云服务器（搭建博客、图床、FTP服务器等、在线Jupyte ...

力扣散题集合简单1200、最小绝对差 提示中可以得知数据量在10^5^，如果使用两层for循环判断必定超时，因此本题不能使用双层for循环进行判断 思路： 对arr进行排序 因为要判断最小绝对差，所以只需要对排序后的数字进行判断相邻两数的差值即可，如果小则更新否则不更新 123456789101112class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: min_ = float("inf") res = [] arr.sort() # 排序之后从前往后进行遍历 排序之后找最小差值 只需要在相邻的两个数之间进行寻找判断即可 for i in range(1,len(arr)): if min_ > abs(arr[i]-arr[i-1]): min_ = abs(arr[i]-arr[i-1]) r ...