- 博客(12)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 最长上升子序列
最长上升子序列在leetcode看到一个解法,说一下自己的理解动态规划设计方法&&纸牌游戏讲解二分解法解答中对于后一种解法没有证明,我试图对之做一些直觉上的说明.想法是,我们可以将原序列分为几类,第iii类记为SiS_iSi,定义为:aaa在某些上升子序列中,且aaa在这些上升子序列中的出现位置最大为iii,则aaa属于SiS_iSi.例如:333可能出现在序列{33...
2020-01-14 00:42:08
82
原创 数论初涉
费马小定理描述：若p为素数，则对所有的正整数a，有ap≡a(modp) a^p \equiv a (mod p)ap≡a(modp)特别地，若（a,p）==1,则ap−1≡a(modp) a^{p-1} \equiv a (mod p)ap−1≡a(modp)证明：p∣ap|ap∣a时是显然的，考虑（p，a）=1我们先证明一个事实：设S={1,2,……p−1}S = \lbra...
2019-09-03 23:47:34
91
原创 软件构造 多线程
---------------------------------------to be continued------------------------------------------一台机器上跑了多个互不相关的程序，叫多进程，一个进程跑了彼此可通信的“小进程”，叫多线程。计算机只有有限的处理器，但需要计算的任务可能是无限多的，如果一个一个的处理，显然不合适，因此，进程（线程）会在cp...
2019-06-03 19:58:43
189
原创 网络流
对于一个管道系统(V,E)来说，每节管道都有一定的最大承载量，超过管道就会爆炸。管道的交点称为节点，源点s是无入度的点，汇点t是无出度的点。我们可以添加管道无限大的“超级源点”和“超级汇点”来保证有且只有一个源（汇）点。方便起见，假定每个v，都有s->v->t这样的一条路径。定义流为一个映射V×V ->R流有如下性质：反对称性，f（u，v）= - f（v，u）；0<...
2019-04-12 19:49:46
119
原创 贪心算法——时间规划问题
问题：给你一些任务，每个任务都占用一段时间，同一时间只能处理一个任务，求能执行的最大任务数。分析：可以使用贪心策略，每次做结束时间最早的任务，关于正确性的证明： 考虑一个可行解，M1是di第一个任务，M2是第二个任务，那么，如果M1是结束时间最早，所以，它的前面不可以再添加任物；而又由于 M1是结束最早的，它和M2之间的间隔最大，因此M1是结束时间最早的可以保证该ke...
2019-03-22 11:57:04
1662
原创 分形树
要画一颗分形树，使用turtle分形图形的特征：子图与自身相似，很容易想到递归。要点在于定义初末状态。调用结束时，让turtle回到开始调用时的位置，并且方向与来时方向一致。public static void drawMyhelper(Turtle tur,int lenth,double angle) { if(lenth<=4) { return ; ...
2019-03-21 17:27:52
1379
1
原创 eclemma
eclemma 是一个eclipse中测试代码覆盖率的插件。所谓代码覆盖率，就是代码被执行的次数。安装：help --> marketplace 搜索eclemma安装成功后会在工具栏出现图标使用：点击图标或右键–>coverage as 可以在这里修改配置绿色表示总执行，黄色表示有时执行，红色表示不执行。...
2019-03-18 13:45:05
314
原创 kmp算法
是时候复习一下kmp算法了kmp算法解决的是匹配问题，即，给你一个字符串A（长为n），让你找一找字符串B（长为m）是否在其中出现。最简单的做法自然是，将B与A的每一个长为m的片段比较。时间复杂度是O（n*m）。kmp算法将时间复杂度简化到了O（n）。其思想是，求出每一位的最大相同前缀，假如字符串B在第k位时匹配失败，那么从k位的最大前缀处重新开始匹配，而不是从头匹配。kmp优化：如果最大前...
2019-01-06 15:09:19
101
原创 最小生成树
求最小生成树的算法所依据的原理为：如果是图G的一个生成森林，在所有不属于这个森林的的边中选择权值最小的一条，设这条边为(v1 v2),v1在g1中，v2在g2中，那么那么g1,g2连通后的权值一定最小。。。。。。kruskal算法此算法的做法是一开始将所有顶点视为一个连通分支，然后选择不在这n个连通分量里的权值最小的边，让这条边连接两个分量。当只剩一个分量时，这个分量就是最小生成树。由...
2019-01-06 00:13:22
115
原创 大作业
为大作业的要求而写 目 录 第1章 概述........................................................................................ - 4 -1.1 Hello简介.............................................................
2018-12-31 16:35:10
363
原创 排序
堆排序：push：以数组保存，父节点下标为 i/2，左儿子下标 2i，右儿子 2i+1，在末尾加入新元素，然后上移调整。在队列头前加入一个大数，以消除边界条件判断。pop：末尾元素放到堆顶，然后下移。实际实现中，末尾的元素都只在最后才被放入空穴。class Heap{//大顶堆private: vector&amp;lt;int&amp;gt; member; int tail; ...
2018-12-28 18:14:34
66
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人