- 博客(147)
- 收藏
- 关注
RSS订阅原创 LeetCode：翻转链表||（python）
1. 题目描述反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL2. 思路题目要求一趟遍历。处理链表的题，一般会生成一个dummy Node，使得du...
2019-07-03 20:22:47
397
1
原创 统计学习方法——朴素贝叶斯法原理
1. 朴素贝叶斯贝叶斯是因为使用了贝叶斯定理，朴素是因为特征条件对立性的假设。朴素贝叶斯因此得名。2. 模型2.1 联合概率分布2.2 学习联合概率分布的目的朴素贝叶斯法通过训练数据集学习联合概率分布P(X,Y)。学习联合概率分布P(X,Y)分布的目的，是为了得到先验概率和条件概率分布。（贝叶斯定理所需要的条件）2.3 条件独立性假设条件概率分布和先验概率分布我们都可以利用训...
2019-07-03 11:50:05
596
原创 LeetCode：复原IP地址
1. 题目描述给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例:输入: “25525511135”输出: [“255.255.11.135”, “255.255.111.35”]2. 思路第一种方法就是暴力枚举，将**.**所有可能放的位置全部列举出来，然后在挑选符合的放法，太复杂，不考虑第二种方法就是回溯法：完整思路，在代码中说。2.1 代码class ...
2019-07-02 11:59:45
413
原创 leetcode：不同的二叉搜索树 II（Python）
1. 题目描述给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。示例:输入: 3输出:[[1,null,3,2],[3,2,null,1],[3,1,null,null,2],[2,1,3],[1,null,2,null,3]]解释:以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 ...
2019-07-01 11:23:56
312
原创 leetcode：不同的二叉搜索树（python）
1. 题目描述给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 ...
2019-07-01 09:30:11
380
原创 leetcode：交错字符串（python）
1. 题目描述给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1:输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出: true示例 2:输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出: false2. 思路2.1 递归...
2019-06-27 14:21:13
868
原创 leetcode：恢复二叉搜索树（python）
1. 题目描述二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。示例 1:输入: [1,3,null,null,2] 1 /3 \ 2输出: [3,1,null,null,2] 3 / 1 \ 2示例 2:输入: [3,1,4,null,null,2] 3 / \1 4 / 2输出: [2,1,...
2019-06-26 22:25:52
542
原创 k近邻算法之kd树优化（kd树的构造和搜索）——基于Python
前言kd树的实现原理，我之前的一篇博客写了一下kd树优化的k近邻算法参考文章：wenffe：python实现KD树1. kd树的构造import numpy as npclass Node(object): """ 定义节点类： val：节点中的实例点 label：节点中实例的类别 dim：当前节点的分割维度 left：节点的左子树 right：节点的右子树 pare...
2019-06-26 16:01:59
2853
原创 kd树优化的k近邻算法
前言k紧邻最简单的实现方法是线性扫描，即遍历整个训练数据集，计算每一个训练实例与输入实例之间的距离。时间复杂度为o（N），当训练数据集中的实例点数N很大时，非常耗时，为了提高k近邻搜索的效率，可以使用特殊的数据结构存储训练数据，以减少计算距离的次数。常用的算法就是kd树方法。1. kd—TreeKd-Tree，即K-dimensional tree，是一棵二叉树，树中存储的是一些K维数据。在...
2019-06-26 14:21:38
1935
原创 K近邻算法的python实现
前言在K近邻的原始算法中，没有对K近邻的方法进行优化，还是遍历训练集，找到与输入实例最近的K个训练实例，统计他们的类别，以此作为输入实例类别的判断。具体的模型理论见：统计学习方法——K近邻法（原始方法）1. K近邻算法的实现在算法实现的过程中，利用的是欧氏距离进行点与点之间的距离度量。在进行数据运算的时候，没有利用numpy，而是利用Python中自带的list来进行数据的计算。def k...
2019-06-25 21:27:46
2271
原创 统计学习方法——K近邻法（原始方法）
1. K近邻算法1.1 K近邻算法过程2. K近邻模型2.1 模型的基本要素2.2 点与点之间的距离度量特征空间中两个实例点的距离是两个实例点相似程度的反映，K近邻模型的特征空间一般是n维实数向量空间。使用的距离是欧氏距离，但也可以是其他距离。2.3 K值的选择K值得选择会对K近邻算法的结果产生重大影响。如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学...
2019-06-25 21:18:12
331
原创 leetcode：从前序与中序遍历序列构造二叉树（python）
1. 题目描述根据一棵树的前序遍历与中序遍历构造二叉树。注意:你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / \ 9 20 / \ 15 72. 思路剑指offer中有这样一道题。还是利用递归，主要是根据先序遍...
2019-06-25 10:27:58
650
原创 leetcode：先序遍历构造二叉树（python）
1. 题目描述返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍...
2019-06-25 09:47:08
839
原创 leetcoe：二叉树的层次遍历||（python）
1. 题目描述给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[[15,7],[9,20],[3]]2. 思路层次遍历，然后反转。2.1 代码...
2019-06-23 11:36:30
518
原创 leetcode：将有序数组转换为二叉搜索树（python）
1. 题目描述将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / ...
2019-06-23 10:53:27
277
原创 leetcode：有序链表转二叉搜索树
1. 题目描述给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定的有序链表： [-10, -3, 0, 5, 9],一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 ...
2019-06-23 10:33:37
227
原创 leetcode：路径总和||（python）
1. 题目描述给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 ...
2019-06-22 11:02:17
221
原创 leetcode：路径总和（python）
1. 题目描述给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ ...
2019-06-22 10:35:36
262
原创 leetcode：不同的子序列（python）
1. 题目描述给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）示例 1:输入: S = “rabbbit”, T = “rabbit”输出: 3解释:如下图所示, 有 3 种可以...
2019-06-22 10:05:54
307
原创 leetcode：填充每个节点的下一个右侧节点指针 II（python）
1. 题目描述给定一个二叉树struct Node {int val;Node *left;Node *right;Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。示例：解释：给定二叉树如图 A 所示，你的函数应该填充...
2019-06-20 13:54:48
396
原创 leetcode：填充每一个节点的下一个右侧节点（python）
1. 题目描述给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：struct Node {int val;Node *left;Node *right;Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置...
2019-06-20 10:20:52
273
原创 leetcode：杨辉三角||（python）
1. 题目描述给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例:输入: 3输出: [1,3,3,1]进阶：空间复杂度为o(k)2. 思路还是利用动态规划。设置一个长度为k+1（当k为0时，返回的是第一行……）的dp数组。然后从第一层开始，开始更新数组。假如当前的层为第i层，那么数组的前i-1个元素是杨辉三...
2019-06-19 18:59:00
351
原创 leetcode：杨辉三角（python）
1. 题目描述给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例:输入: 5输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]2. 思路根据杨辉三角的规则，逐层添加元素2.1 python代码class Solution: def generat...
2019-06-19 16:24:11
571
原创 leetcode：三角形最小路径和（python）
1. 题目描述给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形：[ [2], [3,4], [6,5,7],[4,1,8,3]]自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。2. 思路...
2019-06-19 15:24:16
900
原创 统计学习理论——感知机学习算法python实现（原始形式和对偶形式）
感知机的学习算法分为原始形式和对偶形式。具体模型理论：统计学习——感知机本文将书中的两个算法过程，利用python实现了一下。进行机器学习算法实现的时候，可以利用功能强大的数学运算numpy库。但在这篇文章里，没有用numpy库。数据集以数组的方式输入，在进行相关的向量运算的时候，利用数组的下标来对数组中的数据进行运算。1. 感知机学习算法的原始形式def vectorInnerProd...
2019-06-19 09:47:39
1368
原创 剑指offer（python）：剪绳子（动态规划和贪心）
1. 题目描述给你一根长度为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。2. 思路2.1 动态规划动态规划，先自上而下分析，在长度为n的绳子所求为f(n)，剪下一刀后剩下...
2019-06-18 16:24:25
3629
4
原创 leetcode：买卖股票的最佳时机含手续费（python）
1. 题目描述给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。示例 1:输入: prices = [1, 3, 2, 8, 4, 9], fee = 2输出: 8解释:...
2019-06-18 13:33:02
1050
原创 leecode：最佳买卖股票时机含冷冻期（python）
1. 题目描述给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买...
2019-06-18 11:58:00
290
原创 leetcode：买卖股票的最佳时机 IV（python）
1. 题目描述给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [2,4,1], k = 2输出: 2解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔...
2019-06-18 09:48:33
542
原创 统计学习方法——感知机
1. 感知机原理感知机是一个二类分类模型，输入为实例的特征向量，输出为实例的类别，取值为+1和-1。定义1-1：数据的线性可分性假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面。2. 感知机模型3. 感知机的学习策略为了找出可以将数据集完全正确分开的分离超平面，为了找出这...
2019-06-17 22:40:45
557
原创 leetcode：买卖股票的最佳时机 III（python）
1. 题目描述给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [3,3,5,0,0,3,1,4]输出: 6解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交...
2019-06-17 14:14:43
1496
原创 leetcode：买卖股票的最佳时机2（python）
1. 题目描述给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出...
2019-06-16 11:45:27
2495
原创 leetcode：买卖股票的最佳时机（python）
1. 题目描述给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。示例 1:输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 ...
2019-06-16 11:01:46
2419
1
原创 leetcode：二叉树中最大路径和（python）
1. 题目描述给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1:输入: [1,2,3] 1 / \ 2 3输出: 6示例 2:输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7...
2019-06-16 10:20:08
3524
1
原创 leecod：验证回文串（python）
1. 题目描述给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: “A man, a plan, a canal: Panama”输出: true示例 2:输入: “race a car”输出: false2. 思路利用一个双指针，一个从前往后的left指针，一个从后往前的right指...
2019-06-13 20:48:40
693
原创 leecode：单词接龙之二（python）
1. 题目描述给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明:如果不存在这样的转换序列，返回一个空列表。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假...
2019-06-12 22:45:25
895
原创 leeetoe：单词接龙（python）
1. 题目描述给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明:如果不存在这样的转换序列，返回 0。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假设 beginWord...
2019-06-10 16:28:20
1202
原创 leetcod：最长连续序列（python）
1. 题目描述给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例:输入: [100, 4, 200, 1, 3, 2]输出: 4解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。2. 思路参考https://leetcode-cn.com/problems/longest-consecutive-sequence/soluti...
2019-06-10 11:06:19
725
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人