LeetCode Weekly Contest 115

发表于 | | 阅读次数:
字数统计: 1.9k | 阅读时长 ≈ 8

Prison Cells After N Days

题目链接

https://leetcode.com/problems/prison-cells-after-n-days/

题意

给一个仅包含0和1的长度为8的数组(排成一行)，数组进行一次变换的定义如下:

  • 如果一个元素相邻的元素都为1或都为0，这个元素下一步会变成1
  • 否则，元素变成0

(最首元素和最末元素始终没有两个相邻元素所以会变成0)

求出数组经过$N(1 \leq N \leq 10^{9})$次变换后的值

题目类型

智力

题目分析

咋一看N很大有点吓人，但细细一想数组总的可能情况也只有 $ 2^{8} = 256 $种，而且数组是满足循环性质的，所以数组一定会跑不到N次就出现循环，问题就变得简单了。

利用二进制记录数组状态，一旦数组重复了以前出现的样子，就不必再计算，把 剩下的步数 除以 循环的长度 取模值，继续步进该数值的步数即是循环N次后的答案。

时间复杂度

$O(256*8)$

源代码

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
class Solution {
public:
    int toInt(vector<int> a) {
        int i, x = 0;
        for (i = 0; i < 8; i++)
            x = ((x << 1) + a[i]);
        return x;
    }
    vector<int> change(vector<int> a) {
        int i;
        vector<int> b;
        b.push_back(0);
        for (i = 1; i < 7; i++)
        {
            if (a[i + 1] == a[i - 1])
                b.push_back(1);
            else
                b.push_back(0);
        }
        b.push_back(0);
        return b;
    }
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        int i, tmp;
        vector<vector<int>> save_cells;
        save_cells.push_back(cells);
        map<int, int> S;
        S[toInt(cells)] = 0;
        for (i = 1; i <= N; i++) {
            cells = change(cells);
            tmp = toInt(cells);
            if (S.find(tmp) != S.end())
                break;
            S[tmp] = i;
            save_cells.push_back(cells);
        }
        if (i == N + 1)
            return cells;
        int j = S[tmp];
        N = (N - j) % (i - j) + j;
        return save_cells[N];
    }
};

Check Completeness of a Binary Tree

题目链接

https://leetcode.com/problems/check-completeness-of-a-binary-tree/

题意

给出一棵树判断其是否属于完全二叉树得到true or false，关于完全二叉树的定义: complete binary tree

完全二叉树中除最后一层外均有节点填满，且最后一层的节点全部靠左(还是看wiki吧不知道怎么说)

树的节点数在1到100间

题目类型

树

题目分析

我的办法是首先找到每个节点的深度得到最大深度maxdep，然后统计深度少于maxdep的节点数，要满足等于$2^{maxdep - 1} - 1$

随后把倒数第二层的所有节点的左右儿子(包括NULL)都放入一个数组，判断数组是否是 左边全是not NULL，右边全是NULL，换句话说如果第一次出现NULL了以后如果后面还有not NULL的节点则不是完全二叉树

应该有比我更好的办法

时间复杂度

$O(N)$

源代码

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:
    map<TreeNode*, int>S;
    int maxdep = -1;
    void Dfs(TreeNode *cur, int dep) {
        if (cur == NULL)
            return;
        maxdep = max(maxdep, dep);
        S[cur] = dep;
        Dfs(cur->left, dep + 1);
        Dfs(cur->right,dep + 1);
    }
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*>q;
        TreeNode* cur;
        Dfs(root, 1);
        q.push(root);
        int cnt = 0;
        bool flag = true;
        vector<TreeNode*>a;
        while(!q.empty()) {
            cur = q.front();q.pop();
            cnt++;
            if (flag) {
                if (S[cur] == maxdep) {
                    flag = false;
                    if (cnt != (1 << (maxdep - 1)))
                        return false;
                }
            }
            if (!flag)
                a.push_back(cur);
            if (cur) {
                if (S[cur] < maxdep - 1) {
                    if (!(cur->left && cur->right))
                        return false;
                }
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        flag = true;
        for (int i = 0; i < a.size(); i++) {
            if (!a[i]) {
                flag = false;
            }
            if (!flag && a[i])
                return false;
        }
        return true;
    }
};

Regions Cut By Slashes

题目链接

https://leetcode.com/problems/regions-cut-by-slashes/

题意

由 1 x 1 的方格中组成 N x N 的网格grid，每个 1 x 1 的网格中包含 /,\或空格，这些字符会将方格划分成一些区域。

给出每个网格中的字符，求出划分出的区域的个数。（请注意，反斜杠字符是转义的，因此 \ 用 “\“ 表示）

grid 满足 1 <= grid.length == grid[0].length <= 30

具体含义戳链接看一下样例应该能明白得更透彻

题目类型

图论
并查集

题目分析

很好玩的题目，咋一看很让人摸不着头脑，但是细细一想这道题可以转换成图论中求联通块的数目的问题。

把每个 1 x 1 的小方格分为 左边 和 右边 两个，每次连边时只考虑相邻块的左边的块和上面的块：

  • 连接上面的块时，首先看自己网格，如果是’/‘用左块去连，如果是’'用右块去连;其次看上面网格，是’'则连左边块，是’/‘则连右边块
  • 连接左边的块时，不管左边块是什么，一定是本块的左边块 连 左边网格的右块
  • 方格为’ ‘, 把该网格的左块和右块连起来

连边找联通块数目，并查集解决这个问题非常方便，就不多赘述了

时间复杂度

$O(grid.length ^ {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
class Solution {
public:
    int fa[10020], n;
    int get_fa(int x) {
        if (fa[x] != 0)
            return fa[x] = get_fa(fa[x]);
        return x;
    }
    void Combine(int x, int y) {
        x = get_fa(x);
        y = get_fa(y);
        if (x == y)
            return;
        if (x > y)
            swap(x, y);
        fa[y] = x;
    }
    int get_sit(int x, int y) {
        x++;
        y++;
        return (x - 1) * n + y;
    }
    int regionsBySlashes(vector<string>& grid) {
        int m, sit, sl, sr;
        int upsit,leftsit;
        int i, j, maxsit = 0;
        n = grid.size();
        for (i = 0; i < n; i++) {
            m = grid[i].size();
            for (j = 0; j < m; j++) {
                sit = get_sit(i, j);
                upsit = get_sit(i - 1, j);
                leftsit = get_sit(i, j - 1);
                sl = 2*sit - 1;
                sr = 2*sit;
                maxsit = max(maxsit, sit);
                if (grid[i][j] == ' ') {
                    Combine(sl, sr);
                }
                if (grid[i][j] == '/') {
                    if (i > 0) {
                        if (grid[i - 1][j] == '/')
                            Combine(upsit * 2, sl);
                        else
                            Combine(upsit * 2 - 1, sl);
                    }
                    if (j > 0) {
                        Combine(leftsit * 2, sl);
                    }
                }
                else {
                    if (i > 0) {
                        if (grid[i - 1][j] == '/')
                            Combine(upsit * 2, sr);
                        else
                            Combine(upsit * 2 - 1, sr);
                    }
                    if (j > 0) {
                        Combine(leftsit * 2, sl);
                    }
                }
            }
        }
        int ans = 0;
        for (i = 1; i <= maxsit*2; i++)
            if (fa[i] == 0)
                ans++;
        return ans;
    }
};

Delete Columns to Make Sorted III

题目链接

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

题意

给出一个由N个相同长度的小写字符串组成的数组A，可以选择其中的某列，把所有字符串的该列的字符都删掉。

例如 A = [“babca”,”bbazb”] 删除集合为 {0, 1, 4}， 最后会剩下 [“bc”,”az”]

求出最小的集合，满足删除后的数组A中的每个字符串都有字典序不降序 (ie. A[0][0] <= A[0][1] <= … <= A[0][A[0].length - 1])

其中：

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100

题目类型

动态规划

题目分析

就是披了层皮的最长上升子序列问题，定义第i列小于等于第j列为:

所有A中的字符串都有 A[k][i] <= A[k][j]

如果满足该条件则有转移方程 f[j] = max { f[i] + 1 }

f[i]的初值为1，求出A中的最长上升子序列长度后 列数 - 长度 即为最终的答案

时间复杂度

$O(A.length \ast {A[i].length ^ {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
class Solution {
public:
    bool smaller(int i, int j, vector<string>& A, int n) {
        int k;
        for (k = 0; k < n; k++)
            if (A[k][i] > A[k][j])
                return false;
        return true;
    }
    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].size();
        int i, maxd = -1, j;
        int f[102];
        for (i = 0; i < m; i++) {
            f[i] = 1;
            for (j = 0; j < i; j++)
            {
                if (smaller(j, i, A, n))
                    f[i] = max(f[i], f[j] + 1);
            }
            maxd = max(maxd, f[i]);
        }
        return m - maxd;
    }
};
0%