LeetCode面试题集 和你一起愉快A题 (C++)(持续更新中)
阅读须知
本篇博客是根据 LeetCode101: ALeetCodeGrindingGuide(C++Version)
电子书籍整理而来的版本,参考了部分解题思路,now,一起愉快地A题吧,拿下满意的 Offer~
LeetCode 455. 分发饼干【贪心】
题目描述
有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个大小。每个孩子只能吃 最多一个饼干,且只有饼干的大小大于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩 子可以吃饱。
解题思路
贪心。对孩子饥饿度和饼干尺寸从小到大排序,然后逐一比较,满足条件就算一个孩子。
AC
class Solution { |
LeetCode 135. 分发糖果【贪心】
题目描述
一群孩子站成一排,每一个孩子有自己的评分。现在需要给这些孩子发糖果,规则是如果一 个孩子的评分比自己身旁的一个孩子要高,那么这个孩子就必须得到比身旁孩子更多的糖果;所有孩子至少要有一个糖果。求解最少需要多少个糖果。
解题思路
把所有孩子的糖果数初始化为 1; 先从左往右遍历一遍,如果右边孩子的评分比左边的高,则右边孩子的糖果数更新为左边孩子的 糖果数加1;
再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数 不大于右边孩子的糖果数,则左边孩子的糖果数更新为右边孩子的糖果数加1。
通过这两次遍历, 分配的糖果就可以满足题目要求了。这里的贪心策略即为,在每次遍历中,只考虑并更新相邻一 侧的大小关系。
AC
class Solution { |
LeetCode 435. 无重叠区间【贪心】
题目描述
给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
解题思路
- 在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间 就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区间。
- 具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选 择的区间不重叠的区间。我们这里使用 C++ 的 Lambda,结合 std::sort() 函数进行自定义排序。
- 在样例中,排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略,首先初始化为区间 [1,2];由于 [1,3] 与 [1,2] 相交,我们跳过该区间;由于 [2,4] 与 [1,2] 不相交,我们将其保留。因此最终保留的区间为[[1,2],[2,4]]。
注意 需要根据实际情况判断按区间开头排序还是按区间结尾排序。
AC
class Solution { |
LeetCode 167. 两数之和 II - 输入有序数组【玩转双指针】
题目描述
在一个增序的整数数组里找到两个数,使它们的和为给定值。已知有且只有一对解。
解题思路
- 因为数组已经排好序,我们可以采用方向相反的双指针来寻找这两个数字,一个初始指向最 小的元素,即数组最左边,向右遍历;一个初始指向最大的元素,即数组最右边,向左遍历。 如果两个指针指向元素的和等于给定值,那么它们就是我们要的结果。
- 如果两个指针指向元 素的和小于给定值,我们把左边的指针右移一位,使得当前的和增加一点。如果两个指针指向元 素的和大于给定值,我们把右边的指针左移一位,使得当前的和减少一点。
- 可以证明,对于排好序且有解的数组,双指针一定能遍历到最优解。证明方法如下:假设最 优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候,右指针已经移动到了 r; 此时两个指针指向值的和小于给定值,因此左指针会一直右移直到到达 l。同理,如果我们假设 在右指针在 r 右边的时候,左指针已经移动到了 l;此时两个指针指向值的和大于给定值,因此 右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于(l,r)之间,又因为不满足条 件时指针必须移动一个,所以最终一定会收敛在 l 和r。
AC
class Solution { |
LeetCode 88. MergeSortedArray(Easy)【玩转双指针】
题目描述
给定两个有序数组,把两个数组合并为一个。
解题思路
由于题目要求不借助第三个数组,合并到 nums1
上,就用尾指针,然后逐一比较,运用归并排序的思想来解答。最后判断一下 nums2
数组是否还存在元素,若存在,直接放入(因为数组是有序的)。
AC
class Solution { |
LeetCode 142. Linked List Cycle II【快慢指针】(Floyd判圈法)
题目描述
给定一个链表,如果有环路,找出环路的开始点。
解题思路
对于链表找环路的问题,有一个通用的解法——快慢指针(Floyd判圈法)。给定两个指针, 分别命名为 slow 和 fast,起始位置在链表的开头。每次 fast 前进两步,slow 前进一步。如果 fast 可以走到尽头,那么说明没有环路;如果fast可以无限走下去,那么说明一定有环路,且一定存 在一个时刻slow和fast相遇。当slow和fast第一次相遇时,我们将fast重新移动到链表开头,并 让slow和fast每次都前进一步。当slow和fast第二次相遇时,相遇的节点即为环路的开始点。
AC
/** |
LeetCode 76. 最小覆盖子串 【滑动窗口】
题目描述
给定两个字符串 S 和T,求 S 中包含T 所有字符的最短连续子字符串的长度,同时要求时间 复杂度不得超过O(n)。
解题思路
需要思考以下四个问题:
1、当移动 right
扩大窗口,即加入字符时,应该更新哪些数据?
2、什么条件下,窗口应该暂停扩大,开始移动left
缩小窗口?
3、当移动 left
缩小窗口,即移出字符时,应该更新哪些数据?
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?
如果一个字符进入窗口,应该增加 window
计数器;如果一个字符将移出窗口的时候,应该减少 window
计数器;当 cnt
满足 need
时应该收缩窗口;应该在收缩窗口的时候更新最终结果。
需要注意的是,当我们发现某个字符在window
的数量满足了need
的需要,就要更新 valid,表示有一个字符已经满足要求。而且,你能发现,两次对窗口内数据的更新操作是完全对称的。
当 cnt == need.size()
时,说明T
中所有字符已经被覆盖,已经得到一个可行的覆盖子串,现在应该开始收缩窗口了,以便得到「最小覆盖子串」。
移动 left
收缩窗口时,窗口内的字符都是可行解,所以应该在收缩窗口的阶段进行最小覆盖子串的更新,以便从可行解中找到长度最短的最终结果。
AC
class Solution { |
LeetCode 567. 字符串的排列 【滑动窗口】
题目描述
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
注意:
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
解题思路
这道题依旧是可以用滑动窗口算法来做,基本上与模板没什么太大差别。
需要修改的小地方:
1、本题移动 left 缩小窗口的时机是窗口大小 大于或等于
s1.size() 时。
2、当发现 cnt == need.size() 时,就说明窗口中就是一个合法的排列,所以立即返回 true。
AC
class Solution { |
LeetCode 438. 找到字符串中所有字母异位词【滑动窗口】
题目描述
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
说明:
字母异位词指字母相同,但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:
输入:
s: “abab” p: “ab”
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。
解题思路
输入一个串 S,一个串 T,找到 S 中所有 T 的排列,返回它们的起始索引。
这道题依旧是可以用滑动窗口算法来做,基本上与模板没什么太大差别。
需要修改的小地方:
1、本题移动 left 缩小窗口的时机是窗口大小 大于或等于 s1.size() 时。
2、当发现 cnt == need.size() 时,就说明窗口中就是一个合法的排列,添加对应索引值(即 left
值)
AC
class Solution { |
LeetCode 3. 无重复字符的最长子串【滑动窗口】
题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
- 请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
解题思路
当 window[c] 值大于 1 时,说明窗口中存在重复字符,不符合条件,就该移动 left 缩小窗口。当收缩窗口完成后,此时就不存在重复元素了,判断最长子串即可。
AC
class Solution { |
LeetCode 69. x 的平方根 【二分查找】
题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
- 由于返回类型是整数,小数部分将被舍去。
解题思路
我们可以把这道题想象成,给定一个非负整数 a,求 f(x) = x^2^ −a = 0 的解。因为我们只考虑 x ≥ 0,所以 f(x)在定义域上是单调递增的。考虑到 f(0) = −a ≤ 0,f(a) = a^2^ −a ≥ 0,我们可以对[0,a]区间使用二分法找到 f(x) = 0的解。
注意,在以下的代码里,为了防止除以0,我们把 a = 0的情况单独考虑,然后对区间[1,a] 进行二分查找。
使用了左闭右闭的写法。
AC
class Solution { |
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置【二分查找】
题目描述
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
解题思路
可以看作是自己实现 C++ 里的 lower_bound 和 upper_bound 函数。
AC
class Solution { |
LeetCode 81. 搜索旋转排序数组 II【二分查找】
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
解题思路
本题是需要使用二分查找,怎么分是关键,举个例子:
第一类
10111 和 11101 这种。此种情况下 nums[start] == nums[mid],分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类
2 3 4 5 6 7 1 这种,也就是 nums[start] < nums[mid]。此例子中就是 2 < 5;
这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。
第三类
6 7 1 2 3 4 5 这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2;
这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找,否则去前半部分找。
AC
class Solution { |
LeetCode 215. 数组中的第K个最大元素 【小顶堆与快速选择】
题目描述
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
解题思路
- 小顶推方式
建一个只能存K个数字的小顶堆,超过K时候,每加进来一个,堆顶就要弹出一个。数组遍历完,最终堆顶的元素就是第K大的(堆里其他元素都比他还要大)。
- 快速选择方式
快速选择算法 的平均时间复杂度为 O(N)。就像快速排序那样,本算法也是 Tony Hoare 发明的,因此也被称为 Hoare选择算法。
本方法大致上与快速排序相同。简便起见,注意到第 k 个最大元素也就是第 N - k 个最小元素,因此可以用第 k 小算法来解决本问题。
首先,我们选择一个枢轴,并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。
为了实现划分,沿着数组移动,将每个元素与枢轴进行比较,并将小于枢轴的所有元素移动到枢轴的左侧。
这样,在输出的数组中,枢轴达到其合适位置。所有小于枢轴的元素都在其左侧,所有大于或等于的元素都在其右侧。
这样,数组就被分成了两部分。如果是快速排序算法,会在这里递归地对两部分进行快速排序,时间复杂度为 O(NlogN)。
而在这里,由于知道要找的第 N - k 小的元素在哪部分中,我们不需要对两部分都做处理,这样就将平均时间复杂度下降到 O(N)。
最终的算法十分直接了当 :
随机选择一个枢轴。
使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边,大于等于枢轴的元素移到右边。
比较 pos 和 N - k 以决定在哪边继续递归处理。
! 注意,本算法也适用于有重复的数组
AC
采用小顶推方式:
class Solution { |
采用快速选择方式:
class Solution { |
LeetCode 347. 前 K 个高频元素【桶排序】
题目描述
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
解题思路
顾名思义,桶排序的意思是为每个值设立一个桶,桶内记录这个值出现的次数(或其它属 性),然后对桶进行排序。针对样例来说,我们先通过桶排序得到三个桶[1,2,3,4],它们的值分别 为[4,2,1,1],表示每个数字出现的次数。
紧接着,我们对桶的频次进行排序,前k 大个桶即是前k 个频繁的数。这里我们可以使用各种 排序算法,甚至可以再进行一次桶排序,把每个旧桶根据频次放在不同的新桶内。针对样例来说, 因为目前最大的频次是 4,我们建立 [1,2,3,4] 四个新桶,它们分别放入的旧桶为 [ [3,4],[2],[],[1] ], 表示不同数字出现的频率。
最后,我们从后往前遍历,直到找到 k 个旧桶。
AC
class Solution { |
LeetCode 695. 岛屿的最大面积【dfs】
题目描述
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
解题思路
十分标准的搜索题,用来练手深度优先搜索。
AC
class Solution { |
LeetCode 547. 朋友圈【dfs】
题目描述
班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。
给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
注意:
- N 在[1,200]的范围内。
- 对于所有学生,有M[i][i] = 1。
- 如果有M[i][j] = 1,则有M[j][i] = 1。
解题思路
dfs。朋友圈的个数等于连通块的个数,搜索一遍就累加一次即可。
AC
class Solution { |
LeetCode 417. 太平洋大西洋水流问题【dfs】
题目描述
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。
提示:
输出坐标的顺序不重要
m 和 n 都小于150
示例:
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
解题思路
虽然题目要求的是满足向下流能到达两个大洋的位置,如果我们对所有的位置进行搜索,那么在不剪枝的情况下复杂度会很高。
因此我们可以反过来想,从两个大洋开始向上流,这样我们只需要对矩形四条边进行搜索。搜索完成后,只需遍历一遍矩阵,满足条件的位置即为两个大洋向上流都能到达的位置。
AC
class Solution { |
LeetCode 46. 全排列【dfs】
题目描述
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路
怎样输出所有的排列方式呢?对于每一个当前位置 i,我们可以将其于之后的任意位置交换, 然后继续处理位置 i+1,直到处理到最后一位。
为了防止我们每此遍历时都要新建一个子数组储存位置i之前已经交换好的数字,我们可以利用回溯法,只对原数组进行修改,在递归完成后再修改回来。
我们以样例[1,2,3]为例,按照这种方法,我们输出的数组顺序为[[1,2,3],[1,3,2],[2,1,3],[2,3,1], [3,1,2],[3,2,1]],可以看到所有的排列在这个算法中都被考虑到了。
AC
class Solution { |