Blog of Xingyu Wang
0%

LeetCode周赛0403

Posted on In

1. 最长平衡子字符串

题意

给你一个仅由 0 和 1 组成的二进制字符串 s。如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。返回 s 中最长的平衡子字符串长度。子字符串是字符串中的一个连续字符序列。 ### 思路 通过遍历字符串的方式，来获取连续0和连续1的数量。

解答

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
int findTheLongestBalancedSubstring(string s)
{
    int maxlen = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '1')
            continue;
        int j;
        for (j = i; j < s.size(); j++)
        {
            if (s[j] == '1')
                break;
        }

        int ilen = j - i;
        int k;
        for (k = j; k < s.size(); k++)
        {
            if (s[k] == '0')
                break;
        }
        int jlen = k - j;
        int len;
        cout << ilen << ' ' << jlen << endl;
        if (ilen > jlen)
            len = jlen * 2;
        else
            len = ilen * 2;
        if (len > maxlen)
            maxlen = len;
    }
    return maxlen;
}

2. 转换二维数组

题意

给你一个整数数组 \(nums\) 。请你创建一个满足以下条件的二维数组：

二维数组应该 只包含数组 nums 中的元素。
二维数组中的每一行都包含不同的整数。
二维数组的行数应尽可能少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。请注意，二维数组的每一行上可以存在不同数量的元素。

思路

将\(nums\)数组按照元素值为\(key\)，每一个元素出现的总次数为\(value\)值，建立hash表。将元素按照\(value\)的大小排列，依次建立子数组。

解答

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
static bool cmp(const pair<int, int> a, pair<int, int> b)
{
    return a.second > b.second;
}

vector<vector<int>> findMatrix(vector<int> &nums)
{
    map<int, int> hashtable;
    vector<vector<int>> ans;
    for (int i = 0; i < nums.size(); i++)
    {
        if (hashtable.find(nums[i]) == hashtable.end())
        {
            hashtable[nums[i]] = 1;
        }
        else
            hashtable[nums[i]]++;
    }

    vector<pair<int, int>> v(hashtable.begin(), hashtable.end());
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i].first << " " << v[i].second << endl;
    }

    int loopnum = v[0].second;
    for (int i = 0; i < loopnum; i++)
    {
        vector<int> tmp;
        for (int j = 0; j < v.size(); j++)
        {
            if (v[j].second >= 1)
            {
                tmp.push_back(v[j].first);
                v[j].second--;
            }
        }
        ans.push_back(tmp);
    }
    return ans;
}

备注：对map按照value值进行排序的方法。

3. 老鼠和奶酪

题意

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。

给你一个正整数数组 \(reward1\) ，一个正整数数组$ reward2$ ，和一个非负整数 \(k\) 。请你返回第一只老鼠恰好吃掉 \(k\) 块奶酪的情况下，最大得分为多少。

思路

这是典型的贪心算法。首先假设所有的奶酪都是第二只老鼠吃掉的，则得分为\(sum(reward2)\)。在此基础上，若第\(i\)块奶酪实际为第一只老鼠所食，则得分变化为\(reward1[i] - reward2[i]\)。求出所有的\(reward1[i] - reward2[i]\)，选出其中最大的\(k\)个值与\(sum\)相加即为答案。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int miceAndCheese(vector<int> &reward1, vector<int> &reward2, int k)
{
    int n = reward1.size();
    // 一开始假设都是第二只老鼠吃掉的
    long long ans = 0;
    for (int x : reward2)
        ans += x;
    // 计算每个奶酪的得分变化量
    vector<int> vec;
    for (int i = 0; i < n; i++)
        vec.push_back(reward1[i] - reward2[i]);
    sort(vec.begin(), vec.end());
    // 选出前 K 大的得分变化量
    for (int i = 1; i <= k; i++)
        ans += vec[n - i];
    return ans;
}