Leetcode刷题记录帖

Apr. 20th 2018 --- 1 Problem

## 179. Largest Number (Medium)

### LCM (My solution)

Extend two strings to their lcm length then compare them.

### Connect

Compare (s1 + s2) with (s2 + s1).

### Faults:

1. **[WA]** Compare until one string ends is not enough.
2. **[WA]** The result maybe "00000..." but you should output "0" instead.

Apr. 21st 2018 --- 4 Problems

## 184. Department Highest Salary (Medium)

    SELECT D.Name AS Department ,E.Name AS Employee ,E.Salary
    FROM
        Employee E,
        (SELECT DepartmentId,max(Salary) as max FROM Employee GROUP BY DepartmentId) T,
        Department D
    WHERE E.DepartmentId = T.DepartmentId
    AND E.Salary = T.max
    AND E.DepartmentId = D.id

## 185. Department Top Three Salaries (Hard)

    SELECT D.Name AS Department, E.Name AS Employee, E.Salary
    FROM Department D, Employee E, Employee E2  
    WHERE D.ID = E.DepartmentId AND E.DepartmentId = E2.DepartmentId AND
    E.Salary <= E2.Salary
    GROUP BY D.ID,E.Name HAVING COUNT(DISTINCT E2.Salary) <= 3
    ORDER BY D.Name, E.Salary DESC

## 187. Repeated DNA Sequences (Medium)

Store the string into hash tables. Both HashSet or HashMap is enough.

## 188. Best Time to Buy and Sell Stock IV (Hard)

e[k] means how much we can earn if we had k transactions and finished the lastest one on day i.

e[k] = max{max(e[j][k - 1]) - prices[l]} (j < l < i)

However the input K maybe meaningless large. So we need to firgure out whats the largest number of transactions we could have? The answer is (prices.length / 2). In such a condition, there in no consecutive increasing prices in the input.

### Faults:

1. **[TLE]** K too large.
2. **[TLE]** K too large.
3. **[TLE]** K too large.

Apr. 22nd 2018 --- 4 Problems

## 820. Short Encoding of Words (Medium)

Arrays.sort()
String.endsWith(StringB)

## 821. Shortest Distance to a Character (Easy)

Scan forwards and backwards.

## 822. Card Flipping Game (Medium)

Problem description is crap.

Find the smallest number which doesn't appear on the front and back of the same card.

### Faults:

1. **[WA]** Crap description.
2. **[WA]** Crap description.

## 823. Binary Trees With Factors (Medium)

Dynamic programming.

wasy means the ways of binary trees with i-th (sorted) value as the root.

ways += ways[j] * ways[i / j];

Apr. 23rd 2018 --- 5 Problems

## 192. Word Frequency (Medium)

    cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{ print $2, $1 }'

https://leetcode.com/problems/wo ... My-simple-solution-(one-line-with-pipe)

## 194. Transpose File (Medium)

    awk '
    {
        for (i = 1; i <= NF; i++) {
            if(NR == 1) {
                s= $i;
            } else {
s = s " " $i;
            }
        }
    }
    END {
        for (i = 1; s != ""; i++) {
            print s;
        }
    }' file.txt

## 199. Binary Tree Right Side View (Medium)

Recursion.

Always keep updating because the node you visit later will always be on the right.

## 200. Number of Islands (Medium)

FloodFill.

## 201. Bitwise AND of Numbers Range (Medium)


    int offset = 0;
    while(m != n){
        m >>= 1;
        n >>= 1;
        offset++;
    }
    return m <<= offset;

### Faults:

1. **[TLE]**
2. **[TLE]**

Apr. 24th 2018 --- 3 Problems

## 207. Course Schedule (Medium)

First turn the input list of edges into Map from courses and List.

Then use topo sort with queue to proceed all courses. If the number of courses we polled out of queue equals to the number of courses, the answer is "true".

## 208. Implement Trie (Prefix Tree) (Medium)

Trie.

## 209. Minimum Size Subarray Sum (Medium)

Slide window.

Apr. 25th 2018 --- 3 Problems

## 210. Course Schedule II (Medium)

Same as #207.

### Faults:
1. **[CE]** Extra bracket.

## 211. Add and Search Word - Data structure design (Medium)

Same as #208.

## 212. Word Search II (Hard)

Search the trie while go through the board.
Break when there is no succeeding node in the trie.

### Faults:
1. **[WA]** Confusing DFS code.
1. **[WA]** Return before recover the array.

Apr. 26th 2018 --- 2 Problems

## 213. House Robber II (Medium)

Same as #198. Do the same process for twice, once rob the first houst, once not.

## 214. Shortest Palindrome (Hard)

Match string s with its reverse r.

The length of matched string till the last char of t will be the part of palindrome we could make use of. Add the left part.

follow lz的脚步！

Apr. 27th 2018 --- 1 Problem

## 215. Kth Largest Element in an Array (Medium)

### 1. QuickSort O(nlogn)
### 2. Heap O(nlogn)
### 3. QuickSelect O(n) https://en.wikipedia.org/wiki/Quickselect

水锦鲤 发表于 2018-4-27 01:24
follow lz的脚步！

谢谢 一起加油！ 最近事情太多一天也刷不了几道题……