- 博客(35)
- 收藏
- 关注
RSS订阅
1原创 动态规划总结
胡凡 曾磊《算法笔记》第十一章总结1、动态规划介绍1、定义动态规划（Dynamic Programming,DP），解决最优化问题。将一个复杂问题分解为若干个子问题，通过综合子问题的最优解来得到原问题的最优解。此外，DP为将每个求解过的子问题的解记录下来，这样下次再碰到同样子问题，就可以直接用之前的结果，而不用重复计算。2、满足条件——重叠子问题+最优子结构重叠子问题：如果一个问题可以被分为若干个子问题，且这些子问题会重复出现最优子结构：一个问题可以通过子问题的最优解构造出原问题的最优解
2021-06-04 19:52:52
170
原创 最短路径算法（Dijkstra、Bellman-Ford、SPFA、Floyd）
《算法笔记》笔记解决最短路径问题的常用算法有Dijkstra、Bellman-Ford、SPFA、Floyd算法。1、Dijkstra（1） 解决单源最短路问题。即给定图G和起点s，通过算法得到S到达其他每个顶点的最短距离。只能应对所有边权都是非负数的情况，Dijkstra(G,d[],s){ fill(d,d+N,INF); d[s] = 0; for(循环n次）{ u = 使d[u]最小的还未被访问的顶点的编号； 记u已被访问； for(从u出发能到达的所有顶点v）{
2021-06-02 16:29:58
379
原创 OJ刷题总结
1、设定字符串长度时要比规定长度至少大1不能说字符串最大长度10000，然后你就设定char str[10000]，因为字符串的最后一位是’\0’，所以必须给’\0’留位置。2、取模运算（a+b）%e = (a%e+b)%e（a+b+c）%e =( (a%e+b)%e+c)%e避免数字加和过大，可以在计算中途就进行取模运算3、输出格式...
2021-05-12 19:45:35
766
原创 二分法
《算法笔记》学习笔记1、基本二分查找1、二分查找时一种基于有序序列的查找算法，时间复杂度为O(logn）。#include<stdio.h>//A[]为严格递增序列int binarySearch(int A[],int left,int right,int x){ int mid; while(left<=right){ mid = (left+right)/2; if(x==A[mid]){ return mid; }else if(x>A[mi
2021-05-05 16:42:24
61
原创 递归法求解全排列、N皇后
《算法笔记》第四章学习笔记1、全排列问题一般把1~n这n个整数按照某个顺序摆放的结果称为这n个整数的一个排列，全排列指这n个整数能形成的所有排列。如n=3时，全排列为（1,2，3），（1,3，2），（2,1，3），（2,3，1），（3,1，2），（3,2，1）。全排列问题求解思路：按照位数去递归。设定数组P，用来存放当前的排列；散列数组hashTable，当整数x已经在数组P中时hashTable[x]为true。当递归到第index位时，如果index等于N+1，那么输出数组P的每一位；否
2021-05-05 10:36:04
108
原创 C++sort函数的使用
《算法笔记》笔记1、sort（）排序函数简介sort函数的使用必须加上头文件#include< algorithm>和using namespace stdsort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数（非必填））；2、比较函数若比较函数不填，则默认按照从小到大的顺序排序。若想要从大到小排序，则可这样设定比较函数cmp：bool cmp(int a,int b){ return a>b;//可以理解为当a>b时把a放到b的前面}sort
2021-05-04 21:22:40
78
原创 C/C++基本知识（二）
《算法笔记》第2章笔记（二）1、给整个数组都赋初值0：int a[10] = {0};int a[10]={};使用memset函数，memset建议只用来赋值0或-1。用法：添加string.h头文件，之后memset(数组名，值，sizeof(数组名))#include<stdio.h>#include<string.h>int main(){ int a[5] = {1,2,3,4,5}; memset(a,0,sizeof(a)); return 0;
2021-05-04 12:31:45
78
原创 C/C++基本知识
《算法笔记》（胡凡 曾磊）第2章笔记1、int型：绝对值在 109 范围以内的整数或者32位整数2、long long型： 1018 以内整数或者64位整数3、浮点数：float为单精度，double为双精度，一般使用浮点数时，都使用双精度double存储。4、字符变量：char c = ‘e’小写字母比大写字母的ASCII码值大325、转义字符：\n表示空行，\0代表空字符NULL，其ASCII码为0。6、强制类型转换: （新类型名）变量名double r = 12.56;(int)r
2021-05-03 23:06:15
107
原创 D3学习笔记（7—8.3）
《数据可视化实战》读书笔记第7章 比例尺1、比例尺的输入值域（input domain）：可能的输入值的范围。比例尺的输出范围（output range）：输出值可能的范围。2、D3的比例尺函数生成器，通过d3.scale访问。要生成一个比例尺，在d3.scale后面加上要创建的比例尺类型即可。输入值域：domain()方法，将值域以数组形式传给它。输出范围：range()方法。var scale = d3.scale.linear();//变量scale用来保存函数scale.domai
2020-08-25 21:54:14
220
原创 D3初学习笔记
《数据可视化实战：使用D3设计交互式图表》学习笔记第1-4章1、D3：Data-Driven Documents（数据驱动的文档）。D3扮演的是一个驱动程序的角色，因为它联系着数据和文档。2、D3最擅长处理矢量图形（SVG图或GeoJSon数据），矢量图是由点、直线和曲线，即数据方程式定义的，因此可以随意放大或缩小而不会失真。而位图由像素构成，很难在放大或缩小时做到不失真。3、D3代码在客户端执行，即在用户浏览器而不是WEB服务器中执行，因此你想要可视化的数据必须发送到客户端。4、DOM(Docu
2020-08-18 22:08:16
368
原创 N皇后问题
参考北京大学算法慕课慕课链接n皇后问题：输入整数n，要求n个国际象棋的皇后，摆在n*n的棋盘上，互相不能攻击，输出全部方案。 定义一维数组queenPos记录每一行皇后的位置，即queenPos[x] = y表示第x行的皇后在第y列上。（行、列下标都从0开始） 定义函数NQueen（int k), 此函数代表求第k行皇后的位置，调用此函数时前k-1行皇后的位置已经确定。 main函数内调用NQueen（0），从第0行开始求解。 NQueen函数首先判断出口，若k==N，表示前N-1行的位置
2020-08-18 09:55:34
151
原创 JavaScript初步学习笔记
一、JavaScript简介1、JavaScript可以在网页上实现复杂的功能，网页展现给你的不再是简单的静态信息，而是实时的内容更新，滚动播放的视频等。2、Web技术蛋糕三层以文本标签为例。首先用HTML将文本标记，赋予它结构和目的；之后再为它加一点CSS让它更好看；最后，为它加上JS来实现动态行为（如为事件添加响应）。3、在HTML和CSS集合组装成一个网页后，浏览器的JS引擎将执行JS代码。这保证了当JS开始运行之前，网页的结构和样式已经就位。因为JS最普遍的用处是通过DOM API动态修改
2020-08-12 11:48:09
116
原创 MDN网站CSS学习
一、什么是CSS？1、HTML用于定义内容的结构和语义，CSS用于设计风格和布局。2、CSS语法由一个选择器（selector）开头，它选择了我们将要用来添加样式的HTML元素。接着输入一对大括号{}，括号内部定义一个或多个形式的属性（property）：值（value）。二、CSS学习之旅1、向HTML文本中添加CSS（1）在HTML文档的相同目录创建一个文件，保存并命名为styles.css。在HTML文档中< head>语句模块第一行加上下面代码：< link rel
2020-08-11 19:14:50
345
原创 MDN网站HTML学习记录（二）
HTML学习网站一、高阶文字排版1、描述列表（description list）标记一组项目及其相关描述，例如术语和定义，或者问题和答案。描述列表使用闭合标签 < dl >;每一项都用< dt>(description term)元素闭合。每个描述都用< dd>（description description）元素闭合。一个术语 < dt> 可以同时有多个描述 < dd>。2、引用（？没有搞懂HTML里的引用）3、缩略语<
2020-08-11 11:00:46
151
原创 MDN网站HTML初步学习总结
依据MDN网站学习总结HTML学习网站一、总述1、块级元素：块级元素相对于前面的内容它会出现在新的一行，其后的内容会被挤到下一行展现。内联元素：内联元素通常会出现在块级元素中并环绕文档内容的一小部分，不会导致文本换行，如< em>或< a>。空元素：不是所有元素都拥有开始标签、内容、结束标签。一些元素只有一个标签，通常用来在此位置插入/嵌入一些东西。如< img>用来嵌入图片。2、属性属性包含元素的额外信息，这些信息不会出现在实际的内容中，可用来识别此
2020-08-10 23:34:37
783
原创 7-9 旅游规划 (25分)
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；...
2020-03-23 21:26:49
331
原创 1076 Forwards on Weibo (30分)
Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a ...
2020-03-23 10:26:56
105
原创 7-7 六度空间 (30分)
参考浙江大学数据结构慕课“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。输入格式:输入第1行给出两个正整数，分别表示社交网络图的结...
2020-03-22 20:26:05
489
原创 排序算法总结（选择、冒泡、插入、希尔、堆、归并、快速排序）
根据浙大数据结构慕课和《算法设计与分析基础》整理规定按照从小到大顺序排序。前提：void X_Sort(int A[ ], int N)主函数：int main(){ int N; cin>>N; int a[N]; for(int i = 0;i<N;i++){ cin>>a[i]; } X_Sort(a,N);//排序函数 cou...
2020-03-11 16:25:44
244
原创 Python慕课 MODULE 02: 数据获取与表示之第三周 数据获取与表示3.3~3.6
南京大学用Python玩转数据慕课学习3.31、序列中第一个元素索引为0，则最后一个元素索引为N-1若从最后一个元素开始计数，最后一个元素是-1，则第一个元素为-N2、序列：字符串、列表[]、元组（）序列可迭代，即可以遍历其内部元素3、对象身份比较：is、is not4、’\n’：换行符week[1:4]：输出从索引为1开始的三个元素（4-1=3）week[:6]：输出从索引为0...
2020-02-21 22:57:10
361
原创 Python慕课 MODULE 02: 数据获取与表示之第三周 数据获取与表示3.1~3.2
南京大学用Python玩转数据慕课学习整理3.11、文件用完后养成主动关闭文件的习惯2、Python中二进制文件可以不使用缓冲，但是文本文件必须使用缓冲3、with open(‘firstpro.txt’,‘w’) as f:f.write(‘Hello, World!’)既写文件，又读文件，用’r+’4、open语句读完文件自动关闭，所以不用再额外写上close语句了5、read...
2020-02-21 22:49:12
208
原创 Python慕课学习第一、二章学习笔记
根据南京大学《用Python玩转数据》整理1.1~1.21、Python运行方式：Shell方式。Shell是交互式的解释器，输入一行命令，解释器就解释运行。文件方式。在Python的IDE环境中，创建一个以py为扩展名的文件；用Python解释器在shell中运行出结果。2、Python输出：print函数：print（变量）print（字符串）3、Python输入：in...
2020-02-19 19:28:34
286
原创 《算法神探》读书笔记
前几天读了《算法神探》，挺有意思一本书，使我对数据结构有了更深理解。笔记如下：一、二分搜索1、原理：请注意，通过这几次的操作，此时虽然下界已经是目标值了（v=15），但是我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间值进行判定，而不会判定上界和下界是否是目标值。如果目标值不在数组中会发生什么呢？在搜索过程中，上下界之间的距离会越来越近，直到它们之间没有任何还未检查...
2020-02-18 21:58:08
234
原创 7-5 Tree Traversals Again (25分)
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stac...
2020-01-21 18:40:49
311
原创 7-5 堆中的路径 (25分)
将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。输入格式:每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。输出格式:对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上...
2020-01-21 10:49:08
263
原创 7-4 是否同一棵二叉搜索树 (25分)
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。输入格式:输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的...
2020-01-20 17:41:57
194
原创 7-3 树的同构 (25分)
浙大慕课学习给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。图一：图二：现给定两棵树，请你判断它们是否是同构的。输入格式:输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树...
2020-01-17 17:09:59
239
原创 7-22 堆栈模拟队列 (25分)
题目：设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；void Push(Stack S, ElementType item )：将元素item压入堆栈S；Element...
2020-01-17 13:20:15
1035
原创 7-20 表达式转换 (25分)
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、、\以及左右括号()，表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入样...
2020-01-16 17:02:40
3008
原创 7-2 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。输入格式:输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式:输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。输入样例:4 3 4 -5 2 6 1 ...
2020-01-16 14:49:37
201
原创 01-复杂度3 二分查找
浙江大学慕课本题要求实现二分查找算法。函数接口定义：Position BinarySearch( List L, ElementType X );其中List结构定义如下：typedef int Position;typedef struct LNode List;struct LNode {ElementType Data[MAXSIZE];Position Last; / 保...
2020-01-15 16:05:37
110
原创 01-复杂度2 Maximum Subsequence Sum(浙江大学数据结构编程题2）
思路：用“在线处理”算法，见最大子列和问题设置head和rear分别存放最大子列所对应的首项和尾项的下标。设置head1临时存放正在求和的子列的首项，若正在求和的子列的和大于max，则将head1赋值给head。初始化rear为-1，可根据rear的值去判断是否全是负数。若数列全为负数，则rear始终为-1，否则rear不为-1。注意：1、让你输出的是numbers!是数而不是对应的下...
2020-01-14 22:36:35
95
原创 最大子列和问题
浙江大学数据结构慕课学习给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给...
2020-01-14 21:38:31
215
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人