Golang单机锁 sync.Mutex 核心机制 通过 Mutex 内一个状态值标识锁的状态,例如,取 0 表示未加锁,1 表示已加锁; 上锁:把 0 改为 1; 解锁:把 1 置为 0. 上锁时,假若已经是 1,则上锁失败,需要等他人解锁,将状态改为 0. 下面首先拎清两个概念: 饥饿模式:当 Mutex 阻塞队列中存在处于饥饿态的 goroutine 时,会进入模式,将抢锁流程由非公平机制转为公平机 2024-09-26 开发 #Go
trie树 定义 字典树,英文名 trie。顾名思义,就是一个像字典一样的树。 可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。 举个例子,1→4→8→121→4→8→121→4→8→12 表示的就是字符串 caa。 实现 12345678910111213141516171819202122232425262728293031323334353637383940414 2024-08-06 算法 #算法
线段树 简介 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 O(logN)O (log N)O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。 线段树将每个长度不为1的区间划分成左右两个区间递归求解,把整个线段划分为一个树形结构,通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。 过程 2024-07-26 算法 #算法
Squaring 题目链接: Problem - C - Codeforces 题目描述 ikrpprpp 发现了一个由整数组成的数组 aaa 。他喜欢公平,所以想让 aaa 变得公平,也就是让它不递减 为此,他可以对数组中的索引 1≤i≤n1≤i≤n1≤i≤n 进行公正操作,将 aia_iai 替换为 ai2a_i^2ai2 (位置 iii 的元素及其平方)。例如,如果 a=[2,4,3,3,5,3]a=[ 2024-07-24 算法 #题解
树状数组 简介 树状数组是一种支持 单点修改 和 区间查询 的,代码量小的数据结构。 普通树状数组维护的信息及运算要满足 结合律 且 可差分,如加法(和)、乘法(积)、异或等。 事实上,树状数组能解决的问题是线段树能解决的问题的子集:树状数组能做的,线段树一定能做;线段树能做的,树状数组不一定可以。然而,树状数组的代码要远比线段树短,时间效率常数也更小。 有时,在差分数组和辅助数组的帮助下,树状数组还可解决 2024-07-24 算法 #算法
背包问题 简介 背包问题(英语:Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中,背包的空间有限,但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中,决策者必须分别从一组不可分割的项目或任务中进行选择,而这些 2024-07-16 算法 #算法
拓扑排序 定义 拓扑排序(Topological sorting)要解决的问题是如何给一个有向无环图的所有节点排序。 拓扑排序的目标是将所有节点排序,使得排在前面的节点不能依赖于排在后面的节点。 例如著名的造计算机游戏 Turing Complete 中的关卡,如下图箭头所指,你只有在完成前面三关后才可以解锁箭头所指的关卡。拓扑排序要完成的就是这样一个功能,前面的关卡不能依赖于排在后面的关卡,也就是说排完序 2024-07-15 算法 #算法
课程安排 题目链接: [传智杯 #2 决赛] 课程安排 - 洛谷 题目描述 传智播客的课表上按顺序提供 nnn 节课程,课程可能是 Java、Python 或者前端开发等等,我们用不超过 nnn 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列,作为一周的学习任务。 为了使学习任务不那么枯燥,学员不想连续上两节相同的课。特殊的,这一周学习任务的开头和结尾也不能是相同的课。为了保 2024-07-04 算法 #题解
打字练习 题目链接: 打字练习 - 洛谷 题目描述 R 君在练习打字。 有这样一个打字练习网站,给定一个范文和输入框,会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和 .(英文句号),输入字符后,光标也会跟着移动。 输入的文本有多行,R 君可以通过换行键来换行,换行后光标移动到下一行的开头。 R 君也可以按退格键(为了方便,退格键用 < 表示),以删除上一个打的字符,并将光标回移 2024-07-04 算法 #题解
[AHOI2018初中组] 分组 题目链接: [AHOI2018初中组] 分组 - 洛谷 题目描述 小可可的学校信息组总共有 nnn 个队员,每个人都有一个实力值 aia_iai 。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 nnn 个队员分成若干个小组去参加这场比赛。 但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不 2024-07-03 算法 #题解