15道简单算法题

最近在公司里基本处于打酱油的状态,工作正在交接中。没事又做起了算法题目。好久没怎么写算法题了,感觉手气还不错,经常能一次就写对(编译通过,得到想要的结果,没怎么测试),可能是因为这些题目之前看过或是写过,或许就是自己进步了一点。这15道大部分来自《剑指Offer》,作者的博客之前看过几次,感觉写得很好,但看这本书时却没有那个感觉了,可能是因为看过博客的原因吧,没有了之前的那种惊喜。自己就试着实现里面的一些算法题目,基本上是简单的思考一下,如果没什么思路,就看看作者是怎么想的,大概看一下他的思路或是代码,就开始自己实现。15道算法题如下:源码下载

1:合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素;

2:合并两个单链表;

3:倒序打印一个单链表;

4:给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点;

5:找到链表倒数第K个节点;

6:反转单链表;

7:通过两个栈实现一个队列;

8:二分查找;

9:快速排序;

10:获得一个int型的数中二进制中的个数;

11:输入一个数组,实现一个函数,让所有奇数都在偶数前面;

12:判断一个字符串是否是另一个字符串的子串;

13:把一个int型数组中的数字拼成一个串,这个串代表的数字最小;

14:输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置);

15:输入两个链表,找到它们第一个公共节点;

下面简单说说思路和代码实现

1:合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素;

合并排序一般的思路都是创建一个更大数组C,刚好容纳两个数组的元素,先是一个while循环比较,将其中一个数组A比较完成,将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中,再将A中剩下的数存入C中,但这里是已经有一个数组能存下两个数组的全部元素,就不用在创建数组了,但只能从后往前面存,从前往后存,要移动元素很麻烦。

2:合并两个单链表;

合并链表和合并数组,我用了大致相同的代码,就不多少了,那本书用的是递归实现。

3:倒序打印一个单链表;

递归实现,先递归在打印就变成倒序打印了,如果先打印在调用自己就是顺序打印了。

4:给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点;

删除节点的核心还是将这个节点的下一个节点,代替当前节点。

5:找到链表倒数第K个节点;

通过两个指针,两个指针都指向链表的开始,一个指针先向前走K个节点,然后再以前向前走,当先走的那个节点到达末尾时,另一个节点就刚好与末尾节点相差K个节点。

6:反转单链表;

按顺序一个个的翻转就是了。

7:通过两个栈实现一个队列;

直接上代码

8:二分查找;

二分查找记住几个要点就行了,代码也就那几行,反正我现在是可以背出来了,start=0,end=数组长度-1,while(start<=end),注意溢出

9:快速排序;

来自百度百科,说不清楚

10:获得一个int型的数中二进制中的个数;

核心实现就是while (num= num & (num-1)),通过这个数和比它小1的数的二进制进行&运算,将二进制中1慢慢的从后往前去掉,直到没有。

11:输入一个数组,实现一个函数,让所有奇数都在偶数前面;

两个指针,一个从前往后,一个从后往前,前面的指针遇到奇数就往后走,后面的指针遇到偶数就往前走,只要两个指针没有相遇,就奇偶交换。

12:判断一个字符串是否是另一个字符串的子串;

我这里就是暴力的对比

13:把一个int型数组中的数字拼成一个串,这个串代表的数字最小;

先将数字转换成字符串存在数组中,在通过qsort排序,在排序用到的比较函数中,将要比较的两个字符串进行组合,如要比较的两个字符串分别是A,B,那么组合成,A+B,和B+A,在比较A+B和B+A,返回strcmp(A+B, B+A),经过qsort这么一排序,数组就变成从小到大的顺序了,组成的数自然是最小的。

14:输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置);

递归实现,只要某个节点的两个子节点都不为空,就左右交换,让左子树交换,让右子树交换。

15:输入两个链表,找到它们第一个公共节点;

如果两个链表有公共的节点,那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点(N=短链表的长度节点个数),长链表先往前走K个节点(K=长链表的节点个数-N),这时两个链表都距离末尾N个节点,现在可以一一比较了,最多比较N次,如果有两个节点相同就是第一个公共节点,否则就没有公共节点。

5 收藏 1 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部