腾讯面试50题（一）

发表于 | 分类于 | 页面访问量 次
字数统计: 2.2k 字 | 阅读时长 ≈ 8 分钟

开启新的篇章，LeetCode上的腾讯精选50题。日刷已经完成22题。一周之内完成任务，加上汇总。压力应该不小。不过，没有那么多时间留给你。暂且定为6兔1龟。

题号 难易度
15 三数之和 48 23.0% 中等
16 最接近的三数之和 20 41.1% 中等
2 两数相加 139 34.6% 中等
121 买卖股票的最佳时机 18 50.1% 简单
1 122 买卖股票的最佳时机 II 22 53.9% 简单 C
18 124 二叉树中的最大路径和 12 35.9% 困难
70 爬楼梯 31 45.7% 简单 B-
11 盛最多水的容器 31 56.2% 中等
2 217 存在重复元素 17 48.8% 简单 D
3 237 删除链表中的节点 14 74.5% 简单 D
4 89 格雷编码 14 64.7% 中等 B+
5* 160 相交链表 17 44.6% 简单 B+
6 215 数组中的第K个最大元素 25 57.3% 中等 B
7 230 二叉搜索树中第K小的元素 19 64.7% 中等 C+
8 146 LRU缓存机制 16 41.4% 中等 A-
9 141 环形链表 18 40.5% 简单 D
10 142 环形链表 II 13 40.8% 中等 C+
14 最长公共前缀 43 33.8% 简单
5 最长回文子串 46 25.6% 中等
16 235 二叉搜索树的最近公共祖先 19 59.6% 简单 C
17 236 二叉树的最近公共祖先 12 55.3% 中等 C+
11* 169 求众数 25 59.8% 简单 C
15 104 二叉树的最大深度 31 69.5% 简单 D
53 最大子序和 41 45.7% 简单
4 寻找两个有序数组的中位数 55 35.3% 困难
12 88 合并两个有序数组 39 44.4% 简单 C
21 合并两个有序链表 41 55.3% 简单
23 合并K个排序链表 18 46.7% 困难
13 155 最小栈 20 49.0% 简单 C-
14 43 字符串相乘 25 39.5% 中等 B+
292 Nim 游戏 15 68.8% 简单
9 回文数 71 56.2% 简单
46 全排列 29 69.8% 中等
19 231 2的幂 16 46.3% 简单 D
20 238 除自身以外数组的乘积 12 61.3% 中等 C
26 删除排序数组中的重复项 42 44.8% 简单
7 整数反转 91 32.6% 简单
21 206 反转链表 30 62.4% 简单 C-
22 344 反转字符串 31 66.8% 简单 D-
23 557 反转字符串中的单词 III 23 66.0% 简单 D-
24 61 旋转链表 16 38.6% 中等 C+
33 搜索旋转排序数组 30 36.6% 中等
25 136 只出现一次的数字 28 61.7% 简单 D
148 排序链表 11 60.8% 中等
26* 54 螺旋矩阵 27 36.2% 中等 A-
27* 59 螺旋矩阵 II 23 73.3% 中等 A-
8 字符串转换整数 (atoi) 71 17.2% 中等
28* 78 子集 21 73.9% 中等 B
62 不同路径 22 54.5% 中等
20 有效的括号 67 38.7% 简单

122.买卖股票的最佳时机 II 思考的时候注意，当天卖当天买无影响。只要后一天比前一天数大，就可以迭代买卖。巧用zip()

217 存在重复元素 巧用set()去掉重复字母，直接比较长度。

237 删除链表中的节点 最简单的链表操作

89 格雷编码 有几种做法，遍历，循环，还有公式法i ^ i >> 1 for i in range(1 << n)。复杂性和鲁棒性依次递减

160 相交链表 理解题意，相交点的选取。方法使用的是将两个链形头尾相接成闭环。链表1的长度是x1+y，链表2的长度是x2+y，我们同时遍历链表1和链表2，到达末尾时，再指向另一个链表。则当两链表走到相等的位置时：x1+y+x2 = x2+y+x1。没交点则y=0, 结尾都指向None。

215 数组中的第K个最大元素 几种思路：暴力法直接排序，冒泡，小堆根，introselect（简称“内省选择”）是一个选择算法是一个混合型的quickselect和中位数的中值，其具有快速的平均性能和最佳的最坏情况下的性能。这种方法不是很好理解。暂且搁置。快排变形。

230 二叉搜索树中第K小的元素 开始接触二叉树的题，需要开个专题练习一下。常规方法是中序遍历。巧解是使用迭代器。chain 函数可以组合多个迭代器，islice 函数对迭代器做切片操作。

146 LRU缓存机制 哈希+双向链表。

扩展一下：self.od = collections.OrderedDict()

141 环形链表 哈希法和快慢指针。比较基础的一道环链题。

142 环形链表 II 哈希直接法，还是没什么变化。快慢指针使用了数学法，根据路径替换。

169 求众数 平易近人的一道题啊。很简单，官方解答方法很多。可以着重研究一下。

88 合并两个有序数组 使用方法：合并后排序，或者使用双指针从后往前。

注意问题：

我觉得这里的 Python 代码不应该使用切片操作，因为切片操作会导致列表拷贝，空间复杂度就不再是 O(1) 了。PS：尽管列表切片操作拷贝的只是列表中的对象的引用（也就是地址），并不拷贝对象本身，但通常一个引用/地址也会占用 4 或 8 个字节，相当于一个 int 或 double 类型，这部分空间占用是无法忽略的。

155 最小栈 借用一个辅助栈，来存储stack中最小值。

43 字符串相乘 模拟竖式乘法，将结果加一起。有大神使用快速数论变换(NTT)完全不懂。先搁置一下吧。

收获：ord() 函数是 chr() 函数（对于8位的ASCII字符串）或 unichr() 函数（对于Unicode对象）的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值，如果所给的 Unicode 字符超出了你的 Python 定义范围，则会引发一个 TypeError 的异常。

lstrip() 方法用于截掉字符串左边的空格或指定字符。

104 二叉树的最大深度 两种方法，递归法和迭代法。很简单的二叉树问题。

235 二叉搜索树的最近公共祖先 同样可以使用递归和迭代。

学习一下，同号判断和比较判断。

1
2
3
> while (root.val - p.val) * (root.val - q.val) > 0: 
>       root = (root.left, root.right)[p.val > root.val]
>

236 二叉树的最近公共祖先

map() 会根据提供的函数对指定序列做映射。

124 二叉树中的最大路径和 有了前面的铺垫，还是没什么问题的。路径就是左右返回加上根节点。判断路径如果<0时，直接返回0.

float（‘-inf’）无穷小

231 2的幂 

1
2
 return n > 0 and n & n - 1 == 0
#2 的幂的二进制形式最高位一定是1，其余为0

238 除自身以外数组的乘积 不可以用除法，有时间要求。使用的是计算矩阵的上三角和下三角，并且在计算过程中储存过程值，最终可以在遍历2遍nums下完成结果计算。

206 反转链表 比较常规的一道题。首先还是考虑，递归或者迭代。

  • 此解法为尾递归，即直接以递归返回值作为结果，一般编译器会做优化，避免多余的函数开栈操作，实现效果相当于迭代

344 反转字符串 双指针，直接交换即可。感动。 还有一个内置反向递归。reverse()

1
2
3
> for i in range(int(len(s)/2)):
>             s[i], s[-i-1] = s[-i-1], s[i]      #这种首位交换方式的表达方法值得学习一下。
>

557 反转字符串中的单词 III 两次[::-1]。一次分割换位，再一次整体字母换位。

61 旋转链表 k %= length + 1 关键点，就是拼接成环，找到断点。首尾相接，断点尾部指向None。

136 只出现一次的数字 最优解： 二进制异或，直接排除相同元素。

54 螺旋矩阵 常规做法需要耐心再看一遍。极简做法，感觉很棒~

59 螺旋矩阵 II 只是上一题的变形。其他上同。

78 子集 不错的一道题，适合细心钻研一下。多种解法。

1
2
3
4
> 调库排列组合
> from itertools import combinations
>         return sum([list(combinations(nums, i)) for i in range(len(nums) + 1)], [])
>

一轮兔刷已经完毕，又几道题需要细心琢磨一下。更详细的总结。

0%
undefined