chocolate_chuqi的博客

原创 剑指offer 面试题21（调整该数组中数字的顺序使奇数在偶数前） python

 题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。  方法一：运行时间：30ms占用内存：5660k# -*- coding:utf-8 -*-class Solution:    def reOrderArray(self, a...

原创 剑指offer 面试题22（链表中倒数第K个节点） python

题目描述输入一个链表，输出该链表中倒数第k个结点。运行时间：28ms占用内存：5728k方法一：# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:  ...

原创 剑指offer 面试题18（删除链表中重复的结点） python

题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5   思路看备注：# -*- coding:utf-8 -*-# class ListNode:#     def __init__(sel...

原创 剑指offer 面试题17（打印从1到最大的n位数） python

题目：输入数字n,按顺序打印从1到最大的n位的十进制数。比如输入3，就打出1，2,3...999 代码（一）：# -*- coding:utf-8 -*-class Solution:    def Power(self, num):        # write code here        if num<= 0:            return 0   ...

原创 决策树（ID3、C4.5、CART）

决策树的思路：首先决策树是由结点和有向边组成的。结点分为：内部结点和叶结点。每个内部结点对应一个特征，每个叶结点对应就是：分类--》一个类；回归--》一个值。决策树，从根结点开始，进行一个if-then判断。因为根据给定的训练集可以训练出很多个不同的决策树，因此从很多决策树中选出最优是一个NP-HARD问题。决策树学习是一个递归过程，选取一个次优解。我们希望最后叶结...

原创 L1、L2+回归模型（lasso、ridge、elasticnet）

嵌入式选择有没有可能将特征选择过程与学习器训练过程融为一体。以前我们设计学习器是希望均方误差达到最小值----min E(x;w)但是如果我们希望把不需要的特征变为0呢？我们可以把但是这是一个NP-hard问题。（NP-HARD问题可以理解为容易算出任何一种情况的结果值，但是要计算所有结果值然后统计出最小最大值会很难。） 所以怎么办呢？两个办法，办法一： ...

原创 剑指offer 面试题16（数值的整数次方） python

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 代码（一）：# -*- coding:utf-8 -*-class Solution:    def Power(self, base, exponent):        # write code here        return base**ex...

原创 剑指offer 面试题15（二进制中1的个数） python

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 代码（一）：# -*- coding:utf-8 -*-class Solution:    def NumberOf1(self, n):        # write code here        if n < 0 :            n = n & 0xffffff...

原创 特征选择（过滤式、包裹式）

首先先说说特征选择。特征选择包含三大类：过滤式、包裹式、嵌入式。 过滤式（filter）它是先设计一个过滤方法进行特征选择，再去训练学习器。而这个过滤方式是设计一个“相关统计量”，去对特征进行计算，最后设定一个阈值去进行选择。 相关统计量计算：对于每个样本xi，他都会做以下事情。找出同类中，最邻近的样本x1；在异类中，找出最邻近的x2。如果xi与x1更近，说...

原创 线性模型（二）广义线性模型

在线性回归中，我们是假设目标Y是符合正态分布的。那么如果Y不符合正态分布呢？那我们假设Y符合一个更加通用的指数族分布。借助指数族分布，对响应变量Y的描述将不再局限于正态分布，称观测 来自指数族分布，如果其概率密度函数可以表达为如下形式： 建立指数分布族：伯努利分布（逻辑回归）高斯分布（正态分布）泊松分布 用广义线性模型进行建模：第一步明...

原创 剑指offer 面试题14（剪绳子） python

题目：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],...,k[m].请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18. 代码（一）：# -*- coding:utf-8 -*-class So...

原创 剑指offer 面试题13（机器人的运动范围） python

题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 代码（一）：# -*- coding...

原创 线性回归模型一（线性回归）

 线性回归模型 先假设只有一个特征的时候。我们的目的就是能找出最好的w和b是预测出来的y尽可能接近真实的y。预测函数：F(x) = w*x+b （其中w是权重，x是特征，b是偏差）误差方程：求导方程及其过程：对于凸函数求解，就是导数为0时最优。  如果是多元，也就是多个特征呢？   上式在满秩的时候成立。 ...

原创 剑指offer 面试题12（矩阵中的路径） python

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符...

原创 回顾及总结--评价指标（分类指标）。

对学习器的泛化性能进行评估，不仅仅需要有效可行的实验估计方法，还需要有衡量模型泛华能力的评价标准，这就是性能度量。我们通常会根据不同的业务选出适合的业务指标。评价指标大概有1、回归的有：RMSE(平方根误差)、MAE（平均绝对误差）、MSE(平均平方误差)、Coefficient of determination (决定系数)。2、分类的有：精度、召回率、精确率、F值、ROC-AUC ...

原创 回顾及总结--评价指标（回归指标）

对学习器的泛化性能进行评估，不仅仅需要有效可行的实验估计方法，还需要有衡量模型泛华能力的评价标准，这就是性能度量。我们通常会根据不同的业务选出适合的业务指标。评价指标大概有1、回归的有：RMSE(平方根误差)、MAE（平均绝对误差）、MSE(平均平方误差)、Coefficient of determination (决定系数)。2、分类的有：精确率、召回率、准确率、F值、ROC-AUC...

原创 剑指offer 面试题11 （旋转数组的最小数字） python

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 代码（一）：# -*- coding:utf-8 -*-class Solution:    ...

原创 剑指offer 面试题10 （斐波那契数列） python

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39  代码（1）：# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        # write code here        if n == 1:   ...

原创 剑指offer 面试题9 （用两个栈实现队列） python

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 代码（）：# -*- coding:utf-8 -*-class Solution:    def __init__(self):        self.stack_A = []        self.stack_B = []    def push(self, node...

原创 剑指offer 面试题8 （二叉树的下一个节点） python

题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的一个节点？书中的节点除了有两个分别指向左、右子节点指针，还有一个指向父节点的指针。 代码：# -*- coding:utf-8 -*-# class TreeLinkNode:#     def __init__(self, x):#         self.val = x#         self.lef...

原创 剑指offer 面试题7 （重建二叉树） python

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 代码（递归）：# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(sel...

原创 剑指offer 面试题6 （从尾到头打印链表） python

题目描述请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 方法一：# -*- coding:utf-8 -*-class Solution:    # s 源字符串    def replaceSpace(self, s):        # write code here        s_...

原创 剑指offer 面试题5 （替换空格） python

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 方法一：# -*- coding:utf-8 -*-class Solution:    # array 二维列表    def Find(self, target, array):        # write code here...

原创 剑指offer 面试题4 （二维数组中的查找）python

题目详情在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。1 2 8 92 4 9 124 7 10 136 8 11 15方法一：# -*- coding:utf-8 -*-clas...

原创 剑指offer：题目3（数组中重复的数字）--python

题目详情在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。方法一：# -*- coding:utf-8 -*-class Solution:    # 这里要特别注意~找到任意重复的一...

原创 模拟退火法

Simulated Annealing(SA)之前说的遗传算法、粒子群、蚁群都是模拟生物的规律。那今天说的模拟退火法，就不是模仿生物规律，是学习物理中固体物质的退火过程。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：1.加温过程加温过程对算法设定初温    目的是增强粒子的热运动，使其偏离平衡位置。当温度足够时，固体将融为液体，从而消除系统原先存在的非均匀状态。2.等温过程等温过...

原创 蚁群算法（ACA , Ant Colony Algorithm）

此文通过学习多个视频及博客总结，如有侵犯请私聊。蚁群算法，是模仿蚂蚁的觅食行为。一、蚂蚁是怎样找到食物的？如图，假设两个点之间的距离和时间是相等的，通过观察，我们会发现，走ABD比走ACD花的时间和力气少很多。但是，从A出发还没有走过的蚂蚁，他们开始的时候，并不知道在哪一条更好。所以，他们随机地走，并且为了方便以后自己和同伴知道哪一条路比较好，他们会一边走，一遍释放一个信息素。这个信息素怎么释放才...

原创 粒子群优化 PSO-Particle Swarm Optimization

该文章是根据多个学习视频和各个优秀博客和自己的一些总结，内容如有侵犯，务必私聊。上次我们讲到了-遗传算法。这次我们会分享另一个学习大自然规律来的算法--粒子群优化，一个学习鸟类捕食的优化算法。一、先来讲个故事：如果在一片大森林里面，可能藏有若干的食物。有一群刚来到的鸟，它们都还不知道食物在哪里，但是他们会感应得到食物大概在哪里。然后离最近的小鸟会广播出去，自己的位置。然后整个鸟类群都会改变方向，沿...

原创 遗传算法（Genetic Algorithm, GA）

注：此文是学习了多个博客和视频，整理总结。如有侵犯，请私聊。一、遗传算法是什么？1.就是在一个有可能存在解集的种群开始寻找。（假设我有X这个集，X集中包含不重复的X1,X2,X3....，我的最优解有可能在里面，这个X就是我的种群）2.种群是由多个个体组成的。（个体就是里面的X1,X2,X3.....）3.一个个体是由多个基因组成的。（而我每一个Xi,都是由多个x1，x2,x3...组成的。这些x...

原创 Feasibility of Learning & Training versus Test（林轩田-机器学习）

整体思路：1.想办法找出training set 训练出来的hypothesis 对test set的作用效果。2.通过hoeffding不等式，把通过训练集找出适合测试集且效果好hypothesis。 做数学题或者考公务员的时候，经常会有寻找规律的题目。那我们做一下下面这道题：现实生活中，这类找规律的题不一定会有正确答案。你可以说g(x)=1/-1。 问题：那么我们怎样保证通过训练trainin...

原创 PLA总结（林轩田）

原创 自主学习（active learning）

我是一名小小白~~~一边学习一边总结~~~一边更新~~~是什么？自主学习，可以理解为询问式学习。通常监督学习都喜欢丢一大堆的数据，然后通过对所有数据进行处理得出结果。往往数据量越大，得到的结果可能会相对好一点。而自主学习的特点在于他可以自行选择有用数据去进行学习。这样我们可以用更少的训练样本去训练出更好的分类器。 注：监督学习是把样本都标注好；非监督学习是没有把样本标注；而自主学习呢，他是把一小部...