Skip to content

Latest commit

 

History

History
360 lines (295 loc) · 40 KB

06.算法大汇总.md

File metadata and controls

360 lines (295 loc) · 40 KB
Raw

目录介绍

  • 00.导向[6篇]
  • 01.数组[34篇]
  • 02.链表[32篇]
  • 03.栈[9篇]
  • 04.队列[10篇]
  • 05.树[36篇]
  • 06.排序[10篇]
  • 07.查找[2篇]
  • 08.选择[5篇]
  • 09.散列[8篇]
  • 10.字符串[32篇]
  • 11.递归[13篇]
  • 12.Hash[7篇]
  • 20.其他[43篇]

好消息

  • 博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

00.导向

  • 01.数学Log对数
    • 在数学中，对数是对求幂的逆运算，正如除法是乘法的倒数，反之亦然。这意味着一个数字的对数是必须产生另一个固定数字（基数）的指数。
  • 02.算法基础导论
    • 为何要复杂度分析，大O复杂度表示法
  • 03.时间复杂度
    • 什么是时间复杂度，关注循环执行次数最多的一段代码，加法法则计算时间复杂度，乘法法则计算时间复杂度，复杂度分析建议，复杂度量级分类，多项式时间复杂度
  • 04.空间复杂度
    • 什么是空间复杂度，看一个案例分析，空间复杂度小结
  • 05.最好与最坏
    • 复杂度分析4个概念，最好最坏情况时间复杂度，平均情况时间复杂度，均摊时间复杂度，课后思考练习

01.数组

  • 01.数组的基础介绍
    • 什么是数组，数组的优缺点，数组使用场景，线性表和非线性表，数组的访问，数组和链表区别，数组低效插入，数组低效删除，容器和数组，为何数组从0开始
  • 02.用类实现数组
    • 数组的介绍，用类封装数组
  • 03.从数组中删除重复项
    • 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
  • 04.二维数组中查找
    • 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
  • 07.啤酒与饮料
    • 啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。
  • 08.数组中只出现一次的数字
    • 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
  • 09.买卖股票最佳时机
    • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。
  • 10.调整数组顺序
    • 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
  • 11.找出常用的数字
    • 给你一个长度为n的数组，其中有一个数字出现的次数至少为n/2，找出这个数字
  • 12.旋转数组的最小数字
    • 把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。
  • 13.调整数组顺序使奇数位于偶数前面
    • 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位予数组的后半部分。
  • 14.顺时针打印矩阵
    • 输入一个矩阵，按照从外向里以顺时针的顺序依次扫印出每一个数字。
  • 15.数组中出现次数超过一半的数字
    • 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  • 16.最小的k个数
    • 输入n个整数，找出其中最小的k个数。例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4个数字是1 、2、3 、4
  • 17.连续子数组的最大和
    • 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
  • 18.把数组排成最小的数
    • 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
  • 19.数组中的逆序对
    • 在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
  • 20.在排序数组中出现的次数
    • 统计一个数字：在排序数组中出现的次数。例如输入排序数组｛ 1, 2, 3, 3, 3, 3, 4, 5｝和数字3 ，由于3 在这个数组中出现了4 次，因此输出4 。
  • 21.数组中只出现一次的数字
    • 一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
  • 32.和为s的两个数字
    • 输入一个递增排序的数组和一个数字s，在数组中查找两个数，得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
  • 33.数组中重复的数字
    • 在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
  • 34.滑动窗口的最大值
    • 给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

02.链表

03.栈

04.队列

05.树

  • 00.树的基础介绍
    • 树的概念，树的定义，树的基本术语，
  • 01.二叉树简介
    • 二叉树的定义，二叉树的性质，二叉树分类
  • 02.实现二叉树
    • 二叉查找树节点的定义，二叉树遍历，二叉树查找，最大值和最小值，前驱和后继，插入和删除
  • 03.存储二叉树
    • 二叉树存储方式，链式存储，顺序存储
  • 04.红黑树
    • AVL树是高度平衡的而二叉树。R-B Tree，全称是Red-Black Tree，又称为“红黑树”。
  • 10.重建二叉树1
    • 根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  • 11.重建二叉树2
    • 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
  • 13.二叉搜索树后序遍历
    • 输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。
  • 14.从上往下打印二叉树
    • 从上往下打印出二叉树的每个结点，同一层的结点按照从左向右的顺序打印。
  • 15.二叉树的深度
    • 输入一棵二叉树的根结点，求该树的深度。从根结点到叶子点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
  • 16.判断平衡二叉树
    • 输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1 ，那么它就是一棵平衡二叉树。
  • 17.二叉树下一个结点
    • 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
  • 18.对称的二叉树
    • 请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
  • 19.二叉树打印出多行
    • 从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印一行。
  • 20.按之字形顺序打印二叉树
    • 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，即第一行按照从左到右的顺序打印，第二层按照从右到左顺序打印，第三行再按照从左到右的顺序打印，其他以此类推。
  • 21.二叉搜索树第k个结点
    • 给定一棵二叉搜索树，请找出其中的第k大的结点。
  • 22.二叉树的镜像
    • 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
  • 23.树的子结构
    • 输入两个二叉树A 和B，判断B 是不是A 的子结构。

06.排序

  • 01.冒泡排序
    • 很好理解，从字面意思就知道类似于冒泡。在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
  • 02.插入排序
    • 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
  • 03.选择排序
    • 选择排序分为三种，直接选择排序、树形选择排序（锦标赛排序）、堆排序（大根堆、小根堆）。直接选择排序和堆排序是不稳定排序，树形选择排序是稳定排序。
  • 04.快速排序
    • 快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
  • 05.希尔排序
    • 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
  • 06.归并排序
    • 归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
  • 07.堆排序
    • 堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
  • 08.计数排序
    • 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
  • 09.桶排序
    • 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
  • 10.基数排序
    • 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

07.查找

  • 01.二分查找
    • 无需数组是否能用二分查找？二分查找基本思想，查找过程，以及代码展示

08.选择

09.散列

10.字符串

  • 01.翻转字符串
    • 比如，输入‘yangchong’，则输出‘gnohcgnay’
  • 02.字符串替换空格
    • 实现一个函数，把字符串中的每个空格替换成"%20"，例如“We are happy.”，则输出“We%20are%20happy.”。
  • 04.回文字符串
    • 回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
  • 05.字符串的排列
    • 输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc。则打印出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac 、bca、cab 和cba 。
  • 06.第一个只出现一次的字符
    • 在字符串中找出第一个只出现一次的字符
  • 07.把字符串转换成整数
    • 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。
  • 08.翻转单词顺序
    • 输入一个英文句子，翻转句子中单词的顺序，但单词内字的顺序不变。为简单起见，标点符号和普通字母一样处理。
  • 09.左旋转字符串
    • 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。
  • 10.表示数值字符串
    • 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
  • 11.查找最长公共前缀
    • 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
  • 12.把字符串转换成整数
    • 实现一个函数stringToInt,实现把字符串转换成整数这个功能，不能使用atoi或者其他类似的库函数。

11.递归

12.Hash

20.其他

  • 01.斐波那契数列
    • 什么是斐波那契数列？现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=40，有多种实现方式。为何递归效率低？递归和迭代效率比较是怎样的？
  • 02.跳台阶问题
    • 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
  • 03.二进制中1的个数
    • 请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制1001，有2位1。因此如果输入9，该函数输出2。
  • 04.求从1到n的整数中1出现的次数
    • 输入一个整数n，求从1 到n这n个整数的十进制表示中1 出现的次数。
  • 05.打印1到最大的n位数
    • 输入数字n，按顺序打印出从1到n位最大十进数的数值。比如输入3，则打印出1、2、3一直到最大三位数即999。
  • 06.n个骰子的点数
    • 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s 的所有可能的值出现的概率。
  • 07.扑克牌的顺子
    • 从扑克牌中随机抽5张牌，判断是不是一个顺子， 即这5张牌是不是连续的。2～10为数字本身， A为1。 J为11、Q为12、 为13。小王可以看成任意数字。
  • 08.不用加减乘除做加法
    • 写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷四则运算符号。
  • 09.字符流中第一个不重复的字符
    • 请实现一个函数用来找出字符流中第一个只出现一次的字符。
  • 10.机器人的运动范围
    • 地上有个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。

其他介绍

01.关于博客汇总链接

02.关于我的博客