为了保证制作简历的安全性和流畅性,建议您使用Chrome浏览器进行访问
Smell Billy 2021届
APP 内打开
6
6
2

LeetCode 第 218 场周赛 题解

题目1:5617. 设计 Goal 解析器

思路:模拟

代码:


class Solution {

public:

string interpret(string s) {

int n = s.size();

int i = 0;

string ret = "";

while(i < n) {

if(s[i] == '(' && s[i + 1] == ')') {

i += 2;

ret += "o";

} else if(s[i] == '(') {

i += 4;

ret += "al";

} else {

i++;

ret += "G";

}

}

return ret;

}

};

复杂度分析:

时间复杂度为 O(n),空间复杂度为 O(1)。




题目2:5618. K 和数对的最大数目

思路:哈希表

遍历数组,每遍历到一个元素 x,先进入哈希表检查之前是否出现过 k - x 这个元素,若出现过则默认将这两个元素一起移出数组,结果值 ret 加一;若未出现过则将当前元素存入哈希表。


代码:


class Solution {

public:

int maxOperations(vector& nums, int k) {

unordered_map mp;

int ret = 0;

for(int x : nums) {

if(mp[k - x]) {

mp[k - x]--;

ret++;

} else {

mp[x]++;

}

}

return ret;

}

};

复杂度分析:

时间复杂度为 O(n),空间复杂度为 O(n)。




题目3:5620. 连接连续二进制数字

思路:模拟

我们观察 n = 3 的情况,拼接得到的二进制串为 1\ 10\ 11,转为十进制,相当于 1 * 2^4 + 2 * 2^2 + 3,其中 2^4表示 2、3 对应的二进制串长度为 4,2^2表示 3 对应的二进制串长度为 2 ,所以我们遍历 1-n,求出当前元素二进制串长度 p,其对应的权值 2^p,就可以作为上一个元素得到结果的偏移量。


由于相邻的数字 k, k + 1 对应的二进制串长度基本相同或相差 1,所以不用每次从头开始计算,维护一个变量随着数组遍历过程不断变化即可。


代码:


class Solution {

public:

const int M = 1e9 + 7;

int concatenatedBinary(int n) {

int ret = 0;

int p = 1;

for (int i = 1; i <= n; ++i) {

while (p <= i) { // 相当于求log(i)

p *= 2;

}

ret = ((long long)ret * p + i) % M;

}

return ret;

}

};


复杂度分析:

时间复杂度为 O(nlgn),空间复杂度为 O(1)。




题目4:5619. 最小不兼容性(来自橙名大佬的题解)


代码:


const int INF = 0x3f3f3f3f;

int memo[65536], v[16];


class Solution {

int n, k, sz;

vector nums;

int solve(int state) {

if (memo[state] != -1)

return memo[state];

// 边界条件:当前集合刚好包含n/k个元素,不需要继续划分

if (__builtin_popcount(state) == sz) {

int idx = 0;

for (int i = 0; i < n; ++i) {

if (state & (1 << i)) {

// 将包含的元素存入分组

v[idx++] = i;

}

}

for (int i = 0; i + 1 < sz; ++i) {

// 一个分组有两数相同,则说明是不满足要求的分组

if (nums[v[i]] == nums[v[i + 1]]) {

return memo[state] = INF;

}

}

return memo[state] = nums[v[n / k - 1]] - nums[v[0]];

}

int ans = INF;

// 优化二:子集枚举优化

for (int sub = state - 1; sub; sub = (sub - 1) & state) {

if (__builtin_popcount(sub) % sz != 0)

continue;

// left 和 right 分别表示将当前集合再分为两个子集

int left = solve(sub);

// 优化三:如果左边的最优值已经达到了当前总和的最优值,则不需要继续计算右边。

if (left >= ans)

continue;

int right = solve(state ^ sub);

ans = min(ans, left + right);

}

return memo[state] = ans;

}


public:

int minimumIncompatibility(vector& nums, int k) {

n = nums.size();

sz = n / k;

// 优化一:每个子集的大小为1,不兼容性显然为0,总和也是0。

// 这种情况的筛除非常重要,因为它需要最多的枚举次数。

if (sz == 1)

return 0;

sort(nums.begin(), nums.end());

vector cnt(n + 1);

for (int num : nums) {

// 记录每个数字出现的次数,若大于组数则说明不能分组

cnt[num]++;

if (cnt[num] > k)

return -1;

}

this->k = k; // 更新全局变量

this->nums = nums;

for (int i = 0; i < (1 << n); ++i)

memo[i] = -1;

return solve((1 << n) - 1);

}

};


复杂度分析:

时间复杂度为 O(3^n),空间复杂度为 O(2^n)


如果喜欢,欢迎给作者三连!


发布时间:2020年12月06日
用户头像
我来说两句…
共 6 条评论
🤠 2019届
厉害厉害
2020年12月07日 回复
贾文宇 中国建设银行江西吉安分行·大堂经理助理
2020年12月07日 回复
logic 北京大学
2020年12月08日 回复
用户e0149
厉害了,大佬
2020年12月07日 回复
龙天天 苏州大学·2022届
大佬
2020年12月07日 回复
兔先 湖南大学·2022届
🐂er
2020年12月06日 回复