大数据

排序算法总结(一) 堆排序

1 时间复杂度对比 排序算法时间复杂度总结.png 本节我们只关注堆排序的时间复杂度.首先, 从上图我们可以看到,堆排序是不稳定的. 排序算法的稳定性: 对于一组数,如果相同元素的相对位置在排序前后保持一致,则该算法是稳定的,否则是不稳定的. 其次, 堆排序的时间复杂度都是O(nlogn), 空间复…

程序员

lintcode第十五、十六题 全排列

给定一个数字列表,返回其所有可能的排列,第十五题是没有重复的数字,是十六题是有重复的数字。先来说没有重复数字的情况n个数字有n!个全排列,每个数字都可以成为排列的第一个数字,然后剩下n-1个数字里可以找出第二个数字,之后剩下的n-2个数字里可以找到第三个数字,依次类推,最后只有一个数字可以放在第n个…

程序员

lintcode第七题 二叉树的序列化和反序列化

设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。 样例给出一个测试数据样例, 二叉树{3,9,…

大数据

[Topcoder]SRM369DIV2题解

PirateTreasure 题意: 有8个方向,然后给你一个数组,这个数组描述了朝着那些方向走了多少步。求出发点与终点的距离。 题解: 简单的统计题目,统计x,y的偏移量,最后算出结果。 TurningLightOn 题意: 给你一个棋盘,棋盘上面有0有1,然后翻转一个点为(x,y)的时候,会翻转…

大数据

lintcode 第四题 丑数

设计一个算法,找出只含素因子2,3,5 的第 n 大的数。直接寻找丑数,由定义可知,丑书是由2^m,3^n,5^l,因此不断寻找,将它们按从小到大的顺序排列,第n个即为结果。首先定义一个vector(数组)存放结果,使数组的第一个数ugly[0]为1,然后从ugly[0]乘以2,ugly[0]乘以3…

大数据

三部曲:排序-取舍-平衡

今天学习到的知识。工作生活中我们做的决策,和处理问题的方法,其实都在这个框架下:排序~取舍~平衡。有了框架我们就可以补充血肉了。 排序,例如排序我们用的什么,可以是四像线法,按照时间紧急和重要程度来划分。取舍,我们可以完善自己的价值观或者自己的计算模型等。而平衡可以看做是为取舍做的补偿或者监控,让我…

大数据

Mysql索引原理及慢查询优化

Mysql索引目的 索引的目的在于提高查询效率.可以类比字典,如果要查”mysql”这个单词,我们肯定需要定位到m单词,然后往下找到y字幕,在找到剩下的sql。 如果没有索引,那么你可能需要把所有单词看一遍擦能找到你想要的,如果我想找到m开头的单词呢?或者ze开头的单词呢?是不是觉得如果没有索引,这…

大数据

面试算法题:链表的倒转

具体的代码调试和讲解,请参看视频:如何进入google,算法面试技能全面提升指南 在算法面试中,链表出现的频率相当之高,一是因为链表是数据结构的基础,很多更复杂的高层数据结构的设计大多基于链表之上。其次,链表可以实现多种变化,因此使用链表来考察候选人,既能考察其技术基本功是否扎实,同时又能检验对方的…

大数据

lintcode 第三题 计算数字k在0到n中的出现的次数,k可能是0~9的一个值

当k不为0时从1至10,在它们的个位数中,任意k都出现了1次。从1至100,在它们的十位数中,任意k都出现了10次。从1至1000,在它们的百位数中,任意k都出现了100次。依次类推,从1至10的i次幂,在它们的左数第二位中,任意k都出现了10的i-1次幂次。 举个例子,n = 2593,k = 5…

大数据

树与二叉树

树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。 它具有以下特点: 1.每个节点有零个或多个子节点; 2.没有父节点的节点称为根节点; 3.每一个非根节点有且只有一个父节点 ; 4.除了根节点外,每个子节点可以分为多个不相交的子树。 Paste_Image.png 二叉树 二叉树是每个节…