Leetcode_20 天编程能力基础_day9

Posted on | In ,
| 5.4k | 45 mins.

从周赛回来了~

1630. Arithmetic Subarrays

Analysis

题目有点长，大概意思就是判断给定下标区间内的数能不能构成等差数列。

Code

如果这个题要优化时间，感觉可以从构成等差数列的最大区间入手呢？先暴力再说😂。

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:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        int size = nums.size(), rangesize = l.size();
        vector<bool> ret(rangesize);
        for(int i = 0; i < rangesize; i++) {
            int left = l[i], right = r[i];
            vector<int> tmp;
            while(left <= right) tmp.push_back(nums[left++]);
            sort(tmp.begin(), tmp.end());
            int diff = tmp[1] - tmp[0];
            bool flag = true;
            for(int j = 1; j < tmp.size() - 1; j++) {
                if(diff != tmp[j + 1] - tmp[j]) {
                    ret[i] = false;
                    flag = false;
                    break;
                }
            }
            if(flag) ret[i] = true;
        }
        return ret;
    }
};

em，暴力过了...🤣
想想如何优化，仔细想想构成等差数列的最大区间，其内部的小区间不一定能构成等差数列，所以这个思路可能不太行。
这样看来，一定要得把给定的小区间范围内的数挑出来后，才能进行判断。
看了一下别人的思路，其实可以避免排序。按照等差数列的性质，数列中每一项减去首项后，得到的结果全部是公差的倍数，这样就只用判断这些差是否能别第一项公差整除即可，就不用排序了。
但是要注意公差 d 为 0 时，无法当作除数，但等差数列的公差是可以为 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
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        int rangesize = l.size();
        vector<bool> ret(rangesize);
        for(int i = 0; i < rangesize; i++) {
            int left = l[i], right = r[i];
            int min1 = INT_MAX, min2 = INT_MAX;
            for(int j = left; j <= right; j++) {
                if(nums[j] < min1 && nums[j] < min2) {
                    min2 = min1;
                    min1 = nums[j];
                } else if(nums[j] >= min1 && nums[j] < min2) {
                    min2 = nums[j];
                }
            }
            int size = right - left + 1;
            if(size <= 2) {
                ret[i] = true;
                continue;
            }
            int d = min2 - min1;
            bool flag = true;
            vector<bool> visited(size, false);
            for(int j = left; j <= right; j++) {
                int tmp = nums[j] - min1;
                if((d == 0 && tmp != 0) || (d != 0 && (tmp % d != 0 || tmp / d >= size || visited[tmp / d]))) {
                    flag = false;
                    break;
                }
                if(d != 0) visited[tmp / d] = true;
            }
            ret[i] = flag;
        }
        return ret;
    }
};

就这个题而言，运行速度确实提升了不少...

429. N-ary Tree Level Order Traversal

Analysis

这个题好像是之前每日一题做过的题哈...
常规题型，N 叉树的层序遍历。

Code

这是原来写的：

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>> levelOrder(Node* root) {
        if(!root) return {};
        vector<vector<int>> ret;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            int cnt = q.size();
            vector<int> level;
            for(int i = 0; i < cnt; i++) {
                Node* cur = q.front();
                q.pop();
                level.push_back(cur->val);
                for(auto child: cur->children) {
                    q.push(child);
                }
            }
            ret.push_back(level);
        }
        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<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        queue<Node*> q;
        q.push(root);
        ret.push_back({root->val});
        while(!q.empty()) {
            queue<Node*> tmp;
            vector<int> v;
            while(!q.empty()) {
                Node *node = q.front(); q.pop();
                int size = node->children.size();
                for(int i = 0; i < size; i++) {
                    tmp.push(node->children[i]);
                    v.push_back(node->children[i]->val);
                }
            }
            q = tmp;
            if(v.size() != 0) ret.push_back(v);
        }
        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:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            int cnt = q.size();
            vector<int> level;
            for(int i = 0; i < cnt; i++) {
                Node* node = q.front(); q.pop();
                level.push_back(node->val);
                for(auto &child: node->children) {
                    q.push(child);
                }
            }
            ret.push_back(move(level));
        }
        return ret;
    }
};

用了一下 move 函数，提升一下速度。

Summary

感觉这两个题的难度大概是周赛第二道题的难度...

Buy me a coffee ? :)
0%