chen_冲冲-CSDN博客

原创 leetcode刷题的二分搜索技巧【Python】

4 二分搜索二分查找的常用场景：寻找一个数、寻找左侧边界、寻找右侧边界。先上框架：def binary_search(nums,target): """非递归对有序数组可以寻找下标 """ if len(nums)==0: return -1 #nums=sorted(nums) l,r = 0, len(nums)-1 while l<=r: mid = l + (r-l)//2 if

2022-05-09 21:24:15 356

leetcode刷题的滑动窗口技巧【Python】滑动窗口主要左右指针的应用，其中难点判断什么条件下缩小窗口，主要还是细节问题。以下4到题举例说明：76.最小覆盖子串（困难）image.png题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = “ADOBECODEBANC”, t = “ABC”输出：“B

2022-05-09 19:08:08 419

原创 leetcode刷题的差分数组技巧【Python】

leetcode刷题的差分数组技巧【Python】2 差分数组差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。常规思路是用for循环实现，时间复杂度为O(n)。用差分数组可将时间复杂度降为O(1)。具体做法为先构建差分数组diff，diff[i]=nums[i]-nums[i-1]nums=[8,2,6,3,1]diff =[nums[0]]for i in range(1,len(nums)): diff.append(nums[i]-nums[i-1])print(

2022-05-07 19:51:15 755

原创 leetcode刷题的前缀和数组技巧【Python】

leetcode刷题的前缀和数组技巧【Python】本文主要介绍前缀和数组技巧，不代表无其他解法，比如【303.区域和检索-数组不可变】可直接用切片处理sum(nums[i:j+1])，因此主要目的是训练技巧。强烈建议大家熟悉数据结构的内容之后再去刷题，有事半功倍的效果。下面通过三道leetcode题来具体展开：303.区域和检索-数组不可变题目描述：给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。实现 NumArray 类：NumA

2022-05-07 13:17:08 546

原创 Python递归-时间复杂度

Python递归-时间复杂度递归也是常见算法之一其时间复杂度一般认为O(logn)，但递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数举例面试题：求x的n次方思路一：for循环def x_n(x,n): """ 时间复杂度O(n) """ if n==0: return 1 return x*x_n(x,n-1) if __name__=='__main__': print(x_n(2,0)

2022-03-17 20:41:58 713

原创二分查找--Python

二分查找–Python最常见的算法之一应对场景：元素升序排列的数组精确查找寻找上下边界双指针法，时间复杂度O(logn)def half_search(nums,target): """ 双指针法，时间复杂度O(logn) """ l, r = 0, len(nums)-1 while l<=r: mid =int(l+(r-l)/2) #print('mid',mid) if targe

2022-03-17 20:13:51 724

原创 leetcode 648 位数求和: 所有的长度为n的数中，各个位上的数字之和为m的这些数的和是多少呢。给定n和m，求这些数的和。python

NC648 位数求和题目描述: 所有的长度为n的数中，各个位上的数字之和为m的这些数的和是多少呢。给定n和m，求这些数的和。示例1输入2,3返回值63说明12 + 21 +30 = 63思路：两位数范围10-99，即10**(n-1)~10**n；## 返回这样的数之和# @param n int整型数的长度# @param m int整型各个为之和# @return long长整型#思路：两位数范围10-99，即10**(n-1)~10**n；求和过程超时class

2021-05-14 10:23:04 396

原创 leetcode 91 最长上升子序列：给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）python

最长递增序列题目描述：给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）示例1输入[2,1,5,3,6,4,8,9,7]返回值[1,3,4,8,9]示例2输入[1,2,8,6,4]返回值[1,2,4]说明：其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）## retrun the longest increasing subsequence# @param ar

2021-05-13 17:12:28 1328

原创 leetcode 73 数组中出现次数超过一半的数字：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。python

NC73 数组中出现次数超过一半的数字：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000两种思路。第一种思路，出现次数超过一半的数字，不管如何，必然这个数字位于数组中间的位置，因此可以采用类似于快排的划分的方法，找到位于数组中间的位置的数字，然后在顺序检索是否这个数字出

2021-05-13 17:06:00 255

原创 leetcode 119 最小的k个数：给定一个数组，找出其中最小的K个数。如果K＞数组的长度，那么返回一个空的数组python

nc119 最小的k个数：给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组两种方法。第一种方法是基于划分的方法，如果是查找第k个数字，第一次划分之后，划分的位置如果大于k，那么就在前面的子数组中进行继续划分，反之则在后面的子数组继续划分，时间复杂度O(n)；第二种方法是可以适用于海量数据的方法，该方法基于二叉树或者堆来实现，首先把数组前k个数字构建一个最大堆，然后从第k+1个数字开

2021-05-13 16:37:42 375

原创 leetcode 54 数组中相加和为0的三元组：给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。python

NC54 数组中相加和为0的三元组题目描述给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。注意：三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）解集中不能包含重复的三元组。例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)示例1输入[-2,0,1,1,2]返回值[[-2,0,2],[-2,1,1]]## # @param num

2021-05-13 16:04:01 513

原创 leetcode 536 迷失的括号序列：由‘?‘,‘(‘,‘)‘构成括号序列，将?改为‘(或‘)‘后，若能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible。python

NC536 迷失的括号序列题目描述：牛妹有括号序列brackets，因为过了太久，导致里面有些括号看不清了，所以用??代替，她想知道这个括号序列能不能恢复成合法的括号序列。具体操作是将??改为’(‘或者’)’。brackets只由’?’,’(’,’)'构成。合法的括号序列的定义： 1.空字符为合法括号序列 2.(+合法括号序列+) 为合法括号序列 3.()+合法括号序列为合法括号序列如果能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible示例1输入“()?)”返回值“()

2021-05-13 10:07:18 502

原创 leetcode 49 最长的括号子串：给出一个仅包含字符‘(‘和‘)‘的字符串，计算最长的格式正确的括号子串的长度。python

NC49 最长的括号子串题目描述：给出一个仅包含字符’(‘和’)'的字符串，计算最长的格式正确的括号子串的长度。对于字符串"(()“来说，最长的格式正确的子串是”()"，长度为2. 再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4.示例1输入“(()”返回值2注意：连续有效的括号对数，不连续的不算比如 (((())))(((()) 连续有效的括号对数就是前四对第九个第十个不能配对所以后面的两对不能算是连续有效的这是小弟写的水

2021-05-12 17:55:55 914

原创 leetcode 52 多种括号合法序列：给出一个仅包含字符‘(‘,‘)‘,‘{‘,‘}‘,‘[‘和‘]‘,的字符串，判断给出的字符串是否是合法的括号序列，括号必须以正确的顺序关闭python

leetcode 多种括号合法序列 python题目描述给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。示例1输入“[”返回值false示例2输入“[]”返回值truedef is_valid(s): if len(s)%2==1: return False while '[]' i

2021-05-08 14:38:11 793

原创 leetcode 127 最长公共子串：给定两个字符串str1和str2,输出两个字符串的最长公共子串题目保证str1和str2的最长公共子串存在且唯一。 python

leetcode 最长公共子串 python给定两个字符串str1和str2,输出两个字符串的最长公共子串题目保证str1和str2的最长公共子串存在且唯一。class Solution: def LCS(self , str1 , str2 ): # write code here s1,s2='','' for i in str1: s1=s1+i if s1 in str2:

2021-04-29 17:09:13 1367

原创 leetcode 17 最长回文子串 python

leetcode 最长回文子串 python对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n，请返回最长回文子串的长度。class Solution: def getLongestPalindrome(self, A, n): # write code here maxlen=0 for i in range(n): numa=A[i-maxlen-1:i+1]

2021-04-29 16:57:23 109

原创 leetcode 65.斐波那契数列 python

leetcode 7.斐波那契数列 python题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。 n<=39解法1#动态规划def fbnq_arr(n): if n<=1: return n arr=[0,1] for i in range(2,n+1): arr.append(arr[i-2]+arr[i-1]) return arr[-1]

2021-04-29 15:52:05 142

原创 leetcode 144 正负数交错排列（不占用额外存储空间） python

leetcode144 正负数交错排列（不占用额外存储空间） pythondef arr_rank(arr): arr=sorted(arr)#升序排序 #若均为正数或均为负数，直接输出 if arr[0]>=0 or arr[-1]<0: return arr #start,end=0,len(arr)-1 #计算负数的个数 for i in range(len(arr)):

2021-04-29 15:33:54 410

原创 leetcode 41 最长不重复子串 python

41 最长不重复子串给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。## # @param arr int整型一维数组 the array# @return int整型#class Solution: def maxLength(self , arr ): # write code here dic={} res=tmp=0 for j in range(len(arr)):

2021-04-15 22:39:03 254

原创 10 回归模型 --机器学习基础理论入门

10 回归模型 --机器学习基础理论入门1.1 线性回归模型梯度下降法最小化损失函数常用方法就是梯度下降算法，如果要收敛到最小值附近，则函数须为凸函数。如果凹凸不平，不易得到整体最小值。在多元微分学中，梯度就是函数的导数方向。沿着梯度方向可以保证能够快速达到极小值点。梯度方向就是函数在某个点的切线方向，即导数=0.梯度下降算法推导过程回归模型求解过程三种线性回归模型线性回归模型优缺点优点1）形式简单，易于建模：同事蕴含机器学习中的基本思想（思想、策略、算法）2）可演变为其

2021-02-10 10:54:42 241

原创 15 机器学习模型评估指标--机器学习基础理论入门

15 机器学习模型评估指标–机器学习基础理论入门7.1 回归问题评估指标绝对误差绝对误差为预测点与真实点之间距离之差的绝对值的平均值，即：均方误差均方误差为预测点与实际点之间距离之差平方和的均值，即因为绝对误差不是光滑的函数，所以一般都是使用均方误差作为回归问题的评估指标。7.2 分类问题评估指标分类问题结果类别：混淆矩阵TN：True negative真阴；FP：False positive假阳FN：False negative假阴；TP：True positive真阳1)

2021-02-10 10:45:58 371

原创 14 机器学习模型复杂度度量 -- 机器学习基础理论入门

14 机器学习模型复杂度度量 – 机器学习基础理论入门6.1 经验风险与结构风险机器学习三要素机器学习 = 模型 + 策略 + 算法模型：所要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数；要考虑的是按照什么样的准则从这些假设空间中选取到最优模型。策略：风险最小化或结构风险最小化。损失函数用来度量一次预测的好坏，风险函数度量平均意义下模型预测的好坏。模型关于数据集的平均损失称为经验风险（empirical risk）；再经验风险上加上表示模型复杂度的正则化项或惩罚

2021-02-10 10:40:45 1053

原创 12 聚类模型 -- 机器学习基础理论入门

13 聚类模型 – 机器学习基础理论入门4.1 聚类问题介绍定义聚类分析又称群分析，目标时将样本划分为紧密关系的子集或簇应用聚类分析在实际中应用非常广泛，如：市场细分、社交圈分析、天体数据分析等聚类要求聚类分析的目标时将样本划分为紧密关系的子集或簇。一般要求同一类内的相似度尽量大，不同类间的差异度尽量大。常用聚类算法（1） KMeans聚类（2）层次聚类（3）密度聚类（4）高斯混合聚类（5）谱聚类4.2 K-Means聚类Kmeans聚类过程Kmeans算法时无监

2021-02-08 10:57:31 656

原创 9 正则化概述 --机器学习基础理论入门

9 正则化概述 --机器学习基础理论入门9.1 模型过拟合问题过拟合的概念：过拟合就是训练出来的模型在训练集上表现很好，但是在测试集上表现较差的一种现象。图1欠拟合，图3过拟合模型出现过拟合的原因（1）数据有噪声（2）训练数据不足，有限的训练数据（3）训练模型过度导致模型非常复杂防止过拟合的方法（1） early stopping：可能陷入局部最优（2）数据集扩增：SMOTE（3）正则化方法9.2 回归问题介绍传统编程VS机器学习机器学习的数据回归问题定义

2021-02-08 10:46:09 171

原创 8 模型分类总结机器学习基本理论入门

8 模型分类总结机器学习基本理论入门监督学习与非监督学习简介简介内容（1）牢记并且理解机器学习的基本概念（2）理解监督学习和非监督学习的区别（3）建立起特征工程的概念（4）了解常见的监督学习算法和非监督学习算法经典监督学习算法（1）牢记信息论的基本公式（信息熵、交叉熵计算）（2）决策树属性划分的几种依据以及缺点（3）熟练掌握回归模型中的矩阵运算（4）了解矩阵运算时各种情况的求解（满秩、秩亏损）（5）线性到非线性的变换（换汤不换药，掌握这种非线性变换的思想）经典

2021-01-22 09:31:48 146

原创 7 判别式模型--机器学习基础理论入门

7 判别式模型–机器学习基础理论入门7.1 判别式模型与生成模型的区别判别式模型和生成模型的核心前置知识是判别式函数，其差异主要是对判别式函数的处理方式。一般来说，判别式模型和生成模型都是监督学习。贝叶斯公式再谈因为类先验的概率可以统计，所有类似然的概率是关键点。生成模型的关注点根据上课内容可知，自然现象大多满足正态分布，二项分布还是比较少的。如果已经假设类似然满足正态分布，那类似然函数也可以写出，接着判别式函数也可以写出，然后可以机进行计算，最后选择概率最大的类。判别式模型的关注点

2021-01-22 09:23:26 532

原创 6 生成模型机器学习基础理论入门

5 生成模型机器学习基础理论入门6.1 概率论基础快速回顾概率的性质减法性质：P(A-B)=P(A)-P(AB)加法性质：P(A+B)=P(A)+P(B)-P(AB)条件概率和概率的基本公式条件概率事件A发生的条件下，事件B发生的条件概率，记为P(B|A)，且：P(B|A)=P(AB)/P(A)三个基本公式乘法公式：P(AB)=P(A)P(B|A)全概率公式：贝叶斯公式：思考题设某公路上经过的货车和客车的数量之比为2：1，货车中途停车修理的概率为0.02，客车为0.01，今

2021-01-20 15:26:31 179

原创 4 经典非监督学习算法—K-Means聚类机器学习基础理论入门

4 经典非监督学习算法—K-Means聚类机器学习基础理论入门4.1 高斯混合模型本节内容主要是介绍单变量高斯混合模型的数学表示和集合表示，虽然在K均值聚类中没有很多用武之地，但是在期望最大算法中，五年会更深入的了解一般意义上的高斯混合模型以及高斯混合聚类。单高斯模型（gaussian single model）中间多，两边少时高斯模型的典型特征高斯混合模型（gaussian mixed model）随机变量X属于k个单高斯模型中的某一个，那么：4.2 度量距离的几种方法这里的

2021-01-15 15:18:25 700

原创 1 监督学习与非监督学习简介--机器学习基础理论入门

1 监督学习与非监督学习简介–机器学习基础理论入门1.1 机器学习基本概念什么是机器学习机器学习:机器学习（machine learning，ML）是一门多领域交叉学科，设计概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。输入训练集（training set）:用于建立模型验证集（validation set）:用来检验最终选择最优的模型的性能如何测试集(test set

2021-01-11 18:45:44 696

原创第一章概率与统计介绍--机器学习数学基础

第一章概率与统计介绍–机器学习数学基础1.1 简介概率与统计Lary Wasserman 在《All of Statistics》概率：The basic problem that we study in probability is: Given a data generating process, what are the properties of the outcomes?例如：抛硬币实验，假设硬币时均匀的，会产生两个结果，正面朝上或背面朝上，概率论研究的就是由这个抛硬币过程，正面朝上的

2021-01-08 16:52:11 218

原创 leetcode7：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？python

题目7：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？解析：一个整数（m）加上100后是一个完全平方数 => m+100>=0，所以m>=-100，m取值下限为-100;两个完全平方数的差是168，由于y=x^2这样的二次函数的图象是开口向上的抛物线，函数在x>0区间内单调递增，其导数可知两个相邻值y2-y1差值会越来越大 => (x+1)2-x2<=168，得x<=83.5。由于m=x^2-100，所以大约是m&lt

2020-12-17 16:24:14 2169

原创题目6：企业发放的奖金根据利润(I)的多少来提成

题目6：企业发放的奖金根据利润(I)的多少来提成：低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可提成7.5%； 20万到40万之间时，高于20万元的部分，可提成5%； 40万到60万之间时高于40万元的部分，可提成3%； 60万到100万之间时，高于60万元的部分，可提成1.5%；高于100万元时，超过100万元的部分按1%提成。从键盘输入当月利润I，求应发放奖金总数？解法1：暴力破解def profit(pf):

2020-12-17 16:22:19 1026

原创题目5：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

题目5：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。解法1class Solution: def __init__(self,n): self.n=n self._dp = [0] def numSquares(self): dp = self._dp while len(dp) <= self.n:

2020-12-17 16:20:57 1805

原创题目4：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？

题目4：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？还是和前面的题一样，这种题最简单的思路就是递归。第10次掉下所经过的总距离实际上就是前9次掉下经过的总距离再加上弹起来一次再加掉下去一次。简单思考就可以想到，第n次掉下去的高度总是等于n-1次弹起来的高度，所以我们在程序中只需要计算出n-1次掉落后弹起来的高度，结果就可以出来了。弹起来的高度怎么算呢？我们先来推一下：如题我们知道第一次掉下的高度为10，弹起来的是5，也就是(1

2020-12-17 16:17:25 2523

空空如也

空空如也