maershii-CSDN博客

原创 leetcode 123 二叉树中的最大路径和，且打印对应的路径

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = .

2022-01-11 21:17:52 3538

原创 python 之 yield

一个使用yield的函数，也叫做generator。一个带有 yield 的函数就是一个 generator，它和普通函数不同，生成一个 generator 看起来像函数调用，但不会执行任何函数代码，直到对其调用 next()（在 for 循环中会自动调用 next()）才开始执行。虽然执行流程仍按函数的流程执行，但每执行到一个 yield 语句就会中断，并返回一个迭代值，下次执行时从 yi...

2020-04-28 09:02:14 212

原创 git 常用命令

1. pull覆盖本地代码git fetch --allgit reset --hard origin/mastergit pull2. push review 之后若需要重复修改若需要修改：本地修改后，git add，git commit --amend，git push review3. 版本回滚git log graph找到版本号git res...

2019-05-07 10:14:16 188

原创【leetcode】二分查找

二分搜索在有序数组中查找指定值。一般二分搜索需要注意两个点：循环条件是l<r 还是 l<= r;更新r值时，是r=mid还是r= mid-1；具体问题具体分析。#二分搜索源代码def bisearch(arr, num): l = 0 r = len(arr)-1 while l <= r: mid = int((l+r)/...

2019-01-19 16:14:23 260

原创【leetcode】广度优先遍历BFS

一般使用队列，经典题型：1. 树的层次遍历及其延伸2. 完全平方数https://leetcode-cn.com/problems/perfect-squares/submissions/class Solution: def numSquares(self, n): """ :type n: int :rtype: int...

2019-01-18 14:15:08 369

原创【leetcode】深度优先遍历之孤岛问题

岛屿的个数leetcode 200. 岛屿的个数: https://leetcode-cn.com/problems/number-of-islands/思路： DFS，走过一个要改成-1。class Solution: def numIslands(self, grid): """ :type grid: List[List[str]] ...

2019-01-17 19:45:35 3252

原创【深度学习】Cyclical Learning Rates 周期学习率

论文地址：https://arxiv.org/abs/1506.01186目录1. 背景介绍2. 实现方式2.1 选取base lr，max lr2.2 选取step size 步长2.3 选取衰减函数3. 论文结果1. 背景介绍学习率是深度神经网络中很重要的一个超参数，指代的是我们在梯度下降时参数更新的步长，选取合适的学习率十分重要，太小了会减慢收敛，太大会在...

2019-01-16 15:45:06 3187

原创【NLP】n-gram LM & NN LM

文章目录1. HMM 时序模型任务描述贝叶斯转换求解问题2. n-gram 语言模型任务描述求解问题TricksSmoothingGreedy Search vs Beam SearchLog化乘为加seq2seq 是 sequence to sequence 的缩写，直白的解释是：给定一个模型，输入一个序列，然后模型会预测输出一个序列。那么如何得到预测呢（或者说我们预测的目标是什么）？，当然是...

2019-01-06 16:05:04 1484

原创【NLP】HMM 词性标注&中文分词

HMM中文分词是一种：字标注法。即将分词任务转化成对每个字进行标注标签问题。任务介绍对中文句子进行分词，比如：原句：我喜欢机器学习。分词后：我\喜欢\机器学习。问题分析对每个字赋予一个标签，‘B’代表非词尾，‘E’表示词尾。则上述例子应该被标记为：标记后：我E喜B欢E机B器B学B习E。假设观测序列为O={O1,O2,...,ON}O = \{O_1, O_2, ......

2019-01-04 22:39:53 5022

原创背包问题汇总

详细解析参考“背包九讲”：https://github.com/tianyicui/pack目录1. 背包问题 I ——0-1背包无价值2. 背包问题II ——0-1背包有价值3. 背包问题III —— 完全背包问题小结14. 背包问题IV /V ——求方案数5. 背包问题VII —— 多重背包问题6. 多重背包可行性解7. 换零钱问题1. 背...

2019-01-04 13:00:17 14132 3

原创【leetcode】输出一个数的所有质数因子

trick：不用真的找出所有质数，从2开始循环判断能否整除，直到除不尽2，再判断3，然后因为之前判断过2了，其实到4的时候肯定不会被整除了。因此以后并不会有被非质数整除的情况。 def findPrime(n): if n <= 1: return i = 2 res = [] while n > 1: if n%...

2018-12-29 07:57:55 5631 3

原创买卖股票最佳时机（I II III IV 冷冻期，手续费）

共6个问题：买卖股票最佳时机买卖股票最佳时机 II买卖股票最佳时机 III买卖股票最佳时机 IV最佳买卖股票时机含冷冻期买卖股票最佳时机含手续费分析：只允许一次交易的最大收益（一次买进卖出）动态规划： dp[i] = max(dp[i-1], prices[i] - minval)；允许多次交易的最大收益（多次买进卖出）贪心算法：只要盈利就交易；只允许有两次...

2018-12-21 20:25:57 292

原创【机器学习】为什么负梯度方向是目标函数下降最快的方向

在机器学习中，我们的目标是最小化损失函数: J(θ)J(\mathbf {\theta})J(θ)。为了快速得到最佳的参数θ\mathbf {\theta}θ,我们需要找到损失函数下降最快的方向，即找到一个θ\thetaθ移动的方向v\mathbf{v}v, 使得J(θ)−J(θ+v)J(\theta) - J(\mathbf{\theta + v})J(θ)−J(θ+v) 最大。公式描述为：v...

2018-12-20 18:23:11 2217

原创【机器学习】线性回归+代码实现

参考：《机器学习实战》源码地址以及数据：https://github.com/JieruZhang/MachineLearninginAction_src1. 标准线性回归(LR)y=Xw+b\mathbf{y} = \mathbf{X}w + by=Xw+b平方误差：∑i=1m(yi−xiTw)2平方误差：\sum_{i=1}^m (y_i - x_i^Tw)^2平方误差：i=1∑m(...

2018-12-12 12:00:59 15325 3

原创【机器学习】集成学习+代码实现

1. 概念与分类集成学习（ensemble learning）构建并结合多个学习器，先学习基学习器，再根据某种策略结合起来。结合可以是：①集成不同算法；②集成同一算法不同设置；③数据集分成多部分分给不同分类器的集成。分类：bagging， boosting2. bagging概念：采用bootstraping sampling的有放回的自助采样方法。假设原数据集N个样本，随...

2018-12-10 20:41:19 8129

原创【机器学习】分类器性能指标

1. 错误率：e = 错误分类个数/总样本数2. 正确率：TP：分类正确正例TN：分类正确负例FP：分类错误正例FN：分类错误负例precision = 分类正确的正类/(预测结果中被分为正类的个数) = TP/(TP+FP)3. 召回率：recall = 分类正确的正类/(所有正类的个数) = TP/(TP+FN)4. F1 score5. RO...

2018-12-10 09:45:04 1013

原创【深度学习】batch normalization

参考：https://www.cnblogs.com/guoyaohua/p/8724433.html引入原因：深度网络训练过程中，每一层的参数都会不断变化，很可能导致每一层的输出（即对下一层的输入）的分布发生变化，因此导致模型收敛变慢，（本质原因：输出逐渐向左右两端移动，导致曲线平缓，比如sigmoid，从而梯度消失问题产生，因此收敛越来越慢）。解决方法：BatchNorm就是在深度神经...

2018-12-07 16:44:54 335

原创【机器学习】SVM基础知识+代码实现

1. 基本知识二分类：通过分离超平面对数据点进行分类，训练分离超平面。原理：最大化支持向量到分离超平面的距离。支持向量：离分离超平面最近的点。2. 完全线性可分（硬间隔）2.1 SVM基本型分离超平面：。（训练中更新w和b，或alpha，使得分离超平面分类效果最佳）某点到分离超平面的函数距离：某点到分离超平面的几何距离：, ||w||为w的L2范数。点集到分离...

2018-12-06 16:44:44 1258

原创【机器学习】逻辑回归基础知识+代码实现

1. 基本概念逻辑回归用于二分类，将对输入的线性表示映射到0和1之间，输出为label为1的概率。优点：实现代价低，可输出分类概率。适用于数据线性不可分。缺点：容易欠拟合，分类精度可能不高，且仅限二分类。使用数据类型：数值型和标称数据。逻辑回归本质也是线性回归，但是是将线性回归映射到0/1分类上，因此逻辑回归用于分类。2. 公式推导单个输入样本为 ,第一项为1是为了直接...

2018-12-04 11:41:35 917

原创【机器学习】CART分类决策树+代码实现

1. 基础知识CART作为二叉决策树，既可以分类，也可以回归。分类时：基尼指数最小化。回归时：平方误差最小化。数据类型：标值型，连续型。连续型分类时采取“二分法”，取中间值进行左右子树的划分。2. CART分类树特征A有N个取值，将每个取值作为分界点，将数据D分为两类，然后计算基尼指数Gini(D,A), 选择基尼指数小的特征A的取值。然后对于每个特征在计算基尼指数，最后...

2018-11-30 13:22:23 7113

原创【机器学习】分类决策树基本介绍+代码实现

参考：https://blog.csdn.net/u012351768/article/details/734698131.基础知识基于特征对实例进行分类。优点：复杂度低，输出结果易于理解，缺失中间值不敏感，可处理不相关特征数据。缺点：过度匹配。适用数据类型：标称和数值型。（数值型需要离散化）构建决策树时，在每次分支时都要选择最能区分数据的特征。2.划分数据集依据2...

2018-11-29 13:41:55 3497

原创【机器学习】KNN基本介绍+代码实现

1.基本概念k近邻算法：通过测量待预测点和已知点的特征值之间的距离，选取前k个距离近的，根据多数表决的方法来分类。训练过程：无训练过程。测试过程：根据距离来分类。k越小，模型越复杂，越容易过拟合。需要对各个属性（特征）进行归一化，防止数值较大的属性对分类器的影响过大。2. 优缺点优点：精度高，异常值不敏感，对输入格式无要求。缺点：时间空间复杂度高。无法给出数据的基础...

2018-11-27 19:04:35 269

原创【算法】博弈论

1. 巴什博奕只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。方法：最后取光者赢：n%(m+1) == 0 ，后手胜；最后取光者输：(n-1)%(m+1) == 0 ，后手胜；例题：本游戏是一个二人游戏,有一堆石子一共有n个,两人轮流进行,每走一步可以取走1…m个石子,最先取光石子的一方为胜,如果游戏的双方使用的都是最优策略，请输...

2018-11-27 11:55:34 360

原创【机器学习】朴素贝叶斯基本介绍+代码实现

1. 基本概念根据先验概率和似然函数来求后验概率。一般用于分类任务。先验概率：似然函数：后验概率：根据条件独立性假设：目标函数：即求解使后验概率最大的类。训练过程：即求各个单词的条件概率，和类别的先验概率。测试过程：根据已经得到的条件概率和先验概率，计算不同类别的后验概率，取最大的类。2. 优缺点优点：简单，易于实现。缺点：由于条件独立性假...

2018-11-26 22:07:48 2389 1

原创【算法】蓄水池抽样

例题：有一个机器按自然数序列的方式吐出球，1号球，2号球......。现有一个袋子，袋子里最多只能装下k个球，并且除袋子以外没有更多的空间，球扔掉不能放回。设计一种选择方式，使得当机器吐出第N号球时，袋子中的球数是k个，同时可以保证从1号球到N号球中的每一个被选中进袋子的概率都是k/N。具体例子：有一个只能装下10个球的袋子:当吐出100个球时，袋子里有10个球，且1~100号球中每个...

2018-11-25 20:15:51 222

原创【算法】卡特兰数

相关问题：1. 给定n对括号，求合法的排列个数？2. n个数进出栈的顺序有多少种？（进栈是左括号，出栈是右括号）3. 2n个人买票，n个人拿5块钱，n个人拿10块钱，票价为5块钱，每人买一张票，且售货员手中无零钱，求合法的排队顺序？（5块钱是左括号，10块钱是右括号）4. n个高矮不同的人排成两排，每排从矮到高，并且第二排的人比对应的第一排的人高，求排列方式？（0表示第一排，1...

2018-11-25 09:46:49 299

原创【算法】布隆过滤器

应用场景：网页黑名单系统；垃圾邮件过滤系统；爬虫的网址判断重复系统；容忍一定程度的失误率；对空间要求较严格；概念：布隆过滤器可以精确的代表一个集合，可以精确判断某一元素是否在此集合里。精确程度由用户的具体设计决定，做到100%的精确是不可能的。其优势在于：利用很少的空间可以做到精确率较高。原理和过程：Bloom Filter用途：判断一个元素是否在一个...

2018-11-24 09:39:46 379

原创【算法】链表

1. 将含有random指针的链表复制一份第一遍循环：将每个节点复制一份放在原节点后面；第二遍循环：每个新复制节点的random指向的是“其对应原节点的random节点的下一个节点”，如此得到一个double的大链表；第三遍循环：将大链表拆成两份。class Solution: # 返回 RandomListNode def Clone(self,pHead):...

2018-11-16 17:32:47 110

原创【算法】顺时针打印矩阵

顺时针打印矩阵的实现：打印第一行-> 删除第一行-> 逆时针旋转矩阵，重复该过程知道矩阵为空。note：顺时针 = 上下翻转->转置逆时针 = 转置-> 上下翻转def printMatrix(M): res = [] while M != []: res += M[0] M = M[1:]...

2018-11-13 09:15:32 621

原创【深度学习】Drop out

来源：Dropout: A Simple Way to Prevent Neural Networks from Overfitting1. 原理在每个训练批次的前向传播中，以概率p保留部分神经元。目的是：简化神经网络的复杂度，降低过拟合风险。根据保留概率p计算一个概率向量r（[1,0,1,0,0,1,1....]）, 然后保留部分节点。2. 注意点因为dropout一般只...

2018-11-07 10:11:35 19679

原创【算法】排序

1. 冒泡排序def bubbleSort(arr): for i in range(len(arr)-1): for j in range(len(arr)-1-i): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1], arr[j] ...

2018-11-06 14:25:25 109

原创【算法】查找算法

1. 顺序查找无序序列or顺序序列时间复杂度：O（n）ASL = (n+1)/2def search(arr, a): for i in range(len(arr)): if arr[i] == a: return i return -12. 二分查找顺序序列时间复杂度：O（）。比较次数：a < ...

2018-11-05 20:25:20 215

原创【算法】全排列

1.全排列给定一个没有重复数字的序列，返回其所有可能的全排列#递归，取一个数放在第一个位置，然后求剩下数据的全排列，以此类推class Solution: def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ...

2018-11-05 11:11:43 830

原创【算法】树

二叉树深度优先遍历：先序遍历，中序遍历，后序遍历的递归与非递归。二叉树广度优先遍历：层次遍历。class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None#递归前序def preTran(head): if ...

2018-11-04 11:18:03 100

原创【算法】纸币面额拼凑DP

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。def fun(n): money = [1,5,10,20,50,100] dp = [0 for i in range(n+1)] # dp[i]指n为i时的拼凑方法数 dp[0] = 1 #当n为0是，方法数为1...

2018-11-03 09:56:19 937

原创【算法】子串和（乘积）最大DP

1. 最大子序和给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。nums中有正有负。class Solution: def maxSubArray(self, nums): res = [0 for i in range(len(nums))] res[0] = nums[0] ...

2018-10-31 16:09:50 401

原创【算法】LCS最长公共子串DP

基础题型：最长共公共子序列（不连续）lcs 最长公共子串（连续）lcstr 最长回文子序列（不连续）lps 最长回文子串（连续）lpstr拓展题型平方串（lcs拓展）给定一个字符串，问是否能通过添加一个字母将其变为回文串（lcstr拓展） 1. 最长公共子序列LCS输入：‘abcdef’，‘agbcje’输出：‘abce’#该版本是返回最长公共子串...

2018-10-31 13:55:59 306

原创【算法】括号问题

1. 合法括号深度一个合法的括号匹配序列有以下定义:1、空串""是一个合法的括号匹配序列2、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列3、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列4、每个合法的括号序列都可以由以上规则生成。例如: "","()","()()&

2018-10-31 10:00:34 829

原创【算法】斐波那契数列vs卡塔兰数列DP

1. 斐波那契数列公式：应用：爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？class Solution: def climbStairs(self, n): if n <= 1: return 1 res = [0 for i i...

2018-10-30 14:14:28 276

转载流程图里的形状符号的代表意义

转自豆瓣：https://www.douban.com/note/310371289/Axure里的流程图形状组件面板对于画流程图，是我们经常会遇到的问题。我们和程序工程师沟通，用再多的口水，也无法挑明的事情，画一张简明的流程图，就能很直白的说明关键问题。　　有时候你可能会懊恼，因为程序员的思维犹如计算机，你告诉他为什么没有用，你就告诉他该怎么做，是左是右，是0是1就好了。这个时候，产

2016-04-06 18:37:01 19768

空空如也

空空如也