闲来无事刷刷题

Posted by Ink Bai on 2019-02-11     & views

刷题呢可以活跃思维,巩固基础,当然最重要的是面试要考啦咳咳。
首先需要熟练掌握链表、树、栈、队列和哈希表等数据结构,以及它们的操作。
一般最经常考察链表和二叉树,链表的插入和删除结点,二叉树的各种遍历方法的循环和递归写法。
掌握常用查找排序算法,重点是二分查找、归并排序和快速排序。
更加难一点的要求熟练掌握动态规划和贪婪算法。

查找与排序

十大排序算法
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序

四大查找算法
顺序查找
二分查找
哈希表查找
二叉树查找

数组

数组中的内存是连续的,可以根据下标在 O(1) 时间内读写任何元素,因此它的时间效率很高。我们可以根据数组时间效率高的优点,用数组来实现简单的哈希表:把数组的下标设为哈希表的键值(key),而把数组中的每一个元素设为哈希表的值(value),这样我们就可以在 O(1) 的时间内实现查找。

剑指 offer
面试题 03:二维数组中的查找
面试题 08:旋转数组的最小数字
面试题 14:调整数组顺序使奇数位于偶数前面

字符串

剑指 offer
面试题 04:替换空格

链表

链表问题一般会有大量的指针移动操作,当我们使用一个指针解决不了的时候可以多定义几个指针来解决。

剑指 offer
面试题 05:从尾到头打印链表
面试题 13:在 O(1) 时间删除链表结点
面试题 15:链表中倒数第 k 个结点
面试题 16:反转链表
面试题 17:合并两个排序的链表
面试题 26:复杂链表的复制

树有三种遍历方式:

  • 前序遍历:根结点 -> 左子结点 -> 右子结点
  • 中序遍历:左子结点 -> 根节点 -> 右子结点
  • 后续遍历:左子结点 -> 右子结点 -> 根结点

宽度优先遍历:从上到下,从左到右遍历树。

二叉搜索树:左子结点总是小于或等于根节点,右子结点总是大于或等于根节点。我们可以平均在 O(logn) 的时间内根据数值在二叉搜索树中找到一个结点。

堆:最大堆和最小堆。最大堆中根节点的值最大,在最小堆中根节点的值最小。很多需要快速找到最大值或者最小值的问题都可以用堆来解决。

红黑树:树中的结点定义为红、黑两种颜色,并通过规则确保从根节点到叶结点的最长路径的长度不超过最短路径的两倍。

剑指 offer
面试题 06:重建二叉树
面试题 18:树的子结构
面试题 19:二叉树的镜像
面试题 24:二叉搜索树的后序遍历序列
面试题 25:二叉树中和为某一值的路径
面试题 27:二叉搜索树与双向链表

栈和队列

剑指 offer
面试题 07:用两个栈实现队列
面试题 21:包含 min 函数的栈
面试题 22:栈的压入、弹出序列
面试题 23:从上往下打印二叉树

位运算

剑指 offer
面试题 10:二进制中 1 的个数

回溯法

剑指 offer

动态规划

剑指 offer

大数据算法

剑指 offer

其他

剑指 offer
面试题 09:斐波那契数列
面试题 11:数值的整数次方
面试题 12:打印 1 到最大的 n 位数
面试题 20:顺时针打印矩阵

Refer

十大经典排序算法
面试中的排序算法总结
算法总结
关于快速排序的四种写法
查找算法的Java实现
七大查找算法
八大排序算法稳定性分析