整理之刷过的数据结构与算法题

现在准备春招实习,又要疯狂刷题了,想起之前刷过的数据结构与算法题,放在github了,但是比较乱,没有给索引,后面复习很不方便。所以我决定抽空把之前的题目整理一下,做个索引放在这里,不定期更新。。。(github地址是Python-Machine-Learning-Homework主要是用python写的,混合了部分C和C++代码,题目的来大部分是剑指offer,还有部分网上找的题,往年公司面试、笔试的题目等。也欢迎大家PR补充。。。)

1.输入:输入一个正整数N(N<=10000) 输出:所有小于等于N的素数

2.输入:输入一个正整数N(N<=10000) 输出:前N项斐波那契数列

3.假设小明的家位于数轴上的一点(正数表示在正半轴,负数表示在负半轴,0表示在原点),现有N个数轴上的点,第0个点为小明的家,第N-1个是小明要去的目的地,小明从家开始依次逐个去往每一个点,最后到达目的地。现在小明可以从除去家和目的地的N-2个点中任意去掉一个点。问:小明最少行走的路程为多少?

4.输入一个正整数N,输入一个N维矩阵,输出该矩阵的行列式(结果保留两位小数)

5.输入两个正整数m,n(m>=n),输入一个含有m个不同正整数的集合,输出从该集合中选取n个数的所有可能(不计顺序)

6.N为正整数,N个同学排成一排,每个人的编号为1,2,...,N,每个人身上都有一定数目的钱,现在要从N个人中选出m(1<=m<=N)个人,且要求这m个人相邻序号之差的绝对值不大于k,k是一个正整数(1<=k<=N-1),并且这m个人身上的钱数乘积最大。问:应该如何选取?输入 N,m,k,输入 N个人身上的钱数.输出钱数的最大乘积。

7.在一个字符串中找出长度最长的数字串,并返回最后一个最长的数字串及其长度

8.100个人围成一圈,编号从1开始到100.从1开始报数,报到M的人自动退出,下一个人接着从1开始报数,直到剩余人数小于M。求最后剩余人的编号。

9.酒馆有m个龙头,每个龙头出酒量相等,都为1.现有n名顾客,按照顺序1...n接酒,i号顾客接酒量为w_i。接酒开始时,1到m号顾客分别占领一个酒龙头,同时开始,并且一人接完后,下一人立刻接替。求总接酒时间?

10.输入一个正整数N,输入N*N的矩阵,输出:矩阵是否可逆,0表示不可逆,1表示可逆,输出逆矩阵

11.现在有一个背包重量为n千克,有m种水果,每种水果的的重量分别为w1,w2,...,wm,价值为p1,p2,...,pm,现在要使背包中所装的水果总价值最大,且总重量不超过水果的总负荷,问应该如何装水果?(这里假设m,n,w1,...,wm,p1,...,pm 均为正整数)

12.设n为奇数,将1到nxn这个nxn个数字排列成为一个nxn的方阵,使得各行,各列以及对角线上的数字之和相等。

13.使用python类实现一个双向链表结构,并且实现增删查改等基本操作。

14.3 = 2+1 = 1+1+1,所以3一共有三种拆解的方式.4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 共有5种拆法.输入一个正整数N,输出拆解的总数以及所有可能的拆解

15.已知二维平面有一组点:(0,0),(0,1),(0.5,0.3),(0.2,0.8),(1.2,2.4),(1.5,1.5),(2,2),(2.5,3) 共8个点,前4个点为一类,后4个点为一类,利用感知器算法求出将这两类点划分开来的直线的方程。

16.geohash编码

17.假定一种编码的编码范围是a ~ y的25个字母,从1位到4位的编码,如果我们把该编码按字典序排序,形成一个数组如下: a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index为0,aa的Index为1,aaa的Index为2,以此类推。 编写一个函数,输入是任意一个编码,输出这个编码对应的Index.

18.雨滴问题代码

19.使用python实现二叉树,并写出中序遍历,前序遍历,后序遍历,以及层次遍历的结果。

20.小明手里有一些钱,现在有两个聚宝盆编号为0号和1号。0号的特性是:如果给它投入x的钱,它会变出2x+1的钱;1号的特性是:如果给它投入x的钱,它会变出2x+2的钱。(这里x可以为0)。现在小明手里没有钱,如果他想得到n数量的钱,应该按照什么样的顺序使用两个聚宝盆呢?

21.给定一串字符串,规定连续出现m次的字符串为部分字符串,例如"aabbcdd"的部分字符串有"aa","bb","c","dd",求任意给定字符串的所有部分字符串的平均长度。

22.在字符串中寻找出,第一个只出现一次的字符。

23.把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

24.顺时针打印矩阵

25.某餐馆有n张桌子,每张桌子有一个参数:a 可容纳的最大人数; 有m批客人,每批客人有两个参数:b人数,c预计消费金额。 在不允许拼桌的情况下,请实现一个算法选择其中一部分客人,使得总预计消费金额最大。

26.输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。接下来m行,每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。

27.给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

28.使用python实现二叉排序树(二叉查找树)

29.字符串的朴素匹配与KMP匹配算法

30.快速排序算法(quick sort)

31.设计一种算法,给定数a和数b(a<b),生成服从(a,b)间均匀分布的随机数。在已知均匀分布的情况下,如果已知概率密度函数,如何生成服从该分布的随机数?试以正态分布的情况为例进行说明。

32.给定一个正整数n,集合{1,2,...,n}的所有子集(包括空集)显然有2^n个,请按照字典顺序逐个输出这2^n个子集。

33.python的random 模块有一个shuffle方法,其作用是将列表的所有元素随机打乱顺序然后输出。试设计一种算法,输入正整数n,将1,2,...,n 随机打乱顺序以后输出。

34.八皇后问题

35.扑克牌的24点游戏是一个大家广为熟知的游戏。现在每次随机地从1-13中取出四个数字(可以重复),问在每个数字都需要使用且只能使用一次,数字运算只能使用加减乘除中的一种的条件下,如何操作才能得到数字24?如果存在解,则返回具体的操作方法(全部的解),如果不存在则返回0。

36.实现EM算法(具体可以参见《统计学习方法》对于EM算法的介绍或者自行查找资料),以高斯混合模型(MOG)参数估计为例给出算法的具体说明。

37.使用python实现红黑树。

38.圆周率pi有很多高精度的算法,试自行查阅资料,实现一种算法将圆周率pi计算到小数点后一万位。

39.多层神经网络的一种核心算法之一就是BP算法(误差反向传播算法),阅读相关资料,实现基础的BP算法,并用数据检验其效果如何。

40.设计一个程序,使得该程序的输出就是该程序本身。

41求解生命游戏(game of life,也被称为元胞自动机)。

42大数乘法

43.如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列

44.小易有一些彩色的砖块。每种颜色由一个大写字母表示。各个颜色砖块看起来都完全一样。现在有一个给定的字符串s,s中每个字符代表小易的某个砖块的颜色。小易想把他所有的砖块排成一行。如果最多存在一对不同颜色的相邻砖块,那么这行砖块就很漂亮的。请你帮助小易计算有多少种方式将他所有砖块排成漂亮的一行。(如果两种方式所对应的砖块颜色序列是相同的,那么认为这两种方式是一样的。)例如: s = "ABAB",那么小易有六种排列的结果:"AABB","ABAB","ABBA","BAAB","BABA","BBAA"其中只有"AABB"和"BBAA"满足最多只有一对不同颜色的相邻砖块。

45.给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?

46小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢?

47.Python中的默认排序算法为timsort,一个做了大量优化的归并排序。试查阅资料实现这一排序算法并分析其算法时间复杂度。

48.实现shell排序并分析算法的时间复杂度。

49.现在有一堆(25张)已经被分割的RGB图片(参见[压缩包](https://github.com/Lyrichu/Python-Machine-Learning-Homework/tree/master/20171009/Images)),试设计一种算法将这些图片复原拼接为原本的完整图片

50.现在有一个m*n的网格(m,n均小于100),现在在左上角有一个点A,右下角有一个点B,规定点A每次只能往右或者往下移动,问从A移动到B一共有多少种不同的方法?

51.我们把一个N位的数字等于其各位的N次方之和的数字称为阿姆斯特朗数,求100000以内的所有阿姆斯特朗数。

---------------------------------写的累死了,还有一半,后面有空再贴上去---------------------------------------

PS:贴几个我认为总结的很好的网址

- 常见数据结构详解

- 常用的机器学习算法通俗讲解

-牛客网剑指offer在线编程

热爱编程,热爱机器学习! github:http://www.github.com/Lyrichu github blog:http://Lyrichu.github.io 个人博客站点:http://www.movieb2b.com(不再维护)
上一篇:C语言实现二叉树的基本操作


下一篇:EM 算法求解高斯混合模型python实现