Cinte's Leetcode Record
0%

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

289. 生命游戏

0和1只需要int中的最低位就可以保存了，所以我们用int中的第二位来存储下一个状态的结果。

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                int aliveCell = 0;
                int cur = board[i][j];
                if(i > 0 && board[i - 1][j] & 1)
                    ++aliveCell;
                if(j > 0 && board[i][j - 1] & 1)
                    ++aliveCell;
                if(i < m - 1 && board[i + 1][j] & 1)
                    ++aliveCell;
                if(j < n - 1 && board[i][j + 1] & 1)
                    ++aliveCell;
                if(i > 0 && j > 0 && board[i - 1][j - 1] & 1)
                    ++aliveCell;
                if(i < m - 1 && j > 0 && board[i + 1][j - 1] & 1)
                    ++aliveCell;
                if(i < m - 1 && j < n - 1 && board[i + 1][j + 1] & 1)
                    ++aliveCell;
                if(i > 0 && j < n - 1 && board[i - 1][j + 1] & 1)
                    ++aliveCell;
                if(cur == 1 && (aliveCell < 2 || aliveCell > 3))
                    board[i][j] = 1;
                else if(cur == 0 && aliveCell == 3)
                    board[i][j] = 2;
                else
                    board[i][j] = board[i][j] ? 3 : 0;
            }
        }
        for(auto& line : board)
            for(auto& num : line)
                num >>= 1;
        /*
        for_each(board.begin(), board.end(), [](vector<int>& line){
            for_each(line.begin(), line.end(), [](int& num){
                num >>= 1;
            });
        });
        */
    }
};

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

268. 丢失的数字

类似于hash的一种解法
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        nums.emplace_back(0);
        int n = nums.size();
        for(auto num : nums)
            nums[num % n] += n;
        for(int i = 0; i < n; ++i)
            if(nums[i] < n)
                return i;
        return 0;
    }
};

O(n)

O(1)

排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(nums.front() != 0)
            return 0;
        if(nums.back() != n)
            return n;
        for(int i = 0; i < n; ++i)
            if(nums[i] != i)
                return i;
        return 0;
    }
};

O(nlogn)

O(1)

异或

0~n的所有数字异或一遍，nums中的数字再异或一遍，剩下的就是只出现一次的，也就是只missing一次的。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ret = n;
        for(int i = 0; i < n; ++i)
            ret ^= nums[i] ^ i;
        return ret;
    }
};

O(n)

O(1)

数学
1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = n * (n + 1) / 2;
        return sum - accumulate(nums.begin(), nums.end(), 0);
    }
};

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

242. 有效的字母异位词

hash

如果元素只有a-z，用数组代替hash是基本操作

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.size() != t.size())
            return false;
        int memo[26]{};
        for(auto ch : s)
            ++memo[ch - 'a'];
        for(auto ch : t)
            if(--memo[ch - 'a'] < 0)
                return false;
        return true;
    }
};

如果要支持unicode需要改用hash

c++中char只有4位，而utf-8有8位，所以可能需要wchar_t

排序
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

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

212. 单词搜索 II

前缀树+df
初始版本
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
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        auto root = new TireNode();
        for(auto& word : words)
            insert(root, word);
        int nx = board.size(), ny = board[0].size();
        for(int i = 0; i < nx; ++i)
            for(int j = 0; j < ny; ++j)
                dfs(board, i, j, root, nx, ny);
        vector<string> ret(set.begin(), set.end());
        return ret;
    }
private:
    unordered_set<string> set;
    struct TireNode
    {
        string word;
        unordered_map<char, TireNode*> childs;
    };
    void insert(TireNode* root, string& word)
    {
        auto node = root;
        for(auto ch : word)
        {
            if(!node->childs.count(ch))
                node->childs.emplace(ch, new TireNode());
            node = node->childs[ch];
        }
        node->word = word;
    }
    void dfs(vector<vector<char>>& board, int i, int j, TireNode* node, int nx, int ny)
    {
        if(i < 0 || j < 0 || i >= nx || j >= ny || board[i][j] < 'a')
            return;
        if(!node->childs.count(board[i][j]))
            return;
        node = node->childs[board[i][j]];
        if(!node->word.empty())
            set.emplace(node->word);
        board[i][j] -= 'a';
        dfs(board, i + 1, j, node, nx, ny);
        dfs(board, i - 1, j, node, nx, ny);
        dfs(board, i, j + 1, node, nx, ny);
        dfs(board, i, j - 1, node, nx, ny);
        board[i][j] += 'a';
    }
};
1633941766209.png
优化后的版本
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
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        auto root = new TireNode();
        // 用words中的word构建前缀树
        for(auto& word : words)
            insert(root, word);
        int nx = board.size(), ny = board[0].size();
        for(int i = 0; i < nx; ++i)
            for(int j = 0; j < ny; ++j)
                dfs(board, i, j, root, nx, ny);
        return ret;
    }
private:
    vector<string> ret;
    struct TireNode
    {
        string word;
        TireNode* childs[26]{}; // 不使用hash表而使用数组，可以使得搜索速度更快，但反之也会占用更多空间
    };
    void insert(TireNode* root, string& word)
    {
        auto node = root;
        for(auto ch : word)
        {
            if(!node->childs[ch - 'a'])
                node->childs[ch - 'a'] = new TireNode();
            node = node->childs[ch - 'a'];
        }
        node->word = word;
    }
    void dfs(vector<vector<char>>& board, int i, int j, TireNode* node, int nx, int ny)
    {
        if(i < 0 || j < 0 || i >= nx || j >= ny || board[i][j] == '#')
            return;
        char ch = board[i][j];
        if(!node->childs[ch - 'a'])
            return;
        node = node->childs[ch - 'a']; // 要先过去再判断，因为只有这一步走完后的节点才表示当前ch对应的节点
        if(!node->word.empty())
        {
            ret.emplace_back(node->word);
            node->word.clear(); // 相比将结果放入hash中来去重的方法，这种将走到过的记录为空字符串可以更加节省时间。又可以避免重复录入。
        }
        // 标准的回溯+dfs
        board[i][j] = '#';
        dfs(board, i + 1, j, node, nx, ny);
        dfs(board, i - 1, j, node, nx, ny);
        dfs(board, i, j + 1, node, nx, ny);
        dfs(board, i, j - 1, node, nx, ny);
        board[i][j] = ch;
    }
};
1633941806615.png

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

9. 回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        int num = 0;
        int d = x;
        while(x)
        {
            if(num >= INT_MAX / 10)
                return false;
            num = num * 10 + x % 10;
            x /= 10;
        }
        return num == d;
    }
};

T(n) : O(logn)

每次迭代除以10，所以是logn

题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0  || x % 10 == 0 && x != 0)
            return false;
        int num = 0;
        while(x > num)
        {
            num = num * 10 + x % 10;
            x /= 10;
        }
        return num == x || num / 10 == x;;
    }
};

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

7. 整数反转

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 reverse(int x) {
        int ret = 0;
        bool positive = true;
        if(x == INT_MIN)
            return 0;
        if(x < 0)
        {
            positive = false;
            x = -x;
        }
        while(x)
        {
            int num = x % 10;
            x /= 10;
            if(ret > INT_MAX / 10 || (ret == INT_MAX / 10 && num > INT_MAX % 10))
                return 0;
            ret = ret * 10 + num;
        }
        return positive ? ret : -ret;
    }
};

引入一个小trick

1633332629963.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int reverse(int x) {
        int ret = 0;
        while(x)
        {
            if(ret > INT_MAX / 10 || ret < INT_MIN / 10)
                return 0;
            int num = x % 10;
            x /= 10;
            ret = ret * 10 + num;
        }
        return ret;
    }
};

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

8. 字符串转换整数 (atoi)

参考剑指 Offer 67. 把字符串转换成整数

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:
    int myAtoi(string s) {
        if(s.empty())
            return 0;
        bool positive = true;
        int i = 0;
        while(s[i] == ' ')
            ++i;
        if(!isdigit(s[i]))
        {
            if(s[i] == '+' || s[i] == '-')
                positive = s[i++] == '+';
            else
                return 0;
        }
        int length = s.size();
        int ret = 0;
        while(i < length)
        {
            if(!isdigit(s[i]))
                break;
            int num = s[i] - '0';
            if(ret > INT_MAX / 10 || (ret == INT_MAX / 10 && num > INT_MAX % 10))
                return positive ? INT_MAX : INT_MIN;
            ret = ret * 10 + num;
            ++i;
        }
        return positive ? ret : -ret;
    }
};

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

350. 两个数组的交集 II

hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size())
            return intersect(nums2, nums1);
        unordered_map<int, int> map;
        for(auto& num : nums1)
            ++map[num];
        vector<int> ret;
        for(auto& num : nums2)
        {
            if(map[num] > 0)
            {
                --map[num];
                ret.push_back(num);
            }
        }
        return ret;
    }
};
排序双指针
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<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int pt1 = 0, pt2 = 0;
        int length1 = nums1.size(), length2 = nums2.size();
        vector<int> ret;
        while(pt1 < length1 && pt2 < length2)
        {
            if(nums1[pt1] == nums2[pt2])
            {
                ret.push_back(nums2[pt2]);
                ++pt1;
                ++pt2;
            }else if(nums1[pt1] < nums2[pt2])
                ++pt1;
            else
                ++pt2;
        }
        return ret;
    }
};

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

349. 两个数组的交集

hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        unordered_set<int> set(nums2.begin(), nums2.end());
        unordered_set<int> set2;
        for(auto& num : nums1)
        {
            if(set.count(num) && set2.emplace(num).second)
                ret.push_back(num);
        }
        return ret;
    }
};
双指针

主要是省空间

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:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int length1 = nums1.size();
        int length2 = nums2.size();
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        vector<int> ret;
        while(i < length1 && j < length2)
        {
            if(nums1[i] == nums2[j])
            {
                if(ret.empty() || nums1[i] != ret.back())
                    ret.push_back(nums1[i]);
                ++i;
                ++j;
            }else if(nums1[i] < nums2[j])
                ++i;
            else
                ++j;
        }
        return ret;
    }
};

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

202. 快乐数

用hash记录是否出现了循环

对于 33 位数的数字，它不可能大于 243243。这意味着它要么被困在 243243 以下的循环内，要么跌到 11。44 位或 44 位以上的数字在每一步都会丢失一位，直到降到 33 位为止。所以我们知道，最坏的情况下，算法可能会在 243243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 11。但它不会无限期地进行下去，所以我们排除第三种选择。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        while(set.count(n) == 0)
        {
            set.insert(n);
            int tmp = 0;
            while(n)
            {
                int num = n % 10;
                n /= 10;
                tmp += num * num;
            }
            if(tmp == 1)
                return true;
            n = tmp;
        }
        return false;
    }
};
快慢指针找环路

虽然没有显式的链表，但是每个数字都是一个节点，如果有环路他们终究会相交，如果没有，快指针就会走向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
class Solution {
public:
    bool isHappy(int n) {
        int walker = n;
        int runner = n;
        while(runner != 1)
        {
            walker = getNext(walker);
            runner = getNext(getNext(runner));
            if(runner == walker)
                break;;
        }
        return runner == 1;
    }
private:
    int getNext(int n)
    {
        int tmp = 0;
        while(n)
        {
            int num = n % 10;
            tmp += num * num;
            n /= 10;
        }
        return tmp;
    }
};