- 博客(56)
- 资源 (9)
- 收藏
- 关注
RSS订阅原创 回溯法(Backtracking)
回溯法回溯法概念回溯算法有“通用的解题法”之称。用它可以系统地搜索一个问题的所在解或任一解。回溯法是一个即带有系统性又带有跳跃性的所搜算法。回溯法思想在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的
2016-07-25 16:31:06
14124
2
原创 链表环检测算法
给定两个LeetCode上的问题Linked List CycleGiven a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space?Linked List Cycle IIGiven a linked list, return the node
2016-07-14 16:50:59
3598
原创 LintCode Jump Game 跳跃游戏
跳跃游戏给出一个非负整数数组，你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 判断你是否能到达数组的最后一个位置。样例 A = [2,3,1,1,4]，返回 true.A = [3,2,1,0,4]，返回 false.注意 这个问题有两个方法，一个是贪心和 动态规划。贪心方法时间复杂度为O（N）。动态规划方法的时间复杂度为为O（n^2）。我
2016-01-28 15:40:52
4751
1
原创 LintCode Single Number、落单的数
落单的数给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。样例 给出 [1,2,2,1,3,4,3]，返回 4挑战 一次遍历，常数级的额外空间复杂度落单的数 II给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。样例 给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4挑战 一次遍历，常数级的额外空间复杂度落单的
2016-01-16 14:46:09
836
原创 Moore’s Voting Algorithm
Moore’s Voting AlgorithmMoore’s Voting Algorithm该算法是找出重复元素的最佳的算法，其时间复杂度为O(n)O(n)而空间复杂度为O(1)O(1)。
2015-12-26 21:29:42
1511
原创 LintCode majority numbe (主元素)
LintCode 主元素主元素 给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。给出数组[1,1,1,1,2,2,2]，返回 1 挑战 要求时间复杂度为O(n)，空间复杂度为O(1) 。solution: 对于这个问题，有很多解决的方法。Method1. 最基本的解决方法 使用两个for循环计算出每个元素出现的次数， 如果该次数大于数组元素的二分之一就返回
2015-12-26 13:46:00
886
原创 LintCode 二进制表示
LintCode 二进制表示给定一个数将其转换为二进制（均用字符串表示），如果这个数的小数部分不能在 32 个字符之内来精确地表示，则返回 “ERROR”。样例 n = “3.72”, 返回 “ERROR”.n = “3.5”, 返回 “11.1”.题目很简单，直接上代码吧public class BinaryRepresention { /** * 计算n的二进制表示
2015-12-25 21:12:27
1932
原创 LintCode 快速幂
LintCode 快速幂计算ana^{n} % b ，其中a，b和n都是32位的整数。样例 例如 2312^{31} % 3 = 2例如 1001000100^{1000} % 1000 = 0Solution: 显然不能先计算ana^{n}之后再取余。因为，ana^{n}会溢出。 因此，需要利用取模运算的乘法法则： (a * b) % p = (a % p * b % p) %
2015-12-21 21:43:14
2529
转载 lua初学者教程
lua 初学者教程Lua 介绍Lua是一门脚本语言，它的语法与C语言类似。它也是大小敏感的语言。但是Lua语法比较简单，学习起来也比较容易。在lua语言中，除了关键字一切都是变量。lua脚本的运行与python是一样的。我们可以直接在shell终端输入lua 当然也可以选择IDEA, 比如linux版本的ZeroBrane Studiolua 的注释像高级语言一样，也分为单行注释和多行注释，但
2015-12-13 14:31:59
2014
原创 LintCode 不同的二叉查找树
不同的二叉查找树给出 n，问由 1…n 为节点组成的不同的二叉查找树有多少种？给出n = 3，有5种不同形态的二叉查找树：1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \2
2015-12-08 22:03:15
2689
原创 归并排序与快速排序
分治法分治法的思想：将原问题分解为几个规模较小但类似原问题的子问题，递归的求解这些子问题，然后合并这些子问题的解来建立原问题的解。及分而治之分治模式在每层递归时都有三个步骤： 分解原问题为若干子问题，这些子问题是原问题规模较小的实例 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。 合并这些子问题的解成原问题的解。归并排序归并排序算法完全遵循分治模式。只管上其操作如
2015-11-19 10:12:24
1849
1
原创 word2vec模型
word2vec动机：为什么要学习词向量(Word Embeddings)传统的自然语言处理系统把词(word)当作一个离散的原子符号。比如，猫可以使用Id537来表示，Id143表示狗。这些编码是任意的，这些编码对于系统处理不同的单词并没有提供有用的信息。这就意味着，如果系统已经学习了什么是“猫”的信息，但这个系统处理什么是“狗”是并没有提供很大的帮助(比如：他们都是动物，有四条腿，宠物，等)。这
2015-11-17 18:53:50
12484
1
翻译 理解LSTM网络
colah 写了一篇介绍LSTM的博客，写的非常的好。为了能够是自己更加深入的了解。特此，将它翻译了过来。原文地址：http://colah.github.io/posts/2015-08-Understanding-LSTMs/递归神经网络(Recurrent Neural Networks)人类并不会每一秒都重新开始他们的思维。当你阅读这篇文章，你能够基于你前面的理解，来理解当前的每一个单词。你
2015-11-16 12:25:30
16611
原创 堆排序
堆排序堆排序是建立在数据结构堆上的一种操作。堆排序最简单的一种操作就是，先建立一个堆，然后依次弹出堆中的元素，使用临时数组保存。最后在把临时数组赋值给原数组。(对堆操作不熟悉的请先看数据结构之堆) 其代码为： 由于需要建一个堆，因此产生额外的空间，那么是否可以直接在元素组上建立一个堆呢？ 答案是肯定的。因此，堆排序另外一个优化版本 1. 将要排序的数组arr从0到i(开始时i = arr.le
2015-11-14 12:06:44
366
原创 数据结构之堆
堆数据结构堆是一种特殊的数据结构，也可以称为优先级队列。堆可以近似的看成是一颗完全的二叉树。既可以使用链表实现也可以使用数组实现。但是使用数组实现比较方便。其使用数组实现的一个堆如下图所示。 堆可以分为最大堆和最小堆，堆具有一个非常重要的性质： 对于最大堆：父节点的值要比其两个子节点(如果存在)大。 对于最小堆：父节点的值要比其两个子节点(如果存在)小。 其数学表现形式为： 最大堆: A
2015-11-13 21:15:40
506
原创 排序算法之冒泡、插入和希尔排序
简单排序算法冒泡排序冒泡排序算法是一种很简单的排序算法，它重复的访问要排序的数列，比较两个相邻的元素，如果这个两个元素不是出于正确的位置及左边的元素比右边大，则交换这两个元素的位置(从小到大排序)。一直重复这个过程直到所有的元素都是有序的。 例如：对{5 1 4 2 8}进行从小到大进行排序。 第一遍 ( 5 1 4 2 8 ) →\to ( 1 5 4 2 8 ), 首先, 冒泡算
2015-11-10 10:28:54
620
原创 最小生成树
最小生成树最小生成树的定义给定一个图G=（V，E）G = （V， E）， 并且对于每条边(u,v)∈E(u, v) \in E的权重使用 ω(u,v)\omega(u, v) 来表示。我们希望找到一个无环子集T⊆ET \subseteq E， 既能够将所有的节点连接起来，又具有最小的权重，即 ω(T)=∑(u,v)∈Tω(u,v)\omega(T) = \sum_{(u, v) \in T} \o
2015-10-31 20:08:08
817
原创 07-图6 旅游规划 (25分)
07-图6 旅游规划 (25分)有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路
2015-10-31 19:25:00
3174
原创 07-图4 哈利·波特的考试
07-图4 哈利·波特的考试哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。现在哈利·波特的手里有
2015-10-28 19:53:35
1476
原创 最短路径问题
最短路径1.1 最短路径的定义 其数学表现形式为： 在最短路径问题中，我们给定一个带权重的有向图G=(V, E) 和权重函数ω:E→R\omega: E \to R, 该权重函数将每条边映射到实数值的权重上，图中一条路径p=<v0,v1,...,vk>p = <v_{0}, v_{1}, ... , v_{k}>的权重ω(p)\omega(p)是构成该路径的所有边的权重之和： δ(p)={mi
2015-10-27 15:25:53
2091
原创 动态规划进阶篇
动态规划进阶篇如果你已经熟悉了动态规划的基础知识，那么接下来我们来讨论二维的动态规划吧！问题： 给定一个N×MN \times M的表格，每个格子上放着一个苹果。如果你从最左上角的格子上开始走，每次只能向下或者向右走，每到一个格子你就把苹果收集起来。这样下去，你最多能够收集多杀个苹果？？解决这个问题与其它的DP问题并没有其它的区别。 首先，我们要找到问题的“状态”。我们要注意的是我们最多有两种状
2015-10-23 16:13:02
996
转载 动态规划入门篇
本文整理转载自：Hawstein’s Blog动态规划入门篇什么是动态规划？？动态规划是拆分问题，定义问题的状态和状态之间的关系，使得问题能够以递推或者说分治的方式去解决问题。(详情请点这里)。因此，使用动态规划求解问题时我们需要找到某个转态的最优解，在这个状态的帮助下找到下一个状态的最优解。状态是什么并且如何定义它？通俗的说，状态是来描述子问题的解，或者说子问题的定义。现通过一个例子来讲解什么状态
2015-10-21 14:16:59
970
转载 什么是动态规划
本文整理转载自：知乎什么是动态规划什么是动态规划动态规划（dynamic programming)与分治法相似，都是通过组合子问题的解来求解原问题，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。通常按照下面4个步骤来设计一个动态规划算法： 1. 刻画一个最优解的结构特征。 2. 递归地定义最优解的值 3. 计算最优解的值，通常采用自底向上的方法 4. 利用计算出的信息构造
2015-10-20 18:34:30
684
原创 03-树3 Tree Traversals Again (25分)
03-树3 Tree Traversals Again (25分)An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered f
2015-10-20 16:30:24
8453
2
原创 03-树2 List Leaves (25分)
03-树2 List Leaves (25分)Given a tree, you are supposed to list all the leaves in the order of top down, and left to right. Input Specification: Each input file contains one test case. For each case,
2015-10-19 19:02:02
2403
原创 二叉搜索树
二叉搜索树二叉搜索树：是一颗二叉树但是其根节点的只要比左节点大比右节点小。 二叉树的遍历给定一棵树对其进行访问 1.先序遍历 (1). 访问根节点 (2). 先序遍历其左子树 (3).先序遍历其右子树 其上图二叉树先序遍历的结果为：ABDFECGHI 其代码实现为：void preOrderTraver(BinTree root) { i
2015-10-17 11:01:21
894
原创 Saving James Bond - Easy Version
Saving James Bond - Easy VersionThis time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was
2015-10-14 15:11:34
604
原创 图的表示和遍历
图的表示图(Graph)是由顶点(Vertex)和边(Edge)构成的一种集合,及 G=(V,E)G = (V, E),图在数据结构中有两种表示方式：邻接矩阵和邻接链表邻接矩阵对于图G=(V,E)G = (V, E)的邻接矩阵的表示方式，通常是将图G的节点编为0,1,2,3,...,|V−1|0, 1, 2, 3, ..., |V-1|,这种编号是任意的也可以从1开始进行编号，那么G的邻接矩阵表示由
2015-10-13 09:07:05
1188
原创 LintCode 更新二进制位
更新二进制位给出两个32位的整数N和M，以及两个二进制位的位置i和j。写一个方法来使得N中的第i到j位等于M（M会是N中从第i为开始到第j位的子串） 样例 给出N = (10000000000)2，M = (10101)2， i = 2, j = 6 返回 N = (10001010100)2 挑战 最少的操作次数是多少？solution: 题目的意思就是讲N的第i到j位换成M，因此，我们
2015-10-10 18:59:02
1653
翻译 LintCode 尾部的零
尾部的零设计一个算法，计算出n阶乘中尾部零的个数 样例 11! = 39916800，因此应该返回 2 挑战 O(logN)的时间复杂度solutioin: 转自Factorials and Trailing Zeroes 1.计算 23!23!有多少个尾0 23!=1×2×3×4×5×6×7×8×9×10×11×12×13×14×15×16×17×18×19×20×21×22×2323
2015-10-09 19:56:57
1591
原创 LintCode 将整数A转换为B
将整数A转换为B如果要将整数A转换为B，需要改变多少个bit位？ 样例 如把31转换为14，需要改变2个bit位。 (31)10=(11111)2 (14)10=(01110)2 挑战 你能想出几种方法？solution: 这题的意思就是比较A和B中不同位的个数及相异位的个数。因此，很容易想到异或操作，及相异为1,相同为0。因此可以先做C = A^B，然后在计算C的二进制表示中1的个数。
2015-10-09 18:36:21
1725
1
原创 LintCode 木材加工
木材加工有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。 样例 有3根木头[232, 124, 456], k=7, 最大长度为114. 注意 木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是整数。无法切出要求至少 k 段的,则返回 0 即可
2015-10-08 21:19:34
1278
原创 LintCode 第一个错误的代码版本
第一个错误的代码版本代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。 你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。 样例 给出 n=5 调用isBadVersion(3)，得到false 调用isB
2015-10-08 20:28:40
1080
原创 LintCode 寻找旋转排序数组中的最小值
1 . 寻找旋转排序数组中的最小值假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。 你需要找到其中最小的元素。 你可以假设数组中不存在重复的元素。 样例 给出[4,5,6,7,0,1,2] 返回 0solution: 本题可以直接使用蛮力法计算复杂度为O(n)，但是使用蛮力法的话会失去本题的意思，因为数组是由排序数组旋转之后
2015-10-07 17:56:44
1015
原创 LintCode x的平方根
x的平方根实现 int sqrt(int N) 函数，计算并返回 N 的平方根。 样例 sqrt(3) = 1 sqrt(4) = 2 sqrt(5) = 2 sqrt(10) = 3 挑战 O(log(x))solution: 如果使用蛮力法来求解的话，肯定是会超时的。因此，我们需要使用牛顿迭代法来求解这问题 牛顿迭代法: 对于给定一个函数f(x) = 0,的解为x0x_{0};
2015-10-05 20:23:06
1551
原创 LintCode 二分法查找， 搜索插入位置 和 二维矩阵
1. 二分查找给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。 样例 在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。 挑战 如果数组中的整数个数超过了2^32，你的算法是否会出错？solution: 注意如果出现重复的数字时我们需要放回第
2015-10-05 17:02:56
1410
原创 LintCode 三数之和
1. 三数之和给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。 样例 如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是： (-1, 0, 1) (-1, -1, 2) 注意 在三元组(a, b, c)，要求a <= b <= c。结果不能包含重复的三元组。solution: 因为三元组的元素是按照递增
2015-10-05 12:19:10
4724
1
原创 LintCode 丢失的第一个正整数
丢失的第一个正整数 给出一个无序的正数数组，找出其中没有出现的最小正整数。 样例 如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2 挑战 只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。Solution: 方法一：一种最直接的方法就是对数组进行排序然后再查找.class Solution {public: /**
2015-10-04 16:46:01
2235
原创 LintCode 两数之和
两数之和给一个整数数组，找到两个数使得他们的和等于一个给定的数target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。 样例 numbers=[2, 7, 11, 15], target=9 return [1, 2] 注意 你可以假设只有一组答案。solution:方法一：使用map容器来存储对应的
2015-10-04 15:17:28
2038
2
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人