kbb0824-CSDN博客

原创滑动窗口总结

滑动窗口题目的一般格式：一个序列中，满足某些条件的，子串的，最长/最短/个数。时间复杂度分析：暴力解法的时间复杂度一般为O(N ^ 3)：O(N ^ 2)枚举所有的子串，O(N)判断是否满足条件。滑动窗口在两个方面都降低时间复杂度：首先并不枚举所有的子串，只枚举可能包含答案的那些。其次通过记录窗口内子串的一些信息，使得判断是否满足条件的时间复杂度下降。难点：什么时候更新答案，窗口内保存哪些信息来降低判断的时间。正确性证明：分解为子问题，或者反证法证明窗口内一定包含过正确答案。

2021-03-01 11:58:03 2078 1

原创 2021-01-29

要想使用计算机来处理自然语言，首先要把自然语言变成计算机可以理解的形式。以单词为基本单位，就是要学习单词的表征。学习分布式表征的历史：NNLM首次提出分布式表征，它在一个模型架构中同时学习分布式表征和概率语言模型，最终的目的还是为了做LM。之后提出的一些NNLM先用一个单隐藏层的神经网络学习分布式表征，再用学到的分布式表征来训练NNLM。word2vec只用了第一步，直接学习分布式表征。discrete，localist vs continuous，distributed为

2021-02-09 09:55:17 149

原创并查集模板

class UF: def __init__(self, count): self.count = count self.parent = [i for i in range(count)] self.size = [1]*count def find(self,x): if x==self.parent[x]: return x self.parent[x]=self.find(sel

2021-01-19 22:47:17 103

原创 python处理json文件

json.dumps(data):首先将python数据类型转换为对应的json数据类型，然后变为一个字符串。json.loads(data):将字符串中的json数据类型变为对应的python数据类型，再变为一个python数据结构。JSON standard allows only one top-level value ：实际上是说一个json文件只能有“一个”数据，不能有多个并列的数据，例如想要存放多个字典，必须把他们放入一个列表中，这样json文件就只有一个列表了。正由于上述特性，json.

2021-01-14 14:25:25 2745

原创 python set操作

s.add()：添加一个不可变元素。s.update()：添加一个可迭代对象的所有元素。s.dicard()：删除一个元素，且当该元素不存在时不发生错误。s.remove：删除一个元素，若不存在则发生错误。s.pop()：随机删除元素。s.clear()：清空。s.copy()：复制。&,-,|：交集，差集，并集。s.issubset(s1)：判断s是否是s1的子集。s.issuperset(s1)：判断s是否包含s1。s.symmetric_difference(s1)：返回.

2020-12-13 10:16:37 68

原创 python IO

在python中io.open()==open()。f = open('filename','w')# f本身是一个可迭代对象，迭代一次生成文本中的一行for i in f: print(i)s1 = f.read() # 返回一个字符串，内容是整个文本文件s2 = f.readline() # 把文本文件第一行返回成一个字符串（包含换行符）s3 = f.readlines() # 返回一个列表，其中每个元素是文本文件的一行举例来说，假设文本文件如下：注意，由于f是一个可迭代对

2020-12-10 19:34:56 62

原创 python常用装饰器

装饰器定义：在代码运行期间动态增加功能的方式，称之为“装饰器”（Decorator）。本质上，decorator就是一个返回函数的高阶函数。import functools,timedef execute_time(func): # 定义装饰器 # 此时调用f()时，实际上调用的是wrapper函数，返回值一样，但名字变了。 @functools.wraps(func) # 把名字改回来 def wrapper(*args, **kw): start_time

2020-12-08 19:48:32 2308 1

原创 402. 移掉K位数字

贪心的策略，每次删除一个数使得剩余数组成的数字最小。删除一个数之后，这个数之前的数不变，这个数变成了它右边的数，

2020-12-02 20:23:04 61

原创两数，三数之和

枚举数组中所有可能的互不相同的三元组使其和为0.先不考虑时间复杂度，最简单的想法是枚举所有三元组：for i in range(n): for j in range(i+1,n): for k in range(j+1,n): res.append([a[i],a[j],a[k]])这样会有重复，那什么导致了重复呢？无非是两种情况：[0,1,2]和[2,0,1]重复[0,1,2]和[0,1,2]重复首先可以通过限制a<=b<=c来除去第一个重复，具体操作是先对数组排

2020-12-02 11:56:33 132 2

原创 455A. Boredom

题意如下：在一个数组中删除数字，当删除x时，该x（不包括别的x）以及所有的x-1和x+1都会被删除，得到x分。怎样的删除顺序最终得到的总分最高。分析：将数组排序，cnt[i]记录每个数出现的个数，初始时dp[i][0]表示数字在这里插入代码片表示删除数字i后所能得到的最高分。...

2020-12-01 20:43:51 124

原创 189A. Cut Ribbon

可以这样理解题：从位置0开始走，每一步可以走a或b或c，走到终点n最多需要多少步。dp[i]表示到达位置i最多需要多少步，由于只有位置i-a，i-b，i-c可以到达位置i，所以dp[i]=max(dp[i-a],dp[i-b],dp[i-c])+1，初始时dp[0]=0，其余位置为-1，表示不可到达。n, *rib = map(int, input().split())rib.sort()res = [0] + [-1] * nfor i in range(rib[0], n + 1):

2020-12-01 18:46:06 113

原创二分查找总结

模板如下：first = 0last = len(nums)while first<last: mid = first + (last-first)//2 if nums[mid]<target: first = mid + 1 else: last = mid二分查找有两种理解方式：两个区间的充分扩张：把数组视为两个区间的并，要查找的元素恰好是分界点处的元素。[first0,first) 满足一个条件，如 <target，[last,last0) 满足互补的另

2020-11-24 00:02:56 186

原创 python笔记

变量作用域python引用变量的顺序：当前作用域局部变量->外层作用域变量->当前模块中的全局变量->python内置变量。函数外定义的变量为全局变量。全局变量可以在函数中直接使用，但不可修改。如果想要在函数中修改全局变量，要在函数中用global关键字声明该全局变量（不能同时赋值）。也可以在函数中用global声明新的全局变量。注意这里说的不能修改只是对于不可变对象，可变对象如列表和字典还是可以修改的，但仍然不能赋值。nonlocal关键字用来在函数或其他作用域中使用外层(

2020-11-18 20:46:58 46

原创 300. 最长上升子序列

将问题分解为子问题：求以第 i 个元素为结尾的最长上升子序列。定义子问题的递归求解方式：f(n) = max(f(i)) + 1 , i < n, a[i] < a[n]。依次求解子问题，并保存结果。合并子问题的解，得到最优解。class Solution: def __init__(self): self.ans = [] def f(self,i,nums): # 求解子问题的递归函数 if i == 0: # 终止条件 .

2020-10-26 19:53:26 143

原创 Missing Semester 5

Job controlctrl+c 终止命令执行。实际上是 shell 帮我们给正在执行的命令（程序/进程）发送了一个SIGINT信号。使用一个handler来保存程序的中间状态，可以在以后恢复。在命令的最后加一个 & ，使程序在background运行。Terminal MultiplexierSession，Window，panesDotfileRemote Machine...

2020-10-22 13:54:46 88

原创 Missing Semester 2

在 bash 中，空格是用来区分参数的，给变量赋值不能带空格。# wyk_ubuntu @ WYK-XPS in ~ [22:47:02] C:130$ foo=bar# wyk_ubuntu @ WYK-XPS in ~ [22:55:42]$ foo = barzsh: command not found: foo单引号只能表示纯字符串，双引号可以表示格式化字符串# wyk_ubuntu @ WYK-XPS in ~ [22:57:28]$ echo "hello $foo".

2020-10-19 10:36:09 88

原创 1534. 统计好三元组

2020-10-07 21:32:36 88

原创 1409 查询带键的排列

模拟：每一次查询和移动都要花费O(M)的时间，共查询Q次。时间复杂度为O(Q*M)，空间复杂度为O(M)。class Solution: def processQueries(self, queries: List[int], m: int) -> List[int]: ans = [] p = [i+1 for i in range(m)] for x in queries: pos = p.index(x)..

2020-10-06 22:20:23 67

原创幂集

递推公式法：每次将nums数组中的一个元素添加到结果数组中的每个元素上，形成一个新的数组，再和原结果数组合并。class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: if not nums: return [[]] ans = [[]] for i in nums: ans += [x+[i] for x.

2020-10-06 16:51:18 157

原创 Missing Semester 1

Linux的bash命令行显示如下：wyk_ubuntu@WYK-XPS:~$wyk_ubuntu是用户名，@后面是机器名，~是代表当前工作路径（ ~代表默认的地址），$代表不是root用户。在命令行执行指令，实际上就是让shell帮你运行程序。比如：wyk_ubuntu@WYK-XPS:~$ echo helloecho就是你要执行的程序，hello是参数。参数之间用空格分开。除此之外，还可以通过 flags（一个-）和 options（两个-，带参数的flag）调整程序的行为。例如：wy

2020-10-05 15:16:32 132

原创树状数组

普通数组：单点修改O(1)，区间求和O(n)前缀和数组：单点修改O(n)，区间求和O(1)树状数组：单点修改O(logn)，区间求和O(logn)利用lowbit来划分每个元素控制的区间，保证可以在logn时间内完成单点修改和区间求和。# 注意，树状数组的下标从1开始。# 初始为0，用原数组中的每个数去更新树状数组就完成建树的过程nums = [0, 1, 2, 3, 4, 5, 6, 7, 8]maxn = len(nums)tree = [0] * maxndef lowb.

2020-10-03 20:02:33 76

原创 1365 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。以数组形式返回答案。依次访问数组中的每个元素，对于该元素遍历整个数组来计算比它小的元素的个数，将结果也依次记录再数组中。（O(n^2)，O(1)）用一个新数组记录原数组从小到大排序的结果，依次访问原数组中的每个元素，并在新数组中二分查找该元素，也就得到了比.

2020-10-03 12:26:19 67

原创摩尔投票法

原理：在一个序列中，两两消除不相同的元素，最后如果存在剩下的元素，那它原本的数量一定超过一半。理解：有k个帮派，每个帮派有几个人，大家随机站成一排，一同打擂台。如果擂台上没人（count==0）那你就站上去成为守擂的人（major=i，count=1）；如果擂台上的人和你处于一个帮派（major==i），那你就也站上去（ count+=1）；如果擂台上的人和你不是一个帮派（major！=i），那你就杀掉擂台上的一个人（count-=1）。也就是说，major是守擂的帮派，count是守擂的人。如果最

2020-10-01 16:46:01 83

原创 1576. 替换所有的问号

给你一个仅包含小写英文字母和 ‘?’ 字符的字符串 s，请你将所有的 ‘?’ 转换为若干小写字母，使最终的字符串不包含任何连续重复的字符。注意：你不能修改非 ‘?’ 字符。题目测试用例保证除 ‘?’ 字符之外，不存在连续重复的字符。在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。在字符串前后加入一个特殊字符（非？），问题就转化为对于原s中的每一个？，用一个和其前后字符都不相同的字母代替它。cla.

2020-09-28 23:47:40 177

原创交叉验证

把样本集分为训练集和测试集。对训练集进行划分，用来选择模型的超参数（也就是选择模型）。留出法（hold-out）：对于每组超参数，将训练集划分为训练集和验证集，在训练集上学习，在验证集上检验模型的好坏。也就是说，每组超参数都学习到一个模型，用这个模型在验证集上的误差来代表这组超参数的好坏。但这个方法的问题在于，模型的误差与对训练集的划分有关。例如模型本身不存在过拟合的问题，但由于划分的不好，导致在验证集上表现出过拟合。k折交叉验证法（k-fold cross validation）：为了解决上述问题.

2020-09-28 09:55:30 60

原创 Dataloader

DataLoader(dataset, batch_size=1, shuffle=False, sampler=None, batch_sampler=None, num_workers=0, collate_fn=None, pin_memory=False, drop_last=False, timeout=0,

2020-09-25 17:06:32 199

原创 pandas读写csv

pd.read_csv('ex2.csv')将csv文件读取为dataframe格式。csv文件的第一行做为dataframe的列标签，第二行开始为数据内容。行标签为从0开始的数字。pd.read_csv('ex2.csv', headers=None)列标签为从0开始的数字。pd.read_csv('ex2.csv', names=names, index_col='E') # index_col=4names为列标签，index_col为行标签。如果想用包含列标签的某一列作为行标签，可

2020-08-16 16:29:53 165

原创 Pycharm项目环境配置

网上的教程通常是anaconda+pycharm，但具体到project的创建还是会有一些问题，下面通过一些具体的“实验”来看一下new project的环境该如何配置。首先，下图是创建一个new project时，弹出的界面：我们可以看到，大方向上有两种选择，一个是New environment using，另一个是Existing interpreter。Existing interpreter如果你是小白，且安装了anaconda，那么建议你所有的project都选择这个选项即可。它就相当于

2020-06-27 23:36:09 1452

空空如也

空空如也