剑指offer编程（6-10） 旋转数组中的最小数字 题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 思路一 直接遍历数组，如果一个数比前一个数小，该数即为最小，复杂度较高O（n） 代码实现 class Solution: def minNumberInRotateArray(self, rotateArray): if ...

这几天开始刷牛客网上剑指offer的编程题，下面一系列博客将用python实现里面的编程题，很多参考了大神的思路（C实现），然后用python实现的。 二维数组查找 题目描述 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 6 14 22 26 8 16 24 30 10 20 30 40 输入10 ，返回True 思路 观察数组规律，从左下角元素开始找，如果目标值比它大，就查找下一列，比它小，就查找上一行。 代码实现 class S...

本文主要用python实现二叉树的4种遍历算法，除层次遍历外，前序、中序和后序遍历分别包含递归和非递归2种实现方式。 前序遍历 # -----------前序遍历 ------------ # 递归算法 def pre_order_recursive(self, T): if T == None: return print(T.root, end=' ') self.pre_order_recursive(T.lchild) self.pre_order_recursive(T.r...

本文主要用python语言实现栈和队列的基本操作。 python实现栈的基本操作 """ 以列表的形式简单实现栈 栈：先进后出 """ class Stack: def __init__(self): self.stack = [] # 初始化 def is_empty(self): return not bool(self.stack) # 判空 def push(self, value): self.stack.append(value) #...

刚参加了阿里的计算机视觉实习岗的在线笔试题，人有点懵，提前半小时就交卷了。 单项选择题（10道），半小时交卷 真第一次遇见单选题有6个选项的=-= 网络协议（百万级路由器的TCP协议，让你选择正确的方案） 哈希表 求解[100,999]区间内个十百位相加能被8整除的数字的个数（这个简单） 投票重叠，集合的交并补 双向循环链表（前插后插、删除，选择不正确的一项） 左***，共8发子弹，有2发子弹有问题，问题概率为0.1，其中2枚有问题的子弹放在一起。连续扣动2次扳机，问死亡率为多少？ 有2n张牌（包含2张王），发给2个人A和B，每人n张，每发完一张牌，2人会相互...

本文主要介绍树和二叉树的应用，主要包含3个部分：二叉排序树、平衡二叉树和哈夫曼树和哈夫曼编码。 二叉排序树（BST） 定义 二叉排序树（简称BST），也称二叉查找树。二叉排序树或者是一棵空树，或者是一棵有下列特性的非空二叉树： 若左子树非空，则左子树上所有结点关键字的值均小于根结点的关键字值 若右子树非空，则右子树上所有结点关键字的值均大于根结点的关键字值 左、右子树本身也分别是一棵二叉排序树 查找 关于二叉排序的查找，在C语言实现七大查找算法（三）我的这篇博文中，已经详细介绍了，此处不再赘述。 查找效率：平均查找长度主要取决于树的高度。 二叉排序树和二分...

本文主要介绍线索二叉树和树、二叉树、森林三者之间的相互转换。 对于线索二叉树，这里只做简单介绍，着重还是要理解上篇博文中二叉树的各种遍历算法。 线索二叉树 基本概念 遍历二叉树的实质就是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个直接前驱和直接后继。 传统的链式存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱和后继。通过观察，我们发现在二叉链表表示的二叉树中存在大量的空指针，若利用这些空链域存放指向其直接前驱或后继的指针，则可以方便的运用某些二叉树操作算法。引入线索二叉树的目的是为了加快查找结点前驱和后继的速度。 在二叉树线...

本文主要介绍二叉树的各种遍历方法。 二叉树的遍历 所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。 由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N N N、左子树 L L ...

本部分主要介绍树的相关知识，将分为3篇博文介绍。 本文将着重介绍二叉树的一些基本概念，以及在其基础上的一些特殊的树形式：满二叉树、完全二叉树、线索二叉树、二叉排序树、平衡二叉树等。 树的基本概念 树的定义 树是 N （ N ≥ 0 ） ...

在这篇博文中，我们介绍了剩下4种排序算法，并将对所有的排序算法做一个总结。 代码主要参见数据机构之十大排序，关于拓展里面的桶排序和计数排序，只了解了想法，并未自己实现，不过也给出了参考资料中别人的代码实现。 选择排序（Selection Sort） 基本思想 在要排序的一组数中，选出最小（或者最大）的一个数与第 1 1 1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第 ...

本文主要介绍数据结构中常见的八大排序算法，冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序。 排序相描述 排序分类：若排序过程中，所有的文件都是放在内存中处理的，不涉及数据的内外存交换，则称该排序算法是内部排序算法; 若排序过程中涉及内外存交换，则是外部排序。内部排序适合小文间，外部排序适用于不能一次性把所有记录放入内存的大文件。常见的分类算法还可以根据排序方式分为两大类：比较排序和非比较排序。 排序算法的稳定性： 若排序对象中存在多个关键字相同的记录，经过排序后，相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的，若次序发生变化...

前两天刚参加完百度计算机视觉算法实习岗的远程笔试，下面是我记忆中的一些考题，先记录下来，等答案公布再来详细分析。 题型 选择：30道，每题2分，共60分 问答：1道，每题30分，共30分 设计：1道，每题30分，共30分 编程：2道，每题20分，共40分 总分160分，考试时间2h 选择题 选择题包含单选和多选，涉及到的考点很广，主要包括数据结构、操作系统、网络、C++程序题、视觉相关题等。数据结构和C++程序题偏多。 数据结构 哈希表 动态规划 时间复杂度的影响因素 哈夫曼编码 程序的三大基本结构 逆波兰表达式 操作系统...

上一篇博文主要介绍了哈希查找算法，本文主要介绍树表查找算法。 这是一类算法，主要包含二叉查找树、平衡查找树之2-3查找树、平衡查找树之红黑树（Red-Black Tree）、B树和B+树。 本文主要弄懂各种查找树的思想，也附上了部分实现代码。代码有时间在详细研读，此处先记录下来。红黑树、B树和B+树还是有点难懂~ ~ ~，本文只是简要介绍了思想，具体实现见参考资料 二叉树查找算法 算法简介 二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 ...

在前面的博文中，我们介绍了5种查找算法，本文主要介绍哈希表及哈希查找算法。 在介绍哈希查找算法之前，我们需要详细了解什么是哈希表及其构造实现方法。 哈希表 哈希表的基本思想 我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构。这就是哈希表创建的基本思想，哈希表就是这样一个集查找、插入和删除操作于一身的数据结构。 哈希表的一些基本概念 哈希表（Hash Table）：也叫散列表，是根据关键码值（Key-Value）而直接进行访问的数据结构，也...