LeetCode 题解记录(1)

习题 / OJ / LeetCode
字数统计: 9k   |   阅读时长≈ 42 分钟

分享一些自己LeetCode题目的题解。

*标记的题目为待优化题目。

#799 [Medium]香槟塔 Champagne Tower

我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟。

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0开始）。

香槟的数量范围很大，所以不要想一杯一杯的模拟倾倒。很容易想到香槟的倾倒类似于杨辉三角，但是由于杯子最大容量为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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        int fully_layer = floor(log2(poured+1))-1;
        int rest_poured = poured - (pow(2, fully_layer+1)-1);
        double glass[100][100];
        memset(glass, 0, sizeof(glass));
        
        for(int i=0;i<=fully_layer;i++){
            for(int j=0;j<=i;j++){
                glass[i][j] += ComNum(i, j);
                glass[i+1][j] += (glass[i][j]-1)/2.0;
                glass[i+1][j+1] += (glass[i][j]-1)/2.0;
                glass[i][j] = 1;
            }
        }
        
        for(int j=0;j<=fully_layer+1;j++){
            double frac = rest_poured / (pow(2, fully_layer+1));
            glass[fully_layer+1][j] += ComNum(fully_layer+1, j)*frac;

            if(glass[fully_layer+1][j] > 1){
                glass[fully_layer+2][j] += (glass[fully_layer+1][j]-1)/2.0;
                glass[fully_layer+2][j+1] += (glass[fully_layer+1][j]-1)/2.0;
                glass[fully_layer+1][j] = 1;
            }
        }
        
        for(int i=fully_layer+2;i<query_row;i++){
            for(int j=0;j<=i;j++){
                if(glass[i][j] > 1){
                    glass[i+1][j] += (glass[i][j]-1)/2.0;
                    glass[i+1][j+1] += (glass[i][j]-1)/2.0;
                    glass[i][j] = 1;
                }
            }

        }
        
        double ans = glass[query_row][query_glass];
        if(ans > 1) ans = 1;
        return ans;
        
    }
    
    double ComNum(int n, int m){
        double numerator = 1.0, denominator = 1.0;
        for(int i=0;i<m;i++){
            denominator *= (i+1);
            numerator *= (n-i);
        }
        return numerator/denominator;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了98.15%的用户

内存消耗 :8.8 MB, 在所有 C++ 提交中击败了84.62%的用户

#235 [Easy]二叉搜索树的最近公共祖先 Lowest Common Ancestor of a Binary Search Tree

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

直接用二叉搜索树的性质就行了，这个公共祖先的值必然在两个节点的值之间，递归求解即可。

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:
    TreeNode *ans;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val < root->val && q->val < root->val){
            root = root->left;
            ans = lowestCommonAncestor(root, p, q);
        }
        else if(p->val > root->val && q->val > root->val){
            root = root->right;
            ans = lowestCommonAncestor(root, p, q);
        }
        else ans = root;
        return ans;
    }
};

执行用时 :84 ms, 在所有 C++ 提交中击败了9.13%的用户

内存消耗 :25.8 MB, 在所有 C++ 提交中击败了49.37%的用户

#236 [Medium]二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

用栈存储两个节点的到根节点的序列，序列通过递归求得。最后比较序列即可。一个笨方法。

看了一下其他人分享的题解，也有重建树创建父节点的，DFS的，加布尔标记的，感觉也都不是很聪明。

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
/**
 * 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:
    stack<TreeNode*> sp, sq;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        findParent(root, p, sp); cout<<"---"<<endl;
        findParent(root, q, sq);
        cout<<sp.size()<<" "<<sq.size()<<endl;
        stack<TreeNode*> *max, *min;
        TreeNode *ans = NULL;
        if(sp.size() > sq.size()) { max = &sp; min = &sq; }
        else { max = &sq; min = &sp; }
        int i, max_size = max->size(), min_size = min->size();
        for(i=0;i<(max_size-min_size) && ans == NULL;i++){
            if(max->top() == min->top()){
                ans = max->top();
            }
            else max->pop();
        }
        for(;i<max_size && ans == NULL;i++){
            if(max->top() == min->top()){
                ans = max->top();
            }
            else { max->pop(); min->pop(); }
        }
        return ans;
    }
    
    bool findParent(TreeNode* root, TreeNode* node, stack<TreeNode*> &s){
        s.push(root);
        cout<<"Push "<<root->val<<endl;
        if(root == node) return true;
        if(root->left == NULL && root->right == NULL) {
            cout<<"Pop "<<s.top()->val<<endl;
            s.pop();
            return false;
        }
            
        if(root->left != NULL)
            if(findParent(root->left, node, s)) return true;
        if(root->right != NULL)
            if(findParent(root->right, node, s)) return true;
        cout<<"Pop "<<s.top()->val<<endl;
        s.pop();
        return false;
    }
    
    
};

执行用时 :40 ms, 在所有 C++ 提交中击败了29.07%的用户

内存消耗 :20.5 MB, 在所有 C++ 提交中击败了6.90%的用户

#239* [Hard]滑动窗口最大值 Sliding Window Maximum

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

$O(nk)$ 的算法非常简单，但是很慢：

执行用时 :156 ms, 在所有 C++ 提交中击败了10.90%的用户

内存消耗 :12.6 MB, 在所有 C++ 提交中击败了98.71%的用户

可以尝试 $O(n)$ 的算法，较为复杂。问题的关键在于在常数时间内处理滑动窗口内的最值。

#404 [Easy]左子叶之和 Sum of Left Leaves

计算给定二叉树的所有左叶子之和。

直接递归就好，注意左叶子的定义和特殊情况。这里单独讲一下这题是因为才发现LeetCode可以自定义测试用例，可以对一些需要单独讨论的情形进行测试来避免踩坑。

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 sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL || (root->left == NULL && root->right == NULL)) return 0;
        int left_val = 0;
        int right_val = 0;
        
        if(root->left != NULL && root->left->left == NULL && root->left->right == NULL) 
            left_val = root->left->val;
        if(root->left != NULL && (root->left->left != NULL || root->left->right != NULL))
            left_val = sumOfLeftLeaves(root->left);
        if(root->right != NULL && (root->right->left != NULL || root->right->right != NULL)) 
            right_val = sumOfLeftLeaves(root->right);
        return left_val + right_val;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了90.75%的用户

内存消耗 :13.3 MB, 在所有 C++ 提交中击败了96.55%的用户

#536 [Medium]从字符串生成二叉树 Construct Binary Tree from String

你需要从一个包括括号和整数的字符串构建一棵二叉树。

输入的字符串代表一棵二叉树。它包括整数和随后的0，1或2对括号。整数代表根的值，一对括号内表示同样结构的子树。

若存在左子结点，则从左子结点开始构建。

这题只要注意几个点就好，一个是树深度和字符转数字都需要存储(一般用栈)，一个是回溯的判定条件。如果以括号来判定数字的终止，则需要对无括号的单节点树做单独判断。

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
72
73
/**
 * 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:
    TreeNode* str2tree(string s) {
        if(s == "") return NULL;
        
        TreeNode *root = new TreeNode(0);
        stack<TreeNode *> tree;
        stack<int> num;
        bool isPositive = true;
        for(int i=0;i<s.length();i++){
            if(s[i] == '(' || s[i] == ')'){
                if(num.size() != 0){
                    int val = 0;
                    int times = 1;
                    while(num.size() != 0){
                        val += times * num.top();
                        times *= 10;
                        num.pop();
                    }
                    if(!isPositive) val = -val;
                    root->val = val;
                    isPositive = true;
                }
                
                if(s[i] == '('){
                    if(root->left == NULL){
                        tree.push(root);
                        root->left = new TreeNode(0);
                        root = root->left;
                    }
                    else{
                        tree.push(root);
                        root->right = new TreeNode(0);
                        root = root->right;
                    }
                }
                else if(s[i] == ')'){
                    root = tree.top();
                    tree.pop();
                }
            }
            else if(s[i] == '-'){
                isPositive = false;
            }
            else{
                num.push((int)(s[i]-48));
            }
        }
        
        if(num.size() != 0){
            int val = 0;
            int times = 1;
            while(num.size() != 0){
                val += times * num.top();
                times *= 10;
                num.pop();
            }
            if(!isPositive) val = -val;
            root->val = val;
            isPositive = true;
        }
        return root;
    }
};

执行用时 :44 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :21.9 MB, 在所有 C++ 提交中击败了100.00%的用户

#201 [Medium]数字范围按位与 Bitwise AND of Numbers Range

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

首先弄清楚题意，是把区间内所有的数字做按位与 。实际上只需要处理区间端点即可，由于区间内所有数字在相应位上都是1，结果在这一位才是1，所以对于结果的每一位，这一位为1仅当：

  1. 端点两数在此位为1
  2. 端点两数的差小于此位上对应的二进制数(否则区间内总有一个数在此位上为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
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:
    int rangeBitwiseAnd(int m, int n) {
        string m_2, n_2, ans;
        m_2 = biTrans(m);
        n_2 = biTrans(n);
        int m_2l = m_2.length();
        for(int i=0;i<n_2.length()-m_2l;i++){
            m_2 = "0" + m_2;
        }
        for(int i=0;i<n_2.length();i++){
            if(m_2[i] == '1' && n_2[i] == '1'){
                if(n-m < pow(2,n_2.length()-i-1)) ans.append("1");
                else ans.append("0");
            }
            else ans.append("0");
        }
        int ans_int = 0;
        for(int i=0;i<ans.length();i++){
            if(ans[i] == '1')
                ans_int += pow(2,ans.length()-i-1);
        }
        return ans_int;
    }
    
    string biTrans(int x){
        string str;
        int num = (int)log2(x);
        while(x != 0){
            if(x >= pow(2,num)){
                x = x - pow(2,num);
                str.append("1");
                if(x == 0){
                    while(num != 0){
                        str.append("0");
                        num--;
                    }
                }
            }
            else{
                str.append("0");
            }
            num -- ;
        }
        return str;
    }
    
};

执行用时 :36 ms, 在所有 C++ 提交中击败了21.63%的用户

内存消耗 :8.6 MB, 在所有 C++ 提交中击败了5.30%的用户

从第二点出发可以直接在二进制数上操作，即结果为端点两数从高位开始取连续的相同部分；一旦某一位开始不同，其后取交必为0。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int offset = 0;
        for (; m != n; ++offset) {
            m >>= 1;
            n >>= 1;
        }
        return n << offset;
    }
};

执行用时 :24 ms, 在所有 C++ 提交中击败了56.06%的用户

内存消耗 :8 MB, 在所有 C++ 提交中击败了70.45%的用户

#242 [Easy]有效的字母异位词 Valid Anagram

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意审题，字母异位词的意思是相同的字母打乱生成的串(原题没有明确定义，有些坑)。

第一个想到的是存字典(C++ map)，这种做法可以处理非unicode字符，但是有一个 $O(n)$ 的空间花销（对于不确定的字符种类数来说，若视字符种类数为确定数量的话为 $O(1)$ ）。我后面才看到纯小写字母的字符串，可以直接排序后逐项判断，不过时间就不是 $O(n)$ 的了。

第一次用map，这里的int型初始值都是0，和python的dict有点不一样(因为dict不知道你的值的类型)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char, int> s_map, t_map;
        if(s.length() != t.length()) return false;
        int l = s.length();
        for(int i=0;i<l;i++){
            s_map[s[i]]++;
            t_map[t[i]]++;
        }
        for(int i=0;i<l;i++){
            if(s_map[s[i]] != t_map[s[i]]) return false;
        }
        return true;
    }
};

其实可以不用两个map，s在map上++而t在map上—即可，最终判断map是否全零。

执行用时 :28 ms, 在所有 C++ 提交中击败了40.59%的用户

内存消耗 :9.7 MB, 在所有 C++ 提交中击败了5.14%的用户

#107 [Easy] 二叉树的层次遍历II Binary Tree Level Order Traversal II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

遍历树，递归大法好。第一次用STL中的 reverse 函数。

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
/**
 * 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<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL) return ans;
        iteration(root, ans, 0);
        reverse(ans.begin(),ans.end());
        return ans;
    }
    
    void iteration(TreeNode *root, vector<vector<int>> &array, int layer){
        if(array.size() <= layer) array.push_back({});
        array[layer].push_back(root->val);
        if(root->left  != NULL) iteration(root->left,  array, layer+1);
        if(root->right != NULL) iteration(root->right, array, layer+1);
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了97.54%的用户

内存消耗 :14.7 MB, 在所有 C++ 提交中击败了23.82%的用户

#61 [Medium] 旋转链表 Rotate List

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

只要找到需要移位的链表段，把头尾的next指针改一下即可。怎么找到需要移位的链表段思路简单但是也需要考虑一些特殊情况。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode *fast, *slow, *ans;
        fast = head, slow = head;
        if(head == NULL || head->next == NULL) return head;
        int l=1; //记录长度
        for(int i=0;i<k;i++){
            fast = fast->next;
            l++;
            if(fast->next == NULL) { 
                fast = head; 
                for(int i=0;i<k%l;i++){ //k特别大时去掉循环
                    fast = fast->next;
                }
                break; 
            }
        }
        while(fast->next != NULL){ 
          //fast指向改动段尾部节点，slow指向不动段尾部节点
            fast = fast->next;
            slow = slow->next;
        }
        if(fast == slow) return head;
        ans = slow->next;
        slow->next = NULL;
        fast->next = head;
        return ans;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了86.03%的用户

内存消耗 :8.9 MB, 在所有 C++ 提交中击败了88.27%的用户

#1109 [Medium] 航班预订统计 Corporate Flight Bookings

这里有 n 个航班，它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

这道题主要的难点是卡时间，不能直接进行模拟，一些测试点还锁死了合并处理的可能。这题必须进行预处理，把多个bookings的数据格式整理成长度为n记录bookings起始点和终点的格式，便于后面计算的时候遍历。预处理和计算的复杂度都是 $O(n)$ 。

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> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> start, end, ans;
        for(int i=0;i<n;i++){
            start.push_back(0);
            end.push_back(0);
            ans.push_back(0);
        }
        for(int i=0;i<bookings.size();i++){
            start[bookings[i][0]-1] += bookings[i][2];
            end[bookings[i][1]-1] += bookings[i][2];
        }
        ans[0] = start[0];
        for(int i=1;i<n;i++){
            ans[i] = ans[i-1] + start[i] - end[i-1];
        }
        return ans;
    }
};

执行用时 :364 ms, 在所有 C++ 提交中击败了66.94%的用户

内存消耗 :46.5 MB, 在所有 C++ 提交中击败了100.00%的用户

#240 [Medium] 搜索二维矩阵II Search a 2D Matrix II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

一个比较慢的算法时逐行搜索，跳过从最左边元素大于target、最右边元素小于target的行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int line=0;line<matrix.size();line++){
            if(matrix[line].size() == 0) return false;
            if(matrix[line][0] > target || matrix[line][matrix[line].size()-1] < target) continue;
            for(int col=0;col<matrix[line].size();col++){
                if(matrix[line][col] == target) return true;
                else if(matrix[line][col] > target) break;
            }
        }
        return false;
    }
};

执行用时 :600 ms, 在所有 C++ 提交中击败了9.53%的用户

内存消耗 :12.7 MB, 在所有 C++ 提交中击败了91.83%的用户

可以递归地四分这个矩阵，可以通过同样的规则排除掉至少一个分块矩阵。

#906 [Hard] 超级回文数 Super Palindromes

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

提示：

1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
int(L) <= int(R)

由于L、R在long型的表示范围内，且这个范围内的回文数并不多(70个左右)，大部分答案是自己打表过的(所以平均时间很快)。官方标答为对 $[1,10^5]$ 区间遍历生成回文数，判断其平方是否为区间内超级回文数。

实际这样操作耗时过大，可以进一步优化。考虑回文数的竖式乘法，由于回文数的乘方必须得是回文数，而乘法操作中的进位总是破坏回文对称性，所以回文数的乘法中一定不能进位。最容易进位的位置总是结果中的中间位(也是乘数中的顶位)，通过计算可以知道对于一个 $n$ 回文数，其乘方如果不在顶位上进位，一定有 $\sum n[i]^2 < 10$ 。更进一步的可以找到更多规律，比如除了9之外，剩余的超级回文数开方的数总是由0、1和2组成 (因为 $1^2+3^2+1^2>10$) ，且由于平方和不能超过10，除0之外的数只能有几种组合(11、121、1111、22等)，使用这几种组合可以通过组合数用很少的运算量在任意位数上直接生成该位数的所有超级回文数。虽然仍然需要特殊讨论的情况(奇偶数，9等)，但是肯定比打表更普适，也比官方标答快（因为是直接生成超级回文数而非遍历）。

下面的代码只用上面的部分规则对遍历进行了优化，实质还是遍历区间，所以还是比较慢。如果用3进制来优化遍历，不仅极大优化遍历效果，写起来也容易。

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
class Solution {
public:
    int superpalindromesInRange(string L, string R) {
        //对于3位aba回文数，a^2+b^2+a^2 < 10 （不进位）
        //对于n位abcd...ff...dcba，2a^2+2b^2+...+2f^2 < 10，前半部分<6
        // 1 2 3/ 11 22 111 121 1111 1111.... 1(x10)
        int ans = 0;
        for(int i=0;i<100000;i++){
            string i_s = to_string(i);
            int sum = 0;
            long num = 0;
            for(int j=0;j<i_s.length();j++)
                sum += pow(i_s[j]-48, 2);
            if(sum != 9 && sum > 6 ) continue;
            sum = 0;
            
            string ii = to_string(i); //偶数
            for(int j=i_s.length()-1;j>=0;j--)
                ii += i_s[j];
            for(int j=0;j<ii.length();j++)
                sum += pow(ii[j]-48, 2);
            if(sum < 10){
                num = pow(stol(ii),2);
                if(num <= stol(R) && num >= stol(L))
                    ans++;
            }
            sum = 0;
            
            string iii = to_string(i); //奇数
            for(int j=i_s.length()-2;j>=0;j--)
                iii += i_s[j];
            for(int j=0;j<iii.length();j++)
                sum += pow(iii[j]-48, 2);
            if(sum >= 10) continue;
            
            num = pow(stol(iii),2);
            if(num <= stol(R) && num >= stol(L))
                ans++;
        }
        return ans;
    }
};

执行用时 :1164 ms, 在所有 C++ 提交中击败了16.67%的用户

内存消耗 :8.6 MB, 在所有 C++ 提交中击败了96.00%的用户

#942 [Easy] 增减字符串匹配 DI String Match

给定只含 “I”（增大）或 “D”（减小）的字符串 S ，令 N = S.length。

返回 [0, 1, …, N] 的任意排列 A 使得对于所有 i = 0, …, N-1，都有：

如果 S[i] == “I”，那么 A[i] < A[i+1]
如果 S[i] == “D”，那么 A[i] > A[i+1]

注意审题，返回的是区间内的排列，即不可有重复数字。

直接在递增数列上对D进行处理即可。对连续的n个D，彻底逆序相应位置上的n+1个数（12345变54321）。这样可以既可以保证逆序区间内一定递减，又可以保证区间之间绝对的递增关系。

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> diStringMatch(string S) {
        vector<int> ans;
        for(int i=0;i<=S.length();i++) ans.push_back(i);
        int count = 0;
        for(int i=0;i<S.length();i++){
            if(S[i] == 'I') continue;
            if(S[i] == 'D') {
                count++;
                if(i==S.length()-1 || S[i+1] == 'I'){
                    int len = count;
                    for(int j=0;j<=len;j++){
                        ans[i+1-j] -= count;
                        count -= 2;
                    }
                    count = 0;
                }
            }
        }
        return ans;
    }
};

执行用时 :56 ms, 在所有 C++ 提交中击败了92.67%的用户

内存消耗 :10.5 MB, 在所有 C++ 提交中击败了70.98%的用户

#885 [Easy] 螺旋矩阵III Spiral Matrix III

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

提示：

  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 0 <= c0 < C

看数据规模，直接模拟行走就能过，走的时候判断一下该点是否需要输出即可。

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
class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> ans;
        vector<int> point;
        int len = 1, step = 0, dir, r = r0, c = c0;
        while(ans.size() < R*C){
            dir = step%4;
            if(dir == 0){
                for(int i=0;i<len;i++){
                    point = {r, c+i};
                    if(isInMat(r,c+i,R,C))
                      ans.push_back(point);
                }
                c += len;
            }
            if(dir == 1){
                for(int i=0;i<len;i++){
                    point = {r+i, c};
                    if(isInMat(r+i,c,R,C)) 
                    	ans.push_back(point);
                }
                r += len;
                len++;
            }
            if(dir == 2){
                for(int i=0;i<len;i++){
                    point = {r, c-i};
                    if(isInMat(r,c-i,R,C))
                      ans.push_back(point);
                }
                c -= len;
            }
            if(dir == 3){
                for(int i=0;i<len;i++){
                    point = {r-i, c};
                    if(isInMat(r-i,c,R,C)) 
                      ans.push_back(point);
                }
                r -= len;
                len++;
            }
            step++;
        }
        return ans;
    }
    
    bool isInMat(int r, int c, int R, int C){
        if(r >= 0 && r <= R-1 && c >=0 && c <= C-1) return true;
        else return false;
    }
};

执行用时 :164 ms, 在所有 C++ 提交中击败了7.50%的用户

内存消耗 :13.5 MB, 在所有 C++ 提交中击败了84.38%的用户

#207 [Medium] 课程表 Course Schedule

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
拓扑排序也可以通过 BFS 完成。

之前一直随机做题。。这次定向搞一道图论复习一下。

说明和提示里说的很清楚了，问题等价于查一个有向图中是否有环。DFS或者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
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:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // build the graph
        vector<Node*> classes;
        for(int i=0;i<numCourses;i++){
            Node *node = new Node();
            node->val = i;
            classes.push_back(node);
        }
        for(int i=0;i<prerequisites.size();i++){
            classes[prerequisites[i][0]]->sub_array.push_back(classes[prerequisites[i][1]]);
        }
        // done
        
        // dfs
        for(int i=0;i<numCourses;i++){
            if(classes[i]->islearn == 1) continue;
            if(classes[i]->islearn == 0) return false;
            search(numCourses, classes[i]);
            if(classes[i]->islearn == 0) return false;
        }
        
        return true;
    }
    
    class Node{
    public:
        int val;
        int islearn = 2; // 2 for undefined
        vector<Node*> sub_array;
    };
    
    void search(int numCourses, Node* node){
        if(node->sub_array.size() == 0) {
            node->islearn = 1; return;
        }
        node->islearn = 3; // 3 for searching
        for(int i=0;i<node->sub_array.size();i++) {
            if(node->sub_array[i]->islearn == 2){
                search(numCourses, node->sub_array[i]);
            }
            else{
                if(node->sub_array[i]->islearn == 3 || node->sub_array[i]->islearn == 0){
                    node->islearn = 0;
                    return;
                }
            }
        }
        node->islearn = 1;
        return;
    }
};

执行用时 :52 ms, 在所有 C++ 提交中击败了37.92%的用户

内存消耗 :13.4 MB, 在所有 C++ 提交中击败了16.84%的用户

#200 [Medium] 岛屿数量 Number of Islands

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

说来惭愧，第一次学并查集，第一次写并查集的程序。写的时候觉得DFS虽然复杂度等级一样，但是在这里应该会很慢，但实际跑了 一下DFS似乎也不慢，时间空间都好过并查集，只能说感性上的估计还是不靠谱，有时候硬写DFS也不是不行。

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
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        vector<Node*> set;
        vector<vector<Node*>> map;
        for(int i=0;i<grid.size();i++){
            vector<Node*> newVec;
            map.push_back(newVec);
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j] == '1'){
                    Node* newNode = new Node(1);
                    map[i].push_back(newNode);
                    if(i>=1 && map[i-1][j]->val == 1) map[i][j]->pre = map[i-1][j];
                    if(j>=1 && map[i][j-1]->val == 1) map[i][j]->pre = map[i][j-1];
                    if(i>=1 && j>= 1 && map[i-1][j]->val == 1 && map[i][j-1]->val == 1){
                        if(Node::search(map[i-1][j]) != Node::search(map[i][j-1]))
                            Node::search(map[i][j-1])->pre = Node::search(map[i-1][j]);
                    }
                    if(map[i][j]->pre == NULL) set.push_back(map[i][j]);
                }
                else{
                    Node *newNode = new Node(0);
                    map[i].push_back(newNode);
                }
            }
        }
        int ans = set.size();
        for(int i=0;i<set.size();i++){
            if(set[i]->pre != NULL) ans--;
        }
        return ans;
    }
    
    class Node{
    public:
        Node(int val){ this->val = val; };
        Node *pre = NULL;
        int val = 0;
        static Node* search(Node *node){
            if(node->pre == NULL) return node;
            else return search(node->pre);
        }
        static void nodeUnion(Node *a, Node *b){
            Node::search(a)->pre = Node::search(b);
        }
    };
};

执行用时 :40 ms, 在所有 C++ 提交中击败了5.71%的用户

内存消耗 :14.4 MB, 在所有 C++ 提交中击败了5.04%的用户

#746 [Easy] 使用最小花费爬楼梯 Min Cost Climbing Stairs

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

做一道Medium的DP题练手，突然发现自己好像不会DP了，赶紧来一道Easy的DP压压惊。。

最优子问题是求上到第i级台阶的最小总花费，求解需要知道当前第i级台阶单级花费和第i-2/i-1级的最小总花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> ans(cost.size());
        if(cost.size() == 2) return min(cost[0], cost[1]);
        ans[0] = cost[0];
        ans[1] = cost[1];
        for(int i=2;i<cost.size();i++){
            ans[i] = min(ans[i-1] + cost[i], ans[i-2] + cost[i]);
        }
        return min(ans[cost.size()-1], ans[cost.size()-2]);
    }
    
    int min(int a, int b){
        return a < b ? a : b;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了98.79%的用户

内存消耗 :8.8 MB, 在所有 C++ 提交中击败了78.30%的用户

#768 [Easy] 托普利茨矩阵 Toeplitz Matrix

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

简单的检索。Hard不会做，只能写写Easy维持生活这样子。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int x = matrix.size(), y = matrix[0].size();
        for(int i=0;i<x;i++){
            int num = matrix[i][0];
            for(int j=0;j<y && i+j<x;j++)
                if(matrix[i+j][j] != num)  return false;
        }
        for(int i=0;i<y;i++){
            int num = matrix[0][i];
                    for(int j=0;j<x && i+j<y;j++)
                        if(matrix[j][i+j] != num)  return false; 
        }
        return true;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了91.48%的用户

内存消耗 :9.7 MB, 在所有 C++ 提交中击败了83.67%的用户

#643 [Easy] 子数组最大平均数I Maximum Average Subarray I

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

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

就是很简单的做法，然后我看其他人的代码的时候发现跑的快的几个都带了IO优化。。服辽

执行用时 :188 ms, 在所有 C++ 提交中击败了44.39%的用户

内存消耗 :16.9 MB, 在所有 C++ 提交中击败了62.93%的用户

#221 [Medium] 最大正方形 Maximal Square

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

这题不卡时间，直接暴力也可以做。对于每个1，开始从边长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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0) return 0;
        int x = matrix.size();
        int y = matrix[0].size();
        int ans = 0;
        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                int newAns = findSquare(matrix, i, j);
                if(newAns > ans) ans = newAns;
            }
        }
        return ans*ans;
    }
    
    int findSquare(vector<vector<char>>& matrix, int x, int y){
        int n = 1;
        while(true){
            if(x+n > matrix.size() || y+n > matrix[0].size()) return n-1;
            for(int i=x;i<x+n && i<matrix.size();i++){
                if(matrix[i][y+n-1] == '0') return n-1; 
            }
            for(int i=y;i<y+n && i<matrix[0].size();i++){
                if(matrix[x+n-1][i] == '0') return n-1; 
            }
            n++;
        }
    }
};

执行用时 :28 ms, 在所有 C++ 提交中击败了45.78%的用户

内存消耗 :10.3 MB, 在所有 C++ 提交中击败了100.00%的用户

有一个比较独特的DP的方法，其实挺难想的， 用左-左上-上的数来递推当前格的数，即对每个1，将其更新为 $\min{\text{Left, Left-Up, Up}}+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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int num = 0;
        if(matrix.size() == 0) return 0;
        vector<int> vec(matrix[0].size());
        for(int i=0;i<vec.size();i++){
            vec[i] = matrix[0][i] - 48;
            if(vec[i] > num) num = vec[i];
        }
        for(int i=1;i<matrix.size();i++){
            int pre_num = matrix[i-1][0] - 48;
            vec[0] = matrix[i][0] - 48;
            if(vec[0] > num) num = vec[0];
            for(int j=1;j<matrix[0].size();j++){
                if(matrix[i][j] == '1'){
                    int mid_num = vec[j];
                    vec[j] = min(min(vec[j-1], pre_num), vec[j]) + 1;
                    pre_num = mid_num;
                    if(vec[j] > num) num = vec[j];
                }
                if(matrix[i][j] == '0') vec[j] = 0;
            }
            cout<<endl;
        }
        return num*num;
    }
};

执行用时 :44 ms, 在所有 C++ 提交中击败了11.99%的用户

内存消耗 :10.6 MB, 在所有 C++ 提交中击败了96.41%的用户

（竟然还慢过暴力。。

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2019-2020 thiswinex
  • 访问人数: | 浏览次数:

请我喝奶茶~

支付宝
微信