Majority Number 系列

相关题目: Majority Number Majority Number II Majority Number III 感觉这三题比较 tricky。 Majority Number 解法的具体解释见 Boyer–Moore majority vote algorithm - Wikipedia, the free encyclopedia。以下是实现。 class »

Candy

相关题目: Candy | LeetCode OJ 这题考察 observation。 首先尝试了一个 $O(n \log n)$ 的解法,思路: 构建包含 (rating, index) 的 vector,然后 sort 一下, 复杂度 $O(n \log n) »

Shortest Palindrome 两题

在此给出两道与 Shortest Palindrome 主题相关的解题报告。相关题目: Shortest Palindrome | LeetCode OJ TopCoder Statistics - Problem Statement 后者可视为前者的 follow up。 Leetcode 214. Shortest Palindrome Given a string S, you »

H-Index I, II

相关题目: H-Index | LeetCode OJ H-Index II | LeetCode OJ H-Index 注意 LeetCode 给的 Hint: What are the possible values of h-index? A faster approach is to use »

Word Break I, II

相关题目: Word Break | LeetCode OJ Word Break II | LeetCode OJ Word Break, 一开始打算用 Backtracking 做, 但是 TLE 了. 折腾了许久, 才发现这题本质上是搜索, 存在重复的搜索状态, 遂用 DP 来解. 还有一题简单的 follow »

Meeting Room I, II

相关题目: Meeting Rooms Meeting Rooms II Meeting Rooms 简单题, 但是可以作为 sort 的使用范例. template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare »

Largest Rectangle in Histogram

Largest Rectangle in Histogram | LeetCode OJ 在 Historgram 中寻找 largest rectangle 有三种思路: Brute force 方法, 遍历所有可能的 (l, r), 在 inner loop 中更新一个 min height 的变量. 复杂度是 »

Trapping Rain Water I, II

Trapping Rain Water | LeetCode OJ Trapping Rain Water II | LeetCode OJ 这两题很有意思。其实本质上就是从边界的「最短木板」出发,然后追踪每个 cell 的 maxmin 边界,然后就可以得到 cell 周围(上下左右)的 cells »