Mind palace

some thoughts

0%

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

从右上往左下方向找边缘 O(m+n) time O(1) space
复杂度要不是m要不是n，最多是m+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
/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int row, int col);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        const auto &dim = binaryMatrix.dimensions();
        int m = dim[0], n = dim[1];
        int res = -1, r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (binaryMatrix.get(r, c)) {
                res = c--;
            } else {
                ++r;
            }
        }
        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
/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int row, int col);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        const auto &dim = binaryMatrix.dimensions();
        int m = dim[0], n = dim[1];
        int res = n, r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (binaryMatrix.get(r, c)) {
                res = min(res, c);
                --c;
            } else {
                ++r;
            }
        }
        return res == n ? -1 : res;
    }
};

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

跟301. Remove Invalid Parentheses不完全一样
跟921. Minimum Add to Make Parentheses Valid结合起来看
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 minRemoveToMakeValid(string s) {
        s = remove(s, '(', ')'); // 一定要先从后往前删，再从前往后删，因为s要翻转两次
        return remove(s, ')', '(');
    }

    string remove(const string &s, char lp, char rp) {
        string res;
        int cnt = 0;
        for (int n = s.length(), i = n - 1; i >= 0; --i) {
            cnt += s[i] == lp ? -1 : (s[i] == rp);
            if (cnt < 0) { // 说明找到一个无法匹配的『左括号』
                cnt = 0; // 重置
                continue;
            }
            res += s[i];
        }
        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
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        reverse(begin(s), end(s));
        s = remove(s, ')', '(');
        reverse(begin(s), end(s));
        return remove(s, '(', ')');
    }

    string remove(const string &s, char lp, char rp) {
        string res;
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            cnt += s[i] == rp ? -1 : (s[i] == lp);
            if (cnt < 0) {
                cnt = 0;
                continue;
            }
            res += s[i];
        }
        return res;
    }
};

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

O(m*n) time O(1) space where m is the avg length of a word while n is the number of words

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:
    bool isAlienSorted(vector<string>& words, string order) {
        int dict[26] = {0};
        for (int i = 0; i < 26; ++i) {
            dict[order[i] - 'a'] = i;
        }
        for (int i = 1; i < words.size(); ++i) {
            if (!lte(words[i - 1], words[i], dict)) return false;
        }
        return true;
    }

    bool lte(const string &a, const string &b, int dict[26]) {
        int m = a.length(), n = b.length();
        for (int i = 0; i < min(m, n); ++i) {
            if (a[i] == b[i]) continue;
            return dict[a[i] - 'a'] <= dict[b[i] - 'a'];
        }
        return m <= n;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 590 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
22
23
24
25
/**
 * 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:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        helper(root, res);
        return res;
    }

    int helper(TreeNode *root, int &res) { // 以root结尾的最大和path的最大和
        if (!root) return 0;
        int l = max(0, helper(root->left, res)); // 如果返回的最大和是负数，则直接用0代替
        int r = max(0, helper(root->right, res));
        res = max(res, root->val + l + r); // 更新res
        return root->val + max(l, r); // 返回包括root在内的最大路径
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 798 Reading time ≈ 1 mins. 
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
struct A {
    A() {cout<<"A::A"<<endl;}
    ~A() {cout<<"A::~A"<<endl;x=0;}
    A(const A& a) : x(a.x) {cout<<"copy ctor"<<endl;}
    A(A&& a)  noexcept : x(a.x) {cout<<"move ctor"<<endl;}
    int x = 1;
};

void f1(unique_ptr<A> &&x) {
    cout << x->x<<endl;
    x->x = 2;
}

void f2(const unique_ptr<A> &x) {
    cout<<x->x<<endl;
    x->x = 3;
}

unique_ptr<A> f3(unique_ptr<A> x) {
    cout<<x->x<<endl;
    return x; // 可以拷贝或赋值一个将要被销毁的unique_ptr （C++ Primer 5th p418）
}

int main() {
    auto a = make_unique<A>(); // A::A
    f1(move(a)); // 1
    f2(a); // 2
    a = f3(move(a)); // 3
    return 0; // A::~A
}

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

  • Emacs CS模式
    在~/.emacs里加入

    1
    2
    (require 'server)
    (unless (server-running-p) (server-start))

    或者(server-start)，emacs启动的时候就会自动启动server。然后你可以利
    用emacscilent -c命令来打开一个新的窗口，速度会非常快。这有个缺点，如果充当server
    的emacs被关闭之后，使用客户端命令就会出现无法打开的现象。可以使用emacs –daemon&
    模式在后台打开一个emacs作为server

  • 开机自动启动emacs
    Linux下在~/.profile里加入emacs –daemon&即可
    以后就可以使用emacsclient -c启动客户端了

  • Emacs和Emacsclient
    有的时候，快速启动得到的emacsclient不能编辑需要sudo的文件。这是因为它的server没
    有处在root权限下，所以会出现出错的现象。另外，emacsclient下的字体背景等会和原来
    的有差异。我的解决办法是，平时开启一个emacs进程作为主要编辑的工具，另外一个
    emacsclient则是编辑临时文件的时候使用，这样既保证了编辑临时文件的速度问题，同样
    尽可能的排除错误。

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

O(logn)
循环版本

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double myPow(double x, int n) {
        long t = labs(n); // 注意n溢出！！
        x = n < 0 ? 1 / x : x;
        double res = 1.0;
        while (t > 0) {
            if (t & 1) {
                res *= x;
            }
            x *= x;
            t >>= 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double myPow(double x, int n) {
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }

        double res = 1;
        while (n != 0) {
            if (n & 1) {
                res *= x;
            }
            x *= x;
            n /= 2; // 这里一定不要用 n >>= 1因为n可能为INT_MIN
        }
        return res;
    }
};

1.00000
-2147483648
这个测试用例很重要！因为-INT_MIN还是INT_MIN！！所以必须要把n < 0的分支分离出来，否则会造成死循环

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? power(1 / x, labs(n)) : power(x, n);
    }

    double power(double x, long n) {
        if (n == 0) return 1;
        return n & 1 ? x * power(x * x, n / 2) : power(x * x, n / 2);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double myPow(double x, int n) {
        double res = 1.0;
        n < 0 ? power(1 / x, labs(n), res) : power(x, n, res);
        return res;
    }

    void power(double x, long n, double &res) {
        if (n == 0) return;
        if (n & 1) {
            res *= x;
        }
        power(x * x, n / 2, res);
    }
};

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

O(nk) time
这道题考如何hash
followup是MapReduce

1
2
3
4
5
6
7
8
9
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            d[tuple(f)].append(s)
        return d.values()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def myhash(s): # 'bcabe' -> '1a2b1c1e'
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            res = ''
            for i, cnt in enumerate(f):
                if cnt > 0:
                    res += str(cnt) + chr(ord('a') + i)
            return res
        d = defaultdict(list)
        for s in strs:
            d[myhash(s)].append(s)
        return d.values()
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def myhash(s): # 'bcabe' -> '1 2 1 0 1 0 ... 0'
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            res = ''
            return ' '.join(map(str, f))
        d = defaultdict(list)
        for s in strs:
            d[myhash(s)].append(s)
        return d.values()
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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strs) {
            m[hash(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            res.push_back(p.second);
        }
        return res;
    }

    string hash(const string &s) { // bucket sort
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        string res;
        for (int x : f) {
            res += to_string(x);
            res += ' ';
        }
        return res;
    }
};

普通解法 O(nklogk) time

1
2
3
4
5
6
7
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            d[''.join(sorted(s))].append(s) # key是一个str: 'bcabe' -> 'abbce'
            # d[tuple(sorted(s))].append(s) # key是一个tuple: 'bcabe' -> ('a', 'b', 'b', 'c', 'e')
        return d.values()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hm;
        for (const auto &s : strs) {
            hm[key(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (const auto &p : hm) {
            res.push_back(p.second);
        }
        return res;
    }

    string key(string s) {
        sort(s.begin(), s.end());
        return s;
    }
};
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
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<long, vector<string> > hash_map;
        for (auto &&str : strs)
            hash_map[key(str)].push_back(str);
        vector<vector<string> > ret(hash_map.size());
        size_t i(0);
        for (auto &&pair : hash_map) {
            ret[i].swap(pair.second);
            sort(ret[i].begin(), ret[i].end());
            ++i;
        }
        return ret;
    }

private:
    long key(const string &str) {
        long ret(1);
        for (auto &&c : str)
            ret *= primes[c - 'a'];
        return ret;
    }
};

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

two spins O(n2)
先上下翻转，再沿对称轴翻转

1
2
3
4
5
6
7
8
9
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        for i in range(len(matrix)):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
1
2
3
4
5
6
7
8
9
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        for i in range(len(matrix)):
            for j in range(i + 1, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
1
2
3
4
5
6
7
8
9
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(), matrix.end());
        for (int i(0); i < matrix.size() - 1; ++i)
            for (int j(i + 1); j < matrix.size(); ++j)
                swap(matrix[i][j], matrix[j][i]);
    }
};

直接移 O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if (matrix.empty())
            return;
        int n(matrix.size() >> 1);
        for (int row(0); row < n; ++row)
            for (int col(row); col < matrix.size() - 1 - row; ++col) {
                auto temp(matrix[row][col]);
                matrix[row][col] = matrix[matrix.size() - 1 - col][row];
                matrix[matrix.size() - 1 - col][row] = matrix[matrix.size() - 1 - row][matrix.size() - 1 - col];
                matrix[matrix.size() - 1 - row][matrix.size() - 1 - col] = matrix[col][matrix.size() - 1 - row];
                matrix[col][matrix.size() - 1 - row] = temp;
            }
    }
};

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

O(n*n!) time
先写 dfs 版本再写循环版本
先排序，对于每个位置，从小到大枚举之后的每个数（相同的数要跳过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, n = [], len(nums)
        def dfs(A, b):
            if b == n:
                res.append(A)
                return
            for i in range(b, n):
                if i > b and A[i] == A[b]:
                    continue
                A[b], A[i] = A[i], A[b]
                dfs(A[:], b + 1)
        dfs(nums, 0)
        return res
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>> permuteUnique(vector<int>& nums) {
        sort(begin(nums), end(nums));
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int> nums, int b) { // 注意nums是深拷贝
        int n = nums.size();
        if (b == n) {
            res.push_back(nums);
        }
        for (int i = b; i < n; ++i) {
            if (i > b && nums[i] == nums[b]) continue; // 去重
            swap(nums[i], nums[b]);
            dfs(nums, b + 1);
        }
    }

    vector<vector<int>> res;
};

O(n*n!) time

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while (next(nums));
        return res;
    }

    bool next(vector<int> &A) {
        int n = A.size();
        int x = 0, y = 0;
        for (int i = n - 1; i > 0; --i) {
            if (A[i - 1] < A[i]) {
                x = i - 1;
                y = i;
                break;
            }
        }
        if (y == 0) return false;
        for (int i = n - 1; i > x; --i) {
            if (A[i] > A[x]) {
                swap(A[i], A[x]);
                break;
            }
        }
        reverse(A.begin() + y, A.end());
        return true;
    }
};

O(nn) time

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        visited.resize(n);
        sort(begin(nums), end(nums));
        dfs(nums);
        return res;
    }

    void dfs(const vector<int> &nums) {
        if (v.size() == n) {
            res.push_back(v);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue; // 如果前一个数已经访问过（还没被访问）并且跟这个数相同，则再访问这个数是重复的，如果前一个数正在被访问（说明在v里）则可以访问当前这个数，即便跟前一个数相同
            visited[i] = true;
            v.push_back(nums[i]);
            dfs(nums);
            v.pop_back();
            visited[i] = false;
        }
    }

    int n;
    vector<bool> visited;
    vector<int> v;
    vector<vector<int>> res;
};