Clay_Guo的博客

动态规划问题分类 如果某一个问题有重叠的子问题，则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心算法 动态规划五部曲 确定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. ...

位运算首先介绍一下常见位运算的符号（通常在各个编程语言中位运算的符号都是相似的） 运算符 描述 & 按位与运算，参与运算的两个值如果二进制对应位置都为1结果为1，否则为0 | 按位或运算，参与运算的两个值如果二进制对应位置有一个为1结果为1，两个均为0结果才为0 ^ 按位异或运算，当两个二进制位置对应位置不同时，结果为1，否则为0 ~ 按位取反运算，对数据的每个二进制位置取反，把0变为1，把1变为0 << 左移运算符：运算数的各位二进制全部左移若干位，由<<符号右边的数字决定左移多少位，高位丢弃，低位自动补0 >> 右移运算符：运算数的各位二进制全部右移若干位，由>>符号右边的数字决定右移多少位。 位运算在力扣中有很多题目的应用，位运算通常都是常数级别的时间复杂度 按位与（&）、按位或（|）、按位异或（^）等基本位运算的时间复杂度是 O(1)，它们在一个常数时间内完成。 位左移（<<）**和**位右移（>>）运算的时间复杂度也是 O(1)，因为它们只是在二进制 ...

API版本在开发过程中可能会有多版本的API，因此需要对API进行管理。django drf中对于版本的管理也很方便。 http://www.example.com/api/v1/info http://www.example.com/api/v2/info 上面这种形式就是很常见的版本管理 在restful规范中，后端的API需要体现出版本 在django drf中，共有三种形式的版本管理 通过GET参数传递 通过URL路由进行传递 通过请求头进行传递 下面将对这三种方法逐一介绍 1、通过get请求传递版本信息视图函数代码 1234567891011121314from rest_framework.views import APIViewfrom rest_framework.response import Responsefrom rest_framework.versioning import QueryParameterVersioningclass HomeView(APIView): versioning_class = QueryParameterVersion ...

CloudSim安装与测试用例运行0、CloudSim简介 CloudSim是由澳大利亚墨尔本大学的网格实验室和Gridbus项目共同推出的开源云计算仿真平台； CloudSim是基于Java语言开发的，可实现跨平台运行； CloudSim有助于加快面向云计算平台的算法设计与测试速度，可降低开发的成本； 用户可以通过CloudSim提供的众多核心类来进行大规模的云计算基础设施的建模与仿真。 1、准备工作 一台Windows操作系统的电脑 Java配置 Maven下载与配置 工具下载（下面两个都可以，二选一即可） Eclipse IDEA（推荐） CloudSim下载（本次实验使用CloudSim 5.0） 注：以上所有软件的安装包均可在百度网盘中下载 链接：https://pan.baidu.com/s/12JT4gDKbOLvHIeqyGbgE6A提取码：3fd5 1.1 Java配置首先需要再本地配置好Java的环境，这里不过多赘述，可以参考下面的教程 注：本文中使用的是jdk8的版本 1.1.1 安装Java8双击下载好百度网盘中的文件，选择你的安装路径即可 ...