单周赛 253 题解

知识点:字符串比较,大根堆,贪心,最长上升子序列,二分优化

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

给定一个字符串 \(s\),给定一个字典 \(w\),如果 \(w\) 中前 \(k\) 个字符串可以构成 \(s\),返回 \(true\),否则返回 \(false\),其中 \(1\leq k\leq w.size\)

题解

模拟

// cpp
class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string temp;
        for (int i = 0; i < words.size(); ++i) {
            temp += words[i];
            if (s == temp) return 1;
        }
        return 0;
    }
};
// go
func isPrefixString(s string, w []string) bool {
    var temp string 
    for _, i := range w {
        temp += i
        if s == temp {
            return true
        }
    }
    return false
}

移除石子使总数最小

给定长 \(n\) 的数组 \(a\),给定 \(k\),执行 \(k\) 次操作,每次把 \(a_{i}\) 减去 \(\lfloor\frac{a_{i}}{2}\rfloor\),返回操作后 \(a\) 的数组和的可能的最小值

题解

贪心,每次对最大的 \(a_{i}\) 操作即可,使用优先队列维护,时间复杂度 \(O(n\log n)\)

// cpp
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> pq;
        for (auto &i: piles) pq.push(i);
        while (k--) {
            int top = pq.top(); pq.pop();
            pq.push(top - top / 2);
        }
        int ans = 0;
        while (!pq.empty()) {
            ans += pq.top(); pq.pop();
        }
        return ans;
    }
};

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

给定 [] 组成的字符串,你可以交换任意两个括号,使得整体括号匹配,返回最小的交换数

保证左右括号数相等

题解

找规律,对于题设中的字符串,一定可以抽象成 ]]]]][[[[[ 的形式,设共有 \(n\) 对,那么答案即为 \(\lceil\frac{n}{2}\rceil\)

// cpp
class Solution {
public:
    int minSwaps(string s) {
        int l = 0, r = 0;
        for (auto &i: s) {
            if (i == '[') l++;
            else {
                if (l) l--;
                else r++;
            }
        }
        return (r + 1) / 2;
    }
};
// go
func minSwaps(s string) int {
    l := 0
    r := 0
    for _, i := range(s) {
        if i == '[' {
            l++
        } else {
            if l > 0 {
                l--
            } else {
                r++
            }
        }
    }
    return (r + 1) / 2
}

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

给定长为 \(n\) 的数组 \(a\),找到以每个位置 \(i\) 结尾的最长不降子序列的长度,以数组形式返回

数据规定

\(1\leq n\leq 10^5\)

题解

使用 \(LIS\) 的二分解法

具体来讲,设 \(dp[i]\) 表示长为 \(i + 1\) 的最长不降子序列的最后一个位置的最小值,初始化为 \(inf\)

对于每一个位置 \(i\),可以在 \(dp\) 数组中二分查找最后一个小于 \(a[i]\) 的位置,并把 \(a[i]\) 赋值在该位置后面,获取最长不降子序列的长度只需要用该位置减去数组头,维护答案即可

举个例子,对 a[4] = [1, 2, 3, 2] 进行操作

dp 数组初始化:
[inf, inf, inf, inf]

处理 a[0] = 1,得到:
[1, inf, inf, inf]

处理 a[1] = 2,得到:
[1, 2, inf, inf]

处理 a[2] = 3,得到:
[1, 2, 3, inf]

处理 a[3] = 2,得到:
[1, 2, 2, inf]
// cpp
class Solution {
public:
    #define inf 0x3f3f3f3f
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& o) {
        int n = o.size();
        vector<int> dp(n + 7), ans(n + 7);
        fill(dp.begin(), dp.end(), inf);
        for (int i = 0; i < n; ++i) {
            int len = upper_bound(dp.begin(), dp.end(), o[i]) - dp.begin() + 1;
            *upper_bound(dp.begin(), dp.end(), o[i]) = o[i];
            ans[i] = len;
        }
        return {ans.begin(), ans.begin() + n};
    }
};
上一篇:springboot开启热部署(修改java代码自动重新部署项目)


下一篇:添加WCF服务引用出错:content type 'application/soap+xml; charset=utf-8' was not the expected type 'text/xml; charset=utf-8'.