- 博客(160)
- 收藏
- 关注
RSS订阅原创 机器学习实战|基于概率论的分类方法：朴素贝叶斯
1 基于贝叶斯决策理论的分类方法朴素贝叶斯优点：在数据较少的情况下依然有效，可以处理多类别问题缺点：对于输入数据的准备方式较为敏感适用数据类型：标称型数据贝叶斯决策理论核心思想：选择具有最高概率的决策2 条件概率贝叶斯准则：p(c∣x)=p(x∣c)p(c)p(x)p(c|x)=\frac{p(x|c)p(c)}{p(x)}p(c∣x)=p(x)p(x∣c)p(c)理解记忆：p(c∣x)p(x)=p(x∣c)p(c)=p(x∩c)p(c|x)p(x)=p(x|c)p(c)=p(
2022-01-06 20:39:58
302
原创 机器学习实战|决策树
1 决策树的构造优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据缺点：可能产生过度匹配问题适用数据类型：数值型和标称型解决的首要问题：当前数据集上哪个特征在划分数据分类时起决定性作用创建分支的伪代码函数createBranch():检测数据集中的每个子项是否属于同一分类；if so return 类标签；Else 寻找划分数据集的最好特征 划分数据集 创建分支节点 for 每个划分的子集 调用函数createBranch并增加返回结果到分支
2021-12-26 21:21:05
988
原创 机器学习实战|手写识别系统|k-临近算法
1 准备数据：将图象转化为测试向量为了使用前面使用过的分类器，将图象格式化为一个向量：将3232的二进制图像矩阵转化为11024的向量def img2vector(filename): returnVect = zeros((1, 1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnV
2021-12-21 15:47:44
303
原创 机器学习实战|使用K-临近算法改进约会网站的配对效果
1 准备数据：从文本文件中解析数据datingTestSet.txt:每列分别代表每年获得的飞行常客里程数、玩游戏视频所耗时间百分比、每周消费的冰淇淋公升数、不喜欢/魅力一般/极具魅力（即标签）datingTestSet2.txt:使用file2matrix函数处理输入格式问题，使分类器可以接受：输入为文件名字符串，输出为训练样本矩阵和类标签向量。代码如下：def file2matrix(filename): fr = open(filename) arrayOLines =
2021-12-21 12:58:25
1041
原创 机器学习实战|k-临近算法代码详解
原理将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似(最近邻)的分类标签→一般只选择样本数据集中前k个最相似的数据，k通常不大于20代码及释义from numpy import *import numpy as npimport operatordef createDataSet(): group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) labels = ['A', 'A', '
2021-12-20 15:58:00
156
原创 codeup|实现简单计算器
#include<bits/stdc++.h>using namespace std;//codeup 1918 简单计算器struct node { double num;//操作数 char op;//操作符 bool flag;//true表示操作数，false表示操作符};string str;stack<node> s;//操作符栈queue<node> q;//后缀表达式序列map<char, int>
2021-08-30 12:37:28
78
原创 算法|动态规划
递推求解n阶楼梯上楼问题|华中科大考研复试描述N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）输入描述：输入包括一个整数N,(1<=N<90)。输出描述：可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。#include<iostream>#include<cstdio>using namespace std;const int MAXN=91;long long dp[MAXN];int
2021-08-03 22:44:56
126
原创 数据结构|拓扑排序
拓扑排序限定：有向无环图①从DAG图中选择入度为0的顶点，并输出②从图中删除该入度为0的顶点以及所有以它为起点的边③重复①和②直到当前图为空，或者图不存在入度为0的顶点。前者输出的序列就是拓扑序列，后者说明图中有环，不存在拓扑序列典型例题判断能否构成有向无环图#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;co
2021-08-01 21:26:33
112
原创 数据结构|最短路径
畅通工程续Problem Description某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。Input本题目包含多组数据，请处理到文件结束。每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。
2021-08-01 16:35:42
476
原创 数据结构|并查集
畅通工程|浙大考研复试描述某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
2021-07-30 15:28:53
193
原创 数据结构|映射
查找学生信息|清华考研复试描述输入N个学生的信息，然后进行查询。输入描述：输入的第一行为N，即学生的个数(N<=1000) 接下来的N行包括N个学生的信息，信息格式如下： 01 李江 男 21 02 刘唐 男 23 03 张军 男 19 04 王娜 女 19 然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下： 02 03 01 04输出描述：输出M行，每行包括一个对应于查询的学生的信息。 如果没有对应的学生信息，则输出“No Answer!
2021-07-28 19:16:13
209
原创 数据结构|优先队列
只能访问队列中优先级最高的元素< queue >头文件 priority_queue< typename > name优先队列的应用：求解顺序问题重载！bool operator< (typename x) const{ return …};应用1：解决顺序问题例题：北邮考研复试|复数集合描述一个复数（x+iy）集合，两种操作作用在该集合上： 1、Pop 表示读出集合中复数模值最大的那个复数，如集合为空 输出 empty ，不为空就输出最大的
2021-07-27 11:42:35
97
原创 数据结构|二叉树
二叉树遍历1描述编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。输入描述：输入包括1行字符串，长度不超过100。输出描述：可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。#include<iostream&
2021-07-27 10:06:06
192
原创 深度优先算法
A Knight’s JourneyBackgroundThe knight is getting bored of seeing the same black and white squares again and again and has decided to make a journeyaround the world. Whenever a knight moves, it is two squares in one direction and one square perpendicula
2021-07-26 19:51:24
247
原创 宽度优先算法
Catch That Cow农夫知道一头牛的位置，想要抓住它。农夫和牛都于数轴上 ，农夫起始位于点 N(0<=N<=100000) ，牛位于点 K(0<=K<=100000) 。农夫有两种移动方式： 1、从 X移动到 X-1或X+1 ，每次移动花费一分钟 2、从 X移动到 2*X ，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不。最少要花多少时间才能抓住牛？Input一行: 以空格分隔的两个字母: N 和 KOutput一行: 农夫抓住牛需要的最少时间，单位分钟
2021-07-24 19:59:00
593
原创 贪心算法|
代理服务器 清华考研复试上机#include<iostream>#include<string>#include<vector>#include<map>using namespace std;map<string,bool> agent;void reset(){//初置 for(auto it=agent.begin();it!=agent.end();it++) (*it).second=true;
2021-07-23 22:20:07
102
2
原创 高精度整数的运算
运算模板#include<string>#include<iostream>#include<string.h>using namespace std;const int MAXN = 10000;struct BigInteger { int digit[MAXN]; int length; BigInteger(); BigInteger(int x); BigInteger(string str);
2021-07-18 15:36:37
178
原创 浙大考研复试机试|统计字符
描述统计一个给定字符串中指定的字符出现的次数。输入描述：测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到’#'时输入结束，相应的结果不要输出。输出描述：对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 … 其中ci是第1行中第i个字符，ni是ci出
2021-06-05 20:46:11
336
4
原创 北大考研复试机试|密码翻译
描述在情报传递过程中，为了防止情报被截获，往往需要对情报用一定的方式加密，简单的加密算法虽然不足以完全避免情报被破译，但仍然能防止情报被轻易的识别。我们给出一种最简的的加密方法，对给定的一个字符串，把其中从a-y,A-Y的字母用其后继字母替代，把z和Z用a和A替代，则可得到一个简单的加密字符串。输入描述：读取这一行字符串，每个字符串长度小于80个字符输出描述：对于每组数据，输出每行字符串的加密字符串。示例1输入：Hello! How are you!复制输出：Ifmmp! Ipx bs
2021-06-05 20:17:27
131
原创 华中科大复试|找位置
描述对给定的一个字符串，找出有重复的字符，并给出其位置，如：abcaaAB12ab12 输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。输入描述：输入包括一个由字母和数字组成的字符串，其长度不超过100。输出描述：可能有多组测试数据，对于每组数据， 按照样例输出的格式将字符出现的位置标出。 1、下标从0开始。 2、相同的字母在一行表示出其出现过的位置。示例1输入：abcaaAB12ab12复制输出：a:0,a:3,a:4,a:9b:1,
2021-06-05 16:34:52
51
原创 奥运排序问题
描述按要求，给国家进行排名。输入描述：有多组数据。 第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。 第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人口数（百万）。 接下来一行给出M个国家号。输出描述：排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 对每个国家给出最佳排名排名方式 和 最终排名 格式为: 排名:排名方式 如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例
2021-06-05 15:32:33
153
原创 枚举法|Old Bill
描述Among grandfather’s papers a bill was found. 72 turkeys $679 The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. W
2021-05-30 21:30:54
79
原创 lowbit运算、树状数组详解
lowbit运算lowbit(x)=x&(-x)lowbit(x)可以理解为能整除x的最大2的幂次树状数组存放的是i号位之前（含i号位，下同）lowbit(i)个整数之和C[i]的覆盖长度是lowbit(i)[也可理解为管辖范围]将C[i]画成二维图容易理解树状数组的下标必须从1开始C[x]=A[x-lowbit(x)+1]+···+A[x]getSum(x)返回前x个数之和C[x]=A[x-lowbit(x)+1]+···+A[x]可推得SUM(1,x)=SUM(1,x-lo
2021-05-30 19:44:27
766
原创 KMP算法与next数组
next数组next[i]表示使子串s[0···i]的前缀s[0···k]等于后缀s[i-k···i]的最大的k（前缀和后缀可以重叠，但不能是s[0···k]本身，当找不到相等的前后缀时令next[i]=-1(即next[i]是所求最长相等前后缀中前缀最后一位的下标)用递归法求解next[i]:void getNext(char s[],int len){//getNext求解长度为len的字符串s的next数组 int j=-1; next[0]=-1;//初始化j=next[0]=
2021-05-30 19:43:12
78
原创 codeup|问题 C: 哈夫曼树
题目描述哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。输入输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。输出输出权值。样例输入 Copy22 835 11 30样例输出 Copy1062代码#include<bits/stdc++.h>using namespac
2021-03-29 21:23:16
70
原创 codeup|问题 A: 算法6-12：自底向上的赫夫曼编码
题目描述在通讯领域，经常需要将需要传送的文字转换成由二进制字符组成的字符串。在实际应用中，由于总是希望被传送的内容总长尽可能的短，如果对每个字符设计长度不等的编码，且让内容中出现次数较多的字符采用尽可能短的编码，则整个内容的总长便可以减少。另外，需要保证任何一个字符的编码都不是另一个字符的编码前缀，这种编码成为前缀编码。而赫夫曼编码就是一种二进制前缀编码，其从叶子到根（自底向上）逆向求出每个字符的算法可以表示如下：在本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。
2021-03-29 14:36:02
954
原创 codeup|问题 B: 序列合并
题目描述有两个长度都为N的序列A和B，在A和B中各取一个数相加可以得到N2个和，求这N2个和中最小的N个。输入第一行一个正整数N（1 <= N <= 100000）。第二行N个整数Ai，满足Ai <= Ai+1且Ai <= 109第三行N个整数Bi，满足Bi <= Bi+1且Bi <= 109输出输出仅有一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。样例输入 Copy32 6 61 4 8样例输出 Copy3 6 7提
2021-03-28 17:55:21
176
原创 codeup|问题 A: 算法10-10,10-11：堆排序
题目描述堆排序是一种利用堆结构进行排序的方法，它只需要一个记录大小的辅助空间，每个待排序的记录仅需要占用一个存储空间。首先建立小根堆或大根堆，然后通过利用堆的性质即堆顶的元素是最小或最大值，从而依次得出每一个元素的位置。堆排序的算法可以描述如下：在本题中，读入一串整数，将其使用以上描述的堆排序的方法从小到大排序，并输出。输入输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。输出只有1行，包含n个整
2021-03-28 15:30:56
182
原创 堆的基本操作
#include<bits/stdc++.h>using namespace std;const int maxn = 100;int heap[maxn], n = 10;//heap为堆，n为元素个数//对heap数组在[low,high]范围向下调整//其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标void downAdjust(int low, int high) { int i = low, j = i * 2;//i为欲调整结点,j
2021-03-28 11:00:00
84
原创 并查集的基本操作
#include<bits/stdc++.h>const int maxn = 10001;int father[maxn];void init(int father[], int n) { for (int i = 1; i <= n; i++) { father[i] = i; }}int findFather1(int x) {//返回元素x所在集合的根节点 while (x != father[x]) {//如果不是根节点，.
2021-03-27 20:13:18
53
原创 AVL(二叉平衡树）的基本操作
#include<bits/stdc++.h>using namespace std;struct node { int v, height;//v为结点权值，height为当前子树高度 node *lchild, *rchild;//左右孩子结点地址};node *newNode(int v) {//生成一个结点，v为节点权值 node *Node = new node;//申请一个node型变量的地址空间 Node->v = v;//结点权值
2021-03-27 16:45:09
114
原创 codeup|问题 A: 二叉排序树
题目描述输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。输入输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。输出可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。样例输入 Copy1228 15421 10 5 39样例输出 Copy2228 158 1515 821 10 5 395 10 21 395
2021-03-27 11:44:42
78
原创 PAT|二叉搜索树&镜像二叉树
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains only nodes with keys greater than
2021-03-26 21:02:56
166
原创 二叉查找树的基本操作
#include<bits/stdc++.h>struct node{ int data; node* lchild; node* rchild;};void search(node* root,int x){//查找二叉查找树中数据域为x的结点 if(root==NULL){ printf("search failed\n"); return; } if(x==root->data){//查找成功，
2021-03-26 19:49:02
69
原创 codeup|问题 B: 二叉树
题目描述如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。输入输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入
2021-03-25 19:09:57
205
原创 codeup|问题 A: 复原二叉树
题目描述小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。输入输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。输出对于每组输入，输出对应的二叉树的后续遍历结果。样例输入 CopyDBACEGF ABCDEFGBCAD CBAD样例输出 CopyACBFGEDCDAB代码#include<stdio.h>#include<string
2021-03-25 16:24:28
134
原创 二叉树的操作&&重点：几种遍历方式
题目：已知一棵二叉树的后序遍历和中序遍历序列，求这棵二叉树的层序遍历序列。#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>using namespace std;const int maxn = 50;struct node { int data; node *lchild; node *rchild;};int pre[
2021-03-24 21:41:01
53
原创 codeup|问题 C: 【宽搜入门】8数码难题
题目描述初始状态的步数就算1，哈哈输入：第一个33的矩阵是原始状态，第二个33的矩阵是目标状态。输出：移动所用最少的步数Input2 8 31 6 47 0 51 2 38 0 47 6 5Output6代码#include<iostream>#include<queue>using namespace std;struct node { int x, y; int step; int M[3][3]; int l
2021-03-23 16:05:48
74
原创 codeup|问题 B: DFS or BFS?
题目描述说好了，题目不黑人。给你一个8*8的矩阵，你的初始位置是左下角方格（用’U’表示），你的目标位置是右上角的方格(用’A’表示），其余的62个方格，如果是’.’，表示这个方格为空，如果是’S’，表示这个方格有一块大石头。好了现在你开始从左下角出发，每次可以往上，下，左，右，左上，右上，左下，右下移动一个方格，或者你可以原地不动，一共九个动作方式，在你做完一个动作后，所有的大石头会往下掉一个方格（如果一个大石头的位置是（x，y）,那下一秒是（x+1，y）,不过如果它已经在最下面的一排了，那它就会掉出
2021-03-22 17:25:39
86
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人