owenzhang的博客

Leetcode 第158场周赛解题报告

字数统计: 2k阅读时长: 8 min
2019/04/21
loading

这场比赛不需要太多特定的算法，只要能把问题分析清楚，认真思考，就能够解决掉。几个题目都非常适合当面试题。

下面是详细的题解和思考。

比赛的地址 Weekly Contest 158

https://leetcode-cn.com/contest/weekly-contest-158

1. 分割平衡字符串

题目：

分割平衡字符串(Split a String in Balanced Strings)

地址：

https://leetcode-cn.com/contest/weekly-contest-158/problems/split-a-string-in-balanced-strings/

题意：

在一个「平衡字符串」中，’L’ 和 ‘R’ 字符的数量是相同的。

给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

返回可以通过分割得到的平衡字符串的最大数量。

示例 1：

输入：s = “RLRRLLRLRL”
输出：4
解释：s 可以分割为 “RL”, “RRLL”, “RL”, “RL”, 每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’。

思路：

只要保证R和L的数目相同，就是一个平衡字符串。所以从头遍历，符合平衡就计数，最终遍历完就贪心出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int balancedStringSplit(string s) {
        int cnt = 0;
        int ans = 0;
        for(auto ch : s)
        {
            if(ch == 'L')
                cnt++;
            else
                cnt--;
            if(cnt == 0)
                ans++;
        }
        return ans;
    }
};

2. 可以攻击国王的皇后

题目：

可以攻击国王的皇后(Queens That Can Attack the King)

地址：

https://leetcode-cn.com/contest/weekly-contest-158/problems/queens-that-can-attack-the-king/

题意：

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

「黑皇后」在棋盘上的位置分布用整数坐标数组 queens 表示，「白国王」的坐标用数组 king 表示。

「黑皇后」的行棋规定是：横、直、斜都可以走，步数不受限制，但是，不能越子行棋。

请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标（任意顺序）。

可以攻击国王的皇后的例子

思路：

上图红色的就是符合答案的「黑皇后」。

题目可以利用逆向思维，「白国王」所在的位置，遍历横竖斜八个方向，第一次碰到的「黑皇后」就是答案。

代码：

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<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> v(8, vector<int>(8, 0));
        for(auto q : queens)
        {
            int x = q[0];
            int y = q[1];
            v[x][y] = 1;
        }
        int x = king[0];
        int y = king[1];
        vector<vector<int>> ans;
        int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
        for(int i = 0; i < 8; ++i)
        {
            int r = x;
            int c = y;
            while(true)
            {
                r+=dir[i][0];
                c+=dir[i][1];
                if(r<8&&r>=0&&c>=0&&c<8)
                {
                    if(v[r][c]==1)
                    {
                        ans.push_back({r, c});
                        break;
                    }
                }
                else
                    break;
            }
        }
        return ans;
    }
};

3. 掷骰子模拟

题目：

掷骰子模拟(Dice Roll Simulation)

地址：

https://leetcode-cn.com/contest/weekly-contest-158/problems/dice-roll-simulation/

题意：

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。

输入：n = 2, rollMax = [1,1,2,2,2,3]

输出：34

解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。

但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。

因此，最终答案是 36-2 = 34。

思路：

可以换种方式理解，要形成一个n长度的数字字符串，包括1-6这几个数字。每种数字要求连续不能超过rollMax的数量。

可以利用递归构造出符合要求的数字，构造出一次就加一。从第一位开始构造，一直构造到第n位后结束。

构造当前位时，需要知道前一位数字是什么，以及这个数字累积连续了几次。

所以递归函数需要三个参数，当前要构造的位序号，上一位数字，上一位数字连续出现的次数。

最后用记忆化搜索优化。

ps：一种通用的解法叫数位dp，本题比较简单，还可以构造更复杂的题目。

代码：

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
class Solution {
public:
    const int MOD = 1e9 + 7;
    int memo[5001][7][16];
    int dfs(int index, int pre, int state, int n, vector<int>& rollMax)
    {
        if(index == n+1)
        {
            return 1;
        }
        if(memo[index][pre][state]!=-1)
            return memo[index][pre][state];
        int ans = 0;
        for(int i = 0; i < 6; ++i)
        {
            if(i==pre-1)
            {
                if(rollMax[i]==state)
                    continue;
                else
                {
                    ans += dfs(index+1, i+1, state+1, n, rollMax), ans %= MOD;
                }
            }
            else
                ans += dfs(index+1, i+1, 1, n, rollMax) % MOD, ans %= MOD;
        }
        return memo[index][pre][state]=ans;
    }
    int dieSimulator(int n, vector<int>& rollMax) {
        memset(memo, -1, sizeof(memo));
        return dfs(1, 0, 0, n, rollMax);
    }
};

4. 最大相等频率

题目：

最大相等频率(Maximum Equal Frequency)

地址：

https://leetcode-cn.com/contest/weekly-contest-158/problems/maximum-equal-frequency/

题意：

给出一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回其长度：

从前缀中 删除一个 元素后，使得所剩下的每个数字的出现次数相同。

如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

输入：nums = [2,2,1,1,5,3,3,5]

输出：7

解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4]=5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。

思路：

不使用高级的数据结构，只要做好统计，分析出能够产生的条件，就可以解决。

用两个数组统计每个数字的出现次数number_size，和每种出现次数相同的有多少种数字size_count。

例如：[2,2,1,1,5,3,3,5]

如果全部统计，那么

1
2
3
4
5
6
7
8
number_size[1]=2, 
number_size[2]=2,
number_size[3]=2,
number_size[5]=2,
每种数字都出现了2次

size_count[2]=4
出现2次的数字，有4种

利用上面两个数组的统计，满足以下四种情况，就是符合条件的答案：

  1. 前缀中只包含一种数字（number_size.size()==1）;
  2. 前缀中包含多种数字，每种数字都只包含一个（只有size_count[1]有元素，其他下标都没有），删掉任何一个数字，剩下数字出现次数都为1;
  3. 前缀中，数字出现的次数只有两种，除了一个元素出现次数是1次，其他元素的出现次数都相同。删掉出现1次的那个元素；
  4. 前缀中，出现次数只有两种a和b，满足a=b+1，并且a次数只有一种数字，剩下的数字都出现b次。删掉出现a次数字一个，所有数字出现b次。

代码：

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 maxEqualFreq(vector<int>& nums) {
        map<int, int> number_size; //每个数字有多少次出现
        map<int, int> size_count;  //出现次数的计数
        int i = 0;
        int ans = 0;
        for(auto & num : nums)
        {
            ++i;
            if(number_size.find(num)==number_size.end())
            {
                number_size[num] = 1;
                size_count[1]++;
            }
            else
            {
                int old_size = number_size[num];
                number_size[num]++;
                size_count[old_size]--;
                size_count[old_size+1]++;
                if(size_count[old_size]==0)
                    size_count.erase(old_size);
            }
            if(number_size.size()==1)
                    ans = i;
            else if(size_count.size()==1)
            {
                auto iter = size_count.begin();
                if(iter->first == 1)
                {
                    ans = i;
                }
            }
            else if(size_count.size()==2)
            {
                auto iter = size_count.begin();
                auto riter = size_count.rbegin();
                if((riter->first-iter->first)==1 && (1 == riter->second))
                    ans = i;
                if(iter->first==1&&iter->second==1)
                    ans = i;
            }
        }
        return ans;
    }
};

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-Leetcode-%E7%AC%AC158%E5%9C%BA%E5%91%A8%E8%B5%9B%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

发表日期：April 21st 2019, 10:00:03 am

更新日期：April 21st 2019, 10:00:03 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1. 分割平衡字符串
  2. 2. 2. 可以攻击国王的皇后
  3. 3. 3. 掷骰子模拟
  4. 4. 4. 最大相等频率
Total : 150
2024
2020
2019
2018
2017
2016
2014
2013
2012
2011
技术 读书 思考 技巧 学习 跑步