面试常见算法题

A. 秋招面试经典算法练习-第二十八天-正则表达式匹配问题

秋招面试中，正则表达式匹配问题是经典算法练习之一。每日坚持刷题有助于提升编程技巧和面试应对能力。今天，我们来深入理解并解决一道涉及'.'
和'*'的正则表达式匹配问题。

题目要求实现一个函数，处理包含 '.' 和 '*' 的模式。'.' 表示任意字符，'*' 表示前面的字符可出现任意次。目标是判断给定字符串 str 是否能被模式 pattern 完全匹配，如 "aaa" 与 "a*a" 和 "ab*ac*a" 匹配，但不包括 "aa.a" 和 "ab*a"。

示例1中，输入 "aaa" 和 "a*a"，由于 '*' 可以匹配任意次数的 'a'，结果应为 true。在示例2 "aad" 和 "c*a*d" 中，'*' 表示前面的字符可以为0次，所以匹配成功。

解题思路是采用动态规划，定义 dp[i][j] 表示 str 前 i 个字符和 pattern 前 j 个字符是否匹配。初始化时，空串匹配，dp[0][0]=true。遍历 pattern，处理 '*' 的特殊情况，dp[0][i] 可能等于 dp[0][i-2]，表示 '*' 可以匹配0次前一个字符。

状态转移方程考虑字符不为 '*' 的简单情况和 '*' 出现时的匹配规则，根据 dp[i-1][j-1] 或 dp[i][j-2] 来更新 dp[i][j]。通过画图理解算法，可以更好地掌握动态规划过程。

最后的总结强调了算法练习的重要性，无论对于初学者还是资深开发者，刷题都是提升技术的关键。通过反复训练、设定时间限制和总结反思，我们可以更好地掌握基础算法，解决实际问题，从而在面试中脱颖而出。

B. 14道常见的 操作系统 面试题

1. 进程与线程的区分

进程是操作系统分配资源的核心单元，每个进程都承载一个特定功能的程序，针对数据集执行一次独立运行，独立拥有CPU和内存等资源。而线程则是进程内的执行实体，虽然它不直接占用系统资源，但与进程共享同一份资源。简言之，进程是资源分配的基石，线程则是执行的轻量级单元。

2. 面试题：页面置换算法

页面置换算法是操作系统中的关键策略，包括FIFO（先进先出，适合简单调度）、LRU（最近最少使用，依据使用时间）、LFU（最少使用次数，关注频率）、以及理论最优的OPT，它旨在找出不再使用的页面或最早未使用的页面进行替换。

3. 死锁现象及条件

死锁是多线程竞争有限资源时的尴尬困境，当进程彼此持有资源并等待其他进程释放，形成无尽循环，就陷入了死锁。死锁的四个必要条件：互斥、请求与保持、不剥夺和循环等待，是理解死锁的关键。

4. 危险的缓冲区溢出

缓冲区溢出是编程中的安全隐患，当数据填充超出预设容量，覆盖合法数据，可能导致程序崩溃或恶意代码执行，源于对用户输入的疏忽检查。

5. 非对称与对称加密算法

非对称加密利用公开和私有密钥，加密解密使用不同密钥，如RSA和AES，而对称加密如DES，使用同一密钥进行加密和解密，更便于效率提升。

6. 分段与分页的对比

分页为内存管理提供离散分配，消除零头，提高利用率；分段则关注用户需求，将完整意义的信息组合在一起。两者各有其设计目的。

7. 上下文切换：多任务的幕后英雄

单核环境下，上下文切换是进程切换的机制，通过在进程间快速切换，让看似并发运行。每个切换涉及保存当前状态并加载新进程状态。

8. 进程间通信的艺术

进程间通信的方式多种多样，如管道（半双工）、有名管道（无亲缘性）、信号量（同步）、消息队列（灵活）、信号（事件通知）、共享内存（高效）以及套接字（跨进程通信）。每种都有其独特之处，满足不同场景的需求。

9. 线程间的同步与通信手段

线程间的沟通主要为同步目的，如互斥锁、条件变量、读写锁等。互斥锁保证数据一致性，读写锁允许多线程读，写操作互斥，条件变量则在互斥锁下实现阻塞和唤醒。

C. 阿里面试官：恕我直言，搞懂这10道算法题，轻松拿20K不是问题

01打怪兽

难度：容易

现在有3只怪兽，他们的都有自己的血量a,b,c(1<=a,b,c<=100)，当Tom打死第一怪兽的时候花费的代价为0，其余的怪兽的代价为当前的怪兽的血量减去上一个怪兽的血量的绝对值。问Tom打死这些怪兽所需要的最小代价

02数组变换

难度：中等

给出一个长度为 n 的数组，和一个正整数 d。 你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d，这算作一次操作。你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果无解请输出-1。

01超级区间

难度：中等

Tom现在有一个长度为n的数组，Jerry给Tom定义了一种超级区间，如果区间[l,r]满足(a[l]+…+a[r])>=k,则区间[l,r]被称为超级区间，现在Jerry想让Tom告诉他数组中有多少个超级区间。

02能量半径

难度：中等

codancer来到了一个能量平面上的中心，坐标为(0,0)，接下来巫师Tom会在q个坐标上放置能量点，每个能量点的能量值为1，为了打败哥斯拉，他需要至少k点的能量，因此他想确定一个最小的整数半径r使得codancer能够从这个圆心为(0,0)，半径为r的圆形区域内得到至少k个能量值，请你帮他确定最小的整数半径r。

01找出二叉搜索树的第2大的数

难度：容易

给定一个二叉搜索树，找出其第二大的数。

02字符配对

难度：中等

给你一个字符串，字符串中仅包含"A","B",现在有四种字符串"AA","AB","BA","BB"，每种字符串都有他们的权值，问从给出的字符串中能够得到的最大权值为多少(一个字符只能属于一个子字符串)？

01斐波那契字符串

难度：中等

Tom发现了一种神奇的字符串-斐波那契字符串,定义f[1]=0,f[2]=1,对于所有的i>2都有f[i]=f[i-2]+f[i-1]，其中“+”代表拼接，比如01+10=0110，现在对于字符串f[n]，请判断f[n]的第k项是0，还是1？

01Hikari and Interstellar Experience

难度：容易

在无垠的宇宙中，有 n 个星球，第 i 个星球有权值vi 。由于星球之间距离极远，因此想在有限的时间内在星际间旅行，就必须要在星球间建立传送通道。 任意两个星球之间均可以建立传送通道，不过花费并不一样。 第 i 个星球与第 j 个星球的之间建立传送通道的花费是lowbit(vi ⊕ vj) ，其中⊕为二进制异或，而lowbit(x)为 x 二进制最低位的值，例如lowbit(5) = 1,lowbit(8) = 8 。 特殊地，lowbit(0) = 0。 Hikari 想在这 n 个星球间穿梭，于是――你需要告诉 Hikari，要使这 n 个星球相互可达，需要的花费最少是多少？

02二进制字符串

难度：中等

Tom得到了一个二进制字符串s,即s只由Ɔ'和Ƈ'组成，现在令d(t)代表二进制字符串t在十进制下的值。 那么d(“011”)=3,d(“0001000”)=4,如果t的长度等于d(t),那么就称t是奇妙串，现在Tom想知道s中有多少个子串是奇妙串？

01小明的数学作业

难度：容易

众所周知，小明是一个数学小能手，有一天数学老师给了小明一个长度为n（2<=n<=5000）的序列，其中第i个数是ai（0<=ai<=1e9）,数学老师想知道这个序列排序后，其中最长的等差子序列的长度是多长，聪明的你能帮小明解决这个问题吗？

02Codancer上楼

codancer来到了一栋大楼前，现在他要上楼。

如果codancer从第x层走楼梯到第y层(y>x)，那么他所花费的时间是a[x]+a[x+1]+…+a[y]；

如果他从x层坐电梯到第y层，那么他所花费的时间是c+(b[x]+b[x+1]+…+b[y])，因为他等电梯的时间为c。

现在codancer想知道从第1层到第n层需要最少需要多长时间？

01变换的秘钥

难度：中等

Tom最开始有一个密钥s1，s1是长度为n的由小写字母组成的字符串。Jerry也有一个长度为n的由小写字母组成的密钥s2。现在有m组关系，每组关系由两个数字[u,v]构成(1<=u,v<=26)，表示26个字母表中的第u个小写字母可以直接转换为第v个小写字母。假设u=1，v=2,那么说明字母'a'可以直接转换为字母'b'。现在Tom对于s1的每个字母使用无数次转换，请判断s1能否转换为s2？

01最大边权和

难度：简单

现在有n个点(1<=n<=1000)，每个点都有一个值称为点权ai(ai为偶数，1<=ai<=1000)，现在可以将任意两个点相连，连起来以后这条边也有一个值称为边权，这个边的边权为这两个点的点权之和的一半。现在需要你添加n-1条边，问将这n个点连通以后(连通是指任意两个点都能互相到达)的最大的边权和是多少？

02钱庄

难度：中等

钱庄每天能够收到很多散钱，第i个散钱的值2 wi。为了便于管理，钱庄每天都会向中央银行申请兑换钱币，假设钱庄有一些散钱使得2 k1+2 k2+...+2 km=2^x（x为非负整数），那么就可以将这些散钱兑换成一个大钱币，问在钱庄收到的这些散钱最终最少能变成几个钱币？

01codancer的旅行

难度：困难

期末考试终于结束啦，Codancer开始了他的旅行，现在整个地图上有n个城市，这些城市之间有n-1条道路相连，每条道路都有一个距离，并且保证整个图是连通的，即这个地图可以看作是一棵树，现在假设Codancer要从城市A到城市B，那么他的路费就是从A-B的路径上边权最大的边的权值wmaxx元。现在Codancer有k元，他想知道他能选择那些(A,B)并且A<B使得codancer能够到达？

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。

01全奇数组

难度：中等

codancer现在有n个正整数a[1],a[2]…a[n]，Tom告诉codancer他可以进行下列操作，选择某个偶数x，把这n个数中全部等于x的数字除2，Tom想知道把这n个数字全部变成奇数最少需要几次这样的操作？

以上十道算法题你都能搞定嘛？备战大厂每日刷一道算法题来提升自己，坚持坚持再坚持，必然会有收获。为大家整理一份781页的高分宝典，知识较为全面，可分享给想要学习提升自己的朋友。

领取方式：私信【面试宝典】或点击右方链接： https://shimo.im/docs/QVy8HrQgPYkx9Ddg/ 即可免费领取，喜欢本文不妨关注+转发支持一下~~

D. 面试会出哪些经典算法题

如下：

1、排序算法∶快速排序、归并排序、计数排序

2、搜索算法∶回溯、递归、剪枝技巧

3、图论∶最短路、最小生成树、网络流建模

4、动态规划：背包问题、最长子序列、计数问题

5、基础技巧：分治、倍增、二分、贪心

6、数组与链表：单/双向链表、跳舞链

7、栈与队列

8、树与图：最近公共祖先、并查集

9、哈希表

10、堆：大/小根堆、可并堆

11、字符串∶字典树、后缀树

算法简介：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。

这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。