接着上一篇，mindmap更新如下内容。3.背包、队列和栈 这节主要讲述了这三种数据结构(Bag、Queue、Stack)的API、实现以及链表。Queue和Stack还含有删除元素的方法。并引出了泛型，也就是可以用它来存储任何类型的数据。在API中，类class Bag<Item> implements Iterable<Item>的表示就将Item定义为一个类型参数。在创建数据结构时，我们就可以用任何类型代替Item了。有了泛型，我们就只需要一份API来处理所有类型的数据了。这要...
在介绍朴素贝叶斯分类之前，首先介绍一下大家都比较了解的贝叶斯定理，即已知某条件概率，如何得到两个时间交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)？可以通过如下公式求得：而朴素贝叶斯分类是一种简单的分类算法，称其朴素是因为其思想基础的简单性：就文本分类而言，它认为词袋中的两两词之间的关系是相互独立的，即一个对象的特征向量中的每个维度都是相互独立。朴素贝叶斯分类的正式定义如下：（1）设为一个待...
题目描述 夫夫有一天对一个数有多少位数感兴趣，但是他又不想跟凡夫俗子一样，所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。输入描述:第一行是一个整数t(0<t<=1000000)(表示t组数据)接下来t行，每一行有一个整数n(0<=n<=10000000)输出描述:输出n！在8进制下的位数。示例1输入3 4 2 5输出2 1 3思路: 斯特林公式。斯特林公式（Stirling‘s approximation）是一条用来取n的阶乘的近似值的数学公式，求N！的位数：lnN!=N...
题目描述查找数组 arr 中第 k 小的奇数，如果不存在则返回 0. (arr [i] > 0 (i>=0))计算出时间复杂度（注意代码注释，尽可能不用全排序，不要使?库函数或脚本中已经实现好的排序算法和?具，需要??实现数据结构和所需要的算法）解题方案思路属于 Top K 问题假设数组中数据范围有限，使用一个额外数组，存放每个数字出现的次数，数组下标位置就是数字大小，此种方式为「计数排序法」时间复杂度：O(N)，N 为第 k 小的奇数的大小最坏时...
在竞赛过程中一个对拍程序可以帮你排除许多错误，如果担心自己写的正解被一些小数据卡掉，我们通常会写个对拍程序来检查正解的正确性，通过大量数据观察正解与暴力的输出是否相同。我们首先拿出我们写的可能会超时但是可以保证绝对正确的暴力程序，称作bf.exe，然后拿出我们写的待检测的正解，称作std.exe，接着我们写一个随机数据生成程序，用来一次生成一组自制随机数据用来检测输出，称作gen.exe，然后我们来写一个利用windows批...
Logistic回归为概率型非线性回归模型，是研究二分类观察结果与一些影响因素之间关系的一种多变量分析方法。通常的问题是，研究某些因素条件下某个结果是否发生，比如医学中根据病人的一些症状来判断它是否患有某种病。 在讲解Logistic回归理论之前，我们先从LR分类器说起。LR分类器，即Logistic Regression Classifier。在分类情形下，经过学习后的LR分类器是一组权值，当测试样本的数据输入时，这组权值与测试数据按照线性加和得到...
判断最长不连续回文#include <bits/stdc++.h> usingnamespace std; int main() {char ch[1500];while(gets(ch)){int len=strlen(ch),dp[1500],ans=0;for(int i=0;i<len;i++)ch[i]=tolower(ch[i]),dp[i]=1;for(int i=0;i<len;i++){int cnt=0;for(int j=i-1;j>=0;j--){int tmp=dp[j];if(ch[i]==ch[j]) dp[j]=cnt+2;cnt=max(cnt,tmp);}}for(int i=0;i<len;i++) ans=max(ans,dp[i]);printf("%d\n",ans);}return0; }过程如图bbacbbbcad1...
问题描述 每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。 每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）输入格式 两个整数，表示m和n输出格式 一个整数，表示队伍...
这一章要讲的数据结构基本以实用为主。12.1 自顶而下的伸展树一些定义展开：对于树的操作，叶结点X被插入之后，经过旋转使X成为新的树根。摊还时间：在摊还分析中的一个概念，就是求一个操作的所有情况的平均时间。和O（）的时间不同，后者体现的是最糟糕的情况下程序完成所要花费的时间。P345之中，还有一些内容不是很明白，比如图12.1之中，为什么旋转之后树之间是断开的。我不是很清楚这是怎么回事。原文：http://www.cnblogs.c...
打印字符串的全排列算法的思路：把一个字符串分成两部分，第一个字符+后面部分所有的字符。这样就能够递归的求解整个过程了：1.每个字符都做一次首字符 2.当某个字符作为首字符的时候，求后面所有字符的全排列而这里的求后面所有字符的全排列可以看成递归的子问题 全排列的递归树：但是这里还有一个问题，那就是字符串中有重复的字符时，这样的算法会增加最后的结果数目。比如说字符串aab，a+ab的全排列，然后交换还是a+ab的全排列...
单链表的操作is_empty() 链表是否为空 length() 链表?度 travel() 遍历整个链表add(item) 链表头部添加元素 append(item) 链表尾部添加元素 insert(pos, item) 指定位置添加元素 remove(item) 删除节点 search(item) 查找节点是否存在单链表的实现 class SingleLinkList(object): """单链表""" def __init__(self): ...
本篇讲述了神经网络的误差反向传播以及训练一个神经网络模型的流程更多内容参考 机器学习&深度学习神经网络可以理解为两个过程：信号的正向传播和误差的反向传播。在正向的传播过程中，计算方法为Sj=wijxi+bj，其中i是样本、j是层数。然后xj=f(Sj)，f为激活函数。引入激活函数的原因是可以带来一定的非线性特性。由于样本的y是在最后一层输出的，因此在计算误差的时候，需要从最后一层开始计算、针对与之关联的参数进行求梯度，获得...
问题描述 输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。 算法描述 由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。 定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。 计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C...
kmp的代码很短，但是不太容易理解，还是先说明一下这个算法过程吧。朴素的字符串匹配大家都懂，但是效率不高，原因在哪里？匹配过程没有充分利用已经匹配好的模版的信息，比如说，i是文本串当前字符的下标，j是要匹配的模版串当前正在匹配的字符的下标。（下标都从零开始）当匹配到i = 4， j = 4的时候失配了，朴素的匹配做法是往右边移一位然后从j开始扫，这样做效率很低。不难发现前面已经匹配好的串ab是相同的最大前缀后缀。把串...
一 无向图单源最短路径，Dijkstra算法 计算源点a到图中其他节点的最短距离，是一种贪心算法。利用局部最优，求解全局最优解。 设立一个visited访问和dist距离数组，在初始化后每一次收集一个当前最短的节点cur并将其标记为visited，然后更新这个节点的未被收集临近节点的dist值 [ if ( visited[t] != True && (dis[cur]+ Graph[cur][t]) < dis[t] ) ]，直到所有节点被访问。查找dist中的最短路径节点，可使用最小堆或二...