开发者社区> 问答> 正文

【今日算法】备战大厂必备题目,持续更新

学习算法,每天进步一点点! 想要进入大厂,发现算法题总是困难重重,我们整理了备战大厂那些必不可少的算法题目,周一到周五每天更新一道,答案会在出题第二天倾情奉上哦~

72.堆(7.13更新)

71.二分法(7.11更新)

70.哈希表(7.10更新)

69.一个函数秒杀 2Sum 3Sum 4Sum 问题(7.9更新)

68.线性表(7.8更新)

67.初识Floyd算法(7.7更新)

66.十大经典排序算法大梳理(7.6更新)

65.拓扑排序(7.5更新)

64.程序为什么会超时?(7.4更新)

63.算法分析中的空间复杂度(7.3更新)

62.递归算法的时间复杂度(7.2更新)

61.时间复杂度(7.1更新)

60.五道数组相关的面试题(6.30更新)

59.计算机、数学、运筹学等领域的32个重要算法(6.29更新)

58.不可不会的反转链表(6.28更新)

57.数学之美:布隆过滤器(6.24更新)

56.算法工程师必知必会10大基础算法!(6.23更新)

55.旋转数组的最小数字(6.22更新)

54.递归反转链表:如何拆解复杂问题(6.20更新)

53.详解递归(6.18更新)

52.这几道经典例题帮你轻松搞透贪心算法(6.17更新)

51.什么是线段树?(6.16更新)

50.动态规划的实际应用:图片压缩算法(6.15更新)

49.图解九大数据结构(6.13更新)

48.佩奇排名算法(6.12更新)

47.用位运算来解下八皇后问题(6.11更新)

46.搜索引擎背后的经典数据结构和算法(6.10更新)

45.用 Git 来讲讲二叉树最近公共祖先(6.9更新)

44.我用四个命令,总结了 Git 的所有套路(6.8更新)

43.什么是字典树(Trie)(6.5更新)

42.区间问题之合并相交区间(6.4更新)

41.经典动态规划:高楼扔鸡蛋(进阶篇)(6.3更新)

40.经典动态规划:高楼扔鸡蛋(6.2更新)

39.什么是B+树(6.1更新)

38.优化求最值(5.29更新)

37.BFS暴力搜索算法(5.28更新)

36.随机算法之水塘抽样算法(5.27更新)

35.三个反直觉的概率问题(5.26更新)

34.最大子数组和(动态规划,5.25更新)

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

33.高效寻找缺失和重复的数字(5.23更新)

给一个长度为N的数组nums,其中本来装着[1..N]这N个元素,无序。但是现在出现了一些错误,nums中的一个元素出现了重复,也就同时导致了另一个元素的缺失。请你写一个算法,找到nums中的重复元素和缺失元素的值。

// 返回两个数字,分别是 {dup, missing}
vector<int> findErrorNums(vector<int>& nums);

比如说输入:nums = [1,2,2,4],算法返回[2,3]。

32.烧饼排序(5.22更新)

31.LRU 缓存淘汰算法详解(5.21更新)

30.如何判定括号合法性?(栈,5.20更新)

29.如何高效寻找素数?(5.19更新)

28.编辑距离(动态规划,5.18更新)

给定两个字符串s1和s2,计算出将s1转换成s2所使用的最少操作数。

你可以对一个字符串进行如下三种操作: 1. 插入一个字符 2. 删除一个字符 3. 替换一个字符

示例1:

输入:s1="horse",s2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
horse -> rose(删除 'r')
rose -> ros (删除 'e')

示例2:

输入: s1 = "intention",s2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention ->  exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

27.贪心算法之区间调度问题(5.15更新)

26.动态规划之四键键盘(动态规划,5.14更新)

假设你有一个特殊的键盘包含下面的按键:

  • key 1:(A):在屏幕上打印一个 'A'
  • key 2:(Ctrl-A):选中整个屏幕
  • key 3:(Ctrl-C):复制选中区域到缓冲区
  • key 4:(Ctrl-V):将缓冲区内容输出到上次输入的结束位置,并显示在屏幕上

现在,你只可以按键N次(使用上述四种按键),请问屏幕上最多可以显示几个'A'呢?

样例1:

输入:N=3

输出:3

解释:我们最多可以在屏幕上显示3个'A',通过如下顺序按键:A, A, A

样例2:

输入:N=7

输出:N=9

解释:我们最多可以在屏幕上显示9个'A',通过如下顺序按键:A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V

25.五分钟算法小知识:动态规划之博弈问题(5.13更新)

24.五分钟算法小知识:二叉堆详解实现优先级队列(5.12更新)

23.五分钟算法小知识:动态规划设计:最长递增子序列(5.11更新)

22.五分钟算法小知识:Linux的进程、线程、文件描述符是什么?(5.9更新)

21.五分钟算法小知识:双指针技巧总结(5.8更新)

20.五分钟算法小知识:动态规划详解(5.7更新)

19.五分钟算法小知识:洗牌算法(5.6更新)

18.五分钟算法小知识:回溯算法详解(4.30更新)

17.区间交集问题(双指针,4.29更新)

给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。

返回这两个区间列表的交集。

(形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

示例:

01.png

输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意:输入和所需的输出都是区间对象组成的列表,而不是数组或列表。

16.区间调度问题之区间合并(数组,4.28更新)

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

15.接雨水问题(双指针,4.27更新)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

01.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

14.如何寻找最长回文子串(字符串,4.24更新)

给定一个字符串 s ,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1:

输入: "babad"
输出: "bab"
注意:"aba"也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"
string longestPalindrome(string s) {}

13.如何调度考生的座位(Ordered Map,4.23更新)

假设有一个考场,考场有一排共 N 个座位,索引分别是 [0..N-1],考生会陆续进入考场考试,并且可能在任何时候离开考场。你作为考官,要安排考生们的座位,满足:每当一个学生进入时,你需要最大化他和最近其他人的距离;如果有多个这样的座位,安排到他到索引最小的那个座位。这很符合实际情况对吧,也就是请你实现下面这样一个类:

class ExamRoom {
    // 构造函数,传入座位总数 N
    public ExamRoom(int N);
    // 来了一名考生,返回你给他分配的座位
    public int seat();
    // 坐在 p 位置的考生离开了
    // 可以认为 p 位置一定坐有考生
    public void leave(int p);
}

比方说考场有 5 个座位,分别是 [0..4]:

第一名考生进入时(调用 seat()),坐在任何位置都行,但是要给他安排索引最小的位置,也就是返回位置 0。

第二名学生进入时(再调用 seat()),要和旁边的人距离最远,也就是返回位置 4。

第三名学生进入时,要和旁边的人距离最远,应该做到中间,也就是座位 2。

如果再进一名学生,他可以坐在座位 1 或者 3,取较小的索引 1。

以此类推。

12.删除排序数组中的重复项(数组,4.22更新)

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

11.最小栈的最优解(最小栈,4.21更新)

实现一个这样的栈,这个栈除了可以进行普通的push、pop操作以外,还可以进行getMin的操作,getMin方法被调用后,会返回当前栈的最小值。栈里面存放的都是 int 整数,并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。

附加:如果空间复杂度也能O(1)的话可加分。

10.二分查找详解(二分查找,4.20更新)

有一天阿东到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿东拦下,要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下,以找出引发警报的书,但是保安露出不屑的眼神:你连二分查找都不会吗?于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是阿东背着剩下的书走了。从此,图书馆丢了 N - 1 本书。

9.缺失的第一个正数(数组,4.18更新)

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]输出: 3

示例 2:

输入: [3,4,-1,1]输出: 2

示例 3:

输入: [7,8,9,11,12]输出: 1

说明:你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

8.五分钟算法小知识:学习数据结构和算法的框架思维(4.17更新)

7.两数之和(哈希表,4.16更新)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

6.如何k个一组反转链表(链表,4.15更新)

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5

说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

5.Koko 吃香蕉(二分查找,4.14更新)

Koko喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。Koko可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。Koko喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

示例:

输入: piles = [3,6,7,11], H = 8
输出: 4

4.五分钟算法小知识:王垠的面试 和 P 与 NP(4.13更新)

3.五分钟算法小知识:为什么要分稳定排序和非稳定排序?(4.10更新)

2.四数相加II(哈希表,4.9更新)

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 – 1 之间,最终结果不会超过 231 – 1 。

例如:

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出:
2

解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

1.石子游戏(动态规划,4.8更新)

喜羊羊和灰太狼用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。

喜羊羊和灰太狼轮流进行,喜羊羊先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

假设喜羊羊和灰太狼都发挥出最佳水平,当喜羊羊赢得比赛时返回 true ,当灰太狼赢得比赛时返回 false 。

[免费电子书]覆盖75个算法题目解析,近30种大厂笔试考点,同时还支持“在线”编程的程序员面试宝典,速度下载! https://developer.aliyun.com/article/756998

展开
收起
游客ih62co2qqq5ww 2020-04-08 09:21:40 6648 0
4 条回答
写回答
取消 提交回答
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载