2023年数据结构算法面试100题

《2023年数据结构算法面试100题》由会员分享，可在线阅读，更多相关《2023年数据结构算法面试100题（44页珍藏版）》请在金锄头文库上搜索。

1、数据结构+ 算法面试100题 摘自CSD N ,作者July1. 把二元查找树转变成排序的双向链表( 树)题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。规定不能创建任何新的结点，只调整指针的指向。10/6 14/4 8 12 16转换成双向链表4=6=8=10=12=14=16。一方面我们定义的二元查找树节点的数据结构如下：struct BSTreeNode(int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of

2、node)；2. 设计包含m in函数的栈( 栈)定义栈的数据结构，规定添加一个min函数，可以得到栈的最小元素。规定函数min push以及pop的时间复杂度都是0(1)。参见 C:UsersAdministratorDesktopdemoStack分析：min时间复杂度要达成。 ( 1 ) ,需要我们在栈中存储最小元素3. 求子数组的最大和( 数组)题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。规定期间复杂度为0(n)。例如输入的数组为1, -2, 3,10, -4, 7, 2, - 5 , 和最大的

3、子数组为3,10, -4, 7, 2,因此输出为该子数组的和18。分析：根据dp思想#include #define N 8int main()(int i,aN= 1,-2, 3,10, -4, 7, 2,-5;int fromN, resultN, max;max = 0;from0 = 0;result0 = a0;for (i = 1; i 0)fromi = fromi - 1;resulti = ai + resulti - 1;else(fromi = i;resulti = ai;)if (resulti resultmax)max = i;)printf(%d-%d: %dn

4、H, frommaxz max, resultmax);return 0;)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 nodeBinaryTreeNode *m_pLeft; /

5、 left child of nodeBinaryTreeNode *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

6、,24,0,0,0,1,0,0,00在下排出现了6次，1在下排出现了2次，2在下排出现了 1次，3在下排出现了 0次.以此类推 .第7题 （ 链表）微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如hl, h 2 ,判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1 . 假如链表也许有环列？2 . 假如需规定出俩个链表相交的第一个节点列？第8题 （ 算法）此贴选一些比较怪的题， ， 由于其中题目自身与算法关系不大， 仅考考思维。 特此并作一题。1 .有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一

7、间的情况。现在规定受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？2 . 你让一些人为你工作了七天，你要用一根金条作为报酬。金条被提成七小块，天天给出一块。假如你只能将金条切割两次，你如何分给这些工人？3 . 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。 用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。 用一种算法整理一个数组。你为什么选择这种方法？ 用一种算法使通用字符串相匹配。 颠倒一个字符串。优化速度。优化空间。颠倒一个句子中的词的顺序，比如将“ 我叫克丽丝”转换为“ 克丽丝叫我” ,实现速度最快，移动最少。找到一个子

8、字符串。优化速度。优化空间。比较两个字符串，用 0 （ n） 时间和恒量空间。假设你有一个用1001个整数组成的数组， 这些整数是任意排列的， 但是你知道所有的整数都在1 到 1000（ 涉 及 1000） 之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次解决，用- - 种算法找出反复的那个数字。假如你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗？不用乘法或加法增长8 倍。现在用同样的方法增长7 倍。第 9 题 （ 树）判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。假如是返回

9、tru e ,否则返回false。例如输入5、7、6、9、11、10、8 , 由于这一整数序列是如下树的后序遍历结果:8/ /6 10/ / / /5 79 11因此返回true。假如输入7、4、6、5 , 没有哪棵树的后序遍历的结果是这个序列，因此返回false。第 10题 （ 字符串）翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简朴起见，标点符号和普通字母同样解决。例如输入，am a student.,则输出student, a am I第 11题 （ 树）求二叉树中节点的最大距离假如我们把二叉树当作一个图，父子节点

10、之间的连线当作是双向的，我们姑且定义 距离 为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。第 12题 （ 语法）题 目 : 求 1+2+ +n,规定不能使用乘除法、 for、 whe、 if、 else switch, case等关键字以及条件判断语句（A?B：C） 。第 13题 （ 链表） ：题目：输入一个单向链表，输出该链表中倒数笫k 个结点。链表的倒数第0 个结点为链表的尾指针。链表结点定义如下:struct ListNodeint m_nKey;ListNode* m_pNext;第 14题 （ 数组） ：题目：输入一个已经按升序排序过的数组和一个数字，

11、在数组中查找两个数，使得它们的和正好是输入的那个数字。规定期间复杂度是0 （ n） 。假如有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4 和 11。第 15题 （ 树） ：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完毕树的镜像转换。例如输入：8/ /6 10IIII5 79 11输出:810 6Illi119 7 5定义二元查找树的结点为：struct BSTreeNode / a node in the binary searc

12、h tree (BST)(int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node)；第 16题 ( 树 ) ：题目( 微软) ：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入8/ /610/ / / /5 79 11输出 8 6 105 7 9 llo第 17题( 字符串) :题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。分析：这道题是2023年

13、google的一道笔试题。第 18题 ( 数 组 ) ：题目：n 个 数 字(0,1, ,n -1 )形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第m 个 数 字 ( 第一个为当前数字自身，第二个为当前数字的下一个数字) 。当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经见识过了。第 19题 ( 数 组 、递归) ：题目：定义Fibonacci数列如下：/0n=0f(n)= 1 n=l/ f(n-l)+f(n-2) n=2输 入 n , 用最快的方法求该数列的第n 项。分析：在很多C 语言教科书中讲到递归

14、函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，但 . 呵呵，你知道的。 。第 20题 （ 字符串） ：题目：输入一个表达整数的字符串，把该字符串转换成整数并输出。例如输入字符串345,则输出整数345。第 21题 （ 数组）2023年中兴面试题编程求解：输入两个整数n 和 m ,从数列1, 2, 3.n 中随意取几个数,使其和等于m ， 规定将其中所有的也许组合列出来.第 22题 （ 推理） ：有 4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、 B、 C 三人都可以看见其余两人额头上的牌， 看完后让

15、他们猜自己额头上是什么颜色的牌,A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。请教如何推理，A 是怎么知道的。假如用程序，又怎么实现呢？第 23题 （ 算法） ：用最简朴，最快速的方法计算出下面这个圆形是否和正方形相交。3D坐标系原点(0.0,0.0,0.0)圆形：半径r = 3.0圆心。 = ( * . * , 0.0, *.*)正方形：4 个角坐标；1:(*.*, 0.0, *.*)2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)4:(*.*, 0.0, *.*)第 24题 ( 链 表 ) ：链表操作，单链表就地逆置，第 25题( 字符串) ：写一个函数，

16、 它的原形是 jnt continumax(char *outputstr,char *intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如：abcdl2345edl25ss的首地址传给intputstr后，函数将返回9,outputstr所指的值为26. 左旋转字符串( 字符串)题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。规定期间对长度为n 的字符串操作的复杂度为0 （ n） , 辅

17、助内存为0 （ 1） 。27 . 跳台阶问题（ 递归）题目：一个台阶总共有n 级，假如一次可以跳1 级，也可以跳2 级。求总共有多少总跳法，并分析算法的时间复杂度。这道题最近经常出现，涉及MicroStrategy等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。28 . 整数的二进制表达中1 的 个 数 （ 运算）题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入1。 ，由于其二进制表达为10 10,有两个1 , 因此输出2。分析：这是一道很基本的考察位运算的面试题。涉及微软在内的很多公司都曾采用过这道题。29 . 栈的push、pop序 列 （ 栈）题目：输入两个

18、整数序列。其中一个序列表达栈的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、lo但序列4、3、5、1、2 就不也许是push序 列 1、2、3、4、5 的 pop序列。30 . 在从1 到 n 的正数中1 出现的次数（

19、数组）题目：输入一个整数n , 求 从 1 到 n 这 n 个整数的十进制表达中1 出现的次数。例如输入1 2 ,从 1 到 12这些整数中包含1 的数字有1, 10, 1 . 和 12, 1 一共出现了 5 次。分析：这是一道广为流传的google面试题。31 . 华为面试题（ 搜索） ：一类似于蜂窝的结构的图，进行搜索最短途径（ 规定5 分钟）32 . （ 数组、规划）有两个序列a ,b ,大小都为n,序列元素的值任意整数，无序；规定：通过互换a,b中的元素，使 序列a 元素的和 与 序 列 b 元素的和 之间的差最小。例如：var a= 100,99,98,l,2, 3 ;var b=l

20、, 2, 3, 4,5,40;3 3 .（ 字符串）实现一个挺高级的字符匹配算法：给一串很长字符串，规定找到符合规定的字符串，例如目的串：123*3*2 12*3这些者E要找出来其实就是类似一些和谐系统。 。o。34 . （ 队列）实现一个队列。队列的应用场景为：一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列35 . （ 矩阵）求一个矩阵中最大的二维矩阵（ 元素和最大） . 如：12 0342 345 111 5 3 0中最大的是：455 3规定乂 1） 写出算法; 分析时间复杂度; 用 C 写出关键代码第 36题-40题 （ 有些题目搜集于CSDN上的网友，已标明）

21、：3 6 引用自网友：longzuo （ 运算）谷歌笔试:n支队伍比赛，分别编号为0, 1, 2oo n -1 ,已知它们之间的实力对比关系，存储在一个二维数组wnn中，w iQ 的值代表编号为i, j的队伍中更强的一支。所以w ij=i或者j ,现在给出它们的出场顺序，并存储在数组。rdern中，比如ordern） = 4,3,5,8,1 ,那么第一轮比赛就是4对3, 5对8。. 胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，下一轮由上一轮的胜者按照顺序，再依次两两比，比如也许是4对5,直至出现第一名编程实现，给出二维数组w, 一维数组。rd e r和 用于输出比赛名次

22、的数组resultn,求出 resulto37 .（ 字符串）有n个长为m+1的字符串，假如某个字符串的最后m个字符与某个字符串的前m个字符匹配, 则两个字符串可以联接,问这n个字符串最多可以连成一个多长的字符串，假如出现循环，则返回错误。38 .（ 算法）百度面试：L用 天 平 （ 只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平,最多可以从y个小球中找出较轻的那个，求y与x的关系式。2. 有一个很大很大的输入流，大到没有存储器可以将其存储下来，并且只输入一次，如何从这个输入流中随机取得m个记录。3. 大量的URL字符串，如何从中去除反复的，优化时间空间复杂度39 . （

23、 树、图、算法）网易有道笔试：（ 1） .求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1 , 和相邻兄弟节点间的距离是2 , 优化时间空间复杂度。（ 2） .求一个有向连通图的割点，割点的定义是，假如除去此节点和与其相关的边，有向图不再连通，描述算法。40 . 百度研发笔试题（ 栈、算法）引用自：zp1） 设 一个栈结构，满足一下条件：min, push, pop操作的时间复杂度为0 （ 1） 。2） 一串首尾相连的珠子（ m 个） ，有 N 种颜色（ N2-3和 2-3-5并 为 1-2-3-5此外只能输出结果，不能修

24、改两个链表的数据。43 . 递归和非递归俩种方法实现二叉树的前序遍历。44 . 腾讯面试题（ 算法） ：1 . 设计一个 魔 方 （ 六面）的程序。2 . 有一千万条短信，有反复，以文本文献的形式保存，一行一条，有反复。请用5 分钟时间，找出反复出现最多的前10条。3. 收藏了 1 万条u r l,现在给你一条u r l,如何找出相似的url。（ 面试官不解释何为相似）45. 雅虎（ 运算、矩阵） ：1 .对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（ 上下左右）某一个元素也加一， 现给出一正数矩阵， 判断其是否可以由一个全零矩阵通过上述运算得到。2 . 一个整数数组，长

25、度为n , 将其分为m 份，使各份的和相等，求 m 的最大值比如3, 2, 4, 3, 6 可以提成3, 2, 4, 3, 6） m=l;3,62,4,3 m=23,32,46 m =3所以m 的最大值为346 . 搜狐（ 运算） ：四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（ ）（ ）和 （ （ ） ）47 . 创新工场（ 算法） :求一个数组的最长递减子序列比如9, 4, 3, 2, 5, 4, 3, 2的最长递减子序列为9, 5, 4,3, 248. 微软（ 运算） :一个数组是由一个递减数列左移若干位形成的，比如4, 3, 2, 1, 6, 5是由6, 5, 4, 3,

26、 2, 1左移两位形成的，在这种数组中查找某一个数。49 . 一道看上去很吓人的算法面试题（ 排序、算法） ：如何对n 个数进行排序，规定期间复杂度。 （ n） , 空间复杂度。 （ 1）50 . 网易有道笔试（ so rry,与第39题反复） ：1 . 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1 , 和相邻兄弟节点间的距离是2 , 优化时间空间复杂度。2 . 求一个有向连通图的割点，割点的定义是，假如除去此节点和与其相关的边，有向图不再连通，描述算法。51 . 和为n 连续正数序列（ 数组） 。题目：输入一个正数n

27、 , 输出所有和为n 连续正数序列。例如输入1 5 ,由于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 treeint m_nValue; / value of

28、nodeSBinaryTreeNode *m_pLeft; / left child of nodeSBinaryTreeNode *m_pRight; / right child of node）；分析：这道题本质上还是考察二元树的遍历。53. 字符串的排列（ 字符串） 。题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串a b c ,则输出由字符a、b、c所能排列出来的所有字符串abc、 acb、 bac、 bca、 cab 和 cba。分析：这是一道很好的考核对递归理解的编程题,因此在过去一年中频繁出现在各大公司的面试、笔试题中。54 . 调整数组顺序使奇数位于偶数前面

29、( 数组) 。题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。规定期间复杂度为0(n)。55 .( 语法)题目：类CMyString的声明如下：class CMyStringpublic:CMyString(char* pData = NULL);CMyString(const CMyString& str);CMyString(void);CMyString& operator = (const CMyString& str);private:char* m_pData;请实现其赋值运算符的重载函数，规定异常安全，即当对一个对象进行赚

30、值时发生异常，对象的状态不能改变。56 . 最长公共字串( 算法、字符串) 。题目：假如字符串一的所有字符按其在字符串中的顺序出现在此外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不规定子串( 字符串一) 的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。例如：输入两个字符串BDCABA和 ABCBDAB,字符串BCBA和 BDAB都是是它们的最长公共子串，则输出它们的长度4 , 并打印任意一个子串。分析：求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视

31、算法的公司像MicroStrategy都把它当作面试题。57 . 用俩个栈实现队列( 栈、队列) 。题目：某队列的声明如下：template class CQueue(public:CQueue() CQueue() void appendTail(const T& node); / append a element to tailvoid deleteHead();/ remove a element from headprivate:T m_stackl;T m_stack2;）；分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是规定我们用两个栈来实现一个队列。相信大家

32、对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。58. 从尾到头输出链表（ 链表） 。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下:struct ListNode（int m_nKey;ListNode* m_pNext;分析：这是一道很故意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。59 . 不能被继承的类( 语法) 。题目：用 C+设计一个不能被继承的类。分析：这是Adobe公司2023年校

33、园招聘的最新笔试题。这道题除了考察应聘者的C+基本功底外，还能考察反映能力，是一道很好的题目。60 . 在。(1 ) 时间内删除链表结点( 链表、算法) 。题目：给定链表的头指针和一个结点指针，在 0(1)时间删除该结点。链表结点的定义如下:struct ListNode(int m_nKey;ListNode* m_pNext;);函数的声明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反映速度,更重要的是，还能考察我们对时间

34、复杂度的理解。61 . 找出数组中两个只出现一次的数字( 数组)题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。规定期间复杂度是0 ( n ) ,空间复杂度是0(1)。分析：这是一道很新奇的关于位运算的面试题。62 . 找出链表的第一个公共结点( 链表) 。题目：两个单向链表，找出它们的第一个公共结点。链表的结点定义为：struct ListNodeint m_nKey;ListNode* m_pNext;分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概率相称高。63 . 在字符串中删除特定的字符（

35、字符串） 。题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符.例如，输入They are students.和aeiou,则删除之后的第一个字符串变成” Thy rstdnts.”。分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，由于写程序操作字符串能很好的反映我们的编程基本功。64 . 寻找丑数（ 运算） 。题目：我们把只包含因子2、3 和 5 的数称作丑数（Ugly Number） 。例如6、8 都是丑数,但 14不是，由于它包含因子7。习惯上我们把1 当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：这是一道在网络上广为流传

36、的面试题，据说google曾经采用过这道题。65 . 输出1 到最大的N 位 数 （ 运算）题目：输入数字n , 按顺序输出从1 最大的n 位 10进制数。比如输入3,则输出1、2、3 一直到最大的3 位数即999o分析：这是一道很故意思的题目。看起来很简朴，其实里面却有不少的玄机。66 . 颠倒栈（ 栈） 。题目: 用递归颠倒一个栈。例如输入栈 1,2, 3,4,5 , 1 在栈顶。颠倒之后的栈为 5, 4, 3, 2,1 , 5 处在栈顶。67 . 俩个闲玩娱乐（ 运算） 。1 .扑克牌的顺子从扑克牌中随机抽5 张牌，判断是不是一个顺子，即这5 张牌是不是连续的。2-10为数字自身，A 为

37、 1, J 为 11, Q 为 12, K 为 1 3 ,而大小王可以当作任意数字.2 .n 个骰子的点数。把 n 个骰子扔在地上，所有骰子朝上一 一 面 的点数之和为S。输入n,打印出S 的所有也许的值出现的概率。68. 把数组排成最小的数（ 数组、算法） .题目：输入一个正整数数组， 将它们连接起来排成一个数， 输出能排出的所有数字中最小的一个。例如输入数组 32, 321） , 则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。分析：这是20236月份百度的一道面试题，从这道题我们可以看出百度相应聘者在算法方面有很高的规定。69 . 旋转数组中的最小元素（ 数组

38、、算法） 。题目：把一个数组最开始的若干个元素搬到数组的末尾， 我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组 3, 4, 5 ,1, 2 为 1, 2, 3, 4, 5 的一个旋转，该数组的最小值 为 1。分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是。 （ N） 。但这个思绪没有运用输入数组的特性，我们应当能找到更好的解法。70 . 给出一个函数来输出一个字符串的所有排列（ 经典字符串问题） 。ANSWER简朴的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，尚有逆序生成排列和一些不需要递归

39、生成排列的方法。印象中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 =len2,那

40、么指针p l 由 headl开始向后移动Ienl-len2步 , 指 针 p2=head2,下面p l、p2每次向后前进一步并比较plp2是否相等，假如相等即返回该结点，否则说明两个链表没有交点。3 . 给定单链表(head),假如有环的话请返回从头结点进入环的第一个节点。运用题一，我们可以检查链表中是否有环。假如有环，那么plp2重合点p 必然在环中。从 p 点断开环，方法为：pl=p, p2=p-next, p-next=NULLo此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始， 于是运用题二的方法， 我们找到它们的第一个交点即为所求。4 . 只给定单链表中某个结点

41、p( 并非最后一个结点，即 p-next!=NULL)指针，删除该结点。办法很简朴， 一方面是放p 中数据， 然后将p-next的数据copy入 p 中， 接下来删除p-next即可。5. 只给定单链表中某个结点p（ 非空结点） ，在 p 前面插入一个结点。办法与前者类似，一方面分派一个结点q , 将 q 插入在p 后，接下来将p 中的数据copy入 q 中，然后再将要插入的数据记录在p 中。78 . 链表和数组的区别在哪里（ 链表、数组）？分析：重要在基本概念上的理解。但是最佳能考虑的全面一点，现在公司招人的竞争也许就在细节上产生，谁比较仔细，谁获胜的机会就大。79 . （ 链表、字符串）1

42、 . 编写实现链表排序的一种算法. 说明为什么你会选择用这样的方法？2 . 编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？3 . 请编写能直接实现strstr。 函数功能的代码。80. 阿里巴巴一道笔试题（ 运算、算法）问题描述：12个高矮不同的人， 排成两排， 每排必须是从矮到高排列， 并且第二排比相应的第一排的人高,问排列方式有多少种?这个笔试题， 很 YD,由于把某个递归关系隐藏得很深。先来几组百度的面试题:81. 第1 组百度面试题1 . 一个int数组，里面数据无任何限制，规定求出所有这样的数ai,其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量

43、其它空间实现。2 . 一个文献，内含一千万行字符串，每个字符串在1K 以内，规定找出所有相反的串对，如 abc和 cba。3 .STL的 set用什么实现的？为什么不用hash?82. 第2 组百度面试题1 .给出两个集合A 和 B , 其中集合A=name,集合 B=age、sex、scholarship、address、规定：问题1、根据集合A 中的name查询出集合B 中相应的属性信息；问题2、 根据集合B 中的属性信息（ 单个属性， 如 age20等） ， 查询出集合A 中相应的2 . 给出一个文献，里面包含两个字段url、size,即 url为网址，size为相应网址访问的次数，规定

44、：name。问题1、运 用 Linux Shell命令或自己设计算法,查询出url字符串中包含“ baidu” 子字符串相应的size字段值；问题2、根据问题1 的查询结果，对其按照size由大到小的排列。( 说明：url数据量很大，100亿级以上)83. 第3 组百度面试题1 .今年百度的一道题目百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。规定：空间复杂度0 (1 ),时间复杂度为O(n)。2 . 百度笔试题用 C 语言实现函数 void * memmove(void *dest, const void *src, size_t n)。memmove函数的功

45、能是拷贝src所指的内存内容前n 个字节到dest所指的地址上。分析：由于可以把任何类型的指针赋给void类型的指针这个函数重要是实现各种数据类型的拷贝。84 . 第4 组百度面试题2023年 3 道百度面试题 相信，你懂其中的含金量l .a-z涉及大小写与09组成的N 个数用最快的方式把其中反复的元素挑出来。2 . 已知一随机发生器，产生0 的概率是p , 产 生 1 的概率是l- p , 现在要你构造一个发生器,使得它构造0 和 1 的概率均为1/2;构造一个发生器， 使得它构造1、 2、 3 的概率均为1/3；构造一个发生器，使得它构造1、2、3、.n的概率均为l/ n ,规定复杂度最低

46、。3 . 有10个文献，每个文献1G,每个文献的每一行都存放的是用户的query,每个文献的query都也许反复。规定按照query的频度排序.85. 又见字符串的问题1 . 给出一个函数来复制两个字符串A 和 B。字符串A 的后几个字节和字符串B 的前几个字节重叠。分析：记住，这种题目往往就是考你对边界的考虑情况。2 . 已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde的个数,假如没有返回0 , 有的话返回子字符串的个数。86.如何编写一个程序，把一个有序整数数组放到二叉树中？分析: 本题考察二叉搜索树的建树方法，简朴的递归结构。关于树的算法设计一定要联想到递归，由于

47、树自身就是递归的定义。而，学会把递归改称非递归也是一种必要的技术。毕竟，递归会导致栈溢出，关于系统底层的程序中不到非不得以最佳不要用。但是对某些数学问题，就一定要学会用递归去解决。87.1 . 大整数数相乘的问题。（ 这是2023年在一考研班上碰到的算法题）2 . 求最大连续递增数字串（ 如 ads3sl456789DF34561d345AA” 中 的 “456789）3 . 实现strstr功能，即在父串中寻找子串初次出现的位置。（ 笔试中常让面试者实现标准库中的一些函数）88.2023年 11月金山笔试题。编码完毕下面的解决函数。函数将字符串中的字符 * 移到串的前部分，前面的非阳字符后移

48、，但不能改变非 * 字符的先后顺序，函数返回串中字符 * 的数量。如原始串为: ab*cd*e*12,解决后为* * *abcdel2,函数并返回值为5。（ 规定使用尽量少的时间和辅助空间）89. 神州数码、华为、东软笔试题1.2023年 11月 1 5 日华为软件研发笔试题。实现一单链表的逆转。2 . 编码实现字符串转整型的函数（ 实现函数atoi的功能） ，据说是神州数码笔试题。如将字符串 ” +123“ 123, ” -0123 -123, “ 123CS45” 123, “ 123.45CS” 123, “ CS123.45” 03 . 快速排序（ 东软喜欢考类似的算法填空题，又如堆排

49、序的算法等）4 . 删除字符串中的数字并压缩字符串。如字符串 abcl23de4fg56” 解决后变为“ abcdefg”。注意空间和效率。（ 下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为。 网） ）5 . 求两个串中的第一个最长子串（ 神州数码以前试题） 。如abractyeyt,dgdsaeactyey的最大子串为actyet。90.1 .不开辟用于互换数据的临时空间，如何完毕字符串的逆序（ 在技术一轮面试中，有些面试官会这样问） 。2 . 删除串中指定的字符（ 做此题时，千万不要开辟新空间，否则面试官也许认为你不适合做嵌入式开发）3 . 判断单链表中是否存在环。91.1 .

50、一道著名的毒酒问题有1000桶酒，其 中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。2 . 有趣的石头问题有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量同样,把配对的石头和木头找出来。92.1多人排成一个队列， 我们认为从低到高是对的的序列， 但是总有部分人不遵守秩序。假如说， 前面的人比后面的人高（ 两人身高同样认为是合适的） ，那么我们就认为这两个人是一对“ 捣乱分子”， 比如说, 现在存在一个序列：176, 178,180,170, 171这些捣乱分子对为, , , , , ,那么， 现在给出一个整型序列，

51、 请找出这些捣乱分子对的个数（ 仅给出捣乱分子对的数目即可,不用品体的对)规定：输入：为一个文献(in ),文献的每一行为一个序列。序列全为数字，数字间用“， “分隔。输出：为一个文献(o u t),每行为一个数字，表达捣乱分子的对数。具体说明自己的解题思绪，说明自己实现的一些关键点。并给出实现的代码，并分析时间复杂度。限制：输入每行的最大数字个数为100000个，数字最长为6 位。程序无内存使用限制。93 . 在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。直观想法是用两个数组a、b。ai、bi分别保存从前到i 的最大的数和从后到i 的最小的数,一个解答：这需要两次

52、遍历，然后再遍历一次原数组，将所有 datai=ai-l&datai=biW data川找出即可。给出这个解答后，面试官有规定只能用一个辅助数组，且规定少遍历一次。94 . 微软笔试题求随机数构成的数组中找到长度大于=3的最长的等差数列9 d- x W) w9 ? o3 b0 R输出等差数列由小到大：假如没有符合条件的就输出格式：输入1,3,0,5,-1,6输出-1,1,3,5规定期间复杂度，空间复杂度尽量小95. 华为面试题1 判断一字符串是不是对称的，如：abccba2. 用递归的方法判断整数组aN是不是升序排列96.2023中兴校园招聘笔试题1 . 编写strcpy函数已知strcpy函

53、数的原型是char *strcpy(char *strDest, const char *strSrc);其中strDest是目的字符串，strSrc是源字符串。不调用C+/C的字符串库函数，请编写函数strcpy最后压轴之戏，终结此微软等100题系列V0.1版。那就，连续来几组微软公司的面试题，让你一次爽个够：97. 第1 组微软较简朴的算法面试题1. 编写反转字符串的程序，规定优化速度、优化空间。2 . 在链表里如何发现循环链接？3 . 编写反转字符串的程序，规定优化速度、优化空间。4 . 给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。5 . 写一个函数，检查字符是否是整数，假如是

54、，返回其整数值。（ 或者：如何只用4 行代码编写出一个从字符串到长整形的函数？）98. 第2 组微软面试题1 . 给出一个函数来输出一个字符串的所有排列。2 . 请编写实现malloc（ ） 内存分派函数功能同样的代码。3 . 给出一个函数来复制两个字符串A 和 Bo字符串A 的后几个字节和字符串B 的前儿个字节重叠4 . 如何编写一个程序，把一个有序整数数组放到二叉树中？5 . 如何从顶部开始逐层打印二叉树结点数据？请编程。6 . 如何把一个链表掉个顺序（ 也就是反序，注意链表的边界条件并考虑空链表）？99. 第3 组微软面试题1 . 烧一根不均匀的绳，从头烧到尾总共需要1 个小时。现在有若

55、干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？2 . 你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以拟定你肯定有两个同一颜色的果冻？ （ 5 秒-1 分钟）3 . 假如你有无穷多的水，一个3 公升的提捅，一个5 公升的提捅，两只提捅形状上下都不均匀，问你如何才干准确称出4 公升的水？（40秒-3 分钟）一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的.诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国,但不知道应当走哪条路，需要问这两个人。请问应当怎么问？ （20秒-2 分钟）100. 第4 组微软面

56、试题，挑战思维极限1.12个球一个天平， 现知道只有一个和其它的重量不同， 问如何称才干用三次就找到那个球。13个呢？ （ 注意此题并未说明那个球的重量是轻是重， 所以需要仔细考虑） （5 分钟；小时）2 . 在9 个点上画10条直线，规定每条直线上至少有三个点？ （ 3 分钟-20分钟）3 . 在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有儿次？都分别是什么时间？你如何算出来的？ （5 分钟-15分钟）终结附加题：微软面试题，挑战你的智商说明：假如你是第一次看到这种题，并且以前历来没有见过类似的题型，并且可以在半个小时之内做出答案，说明你的智力超常. . ）1. 第一题.

57、五个海盗抢到了 100颗宝石，每一颗都同样大小和价值连城。他们决定这么分:抽签决定自己的号码（1、2、3、4、5）一方面，由 1 号提出分派方案，然后大家表决，当且仅当超过半数的人批准时，按照他的方案进行分派，否则将被扔进大海喂鲨鱼假 如 1 号死后，再由2 号提出分派方案，然后剩下的4 人进行表决，当且仅当超过半数的人批准时，按照他的方案进行分派，否则将被扔入大海喂鲨鱼。依此类推条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。问题：第一个海盗提出如何的分派方案才干使自己的收益最大化?2. 一道关于飞机加油的问题，己知：每个飞机只有一个油箱，飞机之间可以互相加油（ 注意是互相，没有加油机）一箱油可供一架飞机绕地球飞半圈，问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（ 所有飞机从同一机场起飞，并且必须安全返回机场，不允许半途降落，中间没有飞机场）欢迎，关注此外不同的更精彩的100题 V0.2版，和此V0.1版的答案等后续内容。