Maizi's Blog

To be a craftsman of Information Technology!

A few algorithm about array sorting

binary-tree sorting | stack sorting

排序算法合集之二叉树二叉树排序算法描述:算法分析: 假若排成升序,用顺序表的数据结构来解决该问题,希尔排序是对直接插入排序的改进算法,该算法的时间复杂度O(n)=nlog₂n(最好时复杂度)①先找到一种算法对整个数组进行’分列’,该博文中使用的是用数组长度加一依次除以 2 3 4…得到的结果最为每’列’中元素相邻位置在原一维数组中的增量 ②将 ① 中的每一列依次进行直接插入排序,直......

Posted by Maizi on 2016-09-24

A few algorithm about array sorting

shell sorting | fast sorting | merging sorting

排序算法合集之希尔希尔排序算法描述:算法分析: 假若排成升序,用顺序表的数据结构来解决该问题,希尔排序是对直接插入排序的改进算法,该算法的时间复杂度O(n)=nlog₂n(最好时复杂度)①先找到一种算法对整个数组进行’分列’,该博文中使用的是用数组长度加一依次除以 2 3 4…得到的结果最为每’列’中元素相邻位置在原一维数组中的增量 ②将 ① 中的每一列依次进行直接插入排序,直至最......

Posted by Maizi on 2016-09-16

A question of interview about egg casting from microsoft

use algorithm of dynamic planning can easily deal with it

来自微软的扔鸡蛋面试题问题描述如下: 有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破，在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下，最小化鸡蛋下落的次数。(假设每次摔落时，如果没有摔碎，则不会给鸡蛋带来损耗) 据说下图的力学结构可以保证鸡蛋从......

Posted by Maizi on 2016-09-15

A question about how to build a binary tree from its front traval sequence and middle travel sequence

know everything about the binary tree can do it easily

二叉树相关的算法问题问题描述如下: 给定一棵二叉树的先序遍历和中序遍历的结果,怎么样获取其后续遍历的结果算法描述:算法分析:如果某个数组的元素顺序是某棵二叉树的先续遍历的顺序,那么从数组的第一个元素依次向后取元素可以重建这棵二叉树.①从数组的第一个元素依次向后取元素重建这棵二叉树.③后续遍历 ① 中重建的二叉树. 最后贴上代码:12345678910111213141516171819......

Posted by Maizi on 2016-09-15

A question about how to travel a binary tree in layer sequence

select a right data structure can solve it easily

怎么按层的先后顺序且每层按从左至右的顺序遍历二叉树问题描述如下: 设计一个算法,按层级的先后顺序来遍历二叉树,且每层元素的遍历顺序也是按从左到右的次序算法描述:①使用链表来实现队列(用该队列来实现按层访问).②首先将二叉树的根节点放入队列.获取首元素在二叉树中的左右孩子节点,将首元素出队列,然后将左右孩子(存在的话)依次序入队列并维护队列的首位指针的指向.③重复执行 ② 中的操作.直......

Posted by Maizi on 2016-09-15

A question about how to judge an array is the back sequence of a binary tree

know everything about the binary tree can do it easily

二叉树相关的算法问题问题描述如下: 设计一个算法,判断是一个数组的元素顺序是某棵二叉树的后续遍历的顺序算法描述:算法分析:如果这个数组的元素顺序是某棵二叉树的后续遍历的顺序,那么从数组的最后一个元素依次向前取元素可以重建这棵二叉树.①从数组的最后一个元素依次向前取元素重建这棵二叉树.③后续遍历 ① 中重建的二叉树依次序与数组中的元素对比,如果都相同则说明数组的元素顺序是某棵二叉树的后续......

Posted by Maizi on 2016-09-15

A few algorithm about array sorting

bubble sorting | choosing sorting | inserting sorting

排序算法合集之起泡起泡排序算法描述:算法分析: 假若排成升序,用顺序表的数据结构来解决该问题,该算法的时间复杂度O(n)=n²①第一趟结尾位置为数组的最后一个元素,从数组的第一个元素开始依次和其后面的元素比较,若后面的元素较小则交换这两个元素.这样第一趟跑完数组中最大的元素肯定在当前的结尾位置上,后面的每趟都依次将结尾位置向前移动一个位置②重复 ① 中的过程直至该趟的结尾位置和起始位......

Posted by Maizi on 2016-09-15

A question of interview from DIDI-BUS

a simple question, but lots of people thought in a complicated way...

滴滴打车的一道android面试题问题描述如下: 有个一个饭店,有n张桌子,每张桌子可以招待不同数量的客人,且不能拼桌,现在来了m批客人,每批客人有两个属性,一个是客人的总数,一个是他们消费(预计)的总额请设计一个算法,计算出店家能够获得的最大利润测试用例:3 5 2 4 21 33 5 3 75 91 103 5代表一共有3个桌子 5批客人2 4 2 代表3张桌子的容量分别是2 4 ......

Posted by Maizi on 2016-09-15