Clay_Guo的博客

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 ...

动态规划问题分类 如果某一个问题有重叠的子问题，则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心算法 动态规划五部曲 确定dp数组以及下标的含义 确定递推公式 dp数组如何进行初始化 确定遍历顺序 举例推导dp数组 背包问题 01背包 完全背包 01背包 | 二维数组进行求解有n个物品和最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装进背包里面价值总和最大。 递归五部曲 确定dp数组含义 dp[i][j]表示从下标0-i的物品中任意选取，放进容量为j的背包中，价值总和最大是多少 确定递推公式 有两种情况： 不放物品 dp[i][j] = dp[i-1][j] 即当前dp数组的上一个的位置。这个含义就是，容量为j但是不放入i物品，只选择前i-1个物品 放物品 dp[i][j] = dp[i-1][j-weight[i]] + value[i]**。位于当前位置的左上方，不一定正好是左上角，有可能是左上角的前面的位置。这里的含义就是需 ...

贪心算法大纲题目分类大纲： 什么是贪心算法？贪心算法就是在每个阶段都选择局部最优解，从而达到全局最优。 贪心算法解题步骤 将问题分解为若干个子问题 找出合适的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解 练习题455、分发饼干 思路 遍历胃口和饼干列表，但是需要注意的是饼干列表不是每次都在移动，而是匹配了一个才会移动，因此这里不需要进行两层for循环，只需要一层for循环来遍历胃口列表即可。然后饼干列表可以使用一个指针index进行遍历，只有在能够进行匹配的情况下才需要将index进行移动。同时使用index来保存返回的结果。index可以直接用来当做最终的结果进行返回 利用贪心算法，每次都尽量喂饱胃口最大的，如果满足不了则往后移动判断能否满足下一个胃口最大的。 代码 12345678910class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: # 先满足大胃口 | 此时胃口在移动 g.sort(reverse= ...

回溯算法回溯算法是一种搜索的方法，在二叉树总结当中，经常使用到递归去解决相关的问题，在二叉树的所有路径问题中，我们就使用到了回溯算法来找到所有的路径。 回溯算法本质就是去穷举，性能并不是那么高效。一般为了提高效率，往往回溯算法会跟剪枝操作相结合。 回溯算法通常可以用来解决一些问题，这也是为什么会有回溯算法的原因 组合问题 N个数里面按照一定规则找出k个数的集合。组合不强调元素的顺序 切割问题 一个字符串按一定规则有几种切割方式 分割回文串 复原IP地址 子集问题 一个N个数的集合里有多少符合条件的子集 排列问题 N个数按照一定规则全排列，有几种排列方式。排列强调元素的顺序 棋盘问题 N皇后、解数独问题 理解回溯回溯法解决的问题都可以抽象为树形结构，回溯算法解决问题都是在集合中递归查找子集，集合的大小构成了树的宽度，递归的深度构成了树的深度。 递归必须要有终止条件，所以一定是一个高度有限的N叉树。 回溯模板递归三部曲： 返回值及参数 void backtracking(参数) 回溯函数的终止条件 回溯搜索的遍历过程 12345678910111 ...

二叉树二叉树的理论基础二叉树是结点的度数之和不超过2的树，二叉树总共有五种基本形态 二叉树的种类主要有： 满二叉树 完全二叉树 二叉树的存储方式 顺序存储 链式存储 二叉树的遍历方式 先序遍历（深度优先搜索） 中序遍历（深度优先搜索） 后序遍历（深度优先搜索） 层次遍历（广度优先搜索） 对于二叉树结点的定义： 12345class TreeNode: def __init__(self, val, left = None, right = None): self.val = val self.left = left self.right = right 二叉树的递归遍历先序遍历12345class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] return [root.val] + self.preorder ...

SRv6实验摘要：本文基于Linux SRv6功能，结合Mininet、Quagga、Python等工具，验证SRv6的一系列功能，包括VPN、流量工程、服务链等。 准备工作 Linux （推荐Ubuntu20.04） 最新版Mininet Quagga（在Mininet虚拟拓扑下，提供路由器的静态路由/OSPF/BGP等路由协议支持） Python（通过脚本建立测试拓扑及初试配置） 安装Quagga安装下载地址 https://src.fedoraproject.org/repo/pkgs/quagga/ 下载Quagga1.2.4版本 1wget https://src.fedoraproject.org/repo/pkgs/quagga/quagga-1.2.4.tar.gz/sha512/3e72440bcccfd3c1a449a62b7ff8623441256399a2bee0a39fa0a19694a5a78ac909c5c2128a24735bc034ea8b0811827293b480a2584a3a4c8ae36be9cf1fcd/quagga-1.2.4.tar. ...