Mind palace

some thoughts

0%

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

常规数1法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n > 0) {
            res += (n & 1);
            n >>= 1;
        }
        return res;
    }
};

翻转最后一个1法
这个比较通用，不受n正负的影响

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n > 0) {
            ++res;
            n &= (n - 1); // 把最低位的1变成0
        }
        return res;
    }
};

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

greedy O(n) time O(1) space
只要挣钱（后一天比前一天价格高）就买进卖出

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += max(prices[i] - prices[i - 1], 0);
        }
        return res;
    }
};

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

hashmap O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        int f[256] = {0};
        for (char c : s) {
            ++f[c];
        }
        for (char c : t) {
            if (--f[c] < 0) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (size(s) != size(t)) return false;
        int f[256] = {0};
        for (int i = 0; i < size(s); ++i) {
            ++f[s[i]];
            --f[t[i]];
        }
        return all_of(f, f + 256, [](int x){ return x == 0; });
    }
};

Follow up

What if the inputs contain unicode characters? How would you adapt your solution to such case?

Answer

Use a hash table instead of a fixed size counter. Imagine allocating a large size array to fit the entire range of unicode characters, which could go up to more than 1 million. A hash table is a more generic solution and could adapt to any range of characters.

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

O(n) 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
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int i = 0, n = intervals.size();
        for (; i < n && intervals[i][0] < newInterval[0]; ++i) {
            res.push_back(intervals[i]);
        }
        if (!res.empty() && newInterval[0] <= res.back()[1]) {
            res.back()[1] = max(res.back()[1], newInterval[1]);
        } else {
            res.push_back(newInterval);
        }
        for (; i < n; ++i) {
            if (intervals[i][0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[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
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        int i = 0;
        int n = intervals.size();
        for (; i < n && intervals[i].start < newInterval.start; ++i) {
            res.push_back(intervals[i]);
        }
        if (!res.empty() && newInterval.start <= res.back().end) {
            res.back().end = max(res.back().end, newInterval.end);
        } else {
            res.push_back(newInterval);
        }
        for (int j = i; j < n; ++j) {
            if (intervals[j].start <= res.back().end) {
                res.back().end = max(res.back().end, intervals[j].end);
            } else {
                res.push_back(intervals[j]);
            }
        }
        return res;
    }
};

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

O(n) time O(1) space
要确认第三大指的是第三大不同的数还是相同也行

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> s;
        for (long x : nums) {
            s.insert(x);
            if (size(s) > 3) {
                s.erase(begin(s));
            }
        }
        return size(s) < 3 ? *rbegin(s) : *begin(s);
    }
};
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:
    int thirdMax(vector<int>& nums) {
        long mx1 = LONG_MIN, mx2 = LONG_MIN, mx3 = LONG_MIN; // 必须是long否则最后无法区分，反例[1, 2, INT_MIN]
        for (long x : nums) {
            if (x > mx1) {
                mx3 = mx2;
                mx2 = mx1;
                mx1 = x;
            } else if (x == mx1) {
                continue;
            } else if (x > mx2) {
                mx3 = mx2;
                mx2 = x;
            } else if (x == mx2) {
                continue;
            } else if (x > mx3) { // 注意不是else，是else if
                mx3 = x;
            }
        }
        return mx3 == LONG_MIN ? mx1 : mx3; // 这一行很重要 因为有可能不同的数不足3个
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k 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
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
class Trie {
    struct TrieNode {
        TrieNode() : children({nullptr}), isEnd(false) {}

        TrieNode *children[26];
        bool isEnd;
    };

    TrieNode *root;

public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        auto p = root;
        for (const auto &c : word) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode();
            }
            p = p->children[c - 'a'];
        }
        p->isEnd = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto p = root;
        for (const auto &c : word) {
            p = p->children[c - 'a'];
            if (!p) return false;
        }
        return p->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto p = root;
        for (const auto &c : prefix) {
            p = p->children[c - 'a'];
            if (!p) return false;
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * bool param_2 = obj.search(word);
 * bool param_3 = obj.startsWith(prefix);
 */

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

O(n)
这道题给了我们一个数组，说我们最多有1次修改某个数字的机会，问能不能将数组变为非递减数组。题目中给的例子太少，不能覆盖所有情况，我们再来看下面三个例子：

4，2，3

-1，4，2，3

2，3，3，2，4

我们通过分析上面三个例子可以发现，当我们发现后面的数字小于前面的数字产生冲突后，有时候需要修改前面较大的数字(比如前两个例子需要修改4)，有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2)，那么有什么内在规律吗？是有的，判断修改那个数字其实跟再前面一个数的大小有关系，首先如果再前面的数不存在，比如例子1，4前面没有数字了，我们直接修改前面的数字为当前的数字2即可。而当再前面的数字存在，并且小于当前数时，比如例子2，-1小于2，我们还是需要修改前面的数字4为当前数字2；如果再前面的数大于当前数，比如例子3，3大于2，我们需要修改当前数2为前面的数3。这是修改的情况，由于我们只有一次修改的机会，所以用一个变量cnt，初始化为0，修改数字后cnt自增1，当下次再需要修改时，如果cnt已经为1了，直接返回false。遍历结束后返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n - 1 && cnt <= 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                if (i > 0 && nums[i - 1] > nums[i + 1]) { // 如果前两个数都比nums[i + 1]大，说明nums[i + 1]是一个valley，调整至跟nums[i]一样再继续扫描
                    nums[i + 1] = nums[i];
                } // 否则nums[i]是一个peak
                ++cnt;
            }
        }
        return cnt <= 1;
    }
};

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

dp O(n2) time O(n) space rolling array

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:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> dp(2, vector<int>(m + 1));
        for (int i = 1; i <= m; ++i) {
            dp[0][i] = i; // 添加字符
        }
        for (int i = 1; i <= n; ++i) {
            int k = i & 1;
            dp[k][0] = i; // 删除字符
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[k][j] = dp[k ^ 1][j - 1];
                } else {
                    dp[k][j] = min({dp[k ^ 1][j - 1], dp[k][j - 1], dp[k ^ 1][j]}) + 1;
                }
            }
        }
        return dp[n & 1][m];
    }
};

dp O(n2) time O(n2) space
dp[i][j]表示word1[0:i]变成word2[0:j]最少需要多少步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= m; ++i) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = i;
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) { // 当两个字符相同时什么都不用做，dp[i - 1][j - 1] < dp[i][j - 1] + 1和dp[i - 1][j] + 1所以一定是dp[i - 1][j - 1]
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
                }
            }
        }
        return dp[n][m];
    }
};

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

O(n) time O(128) space
normalize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ms[128] = {0}, mt[128] = {0};
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (ms[s[i]] == 0) {
                ms[s[i]] = i + 1;
            }
            if (mt[t[i]] == 0) {
                mt[t[i]] = i + 1;
            }
            if (ms[s[i]] != mt[t[i]]) return false;
        }
        return true;
    }
};

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

dp

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > ret(m, vector<int>(n, 1));
        for (int row(1); row < m; ++row)
            for (int col(1); col < n; ++col)
                ret[row][col] = ret[row - 1][col] + ret[row][col - 1];
        return ret[m - 1][n - 1];
    }
};