6 GNIHTON

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 9w+

1.PLA算法总结

PLA(Percetron Learning Algorithm):感知学习算法,主要用于解决二维或者高维的线性可分问题,最终将问题分为两类:Yes or No。所谓线性可分就是可以找到一条直线或者一个k-1维超平面将一堆二维或K维数据中两个不同类别数据完美区分。 PLA算法是“错误驱动”的,当我们在训练这个算法的时候,只要输出值是正确的,这个算法就不会进行任何数据的调整,反之,当输出与实际值异...

2018-04-10 23:47:42

项目技术基本知识

一、Agenda 是一个基于命令行的议程管理系统,系统提供用户登录,新用户注册,已注册用户登录后用户可以注销(delete)当前账户,查询(query)用户名单,也可添加(add)、删除(delete)、查询(query)系统中记录的会议安排等管理功能,使用 c++完成,采用 Makefile 编译项目。 1、Makefile是一个文件名为Makefile的文本文件,用于定义项目的编译规则,以便...

2018-04-04 19:05:45

考研复试面试题目

面试要准备知识: 要求: 1.准备自己想从事的科研方向以及相关的知识和最新研究成果或前沿问题要有一定了解和关注(数据挖掘前沿知识、问题) 2.熟悉软件开发过程,掌握一种软件开发方法,软件工程相关知识一定要准备面试准备科目: 重要性:毕业设计、研究方向、软件工程、离散数学、操作系统、数据结构、数据库、计算机组成原理、计算机网络、线性代数、高数、程序设计1.对什么方向感兴趣?那...

2018-04-04 18:39:58

Sicily1153.马的周游问题

题目链接:http://soj.333.edu.gr/1153 。 思路:这道题目给出的棋盘是8*8,如果用一般的DFS+回溯来做会超时,这里加入了贪心策略,在马跳到某个位置A时,先计算从位置A再跳一步可以到达的所有可能候选位置的可扩展数C(也就是从候选位置处出发可以到达的位置数),然后按照每个候选位置的可扩展数来确定A处优先选择下一步的方向,C越小该方向优先级越高。代码实现如下:#in...

2018-03-21 11:39:24

POJ2084.Game of Connections

题目链接:http://poj.org/problem?id=2084。 思路:找规律,发现符合卡特兰数 规律(1,1,2,5,14,42…),卡特兰数的递推式a[i]=a[i-1] * (4*i-2)/(i+1),n最大为100,利用万进制来保存并计算数据。代码实现如下:#include <iostream>#include <cstdio>#include &...

2018-03-21 10:26:29

HDU1042.N!

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1042。 思路:采用万进制保存结果,参考链接:http://blog.csdn.net/lulipeng_cpp/article/details/7437641。代码如下:#include <iostream>#include <vector>#include &l...

2018-03-20 12:29:37

POJ3259.Wormholes

题目链接:http://poj.org/problem?id=3259。 思路:判断Farmer John能否通过虫洞穿越过去见到自己,问题可以转化为判断给定有权图是否存在负权圈,使用Bellman-Ford算法可以判断,代码实现如下:#include <iostream>#include <cstring>#include <vector>us...

2018-03-18 10:39:07

POJ1470.Closest Common Ancestors

题目链接:http://poj.org/problem?id=1470。 思路:给出一棵树和多个求两个节点的最近公共祖先的查询,使用tarjan 离线算法应对多对查询,使用并查集来合并顶点,不过这里不能够使用按秩合并,只能将root的所有孩子节点并到root上,代码如下:#include <iostream>#include <vector>#include &l...

2018-03-16 11:12:33

POJ3177.Redundant Paths

题目链接:http://poj.org/problem?id=3177。 思路:这道题目给出一个无向连通图,要求至少添加多少条边才能够使得任意一对顶点间至少有两条不同的路径(没有相同的边,但可以有共同的中间顶点),利用tarjan求出该连通图的边双连通分量,压缩成一个点,最后能构成一棵树,那么添加的边数=(树中度为1的节点数+1)/2,代码如下:#include <iostream...

2018-03-16 09:19:32

Poj1164.The Castle

题目链接:http://poj.org/problem?id=1164。 思路:这道题目给出了一个城堡的地图,要我们根据地图求出城堡中房间数和最大房间的面积。关键就是利用DFS来求连通分块数,再利用一个全局变量maxArea记录最大房间面积。代码实现如下:#include <iostream>using namespace std;struct G{ int ...

2018-03-14 23:51:00

Poj2488.A Knight's Journey(DFS+回溯)

题目链接:http://poj.org/problem?id=2488。 思路:这道题目给出一个p*q棋盘,让我们判断能否按照马走日字的方式走遍整个棋盘,每个格仅访问一次。可以采用DFS+回溯的方法来做,对于当前的位置,先将访问为置为True,然后按照字典序从小到大的顺序依次访问当前位置能够到达的且未被访问的位置,这样便能够保证如果能够成功遍历整个棋盘时所得到的路径是字典序最小的。代码如下:...

2018-03-14 20:57:04

Poj1077.Eight(BFS+Canton)

题目链接:http://poj.org/problem?id=1077。 思路:经典的八数码问题。棋盘的每个状态对应一个结点,如果状态A可以通过移动一步得到状态B,则从A到B有一条边。将初始状态放入队列中,开始BFS,一旦生成目标状态,BFS便可停止。对于搜索过程中的去重,可以将全排列中的一个状态经过康托展开转换为一个唯一的数来压缩存储空间,利用一个visit数组来判断遍历到的状态是否已生成。代

2018-01-16 17:01:47

Poj2186.Popular Cows(SCC)

题目链接:http://poj.org/problem?id=2186。 思路:利用tarjan构造强连通分量,并统计各强连通分量内节点数目, 然后将各强连通分量当成一个节点对待,构成一个新的图,统计出各节点的出度数,要存在受其他牛欢迎的牛,那么强连通分量构成的图必定是一个连通的DAG,而且该DAG出度为0的节点数有且只有1个,否则是不存在满足题意的牛。代码实现如下:#include

2018-01-16 09:14:21

Strongly connected component

思路:这道题目是让我们求出在经过旷日持久的互殴后至少能够留下多少只怪兽。本质是要我们根据怪兽间关系,构造有向图寻找强连通分量。如果有两个强连通分量那么每个强连通分量中至少会有一只怪兽留下,假设一个有向图中强连通分量个数为n,如果强连通分量间互不连通,那么至少能够留下n只怪兽;若两个强连通分量之间存在一条边相连,那个怪兽的数量为n-1。这道题使用Tarjan来寻找强连通分量,代码实现如下:cla

2018-01-15 11:58:50

215. Kth Largest Element in an Array

题目:Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5.

2018-01-13 11:32:22

判断有向图是否有环

题目:给出一个有向图,判断图中是否有环。 思路:可以利用拓扑排序来进行判断,有两种,一种是基于Kahn’s algorithm,另一种是基于DFS。具体可以参看:https://en.wikipedia.org/wiki/Topological_sorting。Kahn’s algorithm的大致流程是先将有向图中入度为0的顶点放入队列中,然后开始循环直到队列为空,在循环中,取出队首元素记为i...

2018-01-12 16:26:29

Poj1979.Red and Black(DFS)

题目链接:http://poj.org/problem?id=1979。 思路:简单的搜索问题,利用DFS即可。代码实现如下:#include using namespace std;const int MAXN = 25;char graph[MAXN][MAXN];bool visit[MAXN][MAXN];int w, h, cnt = 0;struct To{

2018-01-12 15:05:59

Poj1502.MPI Maelstrom(Dijkstra&Bellman-Ford)

题目链接:http://poj.org/problem?id=1502。 思路:这道题本质是求单源最短路径。Dijkstra算法解决,利用dist数组保存每个顶点到源点的最短路径,利用visited数组标示该顶点是否被访问,每一次更新dist时顺便找出未被访问点到源点的最短路径。代码实现如下:#include #include #include using namespace st

2018-01-10 22:28:54

Poj1308.Is It A Tree?

题目链接:http://poj.org/problem?id=1308。 思路:这道题目要求判断所给有向图是否为一棵树(树可以为空),运用并查集来判断加入一条边后是否符合一棵树的性质,具体判断见下面代码:#include <iostream>#include <cstdio>#include <cstring>#define MAXN 100u...

2018-01-09 18:54:58

127. Word Ladder

题目:Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:Only one letter can be changed at

2018-01-09 18:35:41

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!