image-20210808112249489

5838. 检查字符串是否为数组前缀

md 开始读错题了。。

其实就是把words的前缀拼一起 看有没有等于s的就好

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string ss;
        for(auto w: words) {
            ss += w;
            if(ss == s) return true;
        }

        return false;
    }
};

5839. 移除石子使总数最小

这题很简单， 维护一个队头最大的优先队列。

每次取最大的元素xx，也就是队头，减去⌊x2⌋\lfloor \frac{x}{2} \rfloor就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> q;

        int sum = 0;
        for(auto p: piles) {
           q.push(p);
            sum += p;
        }

        for(int i=0; i<k && !q.empty(); i++) {
            int mx = q.top(); q.pop();
            sum -= mx/2;
            mx -= mx/2;

            q.push(mx);
        }

        return sum;
    }
};

5840. 使字符串平衡的最小交换次数

维护下 括号是否匹配， 如果不匹配就把最后一个 '[' 换过来就好。

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
class Solution {
public:
    int minSwaps(string s) {
        int ls = s.length();
        int ln = ls - 1;

        int sum = 0, ans = 0;
        for(int i=0; i<ln; i++) {
            if (s[i] == ']') {
                sum -= 1;
            } else {
                sum += 1;
            }

            if(sum < 0) {
                while(i<ln && s[ln] == ']') ln--;
                swap(s[i], s[ln]);
                sum += 2;

                ans ++;
            }
        }

        return ans;
    }
};

5841. 找出到每个位置为止最长的有效障碍赛跑路线

md, lis 写不明白了。。。

这题就是求每个元素在最长不下降子序列中的序号。

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
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
    // fmt.Println("---------------------------")
    ans := make([]int, 0)

    // lis
    lis := make([]int, 0)
    for _, v := range obstacles {
        p := 0

        if len(lis) == 0 || lis[len(lis)-1] <= v {
            lis = append(lis, v)

            p = len(lis)
        } else {
            pos := func() int {
                l, r, mid, ans := 0, len(lis)-1, -1, 0
                for l<=r {
                    mid = (l+r) >> 1
                    if lis[mid] > v {
                        r, ans = mid-1, mid
                    } else {
                        l = mid+1
                    }
                }
                return ans
            }()

            lis[pos] = v

            p = pos + 1
        }

        // fmt.Println(lis)

        ans = append(ans, p)
    }


    return ans
}