Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

O(n) time
这道题的hashmap的key必须是余数（被除数）不能用商（数字）因为商可能相同但被除数不同，比如1/333小数部分开始都是0但是被除数是不一样的所以并不是循环节，真正的循环节首尾的被除数必须是一样的！

  1. 判断被除数是否为0，是0直接返回0
  2. 判断结果是否为负
  3. 先处理整数部分，如果余数为0，直接返回结果
  4. 处理小数部分，用一个hashmap维护小数部分每个数字的下标，方便后边插入左括号
  5. 如果找到重复的数字，看该数字是否为0，如果是0则没有循环节不需要插入括号
  6. 用hashmap找到需要插入左括号的位置
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
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string integer, decimal;
        if ((numerator ^ denominator) < 0) {
            integer += '-';
        }
        long n = labs(numerator), d = labs(denominator);
        integer += to_string(n / d);
        n %= d;
        if (0 == n) return integer;
        integer += '.';
        unordered_map<int, int> m; // key是余数，value是在小数部分插入左括号的可能位置的下标
        while (n > 0 && m.count(n) == 0) {
            m[n] = decimal.length();
            n *= 10;
            decimal += to_string(n / d);
            n %= d;
        }
        if (n == 0) return integer + decimal;
        decimal.insert(m[n], "(");
        return integer + decimal + ")";
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 279 Reading time ≈ 1 mins.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int prev = INT_MIN;
        int res = 0;
        int cnt = 0;
        for (int curr : nums) {
            if (prev < curr) {
                ++cnt;
            } else {
                cnt = 1;
            }
            prev = curr;
            res = max(res, cnt);
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.9k Reading time ≈ 3 mins.

Trie+backtracking
把字典先转成trie树，然后利用trie树来dfs遍历board

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
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty() || board[0].empty()) return {};
        TrieNode *root = new TrieNode;
        for (const auto &w : words) {
            insert(root, w);
        }
        vector<string> res;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                dfs(root, board, i, j, dy, dx, res);
            }
        }
        return res;
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        string w; // 这里存单词，空间换时间
    };

    void insert(TrieNode *p, const string &word) {
        for (char c : word) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->w = word;
    }

    // p是当前TrieNode，board[i][j]是下一个字符，要检查的就是p的children里有没有board[i][j]
    void dfs(TrieNode *p, vector<vector<char>> &board, int i, int j, int dy[], int dx[], vector<string> &res) {
        if (i < 0 || j < 0 || i == board.size() || j == board[0].size() || board[i][j] == '#' || !p->children[board[i][j] - 'a']) return;
        char c = board[i][j];
        p = p->children[c - 'a'];
        if (!p->w.empty()) {
            res.push_back(p->w);
            p->w.clear(); // 这里一定要清空，因为board里面一个单词可能会有多个occurrence，为了防止反复找到该单词后添加到答案里，找到以后就改成false，这样下次即便再找到了也不会再往答案里添加了，另外这里不能返回，要继续找，有可能前缀会被复用
        }
        board[i][j] = '#';
        for (int k = 0; k < 4; ++k) {
            dfs(p, board, i + dy[k], j + dx[k], dy, dx, res);
        }
        board[i][j] = c;
    }
};
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
class Solution {
public:
    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        string w;
    };
    TrieNode *root = nullptr;
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty() || board[0].empty() || words.empty()) return {};
        m = board.size(), n = board[0].size();
        root = new TrieNode;
        for (auto &w : words) {
            insert(w);
        }
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                dfs(board, r, c, root);
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& board, int r, int c, TrieNode *p) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] == '#' || !p->children[board[r][c] - 'a']) return;
        char ch = board[r][c];
        p = p->children[ch - 'a'];
        if (!p->w.empty()) {
            res.push_back(p->w);
            p->w.clear();
        }
        board[r][c] = '#';
        dfs(board, r + 1, c, p);
        dfs(board, r - 1, c, p);
        dfs(board, r, c + 1, p);
        dfs(board, r, c - 1, p);
        board[r][c] = ch;
    }

    void insert(const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->w = s;
    }

    int m, n;
    vector<string> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 680 Reading time ≈ 1 mins.

backtracking O(27) time 即O(34)
每一段都有3种可能，总共4段，遍历所有可能即为27种

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
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        dfs(s, "", 4);
        return res;
    }

    void dfs(string_view s, string &&a, int dots) { // 这里a用的value copy省事
        if (dots == 0) {
            if (s.empty()) { // 如果s不为空说明输入的字符串过长
                a.pop_back();
                res.push_back(a);
            }
            return;
        }
        string str;
        for (int i = 0; i < min((int)s.length(), 3); ++i) {
            str += s[i];
            if (str.length() > 1 && str[0] == '0') break; // 检查合法性
            if (stoi(str) > 255) break;
            dfs(s.substr(i + 1), a + str + '.', dots - 1); // 这里append str以后不好弹出来实现回溯，所以直接用value copy就不弹出了
        }
    }

    vector<string> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 824 Reading time ≈ 1 mins.

bfs O(mn) time O(mn) space
这道题的意思是球一直滚到撞墙才能停下换方向
bfs可以避免不必要的stackoverflow

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
class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        unordered_set<int> s{start[0] * n + start[1]}; // 先放起点去重
        queue<vector<int>> q;
        q.push(start);
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto v = q.front(); q.pop();
            if (v == destination) return true;
            for (int i = 0; i < 4; ++i) {
                int r = v[0], c = v[1];
                while (0 <= r && r < m && 0 <= c && c < n && maze[r][c] == 0) {
                    r += dr[i];
                    c += dc[i];
                }
                r -= dr[i];
                c -= dc[i];
                if (!s.count(r * n + c)) {
                    s.insert(r * n + c);
                    q.push({r, c});
                }
            }
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

sweep line O(nlogn)
使用map记录事件，然后遍历map进行事件处理
用一个multiset来从高到低维护所有楼高度的『开始』和『结束』，遇到开始则加入，遇到结束则删除（只删除一个instance），每次遇到『新高』（有可能是开始，也有可能是结束，每次都要先调整multiset之后再从multiset开头取出来『新高』），然后和之前记录的高度对比，如果一样则忽略，否则要记录下来并更新记录

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
class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, vector<pair<int, bool>>> m; // 用map记录所有『事件』用一个bool来表示楼的左边还是右边（开始还是结束）
        for (const auto &b : buildings) {
            m[b[0]].emplace_back(b[2], true);
            m[b[1]].emplace_back(b[2], false);
        }
        multiset<int, greater<int>> s; // set不支持duplicate，priority_queue不支持删除任一元素，所以只能用multiset，从高到低记录每个高度的楼的左边和右边
        int pre = 0;
        vector<pair<int, int>> res;
        for (const auto &p : m) {
            for (const auto &pp : p.second) { // 遍历每个位置的所有可能高度（『事件』），『开始』则向multiset里添加新高度，否则从中删除一个copy
                if (pp.second) { // 遇到『新高』则加入multiset
                    s.emplace(pp.first);
                }
                else {
                    s.erase(s.find(pp.first)); // 遇到某个楼的右边『结束』则从multiset删除指定iterator，不会影响其他相同元素
                }
            }
            int h = s.empty() ? 0 : *s.begin();
            if (h != pre) { // 如果当前位置有『新高』，则跟之前的高度对比并记录下来
                res.emplace_back(p.first, h);
                pre = h;
            }
        }
        return res;
    }
};
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
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, vector<pair<int, bool>>> m;
        for (const auto &b : buildings) {
            m[b[0]].emplace_back(b[2], true);
            m[b[1]].emplace_back(b[2], false);
        }
        vector<vector<int>> res;
        multiset<int, greater<int>> s;
        int prev = -1;
        for (const auto &[k, v] : m) {
            for (auto [h, isL] : v) {
                if (isL) {
                    s.insert(h);
                } else {
                    s.erase(s.find(h));
                }
            }
            int mx = s.empty() ? 0 : *begin(s);
            if (mx != prev) {
                res.push_back({k, mx});
                prev = mx;
            }
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 997 Reading time ≈ 1 mins.

union-find O(m*n+k) time O(m*n) space

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
class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        parent.resize(m * n, -1); // 一定要用-1因为不是每个位置都是岛
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        vector<int> res;
        for (const auto &p : positions) {
            int x = p[0] * n + p[1];
            if (parent[x] == -1) { // 竟然有重复的position。。。
                parent[x] = x;
                ++cnt;
                for (int i = 0; i < 4; ++i) {
                    if (isValid(p[0] + dr[i], p[1] + dc[i], m, n)) {
                        merge(x, (p[0] + dr[i]) * n + p[1] + dc[i]);
                    }
                }
            }
            res.push_back(cnt);
        }
        return res;
    }

    bool isValid(int r, int c, int m, int n) {
        return 0 <= r && r < m && 0 <= c && c < n && parent[r * n + c] != -1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            --cnt;
            parent[px] = py;
        }
    }

    int cnt = 0;
    vector<int> parent;
};

Posted on Edited on In Disqus:
Symbols count in article: 630 Reading time ≈ 1 mins.

O(n)
遍历每个数的每一位，统计每一位0和1的个数，累加乘积即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int totalHammingDistance(vector<int> &nums) {
        int res = 0;
        for (int i = 0, n = nums.size(); i < 32; i++) {
            int cnt = 0;
            for (int x : nums) {
                cnt += (x >> i) & 1;
            }
            res += cnt * (n - cnt);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ret = 0;
        int not_zero = 1;
        while (not_zero) {
            not_zero = 0;
            int counter[2] = {0};
            for (auto& num : nums) {
                ++counter[num & 1];
                num >>= 1;
                not_zero += (num != 0);
            }
            ret += (counter[0] * counter[1]);
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(1) time O(1) space

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
class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) : i(begin(v)), e(end(v)), j(0) {
        adjust();
    }

    int next() {
        int res = i->at(j++);
        adjust();
        return res;
    }

    bool hasNext() {
        return i != e;
    }

    void adjust() {
        while (i != e && j >= i->size()) {
            ++i;
            j = 0;
        }
    }

    vector<vector<int>>::iterator i, e;
    int j;
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
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
class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) : i(begin(v)), e(end(v)), j(0) {

    }

    int next() {
        hasNext(); // adjustment
        return i->at(j++);
    }

    bool hasNext() {
        while (i != e && j >= i->size()) {
            ++i;
            j = 0;
        }
        return i != e;
    }

    vector<vector<int>>::iterator i, e;
    int j;
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
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
class Vector2D {
public:
    Vector2D(vector<vector<int>>& v) : it1(begin(v)), e(end(v)) {
        while (hasNext() && it1->empty()) {
            ++it1;
        }
        it2 = hasNext() ? it1->begin() : it2;
    }

    int next() {
        int res = *it2++;
        while (it2 == it1->end() && ++it1 != e) {
            it2 = it1->begin();
        }
        return res;
    }

    bool hasNext() {
        return it1 != e;
    }

    vector<vector<int>>::iterator it1, e;
    vector<int>::iterator it2;
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(v);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

greedy+backtracking O(n!) time O(n) space
这道题的关键点是要发现贪心去放有可能一次性放不进去，所以必须要回溯反复试数

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
class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        this->n = n;
        res.resize(n + n - 1);
        dfs(0);
        return res;
    }

    bool dfs(int i) {
        if (i == size(res)) return true;
        if (res[i] != 0) return dfs(i + 1);
        for (int x = n; x > 0; --x) {
            if (used & (1 << x)) continue;
            int offset = x == 1 ? 0 : x;
            if (i + offset < size(res) && res[i + offset] == 0) {
                res[i] = res[i + offset] = x;
                used ^= 1 << x;
                if (dfs(i + 1)) return true;
                used ^= 1 << x;
                res[i] = res[i + offset] = 0;
            }
        }
        return false;
    }

    int n, used = 0;
    vector<int> res;
};
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
class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        this->n = n;
        res.resize(n + n - 1);
        used.resize(n + 1);
        dfs(0);
        return res;
    }

    bool dfs(int i) {
        if (i == size(res)) return true;
        if (res[i] != 0) return dfs(i + 1);
        for (int x = n; x > 0; --x) {
            if (used[x]) continue;
            int offset = x == 1 ? 0 : x;
            if (i + offset < size(res) && res[i + offset] == 0) {
                res[i] = res[i + offset] = x;
                used[x] = true;
                if (dfs(i + 1)) return true;
                used[x] = false;
                res[i] = res[i + offset] = 0;
            }
        }
        return false;
    }

    int n;
    vector<int> res;
    vector<bool> used;
};
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
class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        this->n = n;
        res.resize(n + n - 1);
        used.resize(n + 1);
        dfs(0);
        return res;
    }

    bool dfs(int i) {
        if (i == size(res)) return true;
        if (res[i] != 0) return dfs(i + 1);
        for (int x = n; x > 0; --x) {
            if (used[x]) continue;
            if (x == 1) {
                res[i] = x;
                used[x] = true;
                if (dfs(i + 1)) return true;
                used[x] = false;
                res[i] = 0;
            } else if (i + x < size(res) && res[i + x] == 0) {
                res[i] = res[i + x] = x;
                used[x] = true;
                if (dfs(i + 1)) return true;
                used[x] = false;
                res[i] = res[i + x] = 0;
            }
        }
        return false;
    }

    int n;
    vector<int> res;
    vector<bool> used;
};