Cinte's Leetcode Record
0%

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

468. 验证IP地址

模拟

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    string validIPAddress(string queryIP) {
        int mode = 3;
        int begin = 0;
        int n = queryIP.size();
        int count = 0;
        for(int i = 0; i <= n; ++i)
        {
            if((i == n && mode == 2) || queryIP[i] == ':')
            {
                if(mode == 1)
                    return "Neither";
                mode = 2;
                if(!checkIPV6(queryIP, begin, i))
                    return "Neither";
                begin = i + 1;
                ++count;
            }else if((i == n && mode == 1) || queryIP[i] == '.')
            {
                if(mode == 2)
                    return "Neither";
                mode = 1;
                if(!checkIPV4(queryIP, begin, i))
                    return "Neither";
                begin = i + 1;
                ++count;
            }
        }
        return mode == 2 ? (count == 8 ? "IPv6" : "Neither") : (count == 4 ? "IPv4" : "Neither");
    }
private:
    bool checkIPV4(string& ip, int start, int end)
    {
        if(end == start)
            return false;
        if(end - start == 1)
            return isDigital(ip[start]);
        if(ip[start] == '0')
            return false;
        int num = 0;
        for(int i = start; i < end; ++i)
        {
            if(!isDigital(ip[i]))
                return false;
            num = num * 10 + ip[i] - '0';
            if(num > 255)
                return false;
        }
        return true;
    }
    bool checkIPV6(string& ip, int start, int end)
    {
        if(end - start > 4 || end - start == 0)
            return false;
        for(int i = start; i < end; ++i)
        {
            if(!isHex(ip[i]))
                return false;
        }
        return true;
    }
    bool isDigital(char ch)
    {
        return ch >= '0' && ch <= '9';
    }
    bool isHex(char ch)
    {
        return isDigital(ch) || (ch >= 'a' && ch <= 'f') || (ch >= 'A' && ch <= 'F');
    }
};

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

112. 路径总和

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return helper(root, 0, targetSum);
    }
private:
    bool helper(TreeNode* node, int cur, int targetSum)
    {
        if(!node)
            return false;
        cur += node->val;
        if(!node->left && !node->right && cur == targetSum)
            return true;
        return helper(node->left, cur, targetSum) || helper(node->right, cur, targetSum);
    }
};

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

718. 最长重复子数组

标准的dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), ret = 0;
        vector<int> dp(n + 1);
        int tmp = 0;
        for(int i = 1; i <= m; ++i)
        {
            tmp = 0;
            for(int j = 1; j <= n; ++j)
            {
                auto t = dp[j];
                dp[j] = nums1[i - 1] == nums2[j - 1] ? tmp + 1 : 0;
                ret = max(ret, dp[j]);
                tmp = t;
            }
        }
        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
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            int len = min(m - i, n); // 滑的最短长度
            int r = cal(nums1, nums2, i, 0, len);
            ret = max(ret, r);
        }
        for(int i = 0; i < n; ++i)
        {
            int len = min(n - i, m);
            int r = cal(nums1, nums2, 0, i, len);
            ret = max(ret, r);
        }
        return ret;
    }
private:
    int cal(vector<int>& nums1, vector<int>& nums2, int addA, int addB, int len)
    {
        int k = 0, ret = 0;
        for(int i = 0; i < len; ++i)
        {
            if(nums1[addA + i] == nums2[addB + i])
                ++k;
            else
                k = 0;
            ret = max(ret, k);
        }
        return ret;
    }
};

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

470. 用 Rand7() 实现 Rand10()

在拒绝采样中，如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止。

[@mzz](https://leetcode-cn.com/u/coderookie-71/)

1
第一份代码当成模拟 7 进制好理解些，把 rand7() 的值减 1 ，就成了 [0, 6]，模拟两位的 7 进制数，取 [0, 39] 范围内的值，对 10 取余后加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int col, row, ret;
        do{
            col = rand7() - 1;
            row = rand7() - 1;
            ret = col * 7 + row;
        }while(ret >= 40);
        
        return ret % 10 + 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
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int col, row, ret;
        while(true)
        {
            col = rand7();
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 40)
                return ret % 10 + 1;
            col = ret - 39;
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 60)
                return ret % 10 + 1;
            col = ret - 59;
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 20)
                return ret % 10 + 1;
        }
    }
};

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

93. 复原 IP 地址

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
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        vector<int> tmp;
        helper(s, 0, 0, ret, tmp);
        return ret;
    }
private:
    void helper(string& s, int curNum, int index, vector<string>& ret, vector<int>& tmp)
    {
        if(index == s.size() || tmp.size() == 4)
        {
            if(index == s.size() && tmp.size() == 4)
                ret.push_back(move(build(tmp)));
            return;
        }
        int cur = s[index] - '0';
        if(cur == 0 && curNum == 0)
        {
            tmp.push_back(0);
            helper(s, 0, index + 1, ret, tmp);
            tmp.pop_back();
        }else
        {
            int num = curNum * 10 + cur;
            if(num <= 255)
            {
                tmp.push_back(num);
                helper(s, 0, index + 1, ret, tmp);
                tmp.pop_back();
                helper(s, num, index + 1, ret, tmp);
            }
        }
    }
    string build(vector<int>& tmp)
    {
        string ret;
        for(auto num : tmp)
            ret += to_string(num) + '.';
        ret.pop_back();
        return ret;
    }
};

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

1143. 最长公共子序列

dp

f(i, j)表示text1[0...i)和text2[0...j)的公共字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp.back().back();
    }
};

优化空间

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 longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<int> dp(n + 1);
        int tmp = 0;
        for(int i = 1; i <= m; ++i)
        {
            tmp = 0;
            for(int j = 1; j <= n; ++j)
            {
                int pre = dp[j];
                if(text1[i - 1] == text2[j - 1])
                    dp[j] = tmp + 1;
                else
                    dp[j] = max(dp[j], dp[j - 1]);
                tmp = pre;
            }
        }
        return dp.back();
    }
};

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

151. 翻转字符串里的单词

参考剑指 Offer 58 - I. 翻转单词顺序

非原地解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int n = s.size();
        int begin = n - 1, end = n - 1;
        while(begin >= -1)
        {
            if(begin == -1 || s[begin] == ' ')
            {
                if(begin != end)
                {
                    ret += s.substr(begin + 1, end - begin);
                    ret += ' ';
                }
                end = --begin;
            }
            else
                --begin;
        }
        ret.pop_back();
        return ret;
    }
};
原地解法
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:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int idx = 0, end = 0, start = 0;
        int n = s.size();
        while(start < n)
        {
            if(s[start] != ' ')
            {
                end = start;
                while(end < n && s[end] != ' ') s[idx++] = s[end++];
                reverse(s.begin() + idx - (end - start), s.begin() + idx);
                s[idx++] = ' ';
                start = end;
            }
            ++start;
        }
        s.erase(s.begin() + idx - 1, s.end());
        return s;
    }
};

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

82. 删除排序链表中的重复元素 II

内存泄漏到爆炸了

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummyHead;
        dummyHead.next = head;
        ListNode* pre = &dummyHead;
        ListNode* point = head;
        while(point)
        {
            if(!(point->next && point->next->val == point->val))
            {
                if(!(pre->next == point))
                    pre->next = point->next;
                else
                    pre = point;
            }
            point = point->next;
        }
        return dummyHead.next;
    }
};

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

695. 岛屿的最大面积

dfs
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 maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0;
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(grid[i][j] == 1)
                    ret = max(ret, helper(grid, i, j, m, n));
        return ret;
    }
private:
    int helper(vector<vector<int>>& grid, int i, int j, int m, int n)
    {
        if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != 1)
            return 0;
        grid[i][j] = -1;
        int ret = 1 + helper(grid, i + 1, j, m, n) + helper(grid, i - 1, j, m, n) + helper(grid, i, j + 1, m, n) + helper(grid, i, j - 1, m, n);
        return ret;
    }
};

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

1995. 统计特殊四元组

暴力法
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 countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            int a = nums[i];
            for(int j = i + 1; j < n; ++j)
            {
                int t = nums[j] + a;
                unordered_map<int, int> map;
                for(int k = j + 1; k < n; ++k)
                {
                    ret += map[nums[k]];
                    ++map[t + nums[k]];
                }
            }
        }
        return ret;
    }
};

O(n^3)

优化1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        unordered_map<int, int> map;
        for(int c = n - 2; c >= 2; --c) // 从后往前遍历的过程中，hash记录下了所有的值，一旦前面和会等于记录的值，就为一个四元组
        {
            ++map[nums[c + 1]];
            for(int a = 0; a < c; ++a)
                for(int b = a + 1; b < c; ++b)
                    if(int sum = nums[c] + nums[a] + nums[b]; map.count(sum))
                        ret += map[sum];
        }
        return ret;
    }
};

O(n^3)

优化2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        unordered_map<int, int> map;
        for(int b = n - 3; b >= 1; --b) // b+1表示c，往回退时候，c会逐渐遍历到，这样就有所有的d和所有的c
        {
            for(int d = b + 2; d < n; ++d)
                ++map[nums[d] - nums[b + 1]];
            for(int a = 0; a < b; ++a)
                if(int sum = nums[a] + nums[b]; map.count(sum))
                    ret += map[sum];
        }
        return ret;
    }
};