T1

题目链接

题目描述：

给你一个仅由 0 和 1 组成的二进制字符串 s 。

如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。

返回 s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

题解思路：

暴力遍历字符串数组，直接找连续的0和连续的1（01连续中0字符串和1字符串最小长度*2），并记录最大值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
func findTheLongestBalancedSubstring(s string) int {
    res := 0
    for i := 0; i < len(s);{
        x, y := 0, 0
        for i < len(s) && s[i] == '0' {x++; i++}	
        for i < len(s) && s[i] == '1' {y++; i++}
        res = max(res, min(x, y) * 2)	// 这个01连续字符串中0字符串和1字符串最小长度*2
    }
    return res
}
func max(x, y int) int {if x > y {return x}; return y}
func min(x, y int) int {if x < y {return x}; return y}

T2

题目链接

题目描述：

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

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

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

题解思路：

map记录每个值有多少个，值元素个数最多的就是行数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findMatrix(nums []int) [][]int {
    var res [][]int
    mp := make(map[int]int)
    for _, x := range nums {
        mp[x]++	// 记录元素个数
    }
    for len(mp) != 0 {
        var tmp []int
        for k := range mp {
            tmp = append(tmp, k)
            mp[k]--  
            if mp[k] == 0 {
                delete(mp, k)	// 这个元素用完直接删除
            } 
        }
        res = append(res, tmp)
    }
    return res
}

T3

题目链接

题目描述：

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

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

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

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

题解思路：

贪心思想：按照奶酪数组差值从大到小排序。老鼠1选择从按照差值大到小选择k个，剩下全部给老鼠2这样总得分最大。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func miceAndCheese(a []int, b []int, k int) int {
    res := 0
    type s struct {
        z, x, y int
    }
    tmp := make([]s, len(a))
    for i := 0; i < len(a); i++ {
        tmp[i] = s{a[i]-b[i], a[i], b[i]}
    }
    // 按照差值排序
    sort.Slice(tmp, func(i, j int)bool{
        return tmp[i].z > tmp[j].z
    })
    for i := 0; i < len(tmp); i++ {
        if i < k {	// 老鼠1选择前k个
            res += tmp[i].x
        }else {
            res += tmp[i].y
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int miceAndCheese(vector<int>& a, vector<int>& b, int k) {
        vector<pair<int, pair<int, int>>> tmp(a.size());
        for (int i = 0; i < a.size(); i ++) {
            tmp[i] = {a[i]-b[i], {a[i], b[i]}};
        }
        // 按照差值排序
        sort(tmp.begin(), tmp.end(), [](const pair<int, pair<int, int>> x, const pair<int, pair<int, int>> y){
            return x.first > y.first;
        });
        int res = 0;
        for (int i = 0; i < tmp.size(); i++) {
            if (i < k) res += tmp[i].second.first;// 老鼠1选择前k个
            else res += tmp[i].second.second;
            
        }
        return res;
    }
};

T4

题目链接

题目描述：

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

  • 子数组 指的是一个数组里一段连续 非空 的元素序列。
  • 对于所有的 i ，ans[i] 相互之间独立计算。
  • 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。

题解思路：

思路1：最开始直接BFS找能跳并且未跳过的位置，将这个位置加入到队列中。这样因为多了查找已经查找过的元素，导致时间复杂度超时。

思路2：采用BFS，但是并不是直接遍历，而是将遍历过的直接删除，避免因查找重复导致超时。

关键要素

  • 找到一个特征，能跳的位置一定是+2或者-2，所以可以按照奇偶存放未剩下元素。因为每次可跳位置奇偶性相同。
  • 计算出每次可跳范围
    • l = max(-(k - 1), k - 1 - cur * 2)；
    • r = min(k - 1, -(k - 1) + (n - cur - 1) * 2);
  • 从对应奇偶性集合中查找对应范围中的元素，表示为可跳元素，移出集合。

代码：

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:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        vector<int> res(n, -2);
        res[p] = 0;
        for (int x : banned) res[x] = -1;
        // 还没被跳到的位置, 按奇偶放入set
        set<int> st[2];
        for (int i = 0; i < n; i++) if (res[i] == -2) st[i % 2].insert(i);

        queue<int> q;
        q.push(p);
        while  (!q.empty()) {
            int cur = q.front(); q.pop();
            
            // 计算可以跳的范围
            int l, r;
            l = max(-(k - 1), k - 1 - cur * 2);
            r = min(k - 1, -(k - 1) + (n - cur - 1) * 2);

            int x = (cur + (k - 1)) % 2;
            auto it = st[x].lower_bound(cur + l); // 找第一个大于等于的cur + l的位置
            while (it != st[x].end()) {
                if (*it > cur + r) break;   // 超过界限
                res[*it] = res[cur] + 1;    // 可以跳
                q.push(*it);                // 加入队列
                it = st[x].erase(it);       
            }
        }
        for(int i = 0; i < n; i++) if(res[i] == -2) res[i] = -1;
        return res;
    }
};