LeetCode Solutions | 201 - 300
202. Happy Number
Detect Cycles with a HashSet
Floyd's Cycle-Finding Algorithm
209. Minimum Size Subarray Sum
sliding window
calc prefix_sums[], for every prefix_sums[i] >= target find the bs_greatest_smaller_or_equal(0, i, prefix_sums[i] - target)
212. Word Search II
backtracking + trie with remove operation
215. Kth Largest Element in an Array
small heap of size k
quicksort
218. The Skyline Problem
从左到右扫描，用 Operation 记录每个房子的左上角和右上角，当 operation 使得当前最大高度变化时，记录
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct Operation {
position: i32,
building_height: i32,
building_no: usize,
operation_type: OperationType,
}
impl Ord for Operation {
fn cmp(&self, other: &Self) -> Ordering {
match self.position.cmp(&other.position) {
Ordering::Equal => match self.operation_type.cmp(&other.operation_type) {
Ordering::Equal => match self.operation_type {
OperationType::Enter => other.building_height.cmp(&self.building_height),
OperationType::Leave => self.building_height.cmp(&other.building_height),
},
ret => ret,
},
ret => ret,
}
}
}
220. Contains Duplicate III
fixed-size balacend binary search tree to store recent k values
bucket sort, check nearby and self bucket
227. Basic Calculator II
stack -> can be optimized to only use curr_num and prev_num
default curr_op to +
234. Palindrome Linked List
record all values
use fast/slower pointers to find the mid node then reverse the second half in-place
考虑这样的代码，我们以逆序输出节点的值
f curr =
f curr->next
print curr->val
若我们在外侧以正序记录节点的值进行对比则可以知道是否是回文的
每次 curr 返回的时候，front 向前一步
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* front = head;
function<bool(ListNode*)> f = [&](ListNode* curr) {
if (!curr) { return true; }
if (!f(curr->next)) { return false; }
if (curr->val != front->val) { return false; }
front = front->next;
return true;
};
return f(head);
}
};
241. Different Ways to Add Parentheses{href=}
for (let curr = i; curr <= j; curr += 1) {
if (is_op(curr)) {
for (const left of lvs) {
for (const right of rvs) {
const res = calc(expression[curr], left, right)
ret.push(res)
}
}
}
}
// besides this, you need to handle the base/edge cases:
// - no op in current range
// - if lvs.length == 0
dp TODO
243. Shortest Word Distance
hash
250. Count Univalue Subtrees
just iter
251. Flatten 2D Vector
the same with 341. Flatten Nested List Iterator
252. Meeting Rooms
sort then record right_most
257. Binary Tree Paths
iter
259. 3Sum Smaller
sort, then fix i, find two_sum smaller than target - nums[i] using two pointers
function<int(int, int)> two_sum_smaller_cnt = [&](int from, int target) {
if (xs.size() - from < 2) { return 0; }
int ret = 0;
int j = xs.size() - 1;
// for every `i`, find the right most `j`
// when `i` increases, `j` decreases/continues from current value
for (int i = from; i < j; i += 1) {
while (j > i && xs[i] + xs[j] >= target) { j -= 1; }
ret += j - i;
}
return ret
263. Ugly Number
mod 2 or 3 or 5, then check the quotient
266. Palindrome Permutation
return odd_cnt < 2
267. Palindrome Permutation II
266. Palindrome Permutation + 47. Permutations II
268. Missing Number
异或运算满足结合律，并且对一个数进行两次完全相同的异或运算会得到原来的数。
如果数组中没有丢失的数字，range (0 ^ 1 ^ ... ^ n) ^ arr_elements (0 ^ 1 ^ ... ^ n) = 0。如果有一个丢失的数字，将会得到该数字
利用等差数列求和公式先得出 0..=n 的和，再减去数组和将会得到目标数字；需注意溢出
277. Find the Celebrity
O(n^2): indeg/outdeg of every one
O(n): from 0 to n-1 if the candidate knows the next people, then the the next people becomes the candidate. then check the deg of the final candidate
283. Move Zeroes
两个指针，一个 j 指向当前查看的元素，一个 i 指向当前非 0 元素应该插入的位置。 每当检查到一个 0， j++，如果非零元素，插入 i，i++，j++。最后把 i 和她之后的位置全部置零
285. Inorder Successor in BST
do an inorder traversal
if p is guaranteed to exist: if go left, then mark current node as next, if go right, then do nothing, if equal, then go right then go left until null.
287. Find the Duplicate Number
遍历数组，将每个数字交换到它理应出现的位置上，下面情况不用换：
- 当前数字本就出现在理应的位置上，跳过，不用换。
- 当前数字理应出现的位置上，已经存在当前数字，说明出现重复，则返回该数字。
the same with 448. Find All Numbers Disappeared in an Array
295. Find Median from Data Stream
two heaps, the median will always be one of the top or half of the sum of the top of the two heaps
balanced binary search tree
300. Longest Increasing Subsequence
memorized recursion or dp
用一个数组 minimum_ending_with[len] 记录，长度为 len 的串最小可能结尾的数字
for i in 0..nums.len()
// 从右侧开始， `minimum_ending_with` 中找到 `nums[i]` 可接上的位置 `prev_len`
// 显然 `minimum_ending_with` 是递增的
// so this can be optimized using binary search
minimum_ending_with[prev_len + 1] =
min(minimum_ending_with[prev_len + 1], nums[i]);