树状数组+线段树
问题分析树状数组和线段树是两种非常常用的数据结构,那么他们分别是用于什么问题呢?这里借用一位力扣大佬的总结:
数组不变,求区间和:「前缀和」、「树状数组」、「线段树」
多次修改某个数(单点),求区间和:「树状数组」、「线段树」
多次修改某个区间,输出最终结果:「差分」
多次修改某个区间,求区间和:「线段树」、「树状数组」(看修改区间范围大小)
多次将某个区间变成同一个数,求区间和:「线段树」、「树状数组」(看修改区间范围大小)
这样看来,「线段树」能解决的问题是最多的,那我们是不是无论什么情况都写「线段树」呢?
答案并不是,而且恰好相反,只有在我们遇到的问题,不得不写「线段树」的时候,我们才考虑线段树。
因为「线段树」代码很长,而且常数很大,实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。
总结一下,我们应该按这样的优先级进行考虑:
简单求区间和,用「前缀和」
只要求最终结果,用「差分」
多次将某个区间变成同一个数,用「线段树」
其他情况,用「树状数组」
(作者:AC_OIer,链接:https://leetcode-cn.com/problems/range-su ...
如何下载网页上的直播视频
前言昨天接到了一个任务,给一个会议录屏。由于笔者的失误,导致环境声音也被录了进去。不过幸好有回放。但是下一个问题又来了。这个回放依然是直播形式的。也就是说,这个视频是由许多个长度只有几秒的小视频组合而成,并不能直接下载。
解决方法笔者找到了一种可以下载这种视频的方法,亲测有效。其实思路非常简单直接,就是将所有的这些小片段全部下载下来再拼到一起。好,现在思路有了,具体如何实现呢?可以分下面几个步骤。每个步骤的解决方法和实现可能有多种形式,笔者只介绍自己这次用的。
1. 抓取m3u8文件首先,我们需要先找到这场直播的网页中的m3u8格式的文件。这个文件会首先被发送过来。如果把接下来服务器端传过来的几百上千个ts文件(也就是视频文件)比作书的每一章节,那么这个m3u8文件就是这本书的目录,指示每一章节的位置以及页数。
使用记事本打开后,这个文件的内部结构如下(链接的中间部分已打码):
1234567891011121314151617#EXTM3U#EXT-X-VERSION:3#EXT-X-ALLOW-CACHE:NO#EXT-X-TARGETDURATION:5#EXT-X-MEDIA- ...
《宝可梦传说 阿尔宙斯》:GF的大胆创新
宝可梦系列的历史在十几年前的GameBoy以及3ds时代,宝可梦系列的玩法和画面是非常先进的。当年的红宝石/绿宝石,日/月,珍珠/钻石都是兼具人气与质量的佳作。但由于出品宝可梦的公司Game Freak(下文简称GF)的不思进取。在如今宝可梦系列的画面已经远远落后于其他游戏,与任天堂其他的第一方IP(马里奥,塞尔达…)形成了鲜明的对比。在NS上出的两作,《去吧皮卡丘/伊布》和《剑/盾》,第一部是个试水作,精灵很少,玩法也不全,阉割了大量内容。第二部有所好转,但仍不尽如人意。玩家社区内对GF公司怨声载道,指责他们“躺着赚钱,不思进取。”
传统宝可梦传统宝可梦的玩法主要有以下特点:
最突出的特点:回合制对战。这一特点恐怕永远都不会变。
地图里的主要为暗雷,走在路上突然蹦出来宝可梦。
捕捉,对战,培育,进化。
玩家之间的互动,包括互换宝可梦,联机对战等。
挑战道馆,获取徽章。
改进及特色内容阿尔宙斯在上述玩法上做出了很大创新。
地图改成了开放世界,在地图上可以采集资源,宝可梦直接出现在地图上,扔出精灵球直接捕捉,扔出自己的精灵则进入对战。
对战是直接进入,不会更换背景。而且在对战时玩 ...
最大为 N 的数字组合
题目简介902. 最大为 N 的数字组合难度:困难
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如,如果 digits = [‘1’,’3’,’5’],我们可以写数字,如 ‘13’, ‘551’, 和 ‘1351315’。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1:12345输入:digits = ["1","3","5","7"], n = 100输出:20解释:可写出的 20 个数字是:1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2:1234567输入:digits = ["1","4","9"], n = 1000000000输出:29523解释:我们可以写 3 个一位数字,9 个两位数字,27 个三位数字,81 个四位数字,243 个五 ...
最多可达成的换楼请求数目
题目简介1601. 最多可达成的换楼请求数目难度:困难
我们有 n 栋楼,编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节,部分员工想要换一栋楼居住。
给你一个数组 requests ,其中 requests[i] = [fromi, toi] ,表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。
一开始所有楼都是满的,所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ,一个员工要离开楼 1 ,一个员工要离开楼 2 ,如果该请求列表可行,应该要有两个员工搬入楼 0 ,一个员工搬入楼 1 ,一个员工搬入楼 2 。
请你从原请求列表中选出若干个请求,使得它们是一个可行的请求列表,并返回所有可行列表中最大请求数目。
示例1:
1234567891011输入:n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]输出:5解释:请求列表如下:从楼 0 离开的员工为 x 和 ...
Go语言切片题目解析
前言在Go语言中,Slice作为一个比数组更加灵活的数据结构被广泛应用。但也正是由于它的灵活性,导致使用时常常容易犯错。笔者昨天做到了一道很有意思的题目,在这里与大家分享。
题目下面的函数输出什么?
123456789101112131415161718192021package mainimport ( "fmt")func SliceRise(s []int) { s = append(s, 0) for i := range s { s[i]++ }}func main() { s1 := []int{1, 2} s2 := s1 s2 = append(s2, 3) SliceRise(s1) SliceRise(s2) fmt.Println(s1, s2)}
A : [2, 3][][2, 3][2, 3, 4]
B : [1, 2][1, 2, 3]
C : [1, 2][2, 3, 4]
D : ...
多边形三角剖分的最低得分
题目简介1039. 多边形三角剖分的最低得分难度:中等
给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例1:123输入:[1,2,3]输出:6解释:多边形已经三角化,唯一三角形的分数为 6。
示例2:
123输入:[3,7,4,5]输出:144解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144。
示例3:123输入:[1,3,1,4,1,5]输出:13解释:最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
解法时间与内存双百:
核心的动态规划推导式:dp[i][j]= dp[i][k] + dp[k][j] + values[i] * values[k] * values[j] ...
《空洞骑士》:一款不会后悔入坑的游戏
写在前面在刚买Switch的时候,就听说过《空洞骑士》是一款必买的游戏,巴西服打折半价24,但原价买都不亏。作为少数Switch上定价不高于Steam上太多的游戏,在一次打折的时候抱着试试看的心态入坑。之后的游玩经历证明,这是我玩过最好的那一批游戏之一。上一个让我熬夜玩的游戏还是《塞尔达传说:旷野之息》。
正常通关时间在50h左右,当然如果你不想查攻略纯粹依靠自己的努力和探索,可能时间会长一点。就像旷野之息,通关远不是这个游戏的终点,你可以打四锁五门或者手办屋(全是难度BOSS的关卡和挑战)。不断挑战自己。再或者通过苦痛之路,感受真正的痛苦。
剧情作为一款类银河城的游戏,剧情并不是一开始就告诉玩家的,而是随着游戏的推进,在游戏的石刻上,与NPC的对话中,以及猎人图鉴的记录里,不断补充不断完善,最终描述出整个故事走向。
在这里笔者不对剧情做过多介绍,以防剧透。大体就是一个曾经被抛弃的容器回到衰败的地下王国圣巢——这个它曾经出生的地方,打败传播瘟疫的源头辐光,最后拯救圣巢。在小骑士的回忆中,有一段著名场面,与各位分享:
没有可以思考的心智没有可以屈从的意志没有为苦难哭泣的声音生于神与 ...
Moser Flow论文解读
Moser Flow:在流形上的基于散度的生成模型本文为2021年NeurlPS会议的六篇杰出论文之一。核心思想为将连续标准化流(CNF)模型迁移到黎曼流形上,再通过Moser提出的体积元方法使用散度来计算。它的模型(学习)密度被参数化为源(先验)密度减去神经网络(NN)的散度。本模型可以在一般曲面(包括隐式曲面)上进行采样,对比现有的CNF上,本模型在密度估计的样本质量和训练复杂性方面取得了显著的改进。
文章解读(由于公式过多,难以全部搬到Markdown中,所以博主放了PDF版本)(PDF需要翻墙后才能查看)
前置知识说明本文所涉及到的黎曼流形为微分几何内的内容。如果为非数学系的学生想要完全理解需要学习以下内容:数学分析,拓扑学,微分几何。
如果需要相关书籍可以给博主发邮件,联系方式在“公告”或“关于我”中查看。
参考文献Rozen N, Grover A, Nickel M, et al. Moser Flow: Divergence-based Generative Modeling on Manifolds[J]. Advances in Ne ...
创建一个自己的网站
租借云服务器要搭建一个自己的网站,首先需要租一台云服务器。这里推荐阿里云,在国内算是最好用的一个了。如果是学生身份可以认证后以优惠价购买(开发者成长计划),还可以白嫖两个月(需要答题并写一份使用感想)。
以我选择的ECS云服务器为例。购买后进入控制台,选择对应的地区,然后创建一个实例,设置实例密码。
点击远程连接后,选择一个连接方式(推荐workbench)。就可以连接到云服务器了。
网站搭建Web服务器连接上服务器后,选择一个web服务器软件使用(如Apache或Nginx)。
Apache教程:https://blog.csdn.net/weixin_39212776/article/details/81192847
Nginx教程:https://www.cnblogs.com/taiyonghai/p/6728707.html
HTML网站模板可以在“模板之家”这个网站上找自己所需要的样式。下载完直接改动文字或者图片即可,简单快捷。(Adobe的Dw可以进行网页的可视化修改,代码基础不太好的话可以用这个)
选择好后不需要开会员,去淘宝找商家购买即可,价格非常便宜,一个0 ...