编程马拉松

堆 堆排序需要用到二叉堆，在开始之前，我们先来了解一下什么是二叉堆。 当二叉树满足满足如下条件时，我们说这个二叉树是堆有序的： 每一个父结点的值都比它的子结点大（称为大顶堆）或小（称为小顶堆） 子结点的大小与其左右位置无关 堆有序的二叉树，也可称为二叉堆。二叉堆是最常见的堆结构，因此也常将二叉堆直接称为堆，可以采用如下两种方式来表示二叉堆 使用指针，二叉树的每个结点需存储三个指针，分别指向其父结点和两个子结点 使用数组，对二叉树做层序遍历，按层级顺序放入数组中，根结点在数组索引0的位置存放，其子结点分别在索引1和2的位置，1和2个子结点分别在位置3、4和5、6中存放，以此类推 就排序来讲，其所需处理的数据较为连续，没有空隙，可用完全二叉树来表示。对于完全二叉树，采用数组的表示方法也更方便些，下图展示了采用数组实现的两个二叉堆。 对于数组实现的二叉堆，索引为k的结点的父结点的索引为(k-1)/2，它的子结点的索引分别为2k+1和2k+2。 堆有序化 以大顶堆为例，有序化的过程中我们会遇到两种情况 在堆底加入一个较大元素时，我们需要由下至上恢复堆的顺序 当将根结点替换为一个较小元素时，我们需要由上到下恢复堆的顺序 由下至上的堆有序化（上浮） 如果堆的有序状态因为某个结点变的比它的父结点更大而被打破，就需要通过将它与它的父结点交换来恢复堆有序。交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍的用同样的方式来将其向上移动，直到遇到一个比它更大的父结点或到达了堆的根结点，如下图所示。 上浮操作对应的代码如下 1 2 3 4 5 6 private void swim(Integer arr[], int k) { while(k > 0 && arr[(k - 1) / 2] < arr[k]) { //若k>0且索引为k的结点大于其父结点时，将该结点与其父结点交换 swap(arr, k, (k - 1) / 2); k = (k - 1) / 2; } } 由上至下的堆有序化（下沉） 如果堆的有序状态因为某个结点变的比它的某个子结点更小而被打破，就需要通过将它和它的子结点中较大者交换位置来恢复堆有序。交换可能会在子结点处继续打破堆的有序状态，此时可以采用相同的方式，将结点向下移动直到它的子结点都比它小或是到达了堆的底部，如下图所示。 下沉操作对应的代码如下...

本文将介绍三个高级排序算法 希尔排序 归并排序 快速排序 希尔排序 希尔排序(Shell’s Sort)的名称源于它的发明者Donald Shell，这是一种基于插入排序算法的改进。在处理大规模乱序数组时，插入排序的速度不容乐观，因为它只能一点一点的将元素从数组的一端移动到另一端。希尔排序为了加快速度，对插入排序进行了小幅的改动，开始时将数组划分为m相邻的若干个子数组，并对每一个子数组进行插入排序，然后缩小m的值再次划分并排序，循环往复直到完成m = 1时的最后一次插入排序，此时整个数组有序。 插入排序，每次将第k个元素插入前k-1个元素之间。 希尔排序示例，每次将第mk个元素插入到k,2k,3k…mk这m个元素之间。 希尔排序的思路是使数组中任意间隔为m的元素都是有序的，这样的数组被称为m有序数组。一般m的初始值较大，以便我们可以将元素移动到很远的地方，随着希尔排序的进行，m会逐渐变小，当收敛到1时希尔排序完全退化为插入排序，从而完成最后的排序动作。 希尔排序高效的原因是它完全利用了插入排序的特点： 初始时，m值较大，子数组元素个数较小（小规模数据） 初始前几次，构造出了m有序子数组（部分有序） 希尔排序的过程如下图所示 希尔排序代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static void shellSort(Integer arr[]) { long before = System.currentTimeMillis(); int m = 1; //获取的m值，与数组长度相关 //子数组的部分有序的程度取决于m的值，而如何选取m的值是一项数学难题，在这里我们采用`1 4 13 40 121 364`这样的序列来作为希尔排序中m的值。 while (m < arr....

排序是科学计算和数据处理必不可少的一个环节，今天起我们就来聊聊排序。 本文将介绍三个初级排序算法 冒泡排序 选择排序 插入排序 先来看下图这样的一组初始数据，每一个矩形的高度都与其下方的数字成比例，数值越大则矩形的高度就越高。 假设有如下两个问题，我们该如何求解。 找出最(小/大)值 找出第k(小/大)的值 显然，在乱序的数组中这两个问题都不太容易求解，但如果数据是有序的就会容易很多。 冒泡排序 冒泡排序是最容易想到的排序算法。以对N个元素的数组进行升序排序为例，其基本思路如下： 从数组内的前两个元素开始，将这两个元素进行比较，如果前一个元素大于后一个元素，则交换两者的位置 接着取数组中的第2-3个元素进行比较，若第2个元素大于第3个元素，则交换两者的位置 循环往复，直到数组中的最后两个元素，此时，若第N-1个元素大于第N个元素，则交换它们的位置。经过一轮的比较与交换，我们已经得到了数组中最大的元素，并将其安置在了数组的第N位。 经过前三个步骤，我们将数组中最大的元素放到了第N位，下边只用排序数组中的前N-1个元素即可。此时我们将N的值减1，并判断新N的值，若新N>0，则循环1-3步骤；若新N=0，则代表我们已经完成了排序。 冒泡排序的过程(剪辑版)如下图所示，你也可以点击这里查看完整的冒泡排序过程。 我们知道，水杯中出现气泡时，越大的气泡浮力越大，上升速度也就越快，最先到达水面，冒牌排序中每轮遴选较大元素放置末尾的行为与水中气泡上升的现象十分相似，因此得名冒泡排序。 冒泡排序代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static void bubbleSort(Integer arr[]) { int compareCount = 0;//比较次数 int swapCount = 0;//交换次数 long before = System.currentTimeMillis(); for (int i = 0; i < arr....

今天是第二天，继续我们的征程。 题目 编写代码，把字符串中的每个空格替换为%20。例如，输入"hello world."，则输出"hello%20world."。 编写代码，给定系数n，求1+2+3+…+n的总和，即∑运算符 编写代码，观察如下数列，给定系数n，求数列中的第n个数字(tips: 斐波那契数列)。 1 1 2 3 5 8 13 21 34 55 89 ... 字符替换 本题是将空格等特殊字符变为转义字符的函数，常用于URL编码中，用来避免URL中可能存在的字符歧义。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 /** * 判断当前字符是否为普通字符 */ public static boolean isPlainChar(char c) { return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '!...

打算从今天起开始每日一练，巩固一下算法，数据结构相关的知识，废话少说，开始看题。 以上是我近期面试中遇到的一些题，其中1，3题出自百度系面试官；2，4出自Uber系面试官。 两个水杯倒出3L水的问题 先来看第一个问题，题干是要求倒腾出3L的水。我们可以从4、5两个数字入手，观察通过怎样的方式能够得到3，得到以下两种情况 4 * 2 -5 == 3 ( 5 - 4 ) * 3 == 3 转换为文字 第一种方式 先将4L的杯子接满水，全部倒入到5L的杯子中（tips：此时4L的杯子为空，5L的杯子中装载了4L水，还能再倒入1L） 再将4L的杯子接满水，然后向5L的杯子倒水，当5L杯子倒满时，4L杯子剩下3L水 第二种方式 将5L的杯子接满水，倒入4L的杯子中（tips: 此时5L的杯子剩下1L水），然后将4L杯子的水全部倒掉，再将5L杯子剩余的1L水倒入4L的杯子（tips: 此时4L杯子有1L水） 将5L的杯子接满水，倒入4L的杯子中（tips: 由于上一轮4L杯子已存在1L水，本次5L杯最多只能倒出3L水，倒出后5L杯剩余2L水），然后将4L杯子的水全部的倒掉，再将5L杯子剩余的2L水倒入到4L的杯子（tips: 此时4L杯子有2L水） 将5L的杯子接满水，倒入4L的杯子中（tips: 由于上一轮4L杯子已存在2L水，本次5L杯最多只能倒出2L水，倒出后5L杯正好剩余3L水） 大数四则运算 第二个问题是一个典型的大数运算问题。编程中有时会遇到数字上溢（tips: 如数值的大小超过了Long型可表示的最大数）的问题，此时便需要采用字符串替换原有的数值计算。 以10进制加法为例，解决思路如下： 使用字符串装载参与计算的两个数值 分别取两个字符串的末尾数值 a和b，进行相加计算 sum = a+b ，如结果sum大于9，则设置进位标志 flag = 1；否则设置 flag = 0。记录sum%10，表示当前位的结果 再次取两个字符串的次末尾数值 a和b，进行相加计算 sum = a+b+flag ，如结果sum大于9，则设置进位标志 flag = 1；否则设置 flag = 0。记录sum%10，表示当前位的结果 … 重复以上步骤，若两个数字字符串的长度不一致，则当其中较短字符串s1遍历完成后，只遍历另一个字符串s2，每次取出s2的末位数值与flag相加，得到新的进制标志和当前位的结果。 代码如下：...