刷题日记

生活所迫，同时也是锻炼大脑，接着刷题。

优先刷企业面试题库，先刷字节的，

2026.7.5

543 【easy】二叉树的直径，需要注意优化性能

412 【easy】FizzBuzz

14 【easy】最长公共前缀

使用string::substr方法即可。

2026.7.2

215 【medium】数组中的第k个元素

https://leetcode.cn/problems/kth-largest-element-in-an-array

题面：要求设计算法实现在n个数中查找第k大的元素，时间算法复杂度O(n).

注意事项：数组中可能有重复元素，相当于求数组排序后，从大到小第k个元素。

思路一：将所有元素加入multiset，然后从末尾开始往前遍历；但其实复杂度不是O(n)，是O(nlogn).

思路二：利用快排，每次划分后只对包含下标 n-k 那个元素的区间进行子递归。

使用快排也有2种思路,a.hoare partition双指针方法，需要注意如果选pivot时下标偏左，则应该用[left, rptr]和[rptr+1,right]这个划分。b.lomuto partition，选最优元素为pivot，把小于pivot的元素挨个放到左边。lomuto partition方法比hoare partition方法整体运行时间慢许多。