《漫画算法》笔记-下篇

漫画算法-小灰的算法之旅

魏梦舒(@程序员小灰)著

“学习算法,我们不需要死记硬背那些冗长复杂的背景知识、底层原理、指令语法......需要做的是领悟算法思想、理解算法对内存空间和性能的影响,以及开动脑筋去寻求解决问题的最佳方案。相比编程领域的其他技术,算法更纯粹,更接近数学,也更具有趣味性。” -- 作者说

葡京在线网投看完全书,感慨良多,特别是看完最后两章,算法面试与职场应用算法部分,这是全书的精华部分,值得深入研读。同时也感慨,面试中的算法真是灵活多变,若没有广博的数学知识与计算机相关知识,光知道概念,不能深入思考,真的很难应对,真的就是山外山,云外云,永远有你不知道的。也羡慕小灰有大黄这么一个领路人,帮助他学习成长,少走弯路。工作中,算法在实际应用中也是无处不在的,比如发红包,100元如何才能均衡分配。学习,永无止境。面试结束不代表学习结束,仍需钻研深入,方能应对工作中出现的更多业务场景,更好的解决实际问题。

葡京在线网投上篇,我记录了前三章内容的相关笔记。关于算法与数据结构相关概念及相关的时间、空间复杂度,以及基础数据结构:数组、链表、栈、队列、散列表,还有复杂数据结构:树。

本篇记录剩下几章的内容:排序算法、面试算法、职场算法。

第4章 排序算法

根据时间复杂度的不同,主流的排序算法可以分为3大类。

  1. 时间复杂度为O(n²)的排序算法
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
  2. 时间复杂度为O(n㏒n)的排序算法
    • 快速排序
    • 归并排序
    • 堆排序
  3. 时间复杂度为线性的排序算法
    • 计数排序
    • 桶排序
    • 基数排序

根据稳定性,分为稳定排序和不稳定排序。
葡京在线网投 如果值相同的元素在排序后仍然保持着排序前的顺序,则这样的排序算法是稳定排序。反之,为不稳定排序。

冒泡排序

一种基础的交换排序。把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置,当一个元素小于或等于右侧相邻元素时,位置不变。

葡京在线网投一种稳定的排序,值相等的元素并不会打乱原本的顺序。

由于该排序算法的每一轮都要遍历所有元素,总共遍历(元素数据-1葡京在线网投)轮,所以时间复杂度是O(n²)。

优化:以 {5,8,6,3,9,2,1,7} 为例,经过第6轮排序后,整个数列已然是有序的了。可排序算法仍然执行了第7轮。

葡京在线网投优化1:利用布尔变量作为标记,如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列有序,直接跳出大循环。

葡京在线网投优化2:对数列有序区进行界定,若后面的元素实际上已经有序了,则后面的元素比较是没有意义的。在每一轮排序后,记录下最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区了。

function sort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 有序标记,每一轮的初始值都是true
    let isSorted = true
    // 无序数列的边界,每次比较只需要比到这里为止
    let sortBorder = arr.length - 1
    for (let j = 0; j < sortBorder; j++) {
      let tmp
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp;
        // 因为有元素进行交换,所以不是有序的,标记变为false
        isSorted = false
        // 把无序数列的边界更新为最后一次交换元素的位置
        sortBorder = j
      }
    }
    if (isSorted) {
      break
    }
  }
  return arr
}

// 测试
console.log(sort([3, 4, 2, 1, 5, 6, 7, 8])) // [1, 2, 3, 4, 5, 6, 7, 8]

葡京在线网投优化3:鸡尾酒排序-元素比较和交换过程是双向的。实现:外层的大循环控制着所有排序回合,大循环内包含2个小循环,第1个小循环从左向右比较并交换元素,第2个小循环从右向左比较并交换元素。劣势:代码量增加了1倍,优势:大部分有序的场景下能发挥优势。

快速排序

葡京在线网投同冒泡排序,也属性交换排序,不同的是,冒泡排序在每一轮只把一个元素冒泡到数列的一端,而快速排序则在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成两个部分。这种思路叫分治。

基准元素的选择及元素的交换是快速排序的核心问题。

葡京在线网投元素的交换有两种实现方法:双边循环法、单边循环法。

// 快速排序-双边循环法-需要基准元素、左右指针
function quickSort (arr, startIndex, endIndex) {
  // 递归结束条件:startIndex >= endIndex时
  if (startIndex >= endIndex) {
    return
  }
  // 得到基准元素位置
  let pivotIndex = partition(arr, startIndex, endIndex)
  // 根据基准元素,分成两部分进行递归排序
  quickSort(arr, startIndex, pivotIndex - 1)
  quickSort(arr, pivotIndex + 1, endIndex)
}

// 元素交换,双边循环法
function partition (arr, startIndex, endIndex) {
  // 取第一个位置,也可以选择随机位置的元素作为基准元素
  let pivot = arr[startIndex]
  let left = startIndex
  let right = endIndex

  while (left != right) {
    // 控制 right 指针比较并左移
    while(left < right && arr[right] > pivot) {
      right--
    }

    // 控制 left 指针比较并右移
    while (left < right && arr[left] <= pivot) {
      left++
    }
    
    // 交换 left 和 right 指针所指向的元素
    if (left < right) {
      let p = arr[left]
      arr[left] = arr[right]
      arr[right] = p
    }
  }

  // pivot 和指针重合点交换
  arr[startIndex] = arr[left]
  arr[left] = pivot

  return left
}

// 测试
var arr = [4, 4, 6, 5, 3, 2, 8, 1];
quickSort(arr, 0, arr.length-1)
console.log(arr)

堆排序

利用最大堆和最小堆的特性:

  • 最大堆:堆顶是整个堆中最大元素
  • 最小堆:堆顶是整个堆中最小元素

堆排序算法的步骤:

  • 把无序数组构建成二叉树,需要从小到大排序,则构建成最大堆,需要从大到小排序,则构建成最小堆。
  • 循环删除堆顶元素,替换到二叉堆的末尾,调整堆产生新的堆顶。

计数排序

局限性:

  • 当数列最大和最小值差距过大时,并不适合用计数排序
  • 当数列元素不是整数时,也不适合用计数排序

弥补算法:桶排序

第5章 面试中的算法

问题1:如何判断链表有环

题目:有一个单向链表,链表中有可能出现“环”,如何用程序来判断该链表是否为有环链表?

葡京在线网投应用数学中的追击问题的解决方法。环形跑道上,速度快的远动员必然会追上速度慢的运动员。

首先创建两个指针p1、p2,让它们同时指向这个链表的头节点,然后开始一个大循环,在循环体中,让指针p1每次向后移动1个节点,让指针p2每次向后移动2个节点,然后比较两个指针指向的节点是否相同,若相同,则可以判断出链表有环,若不同,则继续下一轮循环。

问题扩展:

  1. 如果链表有环,如何求出环的长度?
  2. 如果链表有环,如何求出入环节点?

问题2:最小栈的实现

题目:实现一个栈,该栈带有出栈,入栈,取最小元素3个方法。要保证这3个方法的时间复杂度都是O(n)。

技巧:利用2个栈实现

问题3:如何求出最大公约数

葡京在线网投题目:写一段代码,求出两个整数的最大公约数,要尽量优化算法的性能。

数学知识:

  • 辗转相除法,也称欧几里得算法。两个正整数a,b(a>b),它们的最大公约数等于a除以b的余数c和b的最大公约数。
  • 更相减损术

最优:更相减损术结合位移

问题4:如何判断一个数是否为2的整数次幂

题目:实现一个方法,来判断一个正整数是否是2的整数次幂(如16是2的4次方,返回true;18不是2的整数次幂,返回false)。要求性能尽可能高。

计算机知识:0 和 1 按位与运算的结果是0,所以凡是2的整数次幂和它本身减1的结果进行与运算,结果都必定是0。反之,如果一个整数不是2的整数次幂,结果一定不是0!

问题4:无序数组排序后的最大相邻差

题目:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。比如:

无序数组:2 6 3 4 5 10 9
排序结果:2 3 4 5 6 9 10
最大相邻差=3

思路:

  1. 利用计数排序的思想,先找出原数组最大值max和最小值min的区间长度k(max-min+1),以及偏移量d=min
  2. 创建一个长度为k的新数组Array
  3. 遍历原数组,每遍历一个元素,就把新数组Array对应下标的值+1。遍历结束后,Array的一部分元素值变成了1或更高的数值,一部分元素值仍然是0。
  4. 遍历新数组Array,统计出Array中最大连续出现0值的次数+1,即为相邻元素最大差值。

升级:利用桶排序思想

问题5:如何用栈实现队列

葡京在线网投题目:用栈来模拟一个队列,要求实现队列的两个基本操作:入队、出队。

葡京在线网投思路:利用两个栈,让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老元素。

问题6:寻找全排列的下一个数

题目:给出一个正整数,找出这个正整数所有数字全排列的下一个数。就是在一个整数所包含数字的全部组合中,找到一个大于且仅大于原数的新整数。举例:
如果输入12345,返回12354。
如果输入12354,返回12435。
如果输入12435,返回12453。

思路:为了和原数接近,需要尽量保持高位不变,低位在最小范围内变换顺序。至于变换顺序的范围大小,则取决于当前整数的逆序区域。

  1. 从后往前查看逆序区域,找到逆序区域的前一位,也就是数字置换的边界。
  2. 让逆序区域的前一位和逆序区域中大于它的最小数字交换位置。
  3. 把原来的逆序区域转为顺序状态。

问题7:删去k个数字后的最小值

题目:给出一个整数,从该整数中去掉k个数字,要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字?举例:
葡京在线网投 假设给出一个整数1593212,删去3个数字,新整数最小的情况是1212。

思路:把原整数的所有数字从左到右进行比较,如果发现某一位数字大于它右面的数字,那么在删除该数字后,必然会使该数位的值降低,因为右面比它小的数字顶替了它的位置。

问题8:如何实现大整数相加

题目:给出两个很大的整数,要求实现程序求出两个整数之和。

思路:用数组存储,数组的每一个元素,对应着大整数的每一个数位。

问题9:如何求解金矿问题

题目:很久很久以前,有一位国王拥有5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人人数也不同。例如有的金矿储量是500g黄金,需要5个工人来挖掘...
如果参与挖矿的工人总数是10。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半的金矿。要求用程序求出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
葡京在线网投 总共10名工人,200kg黄金/3人,300kg黄金/4人,350kg黄金/3人,400kg黄金/5人,500kg黄金/5人。

葡京在线网投典型的动态规划题目,和著名的“背包问题”类似。

动态规划:把复杂的问题简化成规模较小的子问题,再从简单的子问题字底向上一步一步递推,最终得到复杂问题的最优解。

问题10:寻找缺失的整数

题目:在一个无序数组里有99个不重复的正整数,范围是1~100,唯独缺少1个1~100中的整数。如何求出这个缺失的整数?

看完这些题目,你心中有答案了吗?书中有图解哦

最后一章

场景1:bitmap的巧用

用户标签统计

场景2:LRU算法的应用

葡京在线网投用户信息查询,在哈希表中缓存查询数据,提高效率,缓存数据较多后如何优化。

LRU:最近最少使用的意思。基于假设:长期不被使用的数据,在未来被用到的几率也不大。因此,当数据占用内存达到一定阈值时,移除掉最近最少被使用的数据。

场景3:A星寻路算法

“迷宫寻路”益智游戏。在迷宫游戏中,有一些小怪物会攻击主角,现在希望你给这些小怪物加上聪明的AI,让它们可以自动绕过迷宫中的障碍物,寻找到主角的所在。

场景4:如何实现红包算法

葡京在线网投例如一个人在群里发了100块钱红包,群里有10个人一起来抢红包,每人抢到的金额随机分配。规则:

  1. 所有人抢到的金额之和要等于红包金额,不能多也不能少。
  2. 每个人至少抢到1分钱。
  3. 要保证红包拆分的金额尽可能分布均衡,不要出现两极分化太严重的情况。

面对这些场景,你想到如何设计与编码才能最优了吗?

总结

葡京在线网投第1-4章,是关于算法与数据结构基础知识,算法、数据结构、数组、链表、栈、队列、树,图也是数据结构中的一种,但未被本书收纳,可能是作者认为相对于其他数据结构更复杂,也确实是。还有常见的排序算法,比如最基础的冒泡排序。

看完理论与概念,仿佛刚出大学大门,以为懂了一切。可是当踏入职场时,才知道远远不够。

第5-6章,是关于面试与职场算法,面试题详解,从暴力破解法(性能最差)到最优解(性能最优)。如何运用算法解决工作问题。

葡京在线网投面试,考验能力的地方,决定了你是否能进入心仪职场。永远有你不知道的面试题在等着你,所能做的就是永不满足,多汲取,多学习深思,才能在面试时随机应变,过关斩将,最终进入职场。

葡京在线网投工作,更是如此,到处都是挑战,满足现状只会落后,需要不断学习,才能满足多变的业务场景。

学无止境,方能不断接近最优。

posted @ 2019-06-25 21:45  ESnail  阅读(...)  评论(...)    收藏