K-means算法 算法过程描述 随机选取k个点作为簇的中心 对于每一个样本的计算到中心的距离，并将样本分到最近的簇中 更新簇的中心位置 重复上述2-3步，直至簇的中心位置不在发生改变 其中目标函数为其中表示样本是否属于簇 因为如果簇中心位置确定，那么也同时将确定，为了优化目标函数，k-means采用迭代求解的方法，首先固定，优化；然后固定优化。 首先初始化簇中心,固定，最小化: 分配每个样本点到其最近的中心点所在的簇然后固定簇中心，最小化:

LeetCode-5最长回文子串 给你一个字符串s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 示例1： 输入：s=“babad”输出：“bab”解释：“aba”同样是符合题意的答案。 示例2： 输入：s=“cbbd”输出：“bb” 提示： 1<=s.length<=1000s仅由数字和英文字母组成 采用动态规划的思想 首先单个字母一定是回文串，其次判断长度为2的回文串，然后判断长度大于等于3的回文串 创建数组dp使得dp[i][j]=1表示ij为一个回文串，易知当dp[i][j]=1时若存在s[i-1]=s[j+1]则dp[i-1][j...

聚类算法的性能度量 聚类算法就是根据数据中样本与样本之间的距离或相似度，将样本划分为若干组／类／簇，其划分的原则：簇内样本相似、簇间样本不相似，聚类的结果是产生一个簇的集合。 其划分方式主要分为两种， 嵌套类型 非嵌套类型 其中簇往往分为三种情况 基于中心的簇：簇内的点和其“中心”较为相近（或相似），和其他簇的“中心”较远，这样的一组样本形成的簇 基于邻接的簇：相比其他任何簇的点，每个点都至少和所属簇的某一个点更近 基于密度的簇：簇是由高密度的区域形成的，簇之间是一些低密度的区域 簇的相似性与距离度量 若采用距离为度量 闵可夫斯基距离：当时，为欧氏距离当时，为曼哈顿距离： 这...

DNAConsensusString TheHammingdistanceisthenumberofdifferentcharactersateachpositionfromtwostringsofequallength.Forexample,assumewearegiventhetwostrings“AGCAT”and“GGAAT.”TheHammingdistanceofthesetwostringsis2becausethe1standthe3rdcharactersofthetwostringsaredifferent.UsingtheHammingdistance,wecandef...

JoeyTakesMoney 题面翻译 题目翻译如下 题目描述 Joey很穷，因此他的朋友Chandler想要借给他一些钱。但是Joey的自尊心很强，为了不让他的自尊心受挫又能给他钱，Chandler打算和他玩一个游戏。 在这个游戏中，Chandler会给Joey一个数组。Joey可以对这个数组进行如下的操作任意次： 选择一对$i$和$j$($1\lei<j\len)$. 选择两个整数$x$和$y$($x,y\ge1$)使得$x\cdoty=a_i\cdota_j$. 将分别替换为. 最后，Joey将得到的钱就是数组中所有值的和。即Joey所得的钱 你需要求出一个整数，即Joe...

MinimumVariedNumber 题面翻译 题目描述 找出数码和为 例如，如果，那么答案是。这是最小的数字，其中所有数字都不同，数字的总和为（）。 对于给定的 输入格式 第一行包含整数(）—测试用例的数量。 每个测试用例由包含一行唯一整数：指定的()。 输出格式 输出 样例解释 对于第一个测试用例，，最小数字为。 对于第二个测试用例，，最小数字为（）。 对于第一个测试用例，，最小数字为（）。 对于第一个测试用例，，最小数字为（）。 题目描述 Findtheminimumnumberwiththegivensumofdigits$s$suchthatalldigitsinitaredis...

AdaBoost Boosting Boosting是指，仅通过训练精度比随机猜想（50%）稍高的学习器，通过集成的方式过建出强学习器。 其中boosting中最有名的是AdaBoost算法。AdaBoost是英文"AdaptiveBoosting"（自适应增强）的缩写，它的自适应在于：前一个基本分类器被错误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数才确定最终的强分类器。 AdaBoost推导 设存在数据集，其中 考虑二分类问题 因为AdaBoo...

Opponents 题面翻译 问题描述 小白有n个对手，他每天都要和这些对手PK。对于每一天，如果n个对手全部到齐，那么小白就输了一场，否则小白就赢了一场。特别的，如果某天一个对手都没有到，也算小白赢。现在已知对手d天的出场情况，请计算小白最多能连胜多少场。 输入输出格式 输入格式 第一行，两个整数n,d(1≤n,d≤100)。接下来d行，每行n个0或1的整数，依次表示这一天所有对手的到场情况，1表示到场，0表示缺席。 输出格式 一个整数，表示最多的连胜场次。 题目描述 Aryahas$n$opponentsintheschool.Eachdayhewillfightwithalloppon...

UVA108MaximumSum 题面翻译 给定一个含有正负数的二维数组，找出有最大和的子矩阵。矩阵的和指矩阵中所有元素的和。一个子矩阵是任意在总矩阵中大小为1x1或更大的邻近子数组，例如在下面的矩阵中:0−2−70 92−62 −41−41 −180−2 (最大子矩阵)在左下方: 92 −41 −18 并且和为15. 输入: 包括一个N和NxN的矩阵N<=100矩阵中的数字在区间[-127,127]内 输出: 最大子矩阵的和 题目描述 PDF 输入格式 输出格式 样例1 样例输入1 4 0-2-70 92-62 -41-41 -180-2 样例输出1 15 soluti...

给你一个非负整数数组nums和一个整数target。 向数组中的每个整数前添加‘+’或‘-’，然后串联起所有整数，可以构造一个表达式： 例如，nums=[2,1]，可以在2之前添加‘+’，在1之前添加‘-’，然后串联起来得到表达式“+2-1”。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。 示例1： 输入：nums=[1,1,1,1,1],target=3输出：5解释：一共有5种方法让最终目标和为3。-1+1+1+1+1=3+11+1+1+1=3+1+11+1+1=3+1+1+11+1=3+1+1+1+11=3示例2： 输入：nums=[1],target=1输出：...

完美滤波器 如下图所示，第级为输入图像，其中第级为第级的尺寸减半的存在，直至为 设原图像像素点个数为，则图像金字塔的总像素个数为对于图像金字塔建模，设第级为图像降低分辨率后的近似图像，这可以视为由第级图像经过滤波操作和下采样实现后的存在，则第级可以视为第级经过上采样和插值操作后的存在，即如下图所示： 其中对图像进行上采样操作，索引所对应的值为：图像进行下采样操作，索引所对应的值为：上采样可看成是在序列中的每一个样本后插人0;下采样可看成是每隔一个样本丢弃一个样本。 设存在输入信号，其中与 并经过下采样得到与。然后经过上采样，与滤波和并将信号与合并得到信号，若与相等，可以称为采用了完美...

给你一个由无重复正整数组成的集合nums，请你找出并返回其中最大的整除子集answer，子集中每一元素对(answer[i],answer[j])都应当满足：answer[i]%answer[j]=0，或answer[j]%answer[i]=0,如果存在多个有效解子集，返回其中任何一个均可。 示例1： 输入：nums=[1,2,3]输出：[1,2]解释：[1,3]也会被视为正确答案。示例2： 输入：nums=[1,2,4,8]输出：[1,2,4,8] 提示： 1<=nums.length<=10001<=nums[i]<=2109nums中的所有整数互不相同 将输入...

给你一个整数n，请你找出并返回第n个丑数。 丑数就是质因子只包含2、3和5的正整数。 示例1： 输入：n=10输出：12解释：[1,2,3,4,5,6,8,9,10,12]是由前10个丑数组成的序列。示例2： 输入：n=1输出：1解释：1通常被视为丑数。 提示： 1<=n<=1690 设dp[i]为第i个最大的丑数，易知第一个丑数为1，其余的丑数则是较小的丑数的2倍3倍或者5倍，设a=b=c=1，dp[i]=min(dp[a]2,dp[b]3,dp[c]5)，若dp[i]=dp[a]2，则a，若dp[i]=dp[b]3，则b，若dp[i]=dp[c]5，则c。 最优子结构为dp[...

给你一个整数n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。 示例1： 输入：n=3输出：5示例2： 输入：n=1输出：1 采用dp[i]表示含有i个节点的二叉搜索树，其中二叉搜索树由左子树和右子树以及根结点组成。其中dp[i]由含有i-j节点的左子树和j-1节点的右子树和一个根结点组成。所以dp[i]的构造形式由左右子树决定。 最优子结构dp[i] 状态转移方程：dp[i]+=(dp[ij]dp[j1]) intnumTrees(intn){ intdp[20]={0}; dp[0]=1; dp[1]=1; for(inti=2;i&l...

打家劫舍 (a)你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 示例1： 输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。偷窃到的最高金额=1+3=4。示例2： 输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。偷窃到的最高金额=2...

UVA437巴比伦塔TheTowerofBabylon 题面翻译 题目描述 你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质，我们现在会告诉你整个传说： 巴比伦人有种长方形方块，每种有无限个，第种方块的三边边长是。对于每一个方块，你可以任意选择一面作为底，这样高就随着确定了。举个例子，同一种方块，可能其中一个是竖着放的，一个是侧着放的，一个是横着放的。 他们想要用堆方块的方式建尽可能高的塔。问题是，只有一个方块的底的两条边严格小于另一个方块的底的两条边，这个方块才能堆在另一个上面。这意味着，一个方块甚至不能堆在一个底的尺寸与它一样的方块的上面。 你...