精华内容
下载资源
问答
  • 2021最新版数据结构与算法面试题手册,搜集了JAVA、GO等主流编程语言面试常见问题。
  • 2021年最新整合的数据结构与算法面试题,一共100多页的文档,需要的小伙伴可以拿走,里面有按编程语言区分需要学习的算法知识点,很详细很全面。
  • 数据结构与算法面试题 pdf
  • 本人花几个月在多个优秀博客总结整理出来的,希望对大家有用。
  • 精选众多IT企业软开面试题,包括数据结构与算法。 很早之前的文档了,但内容并不过时,多少年了基础的东西就是这些。
  • 数据结构与算法面试题80道

    千次阅读 2019-01-10 19:29:18
    由于这些,实在太火了。所以,应广大网友建议要求,在此把之前已整理公布的前80,   现在,一次性分享出来。此也算是前80第一次集体亮相。   此些,已有上万人,看到或见识到,若私自据为己有,必定为...

    由于这些题,实在太火了。所以,应广大网友建议要求,在此把之前已整理公布的前80题,

     

    现在,一次性分享出来。此也算是前80题第一次集体亮相。

     

    此些题,已有上万人,看到或见识到,若私自据为己有,必定为有知之人识破,付出代价。

     

    所以,作者声明:

     

    本人July对以上所有任何内容和资料享有版权,转载请注明作者本人July出处。

    向你的厚道致敬。谢谢。

     

    ----------------------------------------------------------------------------------------------------------------

     

     

     

    1.把二元查找树转变成排序的双向链表

     题目:

    输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。

    要求不能创建任何新的结点,只调整指针的指向。

       10

     / \

     6 14

     / \ / \

    4 8 12 16

     转换成双向链表

    4=6=8=10=12=14=16。

     

     首先我们定义的二元查找树 节点的数据结构如下:

     struct BSTreeNode

    {

     int m_nValue; // value of node

     BSTreeNode *m_pLeft; // left child of node

     BSTreeNode *m_pRight; // right child of node

    };

     

     

    2.设计包含min函数的栈。

    定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。

    要求函数min、push以及pop的时间复杂度都是O(1)。

     

     

     

     

    3.求子数组的最大和

    题目:

    输入一个整形数组,数组里有正数也有负数。

    数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

    求所有子数组的和的最大值。要求时间复杂度为O(n)。

     

    例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,

    因此输出为该子数组的和18。

     

     

     

    4.在二元树中找出和为某一值的所有路径

     

    题目:输入一个整数和一棵二元树。

    从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

    打印出和与输入整数相等的所有路径。

    例如 输入整数22和如下二元树

     10 

     / \  

     5 12  

     /   \  

    4     7

    则打印出两条路径:10, 12和10, 5, 7。

     

    二元树节点的数据结构定义为:

    struct BinaryTreeNode // a node in the binary tree

    {

    int m_nValue; // value of node

    BinaryTreeNode *m_pLeft; // left child of node

    BinaryTreeNode *m_pRight; // right child of node

    };

     

     

     

    5.查找最小的k个元素

    题目:输入n个整数,输出其中最小的k个。

    例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。

     

     

     

     

    第6题

    腾讯面试题:

    给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数

    要求下排每个数都是先前上排那十个数在下排出现的次数。

    上排的十个数如下:

    【0,1,2,3,4,5,6,7,8,9】

     

    举一个例子,

    数值: 0,1,2,3,4,5,6,7,8,9

    分配: 6,2,1,0,0,0,1,0,0,0

    0在下排出现了6次,1在下排出现了2次,

    2在下排出现了1次,3在下排出现了0次....

    以此类推..

     

     

    第7题

    微软亚院之编程判断俩个链表是否相交

    给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。

    为了简化问题,我们假设俩个链表均不带环。

     

    问题扩展:

    1.如果链表可能有环列?

    2.如果需要求出俩个链表相交的第一个节点列?

     

     

    第8题

    此贴选一些 比较怪的题,,由于其中题目本身与算法关系不大,仅考考思维。特此并作一题。

    1.有两个房间,一间房里有三盏灯,另一间房有控制着三盏灯的三个开关,

     

    这两个房间是 分割开的,从一间里不能看到另一间的情况。

    现在要求受训者分别进这两房间一次,然后判断出这三盏灯分别是由哪个开关控制的。

    有什么办法呢?

     

    2.你让一些人为你工作了七天,你要用一根金条作为报酬。金条被分成七小块,每天给出一块。

    如果你只能将金条切割两次,你怎样分给这些工人?

     

    3. ★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

      ★用一种算法在一个循环的链接表里插入一个节点,但不得穿越链接表。

      ★用一种算法整理一个数组。你为什么选择这种方法?

      ★用一种算法使通用字符串相匹配。

      ★颠倒一个字符串。优化速度。优化空间。

      ★颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”,

     

    实现速度最快,移动最少。

      ★找到一个子字符串。优化速度。优化空间。

      ★比较两个字符串,用O(n)时间和恒量空间。

       ★假设你有一个用1001个整数组成的数组,这些整数是任意排列的,但是你知道所有的整数都在1到1000(包括1000)之间。此外,除一个数字出现 两次外,其他所有数字只出现一次。假设你只能对这个数组做一次处理,用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式,那么你能找到不 用这种方式的算法吗?

      ★不用乘法或加法增加8倍。现在用同样的方法增加7倍。

     

     

     

     

    第9题

    判断整数序列是不是二元查找树的后序遍历结果

    题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。

    如果是返回true,否则返回false。

     

    例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:

             8

          / \

         6    10

        / \ / \

       5 7 9 11

    因此返回true。

    如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

     

     

     

    第10题

    翻转句子中单词的顺序。

    题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。

     

    句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。

    例如输入“I am a student.”,则输出“student. a am I”。

     

     

    第11题

    求二叉树中节点的最大距离...

     

    如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,

    我们姑且定义"距离"为两节点之间边的个数。

    写一个程序,

    求一棵二叉树中相距最远的两个节点之间的距离。

     

     

     

    第12题

    题目:求1+2+…+n,

    要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。

     

     

     

    第13题:

    题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

    链表结点定义如下: 

    struct ListNode

    {

     int m_nKey;

     ListNode* m_pNext;

    };

     

     

     

    第14题:

    题目:输入一个已经按升序排序过的数组和一个数字,

    在数组中查找两个数,使得它们的和正好是输入的那个数字。

    要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。

    例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

     

     

     

    第15题:

    题目:输入一颗二元查找树,将该树转换为它的镜像,

    即在转换后的二元查找树中,左子树的结点都大于右子树的结点。

    用递归和循环两种方法完成树的镜像转换。 

    例如输入:

     8

     / \

     6 10

     /\ /\

    5 7 9 11

     

    输出:

     8

     / \

     10 6

     /\ /\

    11 9 7 5

     

    定义二元查找树的结点为:

    struct BSTreeNode // a node in the binary search tree (BST)

    {

     int m_nValue; // value of node

     BSTreeNode *m_pLeft; // left child of node

     BSTreeNode *m_pRight; // right child of node

    };

     

     

     

    第16题:

    题目(微软):

    输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 

    例如输入

     8

     / \

     6 10

    / \ / \

    5 7 9 11

     

    输出8 6 10 5 7 9 11。

     

     

     

    第17题:

    题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 

    分析:这道题是2006年google的一道笔试题。

     

     

     

     

    第18题:

    题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,

    每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。

    当一个数字删除后,从被删除数字的下一个继续删除第m个数字。

    求出在这个圆圈中剩下的最后一个数字。

    July:我想,这个题目,不少人已经 见识过了。

     

     

     

     

    第19题:

    题目:定义Fibonacci数列如下: 

     / 0 n=0

    f(n)= 1 n=1

     \ f(n-1)+f(n-2) n=2

     

    输入n,用最快的方法求该数列的第n项。

    分析:在很多C语言教科书中讲到递归函数的时候,都会用Fibonacci作为例子。

    因此很多程序员对这道题的递归解法非常熟悉,但....呵呵,你知道的。。

     

     

     

    第20题:

    题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。

    例如输入字符串"345",则输出整数345。

     

     

     

     

    第21题

    2010年中兴面试题

    编程求解:

    输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,

    使其和等于 m ,要求将其中所有的可能组合列出来.

     

     

     

    第22题:

    有4张红色的牌和4张蓝色的牌,主持人先拿任意两张,再分别在A、B、C三人额头上贴任意两张牌,

    A、B、C三人都可以看见其余两人额头上的牌,看完后让他们猜自己额头上是什么颜色的牌,

    A说不知道,B说不知道,C说不知道,然后A说知道了。

    请教如何推理,A是怎么知道的。

    如果用程序,又怎么实现呢?

     

     

     

     

    第23题:

    用最简单,最快速的方法计算出下面这个圆形是否和正方形相交。" 

    3D坐标系 原点(0.0,0.0,0.0)

    圆形:

    半径r = 3.0

    圆心o = (*.*, 0.0, *.*)

     

    正方形:

    4个角坐标; 

    1:(*.*, 0.0, *.*)

    2:(*.*, 0.0, *.*)

    3:(*.*, 0.0, *.*)

    4:(*.*, 0.0, *.*)

     

     

     

    第24题:

    链表操作,

    (1).单链表就地逆置,

    (2)合并链表

     

     

     

    第25题:

    写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)

    功能:

    在字符串中找出连续最长的数字串,并把这个串的长度返回,

    并把这个最长数字串付给其中一个函数参数outputstr所指内存。

    例如:"abcd12345ed125ss123456789"的首地址传给intputstr后,函数将返回9,

    outputstr所指的值为123456789

     

     

     

    26.左旋转字符串

     

    题目:

    定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。

     

    如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。

    要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。

     

     

     

    27.跳台阶问题

    题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。

    求总共有多少总跳法,并分析算法的时间复杂度。

     

    这道题最近经常出现,包括MicroStrategy等比较重视算法的公司

    都曾先后选用过个这道题作为面试题或者笔试题。

     

     

     

     

     

    28.整数的二进制表示中1的个数

    题目:输入一个整数,求该整数的二进制表达中有多少个1。

    例如输入10,由于其二进制表示为1010,有两个1,因此输出2。

     

    分析:

    这是一道很基本的考查位运算的面试题。

    包括微软在内的很多公司都曾采用过这道题。

     

     

     

     

     

     

    29.栈的push、pop序列

    题目:输入两个整数序列。其中一个序列表示栈的push顺序,

    判断另一个序列有没有可能是对应的pop顺序。

    为了简单起见,我们假设push序列的任意两个整数都是不相等的。 

     

    比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。

    因为可以有如下的push和pop序列:

    push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,

    这样得到的pop序列就是4、5、3、2、1。

    但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

     

     

     

     

    30.在从1到n的正数中1出现的次数

    题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

     

    例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

    分析:这是一道广为流传的google面试题。

     

     

     

    31.华为面试题:

    一类似于蜂窝的结构的图,进行搜索最短路径(要求5分钟)

     

     

     

    32.

    有两个序列a,b,大小都为n,序列元素的值任意整数,无序;

    要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。

    例如: 

    var a=[100,99,98,1,2, 3];

    var b=[1, 2, 3, 4,5,40];

     

     

     

     

    33.

    实现一个挺高级的字符匹配算法:

    给一串很长字符串,要求找到符合要求的字符串,例如目的串:123

    1******3***2 ,12*****3这些都要找出来

    其实就是类似一些和谐系统。。。。。

     

     

     

     

    34.

    实现一个队列。

    队列的应用场景为:

    一个生产者线程将int类型的数入列,一个消费者线程将int类型的数出列

     

     

     

     

    35.

    求一个矩阵中最大的二维矩阵(元素和最大).如:

    1 2 0 3 4

    2 3 4 5 1

    1 1 5 3 0

    中最大的是:

    4 5

    5 3

    要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码

     

     

     

     

    第36题-40题(有些题目搜集于CSDN上的网友,已标明):

    36.引用自网友:longzuo

    谷歌笔试:

    n支队伍比赛,分别编号为0,1,2。。。。n-1,已知它们之间的实力对比关系,

    存储在一个二维数组w[n][n]中,w[i][j] 的值代表编号为i,j的队伍中更强的一支。

     

    所以w[i][j]=i 或者j,现在给出它们的出场顺序,并存储在数组order[n]中,

    比如order[n] = {4,3,5,8,1......},那么第一轮比赛就是 4对3, 5对8。.......

    胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,

    下一轮由上一轮的胜者按照顺序,再依次两两比,比如可能是4对5,直至出现第一名

     

    编程实现,给出二维数组w,一维数组order 和 用于输出比赛名次的数组result[n],

    求出result。

     

     

     

    37.

    有n个长为m+1的字符串,

    如果某个字符串的最后m个字符与某个字符串的前m个字符匹配,则两个字符串可以联接,

    问这n个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。

     

     

     

    38.

    百度面试:

    1.用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的,使用x次天平,

    最多可以从y个小球中找出较轻的那个,求y与x的关系式。

     

    2.有一个很大很大的输入流,大到没有存储器可以将其存储下来,

    而且只输入一次,如何从这个输入流中随机取得m个记录。

     

    3.大量的URL字符串,如何从中去除重复的,优化时间空间复杂度

     

     

     

     

    39.

    网易有道笔试:

    (1).

    求一个二叉树中任意两个节点间的最大距离,

    两个节点的距离的定义是 这两个节点间边的个数,

    比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。

     

    (2).

    求一个有向连通图的割点,割点的定义是,如果除去此节点和与其相关的边,

    有向图不再连通,描述算法。

     

    40.百度研发笔试题

    引用自:zp155334877

    1)设计一个栈结构,满足一下条件:min,push,pop操作的时间复杂度为O(1)。

     

    2)一串首尾相连的珠子(m个),有N种颜色(N<=10),

    设计一个算法,取出其中一段,要求包含所有N中颜色,并使长度最短。

    并分析时间复杂度与空间复杂度。

     

    3)设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,

    则中国人民 人民中国都有效。要求:

     

     *系统每秒的查询数量可能上千次;

     *词语的数量级为10W;

     *每个词至多可以与1W个词搭配

     

    当用户输入中国人民的时候,要求返回与这个搭配词组相关的信息。

     

     

     

     

    41.求固晶机的晶元查找程序

    晶元盘由数目不详的大小一样的晶元组成,晶元并不一定全布满晶元盘,

     

    照相机每次这能匹配一个晶元,如匹配过,则拾取该晶元,

    若匹配不过,照相机则按测好的晶元间距移到下一个位置。

    求遍历晶元盘的算法 求思路。

     

     

     

     

    42.请修改append函数,利用这个函数实现:

     

    两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5

    另外只能输出结果,不能修改两个链表的数据。

     

     

     

    43.递归和非递归俩种方法实现二叉树的前序遍历。

     

     

     

    44.腾讯面试题:

    1.设计一个魔方(六面)的程序。

    2.有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。

    请用5分钟时间,找出重复出现最多的前10条。

     

    3.收藏了1万条url,现在给你一条url,如何找出相似的url。(面试官不解释何为相似)

     

     

     

    45.雅虎:

    1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)

     

    某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。

    2.一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值

      比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1;

     {3,6}{2,4,3} m=2

     {3,3}{2,4}{6} m=3 所以m的最大值为3

     

     

     

     

    46.搜狐:

    四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

     

     

     

    47.创新工场:

    求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}

     

     

     

    48.微软:

    一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}

    是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。

     

     

     

    49.一道看上去很吓人的算法面试题:

    如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

     

     

     

    50.网易有道笔试:

    1.求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是 这两个节点间边的个数,

    比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。

     

    2.求一个有向连通图的割点,割点的定义是,

    如果除去此节点和与其相关的边,有向图不再连通,描述算法。

    -------------------------------------------------------------------

     

     

    51.和为n连续正数序列。

    题目:输入一个正数n,输出所有和为n连续正数序列。

     

    例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。

    分析:这是网易的一道面试题。

     

     

     

     

    52.二元树的深度。

     

    题目:输入一棵二元树的根结点,求该树的深度。

     

    从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

     

    例如:输入二元树:

                                                10

                                              /     \

                                            6        14

                                          /         /   \

                                        4         12     16

     

    输出该树的深度3。

     

    二元树的结点定义如下:

     

    struct SBinaryTreeNode // a node of the binary tree

    {

          int               m_nValue; // value of node

          SBinaryTreeNode *m_pLeft; // left child of node

          SBinaryTreeNode *m_pRight; // right child of node

    };

    分析:这道题本质上还是考查二元树的遍历。

     

     

     

     

     

    53.字符串的排列。

    题目:输入一个字符串,打印出该字符串中字符的所有排列。

    例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串

    abc、acb、bac、bca、cab和cba。

     

    分析:这是一道很好的考查对递归理解的编程题,

    因此在过去一年中频繁出现在各大公司的面试、笔试题中。

     

     

     

    54.调整数组顺序使奇数位于偶数前面。

     

    题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,

     

    所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

     

     

     

     

    55.

     

    题目:类CMyString的声明如下:

    class CMyString

    {

    public:

          CMyString(char* pData = NULL);

          CMyString(const CMyString& str);

          ~CMyString(void);

          CMyString& operator = (const CMyString& str);

     

    private:

          char* m_pData;

    };

    请实现其赋值运算符的重载函数,要求异常安全,即当对一个对象进行赋值时发生异常,对象的状态不能改变。

     

     

     

    56.最长公共字串。

     

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,

     

    则字符串一称之为字符串二的子串。

     

    注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。

    请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

     

    例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,

    则输出它们的长度4,并打印任意一个子串。

     

    分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

     

    因此一些重视算法的公司像MicroStrategy都把它当作面试题。

     

     

     

     

    57.用俩个栈实现队列。

     

    题目:某队列的声明如下:

     

    template<typename T> class CQueue

    {

    public:

          CQueue() {}

          ~CQueue() {}

     

          void appendTail(const T& node); // append a element to tail

          void deleteHead();               // remove a element from head

     

    private:

         T> m_stack1;

         T> m_stack2;

    };

     

    分析:从上面的类的声明中,我们发现在队列中有两个栈。

    因此这道题实质上是要求我们用两个栈来实现一个队列。

    相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,

    因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,

    我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。

     

     

     

     

    58.从尾到头输出链表。

     

    题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:

    struct ListNode

    {

     

          int       m_nKey;

          ListNode* m_pNext;

    };

    分析:这是一道很有意思的面试题。

    该题以及它的变体经常出现在各大公司的面试、笔试题中。

     

     

     

     

    59.不能被继承的类。

    题目:用C++设计一个不能被继承的类。

     

    分析:这是Adobe公司2007年校园招聘的最新笔试题。

    这道题除了考察应聘者的C++基本功底外,还能考察反应能力,是一道很好的题目。

     

     

     

     

     

    60.在O(1)时间内删除链表结点。

     

    题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:

     

    struct ListNode

     

    {

     

          int        m_nKey;

     

          ListNode* m_pNext;

     

    };

     

    函数的声明如下:

    void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

     

    分析:这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,

     

    更重要的是,还能考察我们对时间复杂度的理解。

    -------------------------------------------------------------------------

     

     

     

    61.找出数组中两个只出现一次的数字

    题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。

    请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

     

    分析:这是一道很新颖的关于位运算的面试题。

     

     

     

     

    62.找出链表的第一个公共结点。

    题目:两个单向链表,找出它们的第一个公共结点。

     

    链表的结点定义为:

    struct ListNode

     

    {

     

          int         m_nKey;

     

          ListNode*   m_pNext;

     

    };

     

    分析:这是一道微软的面试题。微软非常喜欢与链表相关的题目,

    因此在微软的面试题中,链表出现的概率相当高。

     

     

     

     

    63.在字符串中删除特定的字符。

    题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.”和”aeiou”,

     

    则删除之后的第一个字符串变成”Thy r stdnts.”。

     

    分析:这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部分,

    因为写程序操作字符串能很好的反映我们的编程基本功。

     

     

     

     

    64. 寻找丑数。

    题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,

    但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。

    求按从小到大的顺序的第1500个丑数。

     

    分析:这是一道在网络上广为流传的面试题,据说google曾经采用过这道题。

     

     

     

     

    65.输出1到最大的N位数

    题目:输入数字n,按顺序输出从1最大的n位10进制数。比如输入3,

     

    则输出1、2、3一直到最大的3位数即999。

    分析:这是一道很有意思的题目。看起来很简单,其实里面却有不少的玄机。

     

     

     

    66.颠倒栈。

    题目:用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5},1在栈顶。

    颠倒之后的栈为{5, 4, 3, 2, 1},5处在栈顶。

     

     

     

     

    67.俩个闲玩娱乐。

     

    1.扑克牌的顺子

    从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。

    2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。

     

    2.n个骰子的点数。

    把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,

    打印出S的所有可能的值出现的概率。

    68.把数组排成最小的数。

    题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。

    例如输入数组{32, 321},则输出这两个能排成的最小数字32132。

    请给出解决问题的算法,并证明该算法。

     

    分析:这是09年6月份百度的一道面试题,

    从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

    69.旋转数组中的最小元素。

    题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,

     

    输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

     

        分析:这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,

    时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性,我们应该能找到更好的解法。

    70.给出一个函数来输出一个字符串的所有排列。

    ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法,去看看组合数学,

     

    还有逆序生成排列和一些不需要递归生成排列的方法。

    印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底,

    也需要一定的灵感,有兴趣最好看看。

     

    71.数值的整数次方。

     

    题目:实现函数double Power(double base, int exponent),求base的exponent次方。

    不需要考虑溢出。

     

    分析:这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码:

    double Power(double base, int exponent)

    {

     

          double result = 1.0;

          for(int i = 1; i <= exponent; ++i)

                result *= base;

          return result;

    }

    72.

    题目:设计一个类,我们只能生成该类的一个实例。

    分析:只能生成一个实例的类是实现了Singleton模式的类型。

    73.对策字符串的最大长度。

     

    题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。

    比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。

     

    分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的加强版。

     

    74.数组中超过出现次数超过一半的数字

     

    题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

     

    分析:这是一道广为流传的面试题,包括百度、微软和Google在内的多家公司都

    曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,

    除了较好的编程能力之外,还需要较快的反应和较强的逻辑思维能力。

     

    75.二叉树两个结点的最低共同父结点

    题目:二叉树的结点定义如下:

    struct TreeNode

    {

     

        int m_nvalue;

        TreeNode* m_pLeft;

        TreeNode* m_pRight;

    };

     

    输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。

    分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

    76.复杂链表的复制

     

    题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,

    还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:

     struct ComplexNode

    {

        int m_nValue;

        ComplexNode* m_pNext;

        ComplexNode* m_pSibling;

    };

    下图是一个含有5个结点的该类型复杂链表。

    图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,

    指向NULL的指针没有画出。                                

    请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。

     

    分析:在常见的数据结构上稍加变化,这是一种很新颖的面试题。

    要在不到一个小时的时间里解决这种类型的题目,我们需要较快的反应能力,

    对数据结构透彻的理解以及扎实的编程功底。

    77.关于链表问题的面试题目如下:

     

    1.给定单链表,检测是否有环。

     

     使用两个指针p1,p2从链表头开始遍历,p1每次前进一步,p2每次前进两步。如果p2到达链表尾部,

     

    说明无环,否则p1、p2必然会在某个时刻相遇(p1==p2),从而检测到链表中有环。

     

     

     

    2.给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。

     

            如果head1==head2,那么显然相交,直接返回head1。

     

    否则,分别从head1,head2开始遍历两个链表获得其长度len1与len2,假设len1>=len2,

    那么指针p1由head1开始向后移动len1-len2步,指针p2=head2,

    下面p1、p2每次向后前进一步并比较p1p2是否相等,如果相等即返回该结点,

    否则说明两个链表没有交点。

     

     

    3.给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。

            运用题一,我们可以检查链表中是否有环。

            如果有环,那么p1p2重合点p必然在环中。从p点断开环,

    方法为:p1=p, p2=p->next, p->next=NULL。此时,原单链表可以看作两条单链表,

    一条从head开始,另一条从p2开始,于是运用题二的方法,我们找到它们的第一个交点即为所求。

     

     

    4.只给定单链表中某个结点p(并非最后一个结点,即p->next!=NULL)指针,删除该结点。

     办法很简单,首先是放p中数据,然后将p->next的数据copy入p中,接下来删除p->next即可。

     

    5.只给定单链表中某个结点p(非空结点),在p前面插入一个结点。

      办法与前者类似,首先分配一个结点q,将q插入在p后,接下来将p中的数据copy入q中,

    然后再将要插入的数据记录在p中。

     

    78.链表和数组的区别在哪里?

     

    分析:主要在基本概念上的理解。

    但是最好能考虑的全面一点,现在公司招人的竞争可能就在细节上产生,

    谁比较仔细,谁获胜的机会就大。

    79.

    1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法?

    2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法?

    3.请编写能直接实现strstr()函数功能的代码。

    80.阿里巴巴一道笔试题

     

    问题描述:

    12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

    这个笔试题,很YD,因为把某个递归关系隐藏得很深。

    欢迎关注技术公众号:架构师成长营

     

    展开全文
  • 优胜美地 数据结构与算法面试题 这是最初的测试消息。
  • 24-数据结构与算法面试题(21题).pdf
  • JAVA数据结构算法+面试题

    热门讨论 2011-12-19 22:36:17
    有JAVA数据结构算法的教程 还有算法题 加部分面试题 从别人那下的 在这一次给了 希望能帮到大家
  • 下述是我收录整理的Android面试题汇总,由于篇幅原因,在这只把数据结构与算法的题目列举出来,这是同系列的最后一小节了,后续我会把所有面试题内容整合到一起来发一篇《史上最全的Android面试题集...

    前言

    很多人面试之前,可能没有在互联网公司工作过或者说工作过但年头较短,不知道互联网公司技术面试都会问哪些问题? 再加上可能自己准备也不充分,去面试没几个回合就被面试官几个问题打蒙了,最后以惨败收场。

    下述是我收录整理的Android面试题汇总,由于篇幅原因,在这只把数据结构与算法的题目列举出来,这是同系列的最后一小节了,后续我会把所有面试题内容整合到一起来发一篇《史上最全的Android面试题集锦》,大家可以关注一下我,及时知晓我的更新,同时这份面试集锦的整理也花费了我很多时间,有需要的朋友可以帮忙转发分享下,点个赞~

    数据结构与算法

    1、排序

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    1.1、 直接插入排序

    思想:

    将第一个数和第二个数排序,然后构成一个有序序列 将第三个数插入进去,构成一个新的有序序列。 对第四个数、第五个数……直到最后一个数,重复第二步。 代码:

    首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入。 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。

    2、设计模式

    2.1、单例设计模式

    单例主要分为:懒汉式单例、饿汉式单例、登记式单例。

    特点:

    1. 单例类只有一个实例
    2. 单例类必须自己创建自己的唯一实例
    3. 单例类必须给所有其他对象提供这一实例。

    在计算机系统中,像线程池,缓存、日志对象、对话框、打印机等常被设计成单例。

    懒汉式单例:

    Singleton通过将构造方法限定为private避免了类在外部被实例化,在同一个虚拟机范围内,Singleton的唯一实例只能通过getInstance()方法访问。(事实上,通过Java反射机制是能够实例化构造方法为private的类的,那基本上会使所有的Java单例实现失效。

    它是线程不安全的,并发情况下很有可能出现多个Singleton实例,要实现线程安全,有以下三种方式:

    1.在getInstance方法上加上同步

    2.双重检查锁定

    3.静态内部类

    这种方式对比前两种,既实现了线程安全,又避免了同步带来的性能影响。

    饿汉式单例:

    饿汉式在创建类的同时就已经创建好了一个静态的对象供系统使用,以后不再改变,所以天生是系统安全。

    以上就是Android数据结构与算法的面试题目,后续还会更新更多面试题内容,大家可以关注一下我,及时知晓我的更新,同时这份面试集锦的整理也花费了我很多时间,有需要的朋友可以帮忙转发分享下,点个赞~

    Android架构师之路很漫长,一起共勉吧!

    展开全文
  • 前端数据结构算法面试题题目

    千次阅读 2020-08-12 17:29:44
    分治算法 一行代码实现判断回文字符串 堆排序 跳楼梯(一次一步或者两步 有多少种方法) top K(找数里面第k大的数) email正则匹配,url正则匹配(二面和三面都写了一遍) 如何最高效率的对数组中的数字去重,...
    1. 二分查找
      二叉树的插入
      手写快排(复杂度)
      分治算法
      一行代码实现判断回文字符串
      堆排序
      跳楼梯(一次一步或者两步 有多少种方法)
      top K(找数里面第k大的数)
      email正则匹配,url正则匹配(二面和三面都写了一遍)
      如何最高效率的对数组中的数字去重,复杂度是多少?
      如果数组中包含数字和字符串这个时候又应该怎么去重,复杂度是多少?
      链表反转,不申请额外空间
      二叉树的前中后序遍历,已知前中序,求原有的二叉树
      写程序为什么有逻辑地址,和物理地址
      奇数增,偶数减的链表排序
      二叉树取从左边看到的节点
      链表倒数第k个节点
      判断字符串匹配,s和p包括?匹配任意一个 *匹配任意多个
      有序数组的合并
      硬币问题
      二叉树找和为某个值的所有路径
      各类排序算法介绍,冒泡,快排,堆排,以及相应的算法复杂度
      介绍基本的数据结构及其应用,队列,栈,堆。函数的执行栈和堆内存
      实现队列函数(先进先出),以实现一次100秒后打印出1,200秒后打印2,300秒后打印3这样
      实现类似于模板字符串的功能
      广度搜索
      把一个矩形分成同样大小的正方形,最大边长是多少

       

    展开全文
  • 本文将收录《剑指offer:50道金典面试题》、LeetCode上部分经典题目以及其他【据结构算法】数面试题。 PS:持续更新中,敬请期待~~ 正    文 一、剑指offer:50道金典面试题 ...

    文章目录


    前    言

    本文将收录《剑指offer:50道金典面试题》、LeetCode上部分经典题目以及其他【据结构和算法】数面试题。

    PS:目录中有粉红色标注的题目是已经附带答案


    正    文

    一、剑指offer:50道金典面试题

    面试题1:赋值运算符函数

    在这里插入图片描述

    class CMyString
    {
    public:
    	CMyString(char* pData = NULL);
    	CMyString(const CMyString& str);
    	~CMyString(void);
    
    private:
    	char* m_pData;
    }
    

    \qquad

    解题思路
    java只能重载“+”和“+=”两个运算符,别的都不可以。

    面试题2:实现单例模式

    在这里插入图片描述
    \qquad

    解法一:饿汉式(线程安全,效率高,不能延时加载,典型的以空间换时间)
    public class Singleton {
    	private static Singleton instance = new Singleton();
     
    	// 私有化构造方法
    	private Singleton() {
     
    	}
     
    	public static Singleton getInstance() {
    		return instance;
    	}
     
    }
    

    饿汉式是典型的空间换时间,当类装载的时候就会创建类实例,不管你用不用,先创建出来,然后每次调用的时候,就不需要判断了,节省了运行时间。

    \qquad

    解法二:懒汉式(线程不安全,能延时加载,以时间换空间)
    public class Singleton {
    	//2.本类内部创建对象实例
    	private static Singleton instance = null;
     
    	/**
    	* 1.构造方法私有化,外部不能new
    	*/
    	private Singleton() {
     
    	}
     
    	//3.提供一个公有的静态方法,返回实例对象
    	public static Singleton getInstance() {
    		if (instance == null) {
    			instance = new Singleton();
    		}
    		return instance;
    	}
    }
    

    调用顺序时序图:
    在这里插入图片描述
    单例模式的懒汉式体现了缓存的思想,延时加载就是一开始不要加载资源或者数据,一直 等,等到马上就要使用这个资源的或者数据了,躲不过去了才去加载。

    懒汉式是定性的时间换空间,不加同步的懒汉式是线程不安全的,如下示例:
    在这里插入图片描述
    那么如何解决这个问题呢?
    就是接下来我们要讲的解法三——使用双重检查加锁机制实现单例模式

    \qquad

    解法三:Double CheckLock实现单例(线程安全,能延时加载,以时间换空间)——面试官期待的解法之一
    public class Singleton {
    	private volatile static Singleton instance = null;
     
    	// 私有化构造方法
    	private Singleton() {
     
    	}
     
    	public static Singleton getInstance() {
    		if (instance == null) {
    			synchronized (Singleton.class) {
    				if (instance == null) {
    					instance = new Singleton();
    				}
    			}
     
    		}
    		return instance;
    	}
    	
    }
    

    \qquad

    解法四:静态内部类实现(线程安全,效率高,可延时加载)——面试官期待的解法之一
    public class Singleton {
    	private static class SingletonHoler {
    		/**
    		 * 静态初始化器,由JVM来保证线程安全
    		 */
    		private static Singleton instance = new Singleton();
    	}
     
    	private Singleton() {
    	}
     
    	public static Singleton getInstance() {
    		return SingletonHoler.instance;
    	}
     
    }
    

    \qquad

    解法五:枚举类(线程安全,效率高,不能延时加载,可以天然的防止反射和反序列化调用)
    public enum Singleton {
    	uniqueInstance;// 定义一个枚举的元素,它 就代表了Singleton的一个实例
     
    	public void singletonOperation() {
    		// 功能处理
    		System.err.println("功能处理");
    	}
     
    }
    

    \qquad

    扩展阅读

    java 单例模式的几种实现方式(包含防止单例模式被破坏的解决方案)


    面试题3:二维数组中的查找

    在这里插入图片描述

    解题思路

    别从左到右一个一个比,先比右上角的或左下角的,如果要找的数比这个数小,剔除这一列,比较前一列的第一个数。如果大,剔除这一行,再比较该列下一个数。

    注意:如果先比左上角或右下角的是不行的。

    代码实现
    import java.util.Scanner;
     
    public class Find{
    	public static void main(String[] args){
    		int[][] array = input();
    		if(array != null){
    			System.out.println("请输入要找的数:");
    			Scanner sc = new Scanner(System.in);
    			int target = sc.nextInt();	
    			if(find(array,target) == true){
    				System.out.println("找到了!");
    			}else{
    				System.out.println("没找到!");
    			}
    		}
     
    	}
    	static int[][] input(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请输入二维数组行数:");
    		int rowNumber = sc.nextInt();
    		System.out.println("请输入二维数组列数:");
    		int colNumber = sc.nextInt();
    		int[][] array = new int[rowNumber][colNumber];
    		if(rowNumber != 0 && colNumber != 0){
    			for(int i=0;i<rowNumber;i++){
    				System.out.println("请输入第"+(i+1)+"行的"+(colNumber)+"个数。");
    				for(int j=0;j<colNumber;j++){
    					array[i][j] = sc.nextInt();
    				}
    			}
    			return array;
    		}else {
    			System.out.println("输入有误!数组为空!");
    			return null;
    		}
    	}
    	static boolean find(int[][] array,int target){
    		int row = 0;
    		int col = array[0].length-1;
    		while(row<array.length && col>=0){
    			if(array[row][col] == target){
    				return true;
    			}
    			else if(array[row][col] > target){
    				col--;
    			}else{
    				row++;
    			}
    		}
    		return false;
    	}
    }
    

    面试题4:替换空格

    在这里插入图片描述


    面试题5:反向打印链表

    在这里插入图片描述


    面试题6:重建二叉树

    在这里插入图片描述


    面试题7:用两个栈实现队列(附带用两个队列实现栈)

    在这里插入图片描述
    \qquad

    解题思路
    添加元素即压入一个栈s1,删除元素的话,把s1中的元素按顺序先弹出再压入栈s2中,这是弹出栈s2的元素就能实现先进先出了。

    \qquad

    代码实现
    public class CQueue {
    	private Stack<Integer> stack1 = new Stack<>();
    	private Stack<Integer> stack2 = new Stack<>();
    	
    	public void appendTail(int elem){
    		//添加元素就直接向stack1添加
    		stack1.push(elem);
    		System.out.println("stack1:" + stack1.toString());
    	}
    	public void deleteHead(){
    		//删除分三种情况:1,stack2不空,直接从它里头弹出。2,stack2空,stack1不空,把1中先弹再压到2,再从2弹出。3,两都空。
    		if(!stack2.isEmpty()){
    			stack2.pop();
    		}else if(!stack1.isEmpty()){
    			while(!stack1.isEmpty()){
    				stack2.push(stack1.pop());
    			}
    			stack2.pop();
    		}else{
    			System.out.println("两个栈都空了");
    		}
    		System.out.println("stack1:" + stack1.toString());
    		System.out.println("stack2:" + stack2.toString());
    	}
    	public static void main(String[] args) {
    		CQueue test = new CQueue();
    		test.appendTail(1);
    		test.appendTail(2);
    		test.appendTail(3);
    		test.deleteHead();
    		test.deleteHead();
    		test.appendTail(4);
    		test.deleteHead();
    	}
    }
    

    \qquad

    相关题:用两个队列实现栈

    \qquad

    解题思路
    添加元素即向一个队列q1添加元素,删除元素的话,把q1的元素按顺序出队然后入队到q2,最后q1剩下一个元素,就是要出栈的元素,再添加元素的话,向非空的队列添加。

    \qquad

    代码实现
    import java.util.Queue;
    import java.util.LinkedList;
     
    //以下是相关题,两个队列实现栈。
    public class CStack {
    	//是LinkedList类实现了Queue接口
    	private static Queue<Integer> queue1 = new LinkedList<>();
    	private static Queue<Integer> queue2 = new LinkedList<>();
    	
    	private void appendTail(int elem){
    		//Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。
    		//它们的优点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。 
    		//如果要使用前端而不移出该元素,使用element()或者peek()方法。
    		//这里是向非空的队列里添加值。都为空的话向队列1添加。
    		if(!queue2.isEmpty()){
    			queue2.offer(elem);
    		}else{
    			queue1.offer(elem);
    		}
    		System.out.println("queue1:" + queue1.toString());
    		System.out.println("queue2:" + queue2.toString());
    	}
    	private void deleteHead(){
    		//一个表示空队列,一个表示非空队列
    		Queue<Integer> emptyQueue = queue1;
    		Queue<Integer> notEmptyQueue = queue2;
    		if(!emptyQueue.isEmpty()){
    			emptyQueue = queue2;
    			notEmptyQueue = queue1;
    		}
    		//除了非空队列的最后一个元素,别的都按顺序移到空队列
    		while(notEmptyQueue.size()!=1){
    			emptyQueue.offer(notEmptyQueue.poll());
    		}
    		//删除刚才留下的最后一个元素
    		notEmptyQueue.poll();
    		
    		System.out.println("queue1:" + queue1.toString());
    		System.out.println("queue2:" + queue2.toString());
    	}
     
    	public static void main(String[] args) {
    		CStack test = new CStack();
    		test.appendTail(1);
    		test.appendTail(2);
    		test.appendTail(3);
    		test.deleteHead();
    		test.appendTail(4);
    		test.deleteHead();
    	}
    }
    

    面试题8:旋转数组的最小数字

    在这里插入图片描述


    \qquad

    面试题9:斐波那契数列

    在这里插入图片描述
    \qquad

    被面试官鄙视的解法
    public class Fibonacci {
        /**
         * 递归实现
         */
        public static long fib_rec(int n){
            int[] arr = {0,1};
            if(n <= 2){
                return arr[n-1];
            }
            return fib_rec(n-1)+fib_rec(n-2);
        }
    }
    

    \qquad

    面试官期待的解法
    public class Fibonacci {
         /**
         * 数组+for循环实现(其实就是 动态规划 思想)
         */
        public static long fib_for(int n){
            int[] arr = {0,1};
            if(n < 2){
               return arr[n];
            }
            long first,sencond,res;
            first=0;
            sencond=1;
            res=0;
            for (int i=2;i<n;i++){
                res = first + sencond;
                first = sencond;
                sencond = res;
            }
            return res;
        }
    }
    

    \qquad
    在这里插入图片描述

    这个题目可以使用动态规划来求解,可以参考我的 动态规划? so easy!!!
    这篇文章里的 【题目实战】中的 【爬楼梯】的例子。


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

    在这里插入图片描述


    面试题11:数值的整数次方

    在这里插入图片描述


    面试题12:打印 1 到最大的 n 位数

    在这里插入图片描述


    面试题13:在O(1)时间删除链表结点

    在这里插入图片描述


    面试题14:调整数组顺序使数组中奇数位于偶数前

    在这里插入图片描述


    面试题15:链表中倒数第K个结点

    在这里插入图片描述


    面试题16:反转链表

    在这里插入图片描述


    面试题17:合并两个排序的链表

    在这里插入图片描述
    在这里插入图片描述


    面试题18:树的子结构

    在这里插入图片描述


    面试题19:二叉树的镜像

    在这里插入图片描述


    面试题20:顺时针打印矩阵

    在这里插入图片描述
    在这里插入图片描述


    面试题21:包含 min 函数的栈

    在这里插入图片描述


    面试题22:栈的压人、弹出序列

    在这里插入图片描述


    面试题23:从上往下打印二叉树

    在这里插入图片描述


    面试题24:二叉搜索树的后序遍历序列

    在这里插入图片描述


    面试题25:二叉树中和为某一值的路径

    在这里插入图片描述


    面试题26:复杂链表的复制

    在这里插入图片描述


    面试题27:二叉搜索树和双向链表

    在这里插入图片描述


    面试题28:字符串的排序

    在这里插入图片描述


    面试题29:数组中出现次数超过一半的数字

    在这里插入图片描述


    面试题30:最小的 k 个数

    在这里插入图片描述


    面试题31:连续子数组的最大和(动态规划思想)

    在这里插入图片描述
    这个题目可以使用动态规划来求解,可以参考我的 动态规划? so easy!!!
    这篇文章里的 【题目实战】中的 【最大子序和】的例子。


    面试题32:从1到n整数中1出现的次数

    在这里插入图片描述


    面试题33:把数组排成最小的数

    在这里插入图片描述


    面试题34:丑数

    在这里插入图片描述


    面试题35:第一个只出现一次的字符

    在这里插入图片描述


    面试题36:数组中的逆序对

    在这里插入图片描述


    面试题37:两个链表的第一个公共节点

    在这里插入图片描述


    面试题38:数字在排序数组中出现的次数

    在这里插入图片描述


    面试题39:二叉树的深度

    在这里插入图片描述


    面试题40:数组中只出现一次的数字

    在这里插入图片描述


    面试题41:和为s的两个数字与和为s的连续正数序列

    在这里插入图片描述

    在这里插入图片描述


    面试题42:翻转单词顺序与左旋转字符串

    在这里插入图片描述
    在这里插入图片描述


    面试题43:n个骰子的点数(动态规划)

    在这里插入图片描述


    面试题44:扑克牌的顺子

    在这里插入图片描述


    面试题45:圆圈中最后剩下的数字(约瑟夫环问题)

    在这里插入图片描述


    面试题46:求1+2+…+n

    在这里插入图片描述


    面试题47:不用加减乘除做加法(位运算)

    在这里插入图片描述


    面试题48:设计一个不能被继承的类(final修饰 )


    面试题49:字符串转整数


    面试题50:二叉树两个结点的最低公共祖先


    二、LeetCode上经典题目

    三、其他面试题(理论知识)

    1.说说常见的集合有哪些。

    Map 接口和Collection 接口是所有集合类框架的父接口:
    Collcetion 接口的子接口包括:Set 接口和List 接口。
    Map 接口的实现类主要有:HashMap、HashTable、ConcurrentHashMap 以及Properties
    等。
    Set 接口的实现类主要有:HashSet、TreeSet、LinkedHashSet 等。
    List 接口的实现类主要有:ArrayList、LinkedList、Stack 以及 Vector 等。

    2. HashMap 与 HashTable 的区别。

    主要有以下几点区别。
    HashMap 没有考虑同步,是线程不安全的;HashTable 在关键方法(put、get、contains、
    size 等)上使用了Synchronized 关键字,是线程安全的。
    HashMap 允许Key/Value 都为null,后者Key/Value 都不允许为null。
    HashMap 继承自AbstractMap 类;而HashTable 继承自Dictionary 类。
    在jdk1.8 中,HashMap 的底层结构是数组+链表+红黑树,而HashTable 的底层结构是
    数组+链表。
    HashMap 对底层数组采取的懒加载,即当执行第一次put 操作时才会创建数组;而
    HashTable 在初始化时就创建了数组。
    HashMap 中数组的默认初始容量是 16 ,并且必须是 2 的指数倍数,扩容时
    newCapacity=2oldCapacity;而HashTable 中默认的初始容量是11,并且不要求必须是2 的
    指数倍数,扩容时newCapacity=2
    oldCapacity+1。 在hash 取模计算时,HashTable 的模数一般为素数,简单的做除取模结果会更为均匀,
    int index = (hash & 0x7FFFFFFF) % tab.length;
    HashMap 的模数为2 的幂,直接用位运算来得到结果,效率要大大高于做除法,i = (n - 1) & hash。

    3. HashMap 是怎么解决哈希冲突的

    哈希冲突:当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们
    就把它叫做哈希碰撞。
    在Java 中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址
    容易,插入和删除困难。链表的特点是:寻址困难,但插入和删除容易。所以我们将数组和
    链表结合在一起,发挥两者的优势,使用一种叫做链地址法的方式来解决哈希冲突。这样我
    们就可以拥有相同哈希值的对象组织成的一个链表放在hash 值对应的bucket 下,但相比
    Key.hashCode() 返回的 int 类型,我们 HashMap 初始的容量大小
    DEFAULT_INITIAL_CAPACITY = 1 << 4(即2 的四次方为16)要远小于int 类型的范围,所
    以我们如果只是单纯的使用hashcode 取余来获取对应位置的bucket,这将会大大增加哈希
    碰撞的几率,并且最坏情况下还会将HashMap 变成一个单链表。所以肯定要对hashCode 做
    一定优化。
    来看HashMap 的hash()函数。上面提到的问题,主要是因为如果使用hashCode 取余,
    那么相当于参与运算的只有hashCode 的低位,高位是没有起到任何作用的,所以我们的思
    路就是让**hashCode 取值出的高位也参与运算,进一步降低hash 碰撞的概率,使得数据分
    布更平均,我们把这样的操作称为扰动,在JDK 1.8 中的hash()函数相比在JDK 1.7 中的4 次
    位运算,5 次异或运算(9 次扰动),在1.8 中,只进行了1 次位运算和1 次异或运算(2 次
    扰动),更为简洁了。两次扰动已经达到了高低位同时参与运算的目的,提高了对应数组存
    储下标位置的随机性和均匀性。
    通过上面的链地址法(使用散列表)和扰动函数,数据分布更为均匀,哈希碰撞也减少
    了。但是当HashMap 中存在大量的数据时,假如某个bucket 下对应的链表中有n 个元素,
    那么遍历时间复杂度就变成了O(n),针对这个问题,JDK 1.8 在HashMap 中新增了红黑树的
    数据结构,进一步使得遍历复杂度降低至O(logn)。
    简单总结一下HashMap 是如何有效解决哈希碰撞的:
    使用链地址法(散列表)来链接拥有相同hash 值的元素;
    使用2 次扰动(hash 函数)来降低哈希冲突的概率,使得概率分布更为均匀;
    引入红黑树进一步降低遍历的时间复杂度。

    4. HashMap 中为什么数组长度要保证 2 的幂次方。

    只有当数组长度为 2 的幂次方时,h&(length-1)才等价于 h%length,可以用位运算来
    代替做除取模运算,实现了 key 的定位,2 的幂次方也可以减少冲突次数,提高 HashMap 的
    查询效率;
    当然,HashTable 就没有采用 2 的幂作为数组长度,而是采用素数。素数的话是用简
    单做除取模方法来获取下标 index,而不是位运算,效率低了不少,但分布也很均匀。

    5.什么是 Java 集合的快速失败机制“fail-fast”, 以及安全失败“fail-safe”。

    “fail-fast”是Java 集合的一种错误检测机制,当多个线程对集合进行结构上的改变
    的操作时,有可能会产生fail-fast 机制。
    例如:假设存在两个线程(线程1、线程2),线程1 通过Iterator 在遍历集合A 中的
    元素,在某个时候线程2 修改了集合A 的结构(是结构上面的修改,而不是简单的修改集合
    元素的内容),那么这个时候程序就会抛出ConcurrentModificationException 异常,从而
    产生fail-fast 机制。
    原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount 变
    量。集合在被遍历期间如果内容发生变化,就会改变odCount的值。每当迭代器使用
    hashNext()/next()遍历下一个元素之前,都会检测modCount 变量是否为expectedmodCount
    值,是的话就返回遍历;否则抛出异常ConcurrentModification,终止遍历。
    Java.util 包下的集合类都是快速失败机制,不能在多线程下发生并修改(迭代
    过程中被修改)。
    与“fail-fast”对应的是“fail-safe”。
    采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先copy 原
    有集合内容,在拷贝的集合上进行遍历。由于迭代时是对原集合的拷贝的值进行遍历,所以在
    遍历过程中对原集合所作的修改并不能被迭代器检测到 , 所以不会触发
    ConcurrentModificationException 异常。
    基于拷贝内容的迭代虽然避免了ConcurrentModificationException 异常,但同样地,
    迭代器并不能访问到修改后的内容,简单来说,迭代器遍历的是开始遍历那一刻拿到的集合
    拷贝,在遍历期间原集合发生的修改迭代器行为是不知道的。
    Java.util.concurrent 包下的容器都是安全失败的,可以在多线程下并发使用,并发修
    改。

    6. ArrayList 和 LinkedList 的区别。

    主要有以下几点区别:
    LinkedList 实现了List 和Deque 接口,一般称为双向链表;ArrayList 实现了List 接
    口,是动态数组。
    LinkedList 在插入和删除数据时效率更高,ArrayList 在查找某个index的数据时效率
    更高。
    LinkedList 比ArrayList 需要更多内存。

    7. HashSet 是如何保证数据不可重复的。

    HashSet 的底层其实就是HashMap,只不过HashSet 是实现了Set 接口,并且把数据作
    为Key 值,而Value 值一直使用一个相同的虚值来保存。由于ashMap 的K 值本身就不允许
    重复,并且在HashMap 中如果K/V 相同时,会用新的V 覆盖掉旧的V,然后返回旧的V,那么
    在HashSet 中执行这一句话始终会返回一个false,导致插入失败,这样就保证了数据的不
    可重复性。

    8. BlockingQueue 是什么。

    Java.util.concurrent.BlockingQueue 是一个队列,在进行检索或移除一个元素的时
    候,它会等待队列变为非空;当添加一个元素时,它会等待队列中的可用空间。BlockingQueue
    接口是Java 集合框架的一部分,主要用于实现生产者-消费者模式。这样我们就不需要担心
    等待生产者有可用的空间,以及消费者有可用的对象。因为它们都在BlockingQueue 的实现
    类中被处理了。
    Java 提供了几种 BlockingQueue 的实现,比如 ArrayBlockingQueue 、
    LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue 等。

    9. JDK8 中 HashMap 为什么选用红黑树而不是 AVL 树

    在平常我们用HashMap的时候,HashMap里面存储的key是具有良好的hash算法的key(比
    如String、Integer等包装类),冲突几率自然微乎其微,此时链表几乎不会转化为红黑树,
    但是当key为我们自定义的对象时,我们可能采用了不好的hash算法,使HashMap中key的冲
    突率极高,但是这时HashMap为了保证高速的查找效率,引入了红黑树来优化查询了。
    因为从时间复杂度来说,链表的查询复杂度为o(n);而红黑树的复杂度能达到o(logn);
    比如若hash算法写的不好,一个桶中冲突1024个key,使用链表平均需要查询512次,但是红
    黑树仅仅10次,红黑树的引入保证了在大量hash冲突的情况下,HashMap还具有良好的查询
    性能。
    红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于
    插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的
    不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡
    有时候代价较大,所以效率不如红黑树。

    10. JDK8 中 HashMap 链表转红黑树的阈值为什么选 8?

    HashMap 在jdk1.8 之后引入了红黑树的概念,表示若桶中链表元素超过8 时,会自动
    转化成红黑树;若桶中元素小于等于6 时,树结构还原成链表形式。
    HashMap源码作者通过泊松分布算出,当桶中结点个数为8时,出现的几率是亿分之6的,
    因此常见的情况是桶中个数小于8的情况,此时链表的查询性能和红黑树相差不多,因为红黑
    树的平均查找长度是log(n),长度为8 的时候,平均查找长度为3,如果继续使用链表,平
    均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速
    度也很快的,但是转化为树结构和生成树的时间并不会太短。
    亿分之6这个几乎不可能的概率是建立在良好的hash算法情况下,例如String,Integer
    等包装类的hash算法,如果一旦发生桶中元素大于8,说明是不正常情况,可能采用了冲突
    较大的hash算法,此时桶中个数出现超过8的概率是非常大的,可能有n个key冲突在同一个
    桶中,这个时候就必要引入红黑树了。
    另外,上下阈值选择6 和8 的情况下,中间有个差值7 可以防止链表和树之间频繁的转
    换。假设一下,如果设计成链表个数超过8 则链表转换成树结构,链表个数小于8 则树结构
    转换成链表,如果一个HashMap 不停的插入、删除元素,链表个数在8 左右徘徊,就会频繁
    的发生树转链表、链表转树,效率会很低。

    11. 说下几种常见的排序算法及其复杂度

    a. 快速排序:
    i. 原理:快速排序采⽤用的是⼀种分治的思想,它先找⼀个基准数(⼀般选择第⼀个值),
    然后将⽐这个基准数⼩的数字都放到它的左边,然后再递归调⽤,分别对左右两边快速排序,
    直到每⼀边只有⼀个数字.整个排序就完成了.
    1.选定⼀个合适的值(理想情况中值最好,但实现中⼀般使⽤用数组第⼀个值),称为
    “枢轴”(pivot)。
    2.基于这个值,将数组分为两部分,较⼩的分在左边,较⼤的分在右边。
    3.可以肯定,如此⼀轮下来,这个枢轴的位置⼀定在最终位置上。
    4.对两个⼦数组分别重复上述过程,直到每个数组只有⼀个元素。
    5.排序完成。
    ii. 复杂度:O(n)
    b. 冒泡排序:
    i. 原理:冒泡排序其实就是逐⼀⽐较交换,进⾏⾥外两次循环,外层循环为遍历所有数
    字,逐个确定每个位置,⾥层循环为确定了了位置后,遍历所有后面没有确定位置的数字,与
    该位置的数字进⾏⽐较,只要⽐该位置的数字⼩,就和该位置的
    数字进⾏交换.
    ii. 复杂度:O(n^2),最佳时间复杂度为O(n)
    c. 直接插⼊入排序:
    i. 原理:直接插⼊入排序是将从第⼆个数字开始,逐个拿出来,插⼊到之前排好序的数
    列列⾥.
    ii. 复杂度:O(n^2),最佳时间复杂度为O(n)
    d. 直接选择排序:
    i. 原理:直接选择排序是从第⼀个位置开始遍历位置,找到剩余未排序的数据⾥里里最 ⼩的,找到最⼩的后,再做交换。
    ii. 复杂度:O(n^2)

    12. Hashmap 什么时候进行扩容呢?

    当 hashmap 中的元素个数超过数组大小 loadFactor 时,就会进行数组扩容,
    loadFactor 的默认值为 0.75,也就是说,默认情况下,数组大小为 16,那么当 hashmap 中
    元素个数超过 160.75=12 的时候,就把数组的大小扩展为 216=32,即扩大一倍,然后重新
    计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知
    hashmap 中元素的个数,那么预设元素的个数能够有效的提高 hashmap 的性能。
    比如说,我们有 1000 个元素 new HashMap(1000), 但是理论上来讲 new HashMap(1024)
    更合适,不过上面已经说过,即使是 1000,hashmap 也自动会将其设置为 1024。 但是 new
    HashMap(1024) 还不是更合适的,因为 0.75*1000 < 1000, 也就是说为了让 0.75 * size >
    1000, 我们必须这样 new HashMap(2048) 才最合适,既考虑了 & 的问题,也避免了 resize
    的问题。

    13. HashSet 和 TreeSet 有什么区别?

    HashSet 是由一个 hash 表来实现的,因此,它的元素是无序的。
    TreeSet 是由一个树形的结构来实现的,它里面的元素是有序的。

    14. LinkedHashMap 的实现原理?

    LinkedHashMap 也是基于 HashMap 实现的,不同的是它定义了一个 Entry header,这
    个 header 不是放在 Table 里,它是额外独立出来的。
    LinkedHashMap 通过继承 hashMap 中 的 Entry, 并添加两个属性 Entry
    before,after, 和 header 结合起来组成一个双向链表,来实现按插入顺序或访问顺序排
    序。LinkedHashMap 定义了排序模式 accessOrder,该属性为 boolean 型变量,对于访问
    顺序,为 true;对于插入顺序,则为 false。一般情况下,不必指定排序模式,其迭代顺
    序即为默认为插入顺序。

    15. 什么是迭代器 (Iterator)?

    Iterator 接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返
    回迭代 器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素, 但是不可以
    直接调用集合的 remove(Object Obj) 删除,可以通过迭代器的 remove() 方法删除。

    16. Iterator 和 ListIterator 的区别是什么?

    下面列出了他们的区别:
    Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍历 List。
    Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后向。
    ListIterator 实现了 Iterator 接口,并包含其他的功能,比如:增加元素,替换元
    素,获取前一个和后一个元素的索引,等等。

    17. Collection 和 Collections 的区别。

    collection 是集合类的上级接口, 继承与它的接口主要是 set 和 list。
    collections 类是针对集合类的一个帮助类. 它提供一系列的静态方法对各种集合的
    搜索, 排序, 线程安全化等操作。

    \qquad

    总    结

    本文主要汇总了《剑指offer》50道金典面试题,及部分LeetCode上经典题目。

    PS 答案还在整理中,敬请期待~~

    展开全文
  • 数据结构算法常见面试题大全

    千次阅读 多人点赞 2020-12-07 15:29:16
    截止到目前(2020年12月7日)我公众号“数据结构算法”已经推送了快500道算法题,目前部分已经整理成了pdf格式,上传到百度网盘上了,大家可以下载,文档的部分截图如下 链接:...
  • JavaScript版数据结构与算法 轻松解决前端算法面试视频教程,完整版15章!从求职角度,在面试前建立自己的算法技术体系。本课程带你用JS语言解决LeetCode上的经典算法,对每一道都进行线上测试,每都有时间/...
  • 数据结构与算法三十,弄懂这些面试就够了!

    万次阅读 多人点赞 2019-02-01 08:30:28
    堆栈类似,队列是另一种线性数据结构,以顺序方式存储元素。堆栈和队列之间唯一的显着区别是,队列不是使用 LIFO 方法,而是应用 FIFO 方法,这是 First in First Out(先入先出)的缩写。 队列的完美现实例子...
  • 面试中常见的数据结构与算法题

    千次阅读 2020-09-11 12:00:00
    关注、星标公众号,不错过精彩内容来源:极客大学堂最近一个读者和我反馈,他坚持刷题2个月,终于去了他梦寐以求的大厂,薪资涨幅非常可观,期间面试某大厂还遇到了原...并表示目前国内的大厂和...
  • Java 数据结构 算法 Linux 题目 网络通信 tcp/ip 协议 各种小问题
  • 微软数据结构与算法,看到该文件的网友有福了,哈哈!
  • java面试常用的数据结构与算法,数组、集合、散列表、栈、队列、链表、二叉树
  • 主要介绍了Java常见数据结构面试题,带有答案及解释,希望对广大的程序爱好者有所帮助,同时祝大家有一个好成绩,需要的朋友可以参考下。
  • Java面试题 - 数据结构与算法

    千次阅读 2020-05-28 17:42:38
    1. 说⼀下⼏种常⻅的排序算法和分别的复杂度 【快速排序】 原理:快速排序采⽤的是⼀种分治的思想,它先找⼀个基准数(⼀般选择第⼀个值),然后将⽐这个基准数⼩的数字都放到它的左边,然后再递归调⽤,分别对左右两边...
  • 静态代理、JDK动态代理以及CGLIB动态代理静态代理动态代理cglib代理单例模式工厂模式观察者模式装饰器模式秒杀系统设计分布式分布式概述分布式集群微服务多线程高并发分布式系统设计理念分布式系统的目标要素...
  • 微软等数据结构+算法面试100全部答案集锦 全面剖析
  • 数据结构与算法精选面试50(附答案)

    万次阅读 多人点赞 2019-07-03 21:41:52
    数组是最基本的数据结构,它将元素存储在一个连续的内存位置。这也是面试官们热衷的话题之一,在任何一次编程面试中,你都会听到很多关于数组的问题,比如将数组中元素位置颠倒,对数组进行排序,或者搜索数组上的...
  • 【BAT必备】数据结构算法面试题【BAT必备】数据结构算法面试题【BAT必备】数据结构算法面试题【BAT必备】数据结构算法面试题【BAT必备】数据结构算法面试题【BAT必备】数据结构算法面试题【BAT必备】数据结构算法...
  • 0. 数据结构定义 堆栈:list 原生即可支持堆栈操作: list.append():入栈; list.pop():出栈; not list:堆栈是否为空; 链表节点: class ListNode(object): def __init__(self, x): ...
  • BAT面试题BlockOC底层Runtime数据安全及加密数据结构与算法网络相关面试题资料合集: Animation面试题.pdf BAT面试题.zip Block面试题.pdf OC底层面试题.pdf Runloop面试题.pdf Runtime面试题.pdf UI相关面试题.pdf ...
  • 面试中常见的数据结构与算法

    万次阅读 多人点赞 2018-04-09 15:53:58
    2.1 O(n2) 算法 给定一数组,其大小为8个元素,数组内的数据无序。 6 3 5 7 0 4 1 2 冒泡排序:两两比较,将两者较少的升上去,第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1 public class bubbleSort { ...
  • 网上搜集的一个c++数据结构与算法的文档,包含各类数据结构算法、大量数据处理等方法,然后我还增加了那些是笔试面试中重点需要看的。希望能帮助到找工作的同学。另外可以从我的资源中下载c++基础知识的文档。
  • 题目来源“数据结构与算法面试题80道”。这是第一部分,包含其中的第1题到第5题。 在此给出我的解法,如你有更好的解法,欢迎留言。 问题分析:二叉查找树是一种二叉树的结构,其中,根节点的值大于左子树的值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,502
精华内容 51,000
关键字:

数据结构与算法面试题

数据结构 订阅