ITeye博客

yzmduncan的博客

yzmduncan · 共 92 篇文章

写博客是个好习惯

不记得上一次写博客是什么时候了。平常工作忙的像狗,周末有时也加班,空余时间太少。这周妹纸出差,难得清静。 这一年工作节奏还是蛮快的,参与开发5、6个系统,也学了做了不少东西,有技术性强的,也有边缘性的活,有前端、DB,也有框架、算法,还有线程、缓存、GC。搞技术的还是得总结一下自己学到的东西,拿出来晒晒,一来温故知新,二来也给后面遇到问题的人有个参考。 在这里先列个提纲出来,后面详细分章节。 前端 刚入职其实就被拉进去做前端了,哪里需要就去哪里。在工作中不会有太多时间让你彻底的学习,对于我这个前端小白,除了了解最基础的js、css语法,知道一些现成流行的框架能干啥以外,最好的方式就是在chr…

2015-06-28 01:36 · 评论(1)

朴素贝叶斯在文本分类中的应用

听过朴素贝叶斯的人,知道多项式朴素贝叶斯是神马,伯努利贝叶斯是神马吗?如果不知道,请继续读下去。 其实所谓的“多项式”或“伯努利”,只不过是在求先验概率和条件概率时统计方法不一样,基本原理没变。 贝叶斯分类算法(Naive Bayes)是一种基于统计的概率模型算法。在许多场合,朴素贝叶斯可以与决策树,SVM相媲美。它能应用到大数据中,方法简单且分类准确率高、速度快。但它基于属性之间的独立,在实际情况中经常是不成立的,因此分类准确率可能会下降。总的来说,NB是学习代价较低(理论简单,不像SVM和神经网络那么复杂),但效果较好的分类算法。 贝叶斯分类算法基于托马斯贝叶斯发明的贝叶斯定理,他提出的…

2013-08-29 16:50 · 评论(0)

分类算法综述

分类的概念很简单,就是给出一个样本x,判断样本所属的类别y,分类器就是映射函数f: y=f(x)。当然,这个函数是需要根据以往的经验(大量已知类别的样本集)来构造的。这个构造的过程,称为训练,而如何构造,就是分类算法了。 数据挖掘中分类算法有很多,它们通过对已知类别训练集的分析,从中发现分类规则,以此预测新数据的类别。分类算法应用非常广泛,银行中风险评估、客户类别分类、文本检索和搜索引擎分类、安全领域中的入侵检测等等。主要包括以下几种分类模型: 相似度模型:K-近邻,Rocchio 概率模型:贝叶斯 线性模型:SVM 非线性模型:神经网络,决策树 K-近邻与Rocchio KNN(K-Nea…

2013-08-25 15:44 · 评论(0)

解线性方程组——高斯消元法

例: ZOJ3645 **题意:**高斯消元模板题(浮点型) /** 高斯消元求解线性方程组. */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; ///高斯消元模板 const double eps = 1e-12; const int Max_M = 15; ///m个方程,n个变量 const int Max_N = 15; int m, n; double Aug[Max_M][Max_N+1]; /…

2012-12-03 22:00 · 评论(0)

ZOJ 2012.11月赛

本来上周日(11.25)轮到我做汇报,PPT都写好了,看到ZOJ有月赛,便想练练手。 当时做比赛的时候已经三点了,看到DFIJ这四题出的比较多,就决定拿下这4道题。 J题( ZOJ3675 ) Trim the Nails **题意:**指甲宽为m,指甲刀宽为n,单位均为毫米,但指甲刀是不完整的,'*'表示完整,'.'表示不完整。问最少剪几次可以剪完指甲。注意指甲刀可以翻转。比如输入m=7 n=6且指甲刀表示为***..*: fingernail: ------- nail clipper: *..*** nail clipper turned over: ***..* Requires t…

2012-12-01 15:02 · 评论(0)

【转】STK8.1.1安装方法

STK简介 美国Analytical Graphics公司开发的STK卫星工具包软件,是航天工业领先的商品化分析软件。 STK可以快速方便地分析复杂的陆、海、空、天任务, 并提供易于理解的图表和文本形式的分析结果,确定最佳解决方案。它支持航天任务周期的全过程,包括政策、概念、需求、设计、制造、测试、发射、运行和应用。 STK/Pro 8.1.1提供分析引擎用于计算数据、并可显示多种形式的二维地图,显示卫星和其它对象如运载火箭、地面车辆、目标等。STK的核心能力是产生位置和姿态数据、获取时间、遥感器覆盖分析。 STK专业版扩展了STK的基本分析能力,包括附加的轨道预报算法、姿态定义、坐标类型和…

2012-10-28 12:57 · 评论(0)

计算几何基础

计算几何是研究几何目标在计算机环境内的数学表示,计算等方面的理论和应用。 首先必须理解向量的点积和叉积。点积一般用来计算投影,数学证明等。叉积用来判断相对方位,求面积等,叉积的模为平行四边形面积。 问题1. 如何判断两条线段相交 通过快速排斥实验和跨立实验。快速排斥实验室看以两条线段作为对角线的矩形是否相交,若不相交,则必定两条线段不相交;跨立实验是看其中一条线段是否跨立另一条线段,可以通过矢量叉积实现。 问题2. 如何判断点在多边形内( ZOJ1081 ) 一种简单的方法——射线法。从该点引一条水平射线,根据射线与多边形的交点数的奇偶性来判断。注意一些特殊情况。 问题3. 如何求任意简单多…

2012-08-17 15:51 · 评论(0)

简单树形DP

树形DP,即是在一颗树上进行DP,一般是有叶子节点状态推出根节点状态。结合几个简单例子分析。 例1. POJ2342 / POJ3342 【题意】 公司有n个人,每个人有价值vi,有一天举办年会,每个人都可以参加,但有严格的等级制度,参加活动时,不能同时出现a和a的上司,问如何才能使总和最大。 【分析】 每个人只有去和不去两种状态,设DP[i][0]和DP[i][1]分别表示第i个人不参加和参加年会,获得的总的最大价值。 则状态转移方程为: DP[i][1] += DP[j][0], DP[i][0] += max{DP[j][0],DP[j][1]};其中j为i的孩子节点。 这样,从根节点…

2012-07-13 13:46 · 评论(0)

最长上升子序列O(nlogn)

最近在做单调队列,发现了最长上升子序列O(nlogn)的求法也有利用单调队列的思想。 最长递增子序列问题:在一列数中寻找一些数,这些数满足:任意两个数a[i]和a[j],若i<j,必有a[i]<a[j],这样最长的子序列称为最长递增子序列。 设dp[i]表示以i为结尾的最长递增子序列的长度,则状态转移方程为: dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i]. 这样简单的复杂度为O(n^2),其实还有更好的方法。 考虑两个数a[x]和a[y],x<y且a[x]<a[y],且dp[x]=dp[y],当a[t]要选择时,到底取哪一个构成最优的呢?显然选取a[x]更有潜…

2012-06-01 14:31 · 评论(0)

单调队列及其应用

单调队列 即队列内元素单调递增或递减,删除数据可以在队头或者队尾,加入元素只能在队尾加入。 由于单调队列的队头一定是最小值,故查询为O(1);每个元素最多进队一次,出队一次,摊排分析下来仍然是O(1). 例1. 广告印刷 【问题描述】 最近,afy决定给TOJ印刷广告,广告牌是刷在城市的建筑物上的,城市里有紧靠着的N(N<=400000)个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度,从左到右给出每个建筑物的高度H1,H2…HN,0<Hi<=1,000,000,000,并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。 【输入样例】 6 5…

2012-06-01 13:57 · 评论(0)

平面最近点对问题详解

在二维平面上的n个点中,如何快速的找出最近的一对点,就是最近点对问题。 一种简单的想法是暴力枚举每两个点,记录最小距离,显然,时间复杂度为O(n^2)。 在这里介绍一种时间复杂度为O(nlognlogn)的算法。其实,这里用到了 分治 的思想。将所给平面上n个点的集合S分成两个子集S1和S2,每个子集中约有n/2个点。然后在每个子集中递归地求最接近的点对。在这里,一个关键的问题是如何实现分治法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对。如果这两个点分别在S1和S2中,问题就变得复杂了。 为了使问题变得简单, 首先考虑一维的情形 。此时,S中的n个点退化为x轴上的…

2012-02-29 21:17 · 评论(0)

组合数学——polya定理及其应用

Polya定理 设有n个对象,G是这n个对象上的置换群,用m种颜色涂染这n个对象,每个对象涂染一种颜色,问有多少种染色方案?一种染色方案在群G的作用下变为另一种方案,则这两种方案当作是一种方案。 方案数为 POJ2409 **题意:**一家项链公司生产手镯。n颗珠子形成一个环,用m种颜色给n颗珠子染色,就得到了各种各样的手镯。但是,经过旋转和翻转使之吻合的算同一种方案。 例如,当用2种颜色对5颗珠子进行染色的方案数为8,如下图所示。 **解:**显然,对于这n个对象,有n种旋转和n种翻转。 1. 对于旋转,有c(gi) = gcd(n,i),i为转动几颗珠子。 2. 对于翻转,当n为奇数时,…

2012-02-11 19:48 · 评论(0)

组合数学——错排问题及其应用

n个有序的元素应有n!个不同的排列,若一个排列使得所有的元素都不在原来位置上,则称这个排列为错排。 错排公式推导 设n个数1,2,3...,n错排数目为Dn,对于其中任意一个数i: (1) 数i分别与其他的n-1个数交换位置,其余n-2个数进行错排,共得到(n-1)Dn-2个错排; (2) 对除数i以外的n-1个数进行错排,然后i与其中每个数互换,得到(n-1)Dn-1个错排。 因此,得到递推关系:Dn=(n-1)(Dn-1 + Dn-2),D1=0,D2=1。它的通解为Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)! - ... +(-)C(n,n)1!。 HDU2048 题…

2012-02-10 15:50 · 评论(0)

组合数学——鸽巢原理及其应用

所谓鸽巢原理,即n+1只鸽子,只有n个巢,则至少有一鸽巢有两只鸽子。 鸽巢原理理解起来并不困难,有些题目需要转换一下。 POJ3770 **题意:**有n个数,可能相同也可能不相同,从中取出一些数,使它们的和能被c整除(c<=n),任意输出一种方案。 **解:**构造序列si,使得 s1 = a1 s2 = a1 + a2 s3 = a1 + a2 + a3 ... sn = a1 + a2 + ... + an 这样,有两种可能: (1) 若其中有一项si是c的倍数,则即找到解; (2) 否则,si=ri (mod c),取值只可能在[1,c-1]这c-1个数,然而有n个数,且c<=n,则…

2012-02-10 13:20 · 评论(0)

数论——中国剩余定理(互质与非互质)

中国剩余定理 中国剩余定理是中国古代求解一次同余方程组的方法,是数论中的一个重要定理。 设m1,m2,m3,...,mk是两两互素的正整数,即gcd(mi,mj)=1,i!=j,i,j=1,2,3,...,k. 则同余方程组: x = a1 (mod n1) x = a2 (mod n2) ... x = ak (mod nk) 模[n1,n2,...nk]有唯一解,即在[n1,n2,...,nk]的意义下,存在唯一的x,满足: x = ai mod [n1,n2,...,nk], i=1,2,3,...,k。 解可以写为这种形式: x = sigma(ai mi*mi') mod(N) *…

2011-12-24 10:38 · 评论(0)