Mind palace

some thoughts

0%

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

O(nx * nx * ny) time O(nx * ny) space
当nx趋近于n时时间复杂度上界是O(n2)所以理论上更优
把所有点按序存起来，先按x轴枚举任意两列，再对这两列依次比较相邻两行，找到最小矩形即可

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:
    int minAreaRect(vector<vector<int>>& points) {
        map<int, set<int>> m; // 排序+去重
        for (const auto &p : points) {
            m[p[0]].insert(p[1]);
        }
        int res = INT_MAX;
        for (auto i = begin(m); i != end(m); ++i) {
            auto &&si = i->second;
            if (si.size() == 1) continue;
            for (auto j = next(i); j != end(m); ++j) {
                auto &&sj = j->second;
                if (sj.size() == 1) continue;
                bool found_one = false;
                int prev = -1;
                for (int y : sj) {
                    if (!si.count(y)) continue;
                    if (prev > -1) {
                        res = min(res, (j->first - i->first) * (y - prev));
                    }
                    prev = y;
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

O(n2) time O(n) space
用对角线上两点找符合要求的矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<int> s;
        for (const auto &p : points) {
            s.insert(p[0] * 40001 + p[1]); // 把所有点用int来表示
        }
        int res = INT_MAX;
        int n = points.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (points[i][0] == points[j][0] || points[i][1] == points[j][1]) continue;
                if (s.count(points[i][0] * 40001 + points[j][1]) && s.count(points[j][0] * 40001 + points[i][1])) { // 如果对角线两个点能找到对应的组成矩形的反对角线的另外两个点
                    res = min(res, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
                }
            }
        }
        return res == INT_MAX ? 0 : 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
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        auto cmp = [](const vector<int> &a, const vector<int> &b){
            return a[0] < b[0] || a[0] == b[0] && a[1] < b[1];
        };
        sort(begin(points), end(points), cmp);
        vector<int> xs;
        unordered_map<int, vector<int>> m;
        for (const auto &p : points) {
            m[p[0]].push_back(p[1]);
            if (xs.empty() || xs.back() != p[0]) {
                xs.push_back(p[0]);
            }
        }
        int res = INT_MAX;
        int nx = xs.size();
        for (int i = 0; i < nx; ++i) {
            if (m[xs[i]].size() == 1) continue;
            for (int j = i + 1; j < nx; ++j) {
                if (m[xs[j]].size() == 1) continue;
                res = min(res, helper(m, xs[i], xs[j]));
            }
        }
        return res == INT_MAX ? 0 : res;
    }

    int helper(unordered_map<int, vector<int>> &m, int a, int b) {
        unordered_set<int> s(begin(m[a]), end(m[a]));
        int n = m[b].size();
        int diff = INT_MAX;
        for (int i = 0; i < n; ++i) {
            if (!s.count(m[b][i])) continue;
            int j = i + 1;
            while (j < n && !s.count(m[b][j])) ++j;
            if (j == n) break;
            diff = min(diff, m[b][j] - m[b][i]);
            i = j - 1;
        }
        return diff == INT_MAX ? diff : (b - a) * diff;
    }
};

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

O(n) time O(1) space
双指针
如果抛物线parabola开口朝上（a > 0）则取较大的那个数从后往前放
如果抛物线开口朝下（a < 0）则取较小的那个数从前往后放
可以看做977. Squares of a Sorted Array的followup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size(), l = 0, r = n - 1, i = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        auto f = [a, b, c](int x) { return (a * x + b) * x + c; };
        while (l <= r) { // 注意这里必须是l <= r因为l和r相遇时的那个数也要处理
            int fl = f(nums[l]), fr = f(nums[r]), mn = min(fl, fr), mx = max(fl, fr);
            if (a < 0) {
                res[i++] = mn;
                mn == fl ? ++l : --r;
            } else {
                res[i--] = mx;
                mx == fl ? ++l : --r;
            }
        }
        return res;
    }
};
Read more »

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

two pointer O(n) time O(1) space
跟360. Sort Transformed Array不完全一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = size(A);
        vector<int> res(n);
        for (int l = 0, r = n - 1, i = n - 1; l <= r; --i) {
            if (abs(A[l]) < abs(A[r])) {
                res[i] = A[r] * A[r];
                --r;
            } else {
                res[i] = A[l] * A[l];
                ++l;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res;
        int n = A.size();
        for (int l = 0, r = n - 1; l <= r;) {
            if (abs(A[l]) < abs(A[r])) {
                res.push_back(A[r] * A[r]);
                --r;
            } else {
                res.push_back(A[l] * A[l]);
                ++l;
            }
        }
        return vector<int>(rbegin(res), rend(res));
    }
};

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

O(m+n) time O(1) space
按照S的顺序把T中所有的字符重排即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string customSortString(string S, string T) {
        int f[26] = {0};
        for (char c : T) { // 先统计T中字母频数
            ++f[c - 'a'];
        }
        string s;
        for (char c : S) {
            s.append(f[c - 'a'], c); // 按照S中的顺序重排
            f[c - 'a'] = 0; // 重排后频数清零
        }
        for (int i = 0; i < 26; ++i) {
            s.append(f[i], 'a' + i); // 剩余没出现在S中的字母依次放到尾部即可
        }
        return s;
    }
};

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

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            auto n = q.front(); q.pop();
            if (!n) { // 完全二叉树必须后边所有的都是nullptr
                while (!q.empty()) {
                    auto x = q.front(); q.pop();
                    if (x) return false;
                }
                return true;
            }
            q.push(n->left);
            q.push(n->right);
        }
        return true;
    }
};

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

二分猜数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int lo = 1, hi = 1e9;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(piles, H, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<int> &piles, int H, int m) {
        return accumulate(begin(piles), end(piles), 0, [m](int x, int y) { return x + (y - 1) / m + 1; }) <= H;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int lo = 1, hi = *max_element(begin(piles), end(piles));
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(piles, H, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<int> &piles, int H, int m) {
        return accumulate(begin(piles), end(piles), 0, [m](int x, int y) { return x + ceil(y / (double)m); }) <= H;
    }
};

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

dp O(n) time O(1) space
思考过程
f[0] f[1] f[2]分别表示到当前数为止模3结果为0 1 2的最大和
0可以由0 + 0，1 + 2， 2 + 1生成
1可以由0 + 1, 1 + 0, 2 + 2生成
2可以由0 + 2， 1 + 1， 2 + 0生成
用这个
每得到一个新结果就尝试去更新对应的最大和
下面这种做法的转移方程为
f[{(f[i] + x) % 3}] = max{f[{(f[i] + x) % 3}], f[i] + x}, where i ~ [0, 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f(3); // 要初始化为0，因为后边要做加法
        for (int x : nums) {
            auto t = f;
            for (int y : f) {
                t[(y + x) % 3] = max(t[(y + x) % 3], y + x);
            }
            f = t;
        }
        return f[0];
    }
};

下面这些方法f[1] f[2]必须初始化为无穷小表示不存在，因为最开始一个数都没有是不可能出现余数为1或2的最大和的，上面那种解法初始化为0是因为要用前一次迭代的最大和直接参与计算本次迭代的结果应该给哪个余数下标，算法上有区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f{0, INT_MIN, INT_MIN};
        for (int x : nums) {
            auto t = f;
            for (int i = 0; i < 3; ++i) {
                t[(x + i) % 3] = max(f[(x + i) % 3], f[i] + x);
            }
            f = t;
        }
        return f[0];
    }
};
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:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f{0, INT_MIN, INT_MIN};
        for (int x : nums) {
            switch (x % 3) {
                case 0: {
                    f[0] += x;
                    f[1] += x;
                    f[2] += x;
                } break;
                case 1: {
                    auto t = {max(f[0], f[2] + x),
                              max(f[1], f[0] + x),
                              max(f[2], f[1] + x)}; // t的type是initializer_list<int>
                    f = t; // vector<int>的operator=支持initializer_list<int>传参
                } break;
                default: {
                    auto t = {max(f[0], f[1] + x),
                              max(f[1], f[2] + x),
                              max(f[2], f[0] + x)};
                    f = t;
                }
            }
        }
        return f[0];
    }
};

NP

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:
    int maxSumDivThree(vector<int>& nums) {
        sort(begin(nums), end(nums));
        t = accumulate(begin(nums), end(nums), 0);
        if (t % 3 == 0) return t;
        dfs(0, nums, 0);
        return res;
    }

    void dfs(int s, const vector<int> &A, int b) {
        for (int i = b; i < A.size(); ++i) {
            s += A[i];
            if (t - s <= res) return;
            if ((t - s) % 3 == 0) {
                res = max(res, t - s);
                return;
            } else {
                dfs(s, A, i + 1);
            }
            s -= A[i];
        }
    }

    int res = 0, t = 0;
};

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

O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string toGoatLatin(string S) {
        istringstream input(S);
        string res, s;
        int i = 0;
        unordered_set<char> vowel = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        while (input >> s) {
            if (!vowel.count(s[0])) {
                s += s[0];
                s.erase(0, 1);
            }
            s += "ma";
            s.append(++i, 'a');
            res += s;
            res += " ";
        }
        res.pop_back();
        return res;
    }
};

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

greedy O(nlogn)
思路很基本，维护一个当前全局结束时间，先按开始时间排序，再扫描看当前interval是否和当前全局最晚结束的一个interval有overlap（即当前interval的开始时间早于当前全局结束时间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        int res = 0, e = INT_MIN;
        for (const auto &i : intervals) {
            if (i[0] < e) {
                ++res;
                e = min(e, i[1]);
            } else {
                e = i[1];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = size(intervals);
        if (n < 2) return 0;
        sort(begin(intervals), end(intervals));
        int res = 0;
        for (int e = intervals[0][1], i = 1; i < n; ++i) {
            if (intervals[i][0] < e) {
                ++res;
                e = min(e, intervals[i][1]);
            } else {
                e = intervals[i][1];
            }
        }
        return res;
    }
};

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

O(m+n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length();
        if (m > n) {
            swap(s, t);
            swap(m, n);
        }
        if (n - m > 1) return false;
        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                if (m < n) return s.substr(i) == t.substr(i + 1);
                return s.substr(i + 1) == t.substr(i + 1);
            }
        }
        return m + 1 == n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length();
        if (m > n) {
            return isOneEditDistance(t, s);
        }
        if (n - m > 1) return false;
        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                if (m < n) return s.substr(i) == t.substr(i + 1);
                return s.substr(i + 1) == t.substr(i + 1);
            }
        }
        return m + 1 == n;
    }
};
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:
    bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length();
        if (m == n) {
            int diff = 1;
            for (int i = 0; i < n; ++i) {
                if (s[i] != t[i]) {
                    if (diff == 1) {
                        diff = 0;
                    } else {
                        return false;
                    }
                }
            }
            return diff == 0; // s和t都为空
        }
        if (m > n) {
            s.swap(t);
            swap(m, n);
        }
        if (n - m != 1) return false;
        int diff = 1;
        for (int i = 0, j = 0; i < m && j < n; ++i, ++j) {
            if (s[i] != t[j]) {
                if (diff == 1) {
                    --i;
                    diff = 0;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};