七夕佳节，程序员情侣秀了我一脸，我也不甘示弱打掉了周赛

ACM算法日常

发布于 2021-09-07 14:53:27

3370

发布于 2021-09-07 14:53:27

文章被收录于专栏：ACM算法日常

七夕佳节，同事在群里发了他和对象过节的方式：早上 PK 词汇量，下午一起学框架。

太秀了太秀了，小弟甘拜下风，不过大家和对象约完会之后可不要忘了打卡本周周赛（笑）

说回本场周赛，略有难度，知识点：字符串，构造，贪心，广度优先搜索，二分答案

作为子字符串出现在单词中的字符串数目

给定字典

，给定字符串

，判断

中有多少字符串是

的子串

题解

直接模拟

// go
func numOfStrings(patterns []string, word string) int {
    ans := 0
    for _, v := range(patterns) {
        if strings.Contains(word, v) {
            ans++
        }
    }
    return ans
}

构造元素不等于两相邻元素平均值的数组

给定一个数组

，保证元素互不相同，要求重排列，使得除去头尾的其他每一个元素都不是左右两个元素的平均值

数据规定

1\leq n\leq 10^5

题解

将数组排序，用两个指针从头尾开始扫，先放头再放尾，就可以保证每一个元素都小于/大于相邻的左右两个元素，时间复杂度

O(n\log n)

// cpp
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> ans;
        int i = 0, j = n - 1;
        while (i <= j) {
            if (i <= j) ans.push_back(nums[i++]);
            if (i <= j) ans.push_back(nums[j--]);
        }
        return ans;
    }
};

// go
func rearrangeArray(nums []int) []int {
    n := len(nums)
    sort.Ints(nums)
    ans := []int{}
    for i, j, k := 0, n - 1, 0; i <= j; k++ {
        if i <= j {
            ans, i = append(ans, nums[i]), i + 1
        }
        if i <= j {
            ans, j = append(ans, nums[j]), j - 1
        }
    }
    return ans
}

数组元素的最小非零乘积

给定正整数

，给定数组

，包含 1, 2, .., 2^p - 1 中的所有正整数

现在可以选择数组中的任意两个元素

a,\ b

，把其中一位不同的二进制位互相替换

例如对于 1011, 0100，可以换成 1111, 0000

可以执行任意多次操作，要求计算操作后数组乘积的最小值

数据规定

1\leq p\leq 60

题解

可以执行任意多次操作，就很有搞头了

设

m = 2^p - 1

，选取

a,\ m - a

，一定可以保证他们的二进制互补，互补的含义是每一位都不相同

例如

m = 2^4 - 1 = 15

，选取

a = (0111)_2 = 7,\ b = (1000)_2 = 8

我们执行一定次数的操作，一定可以使得

a,\ b

最终成为

1,\ m - 1

，例如在上述例子中为

1,\ 14

，这样的乘积是最小的

考虑互补的对数，一共有

2^{p - 1} - 1

对，每一对的乘积为

2^p - 2

，再乘上不配对的

2^p - 1

，因此最终的答案为

(2^p - 1)\cdot (2^p - 2)^{2^{p - 1} - 1}

利用快速幂，时间复杂度为

O(p)

// go
const mod int = 1e9 + 7

func minNonZeroProduct(p int) int {
    return (1<<p - 1) % mod * qpow(1<<p-2, 1<<(p-1)-1, mod) % mod
}

func qpow(a int, b int, mod int) int {
    ans := 1
    for a %= mod; b > 0; b >>= 1 {
        if b&1 != 0 {
            ans = ans * a % mod
        }
        a = a * a % mod
    }
    return ans
}

你能穿过矩阵的最后一天

给定一个

row\times col

的二进制矩阵，每一天都会有一个位置水漫金山，有水的位置用

表示，其他地方用

你可以从第一行的任意位置出发，从最后一行的任意一个位置离开，请计算出能够安全离开矩阵的最后一天

题解

二分答案，然后用 bfs 判断可行性

判定

是否可行，只要设定一个全

矩阵，将前

天的水漫金山情况用

表示，然后将第一行所有不为

的位置放入队列进行 bfs 即可，设

M = col\cdot row

，时间复杂度

O(M \log M)

// cpp
#define pii pair<int, int>
const int DX[] = {1, 0, -1, 0};
const int DY[] = {0, -1, 0, 1};
bool bfs(int d, int m, int n, vector<vector<int>> &grid) {
    queue<pii> q;
    for (int i = 1; i <= n; ++i)
        if (!grid[1][i]) q.push(pii{1, i}), grid[1][i] = 1;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == m) return 1;
        for (int i = 0; i < 4; ++i) {
            int tx = DX[i] + x;
            int ty = DY[i] + y;
            if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && !grid[tx][ty])
                q.push(pii{tx, ty}), grid[tx][ty] = 1;
        }
    }
    return 0;
}
class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int m = cells.size(), n = cells[0].size();
        int l = 0, r = row * col, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            vector<vector<int>> grid(row + 7, vector<int>(col + 7, 0));
            for (int i = 0; i < mid; ++i) grid[cells[i][0]][cells[i][1]] = 1;
            if (bfs(mid, row, col, grid)) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

node.js

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

node.js

登录后参与评论

0 条评论

热度