653. Two Sum IV - Input is a BST
solution 1: use set.
solution 2: use the fact that a sorting array is given.
[LeetCode] Challenge log 374
374. Guess Number Higher or Lower
No explainaton needed. It is a good code template for BS.
[LeetCode] Challenge log 658
658. Find K Closest Elements
It has some problems with test cases so can’t get it ac. Whatever, I have the correct code anyway…
- Binary search to locate the position
- Create a len(k) sliding window start from the position, slide it left until the furthest distance starts to increase.
[LeetCode] Challenge log 719
719. Find K-th Smallest Pair Distance
Related problem: #378, # 668. The difference is how to count how many smaller. To count quickly, you need to:
- Sort the array first.
- Do a while loop within a for loop; Each time the element that just gives enough distance to the one that in the outer loop; For next iteration, start looking from the last element found to save time.
[LeetCode] Challenge log 668
668. Kth Smallest Number in Multiplication Table
Similar to #378: http://localhost:4000/2018/06/21/LeetCode-Challenge-log-378/, except now we can count how many smaller faster in O(n) time! There is also two tricks to achieve 99% beaten:
- Switch m and n if m > n. So it can count faster
- Do not use build-in min() but if statement. Too many function calls slows down the speed.
[LeetCode] Challenge log 378
378. Kth Smallest Element in a Sorted Matrix
Similar to #373: https://marcopolocai.github.io/2018/06/20/LeetCode-Challenge-log-373/.
However, because all we want is just the kth number, we can use a binary-search-like approach to make a guess and count if it has k-1 lower numbers. It is a faster approach but very tricky to implement, as you has to be very careful on the boundary.
Understanding _ in Python
When reading the python docs and source codes, I see there is lots of usage of “___” in naming and other places. So I google a bit and find two great articles for explanation. Here are the links and thank Chevalier and Shahriar for their great summaries :
[LeetCode] Challenge log 373
373. Find K Pairs with Smallest Sums
Tried many methods. Take it as a review to heap and piority queue…
- qsort —> time limit exceed
- build min heap, pop the first k pairs —> ac, beat 9%
- use max heap to maintain the k min pairs —> ac, beat 14%
- use the fact that both arrays are presorted, and piority queue to maintain the candidates —> ac, beat 52%
- use built-in library “heapq” —> ac, beat 74%
- use set, instead of array to mark visted slots —> ac, beat 95%