Mind palace

some thoughts

0%

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

跟157. Read N Characters Given Read4的区别是前一次read过的剩余字符下次read的时候直接写进buf

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
/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char *buf4);
 */

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        int cnt = 0;
        while (b != e && cnt < n) {
            buf[cnt++] = buf4[b++];
        }
        if (cnt == n) return cnt;
        b = 0; // cnt不等于n，说明b == e，重置b，更新e读新字符
        e = read4(buf4);
        if (e == 0) return cnt;
        return cnt + read(buf + cnt, n - cnt);
    }

    char buf4[4];
    int b = 0, e = 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
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        int cnt = 0;
        while (i < e && cnt < n) { // 在全局buffer的边界之内尽可能多的读字符
            buf[cnt++] = t[i++];
        }
        if (i == e) i = e = 0; // 如果全局buffer里到边界的所有字符都被读走，则重置下标和边界
        if (cnt == n) return cnt; // 如果已经读够了需要的字符，则返回
        e = read4(t);
        if (e == 0) return cnt; // 如果还需要继续读字符但是读出的字符数为0
        return cnt + read(buf + cnt, n - cnt); // 如果还需要继续读字符，递归
    }

    int i = 0, e = 0; // 维护全局buffer的下标和右边界（不一定为4）
    char t[4];
};

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

bfs O(n) time O(n) space
bfs逐层遍历每次取最后一个即可

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
/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        list<TreeNode *> q; // q{{root}};
        q.push_back(root);
        while (!q.empty()) {
            res.push_back(q.back()->val);
            for (int i = q.size(); i > 0; --i) {
                auto p = q.front(); q.pop_front();
                if (p->left) { // 因为要直接access node一定不能把nullptr放进去
                    q.push_back(p->left);
                }
                if (p->right) {
                    q.push_back(p->right);
                }
            }
        }
        return res;
    }
};

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

recursive

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
unordered_map<int, string> m = {
    {1e9, "Billion"}, {1e6, "Million"}, {1e3, "Thousand"}, {100, "Hundred"},
    {90, "Ninety"}, {80, "Eighty"}, {70, "Seventy"}, {60, "Sixty"}, {50, "Fifty"}, {40, "Forty"}, {30, "Thirty"}, {20, "Twenty"},
    {19, "Nineteen"}, {18, "Eighteen"}, {17, "Seventeen"}, {16, "Sixteen"}, {15, "Fifteen"}, {14, "Fourteen"}, {13, "Thirteen"}, {12, "Twelve"}, {11, "Eleven"},
    {10, "Ten"}, {9, "Nine"}, {8, "Eight"}, {7, "Seven"}, {6, "Six"}, {5, "Five"}, {4, "Four"}, {3, "Three"}, {2, "Two"}, {1, "One"},
    {0, "Zero"}
};
class Solution {
public:
    string numberToWords(int num) {
        string res;
        vector<int> v = {1e9, 1e6, 1e3, 100}; // 100以上的数统一处理
        for (int x : v) {
            if (num >= x) {
                res.append(numberToWords(num / x)).append(" ").append(m[x]);
                num %= x;
                return num > 0 ? res.append(" ").append(numberToWords(num)) : res;
            }
        }
        if (num >= 20) { // 100以内20以上的数统一处理
            res.append(m[num - num % 10]);
            num %= 10;
            return num > 0 ? res.append(" ").append(numberToWords(num)) : res;
        }
        return m[num]; // 20以内的数直接查表
    }
};
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
unordered_map<int, string> m = {
    {1e9, "Billion"}, {1e6, "Million"}, {1e3, "Thousand"}, {100, "Hundred"},
    {90, "Ninety"}, {80, "Eighty"}, {70, "Seventy"}, {60, "Sixty"}, {50, "Fifty"}, {40, "Forty"}, {30, "Thirty"}, {20, "Twenty"},
    {19, "Nineteen"}, {18, "Eighteen"}, {17, "Seventeen"}, {16, "Sixteen"}, {15, "Fifteen"}, {14, "Fourteen"}, {13, "Thirteen"}, {12, "Twelve"}, {11, "Eleven"},
    {10, "Ten"}, {9, "Nine"}, {8, "Eight"}, {7, "Seven"}, {6, "Six"}, {5, "Five"}, {4, "Four"}, {3, "Three"}, {2, "Two"}, {1, "One"},
    {0, "Zero"}
};
vector<int> v = {1000000000, 1000000, 1000, 100};
class Solution {
public:
    string numberToWords(int num) {
        string res;
        if (auto it = lower_bound(begin(v), end(v), num, greater<>()); it != end(v)) {
            int x = *it;
            res.append(numberToWords(num / x).append(" ").append(m[x]));
            num %= x;
            return num > 0 ? res.append(" ").append(numberToWords(num)) : res;
        }
        if (num >= 20) {
            res.append(m[num - num % 10]);
            num %= 10;
            return num > 0 ? res.append(" ").append(numberToWords(num)) : res;
        }
        return m[num];
    }
};

Posted on Edited on Disqus:
Symbols count in article: 209 Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main() {
	// your code goes here
	size_t x = 0;
	auto j = x - 1;
	cout << j << endl; // 18446744073709551615
	int i = j;
	cout << i << endl; // -1
	return 0;
}

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

O(max(m, n)) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        for (int c = 0, i = a.length() - 1, j = b.length() - 1;
            i >= 0 || j >= 0 || c > 0;
            --i, --j) {
            int x = i < 0 ? 0 : (a[i] - '0');
            int y = j < 0 ? 0 : (b[j] - '0');
            int s = x + y + c;
            res += '0' + (s & 1);
            c = s >> 1;
        }
        return string(rbegin(res), rend(res));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        int c = 0;
        string res;
        while (!a.empty() || !b.empty() || c > 0) {
            int x = a.empty() ? 0 : (a.back() - '0');
            int y = b.empty() ? 0 : (b.back() - '0');
            if (!a.empty()) {
                a.pop_back();
            }
            if (!b.empty()) {
                b.pop_back();
            }
            int s = x + y + c;
            res += '0' + (s & 1);
            c = (s >> 1);
        }
        return string(rbegin(res), rend(res));
    }
};

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

O(n) 两个指针l和r从外往内扫描，如果遇到两个字符s[l]和s[r]不一样，则分别判断s[l:r-1]和s[l+1:r]是不是回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool validPalindrome(string s) {
        for (int n = s.length(), l = 0, r = n - 1; l < r; ++l, --r) {
            if (s[l] != s[r]) {
                return isPalin(s, l, r - 1) || isPalin(s, l + 1, r);
            }
        }
        return true;
    }

    bool isPalin(const string &s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }
};

O(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
37
38
39
40
41
class Solution {
public:
    bool validPalindrome(string s) {
        int n = s.length();
        int l = 0, r = n - 1;
        int cnt1 = 0;
        while (l < r) {
            if (s[l] != s[r]) {
                ++cnt1;
                if (cnt1 > 1) break;
                if (s[l + 1] == s[r]) {
                    ++l;
                } else if (s[l] == s[r - 1]) {
                    --r;
                } else {
                    return false;
                }
            }
            ++l;
            --r;
        }
        l = 0, r = n - 1;
        int cnt2 = 0;
        while (l < r) {
            if (s[l] != s[r]) {
                ++cnt2;
                if (cnt2 > 1) break;
                if (s[l] == s[r - 1]) {
                    --r;
                } else if (s[l + 1] == s[r]) {
                    ++l;
                } else {
                    return false;
                }
            }
            ++l;
            --r;
        }
        return cnt1 < 2 || cnt2 < 2;
    }
};

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

O(m+n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string addStrings(string num1, string num2) {
        string res;
        for (int i = num1.length() - 1, j = num2.length() - 1, c = 0;
             i >= 0 || j >= 0 || c > 0;
             --i, --j) {
            int a = i < 0 ? 0 : (num1[i] - '0');
            int b = j < 0 ? 0 : (num2[j] - '0');
            int s = a + b + c;
            res += '0' + s % 10;
            c = s / 10;
        }
        return string(rbegin(res), rend(res));
    }
};

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

quickselection
O(n) time on average 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
34
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        srand(time(NULL));
        int n = points.size(), l = 0, r = n - 1;
        while (l <= r) {
            int k = partition(points, l, r);
            if (k == K - 1) break;
            if (k < K - 1) {
                l = k + 1;
            } else {
                r = k - 1;
            }
        }
        return vector<vector<int>>(begin(points), begin(points) + K);
    }

    int partition(vector<vector<int>>& p, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(p[l], p[v[rand() % 3]]);
        int j = l + 1;
        for (int i = j; i <= r; ++i) {
            if (lt(p[i], p[l])) {
                swap(p[i], p[j++]);
            }
        }
        swap(p[--j], p[l]);
        return j;
    }

    bool lt(const vector<int> &a, const vector<int> &b) {
        return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
    }
};
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
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        srand(time(NULL));
        int n = points.size(), l = 0, r = n - 1;
        while (l <= r) {
            int k = partition(points, l, r);
            if (k == K - 1) break;
            if (k < K - 1) {
                l = k + 1;
            } else {
                r = k - 1;
            }
        }
        return vector<vector<int>>(begin(points), begin(points) + K);
    }

    int partition(vector<vector<int>>& p, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(p[l], p[v[rand() % 3]]);
        auto pivot = p[l];
        while (l < r) {
            while (l < r && !lt(p[r], pivot)) --r;
            p[l] = p[r];
            while (l < r && lt(p[l], pivot)) ++l;
            p[r] = p[l];
        }
        p[l] = pivot;
        return l;
    }

    bool lt(const vector<int> &a, const vector<int> &b) {
        return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
    }
};

O(nlogK) time O(K) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        int n = points.size();
        using vi = vector<int>;
        auto less = [](const vi &a, const vi &b){return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];};
        priority_queue<vi, vector<vi>, decltype(less)> q(less);
        for (const auto &p : points) {
            q.push(p);
            if (q.size() > K) {
                q.pop();
            }
        }
        vector<vi> res;
        while (!q.empty()) {
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

O(nlog(n-K)) time O(n-K) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        int n = points.size();
        using vi = vector<int>;
        auto greater = [](const vi &p1, const vi &p2) {return p1[0] * p1[0] + p1[1] * p1[1] > p2[0] * p2[0] + p2[1] * p2[1];};
        priority_queue<vi, vector<vi>, decltype(greater)> q(greater);
        vector<vector<int>> res;
        for (const auto &p : points) {
            if (q.size() < n - K) {
                q.push(p);
            } else if (greater(p, q.top())) {
                res.push_back(q.top());
                q.pop();
                q.push(p);
            } else {
                res.push_back(p);
            }
        }
        return res;
    }
};

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

O(n) 在遍历每个数的过程中用hashmap把已经算过的前缀和存起来，之后只需要查看目标前缀和的个数即可
初始化要加入{0,1}这对映射，这是为啥呢，因为我们的解题思路是遍历数组中的数字，用sum来记录到当前位置的累加和，我们建立哈希表的目的是为了让我们可以快速的查找sum-k是否存在，即是否有连续子数组的和为sum-k，如果存在的话，那么和为k的子数组一定也存在，这样当sum刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果哈希表中事先没有m[0]项的话，这个符合题意的结果就无法累加到结果res中，这就是初始化的用途

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m{{0, 1}};
        int s = 0, res = 0;
        for (int x : nums) {
            s += x;
            res += m[s - k];
            ++m[s];
        }
        return res;
    }
};

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                res += (sum[i] + k == sum[j]);
            }
        }
        return res;
    }
};

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

O(n) time O(1) space
input: 1 2 3 4
res: 1 1 1 1
-->

1
2
3
4
5
6
1 2 3 4
-------
1 1 1 1
  1 1 1
    2 2
      3

<–

1
2
3
4
5
6
1 2 3 4
-------
1 1 1 1
4 1 1 1
3 4 2 2
2 3 4 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1; i < n; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        for (int i = n - 1, p = 1; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 0, p = 1; i < n; p *= nums[i++]) {
            res[i] *= p;
        }
        for (int i = n - 1, p = 1; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1, p = nums[i - 1]; i < n; p *= nums[i++]) {
            res[i] *= p;
        }
        for (int i = n - 2, p = nums[i + 1]; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        int p = 1;
        for (int i = 1; i < n; ++i) {
            p *= nums[i - 1];
            res[i] = p;
        }
        p = 1;
        for (int i = n - 2; i >= 0; --i) {
            p *= nums[i + 1];
            res[i] *= p;
        }
        return res;
    }
};