刷题记录帖子

609. Find Duplicate File in System

感觉这道题目的 follow up 特别有意思。

BFS vs DFS
BFS explores neighbors first. This means that files which are located close to each other are also accessed one after another. This is great for space locality and that's why BFS is expected to be faster. Also, BFS is easier to parallelize (more fine-grained locking). DFS will require a lock on the root node.

Very large files and false positives
For very large files we should do the following comparisons in this order:

compare sizes, if not equal, then files are different and stop here!
hash them with a fast algorithm e.g. MD5 or use SHA256 (no collisions found yet), if not equal then stop here!
compare byte by byte to avoid false positives due to collisions.
Have you used an IDE in remote development mode?
For example, CLion has some options on how to compare the local files with the remote server files and then decides to synchronize or not.

Complexity
Runtime - Worst case (which is very unlikely to happen): O(N^2 * L) where L is the size of the maximum bytes that need to be compared
Space - Worst case: all files are hashed and inserted in the hashmap, so O(H^2*L), H is the hash code size and L is the filename size

453. Minimum Moves to Equal Array Elements

len*(min+k)=sum+k*(len-1). ==> k=sum-min*len

462. Minimum Moves to Equal Array Elements II

This problem is deceptive in its simplicity. Ultimately, the value to which you want to set each element equal is the median of the sorted nums array. To come to this realization, we have to first think about the nature of the problem.

Let's consider a possible scenario in which we've decided that our target value is x which would take ans number of moves to complete. What would happen to ans if we increased x by 1? If we did, each element that is below the new x would have to spend another move to get up to x, but every element that is above the new x would have to spend one less move to get down to x.

This means that x should naturally move up if there are more elements above x than below. It also means the inverse, that x should move down if there are more elements below x than above. The natural outcome of this is that x will settle at a spot where there are the same number of elements on either side, which is the median value of nums.

https://leetcode.com/problems/mi ... ution-w-Explanation

102. Binary Tree Level Order Traversal

之前写过，这次 3 min 解决，给自己加个油，功不唐捐。

890        Find and Replace Pattern        Medium        5        Two Maps CrossCheck / One Map FingerPrint

485        Max Consecutive Ones

Easy 但是需要知道如何简洁地得到 code。

                               
414        Third Maximum Number        Easy        4        set, sort, a[-3] for third max

263        Ugly Number        Easy        3        Definiation of ugly number

LC 197

SQL to remember how to do

1. 
   
2. 
   
3. # Write your MySQL query statement below
   
4. SELECT
   
5.     weather.id AS 'id'
   
6. FROM
   
7.     weather
   
8.         JOIN
   
9.     weather w ON DATEDIFF(weather.recordDate, w.recordDate) = 1
   
10.         AND weather.Temperature > w.Temperature
    
11. ;
    
12. 
    

复制代码

118        Pascal's Triangle        Easy