校招算法梳理(三)

比较器的使用

非基于比较的排序

数组/队列/栈题目合集

1、比较器的使用

c++重载运算符–>自己定义比较器

使用排序的时候,直接用比较器会更加方便。

定义student类型如何比较大小的?

堆结构也能用比较器,帮助组织堆

有序结构中,伴随比较器的构造,可以构造treemap(红黑树)

2、非基于比较的排序

桶排序

是一个概念,有一定的局限性,无法作为通解被应用。是稳定的排序,一个萝卜一个坑。

计数排序

有一定的范围限制

一遍排序,记录数组中每一个数的词频,之后重构新数组即做好了排序,0号位置有多少个数,1号位置有多少个数,按照数据状况设计容器,。O(n)

基数排序

只准备10个桶

给定数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(n),且要求不能用非基于比较的排序。

(年年考)插图 MaxGap

  • 准备桶,

    数组中n个数,准备n+1个桶

    遍历整个数组,找到最小值和最大值,若最小值和最大值相等,则只有一种数

    若最小值,最大值不等,最小值放0,最大值放n号桶,中间位置的数等分成(n+1)份,一个数属于哪个范围进几号桶。

    空桶没收集过数。左右桶最小的最大差值一定大于桶的表示范围。来自一个桶内部产生的差值一定小于这个范围。最大差值一定来自跨桶的相邻两个数。

    只存每个桶是否进来数、桶内最大值、桶内最小值。空则跳下一个数,非空桶找左边离他最近的非空桶的最大值,算最大差值。所有的差值算出来,一定存在最大差值。

用数组结构实现大小固定的队列和栈

实现一个特殊的栈,在实现栈基本功能的基础上,再返回栈中最小元素的操作 插图

要求

  • pop push getMin的时间复杂度都是0(1)
  • 设计的栈类型可以采用现成的栈结构

准备两个栈,DATA和MIN栈,当前数和MIN栈顶比较,当前数小,则压当前数,否则重复压入MIN栈顶。MIN栈随之一起压,在任何一部得到最小元素,则MIN栈栈顶即为最小元素。

弹出一个数的时候,无任何判断,同步弹出。增加空间,维持最小值的结构。

如何仅用队列结构实现栈结构?

插图

栈先进后出

队列Data,队列Help,Data队列存1-(n-1),Data存最后数,其他数出站进入help。

数只进Data数列,

如何仅用栈结构实现队列结构?

两个栈结构,PUSH和POP栈

新给的数进PUSH栈,最后的数留着,其他的数倒入POP栈。

倒数句的行为要满足以下两个规则才不会出错,无论发生在何时倒数据一定对。

  • PUSH栈决定倒,则需要一次倒完
  • POP栈有东西,PUSH栈一定不要倒

猫狗问题

设计猫狗队列的结构,往里面丢狗或者猫,通过宠物的type类型

转圈打印矩阵

反转单向和双向链表

之字形打印矩阵

知道斜线的端点,打印斜线的点集

行和列都排好序的矩阵中找数

右上角开始按行往回走,O(n+m),右上角大于要找的数,则此列不可能

要么从数据状况出发,要么从本身问法出发,往往能得到很多优良的解。

判断链表是否为回环结构

笔试,面试不一样,要求优化额外空间复杂度。

面试要求额外空间复杂度尽可能少。笔试的话以最快解出来的方式去做。

1.遍历时把节点放到栈里面去,变成逆序,遍历时每次从栈中拿,比较拿出来的数是否相等

2.快指针一次走两步,慢指针一次走一步,快指针走完了,慢指针还没走完,后面遍历时压栈。再从头开始遍历和栈里面的去比较。相当于只把后半段逆序,和前半段比较。

3,快指针一次两步,慢指针一次一步,中点时,把右半部分逆序。奇数个数的时候,走到中点,偶数个数时走到中点前一个,把中点后的逆序。记录中点位置,后面还得逆序把结构改回去。

单向链表划分左边小,中间相等,右边大

调好数组,node类型的。荷兰国旗问题,不稳定。

进阶:稳定性,额外复杂度空间O(1)

less equal more = null

遍历链表,找到第一个小于num的节点,让less=num equal =num

三条链表,最后链接在一起

每一个区域次序都是串好的,链接的时候和其他区域首尾相连接即可。

两个单链表相交的一系列问题

有环还是无环,找相交的第一个节点,相交则返回第一个节点,不想交返回null,时间复杂度O(M+N),额外空间复杂度O(1)。

判断有环无环,用哈希表,保留key,hashSet(只有key),之前加入过set则有环,第一次查到的存在的key就是第一个相交的节点。

不用哈希表,准备两个指针,快指针和慢指针,快2慢1,快走的时候碰到null,则无环。有环,则快慢指针必相遇,相遇时,快指针回到开头,快指针变成一次走一步,则必定在第一个入环节点处相遇。(结论,数学证明,归纳法)

相交只有三种拓扑结构

各自成环不想交

各自相交共一个环

各自共一个环,其他不想交

如何区分?head1 loop1 和head2 loop2,环外单链表

loop1 == loop2,等同于无环链表相交。

head1调方法得到其第一个入环节点loop1,head2 loop2 直到null,如果end1不等于end2,则必定不想交。

loop1 next next往下走转回来则不想交,返回loop1

复制含有随机指针节点的链表

每个节点有next和random指针,random指向链表中的某个节点,如何拷贝这个结构?

方法1笔试

遍历,把拷贝的节点作为此节点的value存到map里面,

从1的value找到next指针,可以找到2,通过key为2可以找到2的next,连接起来。

1的value找到random指针,通过random找到3,连接起来。

使用额外空间,装了O(n)。

方法2面试

遍历节点,1 next指向1’,1’指向2,2指向2‘

第二次遍历。每次拿出1和1’,1的random可以找到3,3的next找到3’,连接1’和3’,还是解决3如何找到3’的问题。用结构关系把哈希表省掉。

老链表的random指向老链表的节点,新链表的next不变,两个random不会相互干扰的。next指针怎么新老链表分开,就整个分开了。

再把大的结构,

哈希表结构

k-v结构,查key是否存在,查value是否存在,把key/value可以放到map里面

增删改查和数据量没关系,这些操作的时间复杂度均为O(1),但常数项很大。哈希表记录之间不是连续的。

-------------    本文结束  感谢您的阅读    -------------
胡想成 wechat
欢迎关注个人公众号!
您的支持,是我装逼的最大动力!

本文标题:校招算法梳理(三)

文章作者:胡想成

发布时间:2019年09月02日 - 23:09

最后更新:2020年03月14日 - 10:03

原始链接:xchu.net/2019/09/02/算法3/

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0许可协议,转载请注明出处!