Fork me on GitHub

Posted on

Description

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

Example:

1
2
Input: nums = [3,5,2,1,6,4]
Output: One possible answer is [3,5,1,6,2,4]

https://leetcode.com/problems/wiggle-sort/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int size = nums.size();
        if (size == 0|| size == 1) return;
        for (int i = 0; i < size - 1; ++i)
            if ((i % 2 == 1 && nums[i] < nums[i + 1]) || (i % 2 == 0 && nums[i] > nums[i + 1]) )
                swap(nums[i], nums[i + 1]);
        return;
    }
};

Posted on

Description

https://leetcode.com/problems/sparse-matrix-multiplication/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int a = A.size();
        int b = B.size();
        int c = B[0].size();
        unordered_map<int, unordered_map<int, int>> rowAMap;
        unordered_map<int, unordered_map<int, int>> columnBMap;
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < b; ++j) {
                if (A[i][j]) {
                   rowAMap[i][j] = A[i][j]; 
                }
            }
        }
        
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < b; ++j) {
                if (B[j][i]){
                    columnBMap[i][j] = B[j][i];
                }
            }
        }
        
        vector<vector<int>> ret(a, vector<int>(c, 0));
        for (auto& item1 : rowAMap) {
            int row = item1.first;
            for (auto& item2 : columnBMap) {
                int column = item2.first;
                int sum = 0;
                for (auto& item3 : item1.second){
                    sum += item2.second[item3.first] * item3.second;
                }
                ret[row][column] = sum;
            }
            
        }
        return ret;
        
    }
};

Posted on

Description

https://leetcode.com/problems/design-in-memory-file-system/description/

Solution

`
class Node {
public:
bool type; //true is file, false is directory
map<string, Node*> mapping;
string str;
string name;
Node (string fileName, bool isFile) {
name = fileName;
type = isFile;
}
};

class FileSystem {
private:
Node* root;
public:
FileSystem() {
root = new Node(“LLL”, false);
}

vector<string> ls(string path) {
    int size = path.size();
    Node* traverse = root;
    int index = 1;
    while (index < size) {
        int count = 0;
        while(index + count < size && path[index + count] != '/') ++count;
        string target = path.substr(index, count);

        index += count;
        ++index; //skip the '/'

        auto iter = traverse->mapping.find(target);
        if (iter == traverse->mapping.end()) return vector<string>();
        traverse = traverse->mapping[target];
    }
    vector<string> ret;
    //Is a file
    if (traverse->type)  {
        ret.push_back(traverse->name);
        return ret;
    }
    //Is a directory
    for (auto item : traverse->mapping) {
        ret.push_back(item.first);
    }
    return ret;
}


void mkdir(string path) {
    int size = path.size();
    if (size == 1) return;
    Node* traverse = root;
    int index = 1;
    while (index < size) {
        int count = 0;
        while(index + count < size && path[index + count] != '/') ++count;
        string target = path.substr(index, count);

        index += count;
        ++index; //skip the '/'

        auto iter = traverse->mapping.find(target);
        if (iter == traverse->mapping.end()) traverse->mapping[target] = new Node(target, false);
        traverse = traverse->mapping[target];
    }
    return;
}

void addContentToFile(string filePath, string content) {
    int size = filePath.size();
    if (size == 1) return;
    Node* traverse = root;
    int index = 1;
    while (index < size) {
        int count = 0;
        while(index + count < size && filePath[index + count] != '/') ++count;
        string target = filePath.substr(index, count);

        index += count;
        ++index; //skip the '/'

        auto iter = traverse->mapping.find(target);
        if (iter == traverse->mapping.end()) traverse->mapping[target] = new Node(target, true); //Add a new file
        traverse = traverse->mapping[target];
    }
    traverse->str += content;
    return;
}

string readContentFromFile(string filePath) {
    int size = filePath.size();
    if (size == 1) return string();
    Node* traverse = root;
    int index = 1;
    while (index < size) {
        int count = 0;
        while(index + count < size && filePath[index + count] != '/') ++count;
        string target = filePath.substr(index, count);

        index += count;
        ++index; //skip the '/'

        traverse = traverse->mapping[target];
    }
    return traverse->str;
}

};

/**

  • Your FileSystem object will be instantiated and called as such:
  • FileSystem obj = new FileSystem();
  • vector param_1 = obj.ls(path);
  • obj.mkdir(path);
  • obj.addContentToFile(filePath,content);
  • string param_4 = obj.readContentFromFile(filePath);
    */

Posted on

Description

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Example 1:

1
2
3
4
5
put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:

  1. There will be at most 300 operations of Put or Retrieve.
  2. Year ranges from [2000,2017]. Hour ranges from [00,23].
  3. Output for Retrieve has no order required.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Time {
public:
    int year;
    int month;
    int day;
    int hour;
    int minute;
    int second;
    bool operator<(const Time& t2) const {
        if (year != t2.year) return year < t2.year;
        if (month != t2.month) return month < t2.month;
        if (day != t2.day) return day < t2.day;
        if (hour != t2.hour) return hour < t2.hour;
        if (minute != t2.minute) return minute < t2.minute;
        if (second != t2.second) return second < t2.second;
        return false;
    }
    Time(string& s) {
        year = stoi(s.substr(0,4));
        month = stoi(s.substr(5, 2));
        day = stoi(s.substr(8, 2));
        hour = stoi(s.substr(11, 2));
        minute = stoi(s.substr(14, 2));
        second = stoi(s.substr(17, 2));
    }
};



class LogSystem {
private:
    map<Time, int> mapping;
public:
    LogSystem() {
        
    }
    
    void put(int id, string timestamp) {
        Time time(timestamp);
        mapping[time] = id;
    }
    
    vector<int> retrieve(string s, string e, string gra) {
        Time start(s);
        Time end(e);
        if (gra == "Second") return findKeys(start, end); 
        start.second = 0;
        end.second = 59;
        if (gra == "Minute") return findKeys(start, end);
        start.minute = 0;
        end.minute = 59;
        if (gra == "Hour") return findKeys(start, end);
        start.hour = 0;
        end.hour = 23;
        if (gra == "Day") return findKeys(start, end);
        start.day = 0;
        end.day = 30;
        if (gra == "Month") return findKeys(start, end);
        start.month = 0;
        end.month = 12;

        if (gra == "Year") return findKeys(start, end);
        start.year = 2000;
        end.year = 2018;
        return vector<int>();
    }
    
    vector<int> findKeys(Time& start, Time& end) {
        vector<int> ret;
        auto startIter = mapping.lower_bound(start);
        auto endIter = mapping.upper_bound(end);
        for(auto iter = startIter; iter != endIter; ++iter) ret.push_back(iter->second);
        return ret;
    }
};

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * vector<int> param_2 = obj.retrieve(s,e,gra);
 */

Posted on

Description

https://leetcode.com/problems/number-of-islands-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> ret;
        vector<int> roots(m * n, -1);
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int count = 0;
        for (auto& position : positions) {
            int x = position.first;
            int y = position.second;
            int pos = x * n + y;
            if (roots[pos] == -1) {
                roots[pos] = pos;
                count += 1;
            }
            for (auto& dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                int newPos = newX * n + newY;
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || roots[newPos] == -1) continue;
                int rootCur = findRoot(roots, pos);
                int rootNew = findRoot(roots, newPos);
                
                if (rootCur != rootNew) {
                    roots[rootCur] = rootNew;
                    --count;
                }
            }
            ret.push_back(count);
        }
    
        return ret;
    }
    
    int findRoot(vector<int>& roots, int pos) {
        stack<int> st;
        while (roots[pos] != pos) {
            pos = roots[pos];
            st.push(pos);
        }
        while(!st.empty()) {
            roots[st.top()] = pos;
            st.pop();
        }
        return pos;
    }
};

Posted on

Description

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except ‘#’, you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

  1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
  2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
  3. If less than 3 hot sentences exist, then just return as many as you can.
  4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Your job is to implement the following functions:

The constructor function:

AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data. Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.

Now, the user wants to input a new sentence. The following function will provide the next character the user types:

List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example:
Operation: AutocompleteSystem([“i love you”, “island”,”ironman”, “i love leetcode”], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:

Operation: input(‘i’)
Output: [“i love you”, “island”,”i love leetcode”]
Explanation:
There are four sentences that have prefix "i". Among them, “ironman” and “i love leetcode” have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, “i love leetcode” should be in front of “ironman”. Also we only need to output top 3 hot sentences, so “ironman” will be ignored.

Operation: input(‘ ‘)
Output: [“i love you”,”i love leetcode”]
Explanation:
There are only two sentences that have prefix "i ".

Operation: input(‘a’)
Output: []
Explanation:
There are no sentences that have prefix "i a".

Operation: input(‘#’)
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.

Note:

  1. The input sentence will always start with a letter and end with ‘#’, and only one blank space will exist between two words.
  2. The number of complete sentences that to be searched won’t exceed 100. The length of each sentence including those in the historical data won’t exceed 100.
  3. Please use double-quote instead of single-quote when you write test cases even for a character input.
  4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see here for more details.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#define TOP 3

class TrieNode {
public:
    map<char, TrieNode*> next;
    int wordCount;
    string currentStr;
    TrieNode() {
        wordCount = 0;
    }

};

class AutocompleteSystem {
private: 
    TrieNode* root;
    TrieNode* cur;
    string str;
public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        root = new TrieNode();
        cur = root;
        int size = times.size();
        for (int i = 0; i < size; ++i) {
            insertWord(sentences[i], times[i]);
        }
        
        traverse(root); //For testing
    }
    void traverse(TrieNode* root) {
        auto& mp = root->next;
        for (auto& item : mp) {
            traverse(item.second);
        }
    }
    
    void insertWord(string& word, int count) {
        auto current = root;
        int index = 0;
        int size = word.size();
        while(index < size) {
            char ch = word[index];
            if(current->next.find(ch) == current->next.end()) {
                current->next[ch] = new TrieNode();
            }
            ++index;
            current = current->next[ch];
        }
        current->wordCount += count;
        current->currentStr = word;
        return;
    }
    
    vector<string> input(char c) {
        vector<string> ret;
        if (c == '#') {
            cur->wordCount += 1;
            cur->currentStr = str;
            cur = root;
            str = "";
            return ret;
        }
        str += c;
        if(cur->next.find(c) == cur->next.end()) {
            cur->next[c] = new TrieNode();
        }
        cur = cur->next[c];

        map<int, list<string>> counter;
        
        fetchStr(cur, counter, 0);

        int remain = TOP;
        // for (auto& item : counter) {
        //     cout << item.first << ":";
        //     for (auto& str : item.second) {
        //         cout << str << ", ";
        //     }
        //     cout << endl;
        // }


        for (auto iter = counter.rbegin(); remain > 0 && iter != counter.rend(); ++iter) {
            auto iterStr = iter->second.begin();
            while (remain > 0 && iterStr != iter->second.end()) {
                ret.push_back(*iterStr);
                ++iterStr;
                --remain;
            }
        }
        cout << ret.size() << endl;
        for (auto& item : ret) {
            cout << item << ", ";
        }
        cout << endl;
        return ret;
    }

    void fetchStr(TrieNode* current, map<int, list<string>>& counter, int depth) {

        if (current->wordCount != 0) {
            list<string>& lis = counter[current->wordCount];
            auto iter = lis.begin();
            while (iter != lis.end() && current->currentStr > *iter) {
                ++iter;
            }
            lis.insert(iter, current->currentStr);
        }
        
        map<char, TrieNode*>& mp = current->next;
        for (auto& item : mp) {
            fetchStr(item.second, counter, depth + 1);
        }
        
        return;
    }

};

Posted on

Description

https://leetcode.com/problems/meeting-rooms-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        int size = intervals.size();
        if (size == 1) return 1;
        
        map<int, int> timer;
        for (auto& interval : intervals) {
            ++timer[interval.start];
            --timer[interval.end];
        }
        int currentHouse = 0, peak = 0;
        for (auto& item : timer) {
            currentHouse += item.second;
            peak = max(currentHouse, peak);
        }
        return peak;
    }
};

Posted on

Description

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        vector<bool> candidates(n, true);
        vector<vector<int>> know_matrix(n, vector<int>(n, -1));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (candidates[i] == false) break;
                if (getKnow(know_matrix, i, j)) {candidates[i] = false; break; }
                know_matrix[i][j] = 0;
                if (!getKnow(know_matrix, j, i)) {candidates[i] = false; break;}
                //j knows i means the j is not a celebrity.
                candidates[j] = false;
            }
            if (candidates[i] == true) return i;
        }
        return -1;
    }
    
    bool getKnow(vector<vector<int>>& matrix, int i, int j) {
        if (matrix[i][j] == -1) matrix[i][j] = knows(i, j);
        return matrix[i][j];
    }
};

Posted on

Description

https://leetcode.com/problems/alien-dictionary/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    void extractRules(string& word1, string& word2, unordered_map<char, unordered_set<char>>& rules, unordered_map<char, int>& counter) {
        int index = 0;
        int bound = min(word1.size(), word2.size());
        while(index < bound && word1[index] == word2[index]) {
            ++index;
        }
        if (index == bound) return;
        char left = word1[index];
        char right = word2[index];
        
        if(rules[left].find(right) == rules[left].end()) {
            rules[left].insert(right);
            ++counter[right];
        }
    }
    
    void fillCharacter(unordered_map<char, int>& counter, vector<string>& words) {
        for (string& word : words) {
            for(int index = 0; index < word.size(); ++index) {
                if (counter.count(word[index]) == 0) counter[word[index]] = 0;
            }   
        }
    }
    
    string alienOrder(vector<string>& words) {
        int size = words.size();
        string ret;
        if (size == 0) return ret;
        unordered_map<char, unordered_set<char>> rules;
        unordered_map<char, int> counter;
        
        fillCharacter(counter, words);
        
        for (int i = 0; i < size - 1; ++i){
            for (int j = i + 1; j < size; ++j) {
                string& word1 = words[i];
                string& word2 = words[j];
                extractRules(word1, word2, rules, counter);
            }
        }
        
        queue<char> que;
        for (auto iter = counter.begin(); iter != counter.end(); ++iter) {
            if (iter->second == 0) {
                ret += iter->first;
                que.push(iter->first);   
            }
        }
    
        
        while (!que.empty()) {
            char c = que.front();
            que.pop();
            unordered_set<char>& follows = rules[c];
            for (char ch : follows) {
                --counter[ch];
                if (counter[ch] == 0) {
                    ret += ch;
                    que.push(ch);
                }
            }
        }
        
        for (auto& iter : counter) if (iter.second != 0) return string();
    
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ret;
        serializeHelper(root, ret);
        cout << ret << endl;
        return ret;
    }
    
    void serializeHelper(TreeNode* root, string& ret) {
        if (root == NULL) {ret += '#'; return;}
        ret += to_string(root->val);
        ret += ',';
        serializeHelper(root->left, ret);
        serializeHelper(root->right, ret);
        return;   
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int index = 0;
        TreeNode* ret = deserializeHelper(data, index);
        return ret;
    }
    
    TreeNode* deserializeHelper(string& data, int& index) {
        if (index == data.size() || data[index] == '#') {
            ++index;
            return NULL;
        }
        int number = extractNumber(data, index);
        TreeNode* ret = new TreeNode(number);
        
        index += 1; //Skip the ','
        ret->left = deserializeHelper(data, index);
        ret->right = deserializeHelper(data, index);
        cout << number << " ";
        cout << index << endl;
        return ret;
    }
    
    int extractNumber(string& data, int& index) {
        int ret = 0;
        int sign = 1;
        if (data[index] == '-') {sign = -1; ++index; }
        while ('0'<=data[index] && '9'>=data[index]) {ret = ret * 10 + data[index] - '0'; ++index;}
        
        return ret * sign;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));