力扣第331场周赛题解

大大源码 • 2023年4月19日 pm11:32 • 其他

rank	T1	T2	T3	T4
331 / 4256	0:01:46	0:06:18 (1)	0:11:58	0:57:29 (4)

T1 从数量最多的堆取走礼物

模拟题，每次操作找出最大值

maxx

$ma xx$ 并将其变成

(

)

sqrt(maxx)

$s q r t (ma xx)$ ，

$k$ 次操作后求和。

数据范围很小，可以暴力模拟，更好的方法是使用优先队列模拟。

时间复杂度

(

)

(

)

O(max(n,k)log(n))

$O (ma x (n, k) l o g (n))$
空间复杂度

(

)

O(n)

$O (n)$

参考代码

class Solution {
   public:
    long long pickGifts(vector<int>& a, int k) {
        priority_queue<int> q;
        for (auto it : a) {
            q.push(it);
        }
        while (k--) {
            int s = q.top();
            q.pop();
            s = sqrt(s);
            q.push(s);
        }
        long long ans = 0;
        while (q.size()) {
            ans += q.top();
            q.pop();
        }
        return ans;
    }
};

T2 统计范围内的元音字符串数

给定一个字符串数组，每次询问区间

[

]

[l,r]

$[l, r]$ 内，首尾字母都是元音字母的字符串数量。

预处理前缀和，差分询问。

时间复杂度

(

)

O(n+q)

$O (n + q)$
空间复杂度

(

)

O(n)

$O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
class Solution {
   public:
    map<int, int> mp;
    bool check(string s) {
        return mp[s[0]] && mp[s.back()];
    }
    int sum[N];
    vector<int> vowelStrings(vector<string>& a, vector<vector<int>>& q) {
        mp['a'] = 1;
        mp['e'] = 1;
        mp['i'] = 1;
        mp['o'] = 1;
        mp['u'] = 1;
        int n = a.size();
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + check(a[i]);
        }
        vector<int> ans;
        for (auto it : q) {
            ans.emplace_back(sum[it[1] + 1] - sum[it[0]]);
        }
        return ans;
    }
};

T3 打家劫舍 IV

要求最大值最小，经典二分答案+

check

$c h ec k$

check

$c h ec k$ 思路：二分出

mid

$mi d$ ，贪心地线性检查能否取出

$k$ 个价值

<=mid

$<= mi d$ 的房屋即可。

时间复杂度

(

)

O(nlog(m))

$O (n l o g (m))$
空间复杂度

(

)

O(n)

$O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

class Solution {
   public:
    int minCapability(vector<int>& a, int k) {
        int n = a.size();
        int l = 1, r = 1e9, ans;
        while (l <= r) {
            int mid = (l + r) / 2;
            int pre = -2;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if (i - pre == 1) {
                    //不能相邻
                    continue;
                }
                if (a[i] <= mid) {
                    //选择
                    sum++;
                    pre = i;
                }
            }
            if (sum >= k) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};

T4 重排水果

如下考虑：

判断原数组是否合法：两个数组排序后相同，则直接返回0。
判断是否存在解：将两个数组的元素混合在一起，如果某个元素为奇数个，那么一定无解。
剩下来的是必定有解，但需要交换的情况。
首先去除他们的交集元素，现在数组

a

a

$a$ 和数组

b

b

$b$ 分别多了某些元素。根据每个元素的总数量，容易计算得到他们分别多出来

x

i

x_i

$x_{i}$ 个

y

i

y_i

$y_{i}$ ，维护

o

u

t

a

outa

$o u t a$ 和

o

u

t

b

outb

$o u t b$ ，

o

u

t

a

[

x

]

=

y

outa[x]=y

$o u t a [x] = y$ 表示数组

a

a

$a$ 的

x

x

$x$ 元素多了

y

y

$y$ 个。
考虑如何交换最优：
① 用数组

a

a

$a$ 中的最小值和数组

b

b

$b$ 中的最大值交换，花费为

m

i

n

(

a

m

i

n

n

,

b

m

a

x

x

)

min(a_{minn},b_{maxx})

$min (a_{minn}, b_{ma xx})$
② 用数组

a

a

$a$ 中的最大值和数组

b

b

$b$ 中的最小值交换，花费为

m

i

n

(

b

m

i

n

n

,

a

m

a

x

x

)

min(b_{minn},a_{maxx})

$min (b_{minn}, a_{ma xx})$
③ 容易遗漏的一种情况，利用所有元素的最小值作为中间者，间接的交换

a

b

ab

$ab$ 中的元素：swap(a,c); swap(b,c);，因为

c

c

$c$ 必定为最小值，且被用到了两次，因此花费为

m

i

n

n

∗

2

minn*2

$minn * 2$
贪心地，如果数组

a

a

$a$ 中的最小值

<

<

$<$ 数组

b

b

$b$ 中的最小值，则选用方案①③的组合，否则选用方案②③的组合。

时间复杂度

(

)

O(nlog(n))

$O (n l o g (n))$
空间复杂度

(

)

O(n)

$O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
class Solution {
   public:
    long long minCost(vector<int>& a, vector<int>& b) {
        int MINN = INF;
        map<int, int> mp, ma, mb;
        for (auto it : a) {
            mp[it]++, ma[it]++;
            MINN = min(MINN, it);
        }
        for (auto it : b) {
            mp[it]++, mb[it]++;
            MINN = min(MINN, it);
        }
        if (ma == mb) {
            // 已经合法
            return 0;
        }
        for (auto& it : mp) {
            if (it.second % 2) {
                // 某个元素总数量奇数个，不能平分
                return -1;
            }
            // 期望每个数组各有it.second个it.first
            it.second /= 2;
        }
        vector<pair<int, int>> outa, outb;
        int all = 0;
        for (auto it : mp) {
            int delta = ma[it.first] - it.second;
            // a中需要给出delta个it.first
            if (delta > 0) {
                // 总共需要给出all个
                all += delta;
                outa.emplace_back(make_pair(it.first, delta));
            }
            delta = mb[it.first] - it.second;
            // b中需要给出delta个it.first
            if (delta > 0) {
                outb.emplace_back(make_pair(it.first, delta));
            }
        }

        long long ans = 0;
        int n = outa.size();
        int ra = outa.size() - 1;
        int rb = outb.size() - 1;
        int la = 0;
        int lb = 0;

        while (all--) {
            if (!outa[la].second) {
                ++la;
            }
            if (!outa[ra].second) {
                --ra;
            }
            if (!outb[lb].second) {
                ++lb;
            }
            if (!outb[rb].second) {
                --rb;
            }
            if (outa[la].first < outb[lb].first) {
                outa[la].second--;
                outb[rb].second--;
                // 两种情况，借助最小值来间接交换 / 直接交换
                ans += min(min(MINN * 2, outa[la].first), outb[rb].first);
            }
            if (outa[la].first > outb[lb].first) {
                outa[ra].second--;
                outb[lb].second--;
                ans += min(min(MINN * 2, outa[ra].first), outb[lb].first);
            }
        }
        return ans;
    }
};