力扣第253场周赛

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

描述

给你一个字符串 s 和一个字符串数组 words ，请你判断 s 是否为 words 的 前缀字符串 。

字符串 s 要成为 words 的 前缀字符串 ，需要满足：s 可以由 words 中的前 k（k 为 正数 ）个字符串按顺序相连得到，且 k 不超过 words.length 。

如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。

示例 1：

输入：s = "iloveleetcode", words = ["i","love","leetcode","apples"] 输出：true 解释： s 可以由 "i"、"love" 和 "leetcode" 相连得到。 示例 2：

输入：s = "iloveleetcode", words = ["apples","i","love","leetcode"] 输出：false 解释： 数组的前缀相连无法得到 s 。

思路

直接遍历。

代码

/**
 * @author mikusugar
 */
public class N1 {
    public boolean isPrefixString(String s, String[] words) {
        final StringBuilder sb = new StringBuilder();
        for (String str : words) {
            sb.append(str);
            if (sb.toString().equals(s)) return true;
        }
        return false;
    }
}

题二 移除石子使总数最小

描述

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。 注意：你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

示例 1：

输入：piles = [5,4,9], k = 2 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。 剩下石子的总数为 12 。 示例 2：

输入：piles = [4,3,6,7], k = 3 输出：12 解释：可能的执行情景如下： - 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。 - 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。 - 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。 剩下石子的总数为 12 。

提示：

1 <= piles.length <= 10^5 1 <= piles[i] <= 10^4 1 <= k <= 10^5

思路

贪心，每次选当前最大的堆。

用优先队列。

代码

import java.util.PriorityQueue;

/**
 * @author mikusugar
 */
public class N2 {
    public int minStoneSum(int[] piles, int k) {
        final PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
        for (int num : piles) pq.add(num);
        while (k-- > 0) {
            final int cur = pq.poll();
            pq.add(cur - (int) Math.floor(cur / 2.0));
        }
        int res = 0;
        while (!pq.isEmpty()) res += pq.poll();
        return res;
    }
}

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

描述

给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

字符串是一个空字符串，或者 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。 你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

示例 1：

输入：s = "][][" 输出：1 解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。 最终字符串变成 "[[]]" 。 示例 2：

输入：s = "]]][[[" 输出：2 解释：执行下述操作可以使字符串变成平衡字符串：

• 交换下标 0 和下标 4 对应的括号，s = "[]][[]" 。
• 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。 最终字符串变成 "[[][]]" 。 示例 3：

输入：s = "[]" 输出：0 解释：这个字符串已经是平衡字符串。

思路

找规律。

交换一次最多可以令两对配对。

令无法配对的对数为f，可得 res=f/2+f%2;

代码

/**
 * @author mikusugar
 */
public class N3 {
    public int minSwaps(String s) {
        int f = 0;
        int a = 0;
        int b = 0;
        final char[] strs = s.toCharArray();
        for (char c : strs) {
            if (c == ']') {
                a++;
                if (a > b) {
                    f++;
                    a--;
                }
            } else b++;
        }
        return f / 2 + f % 2;
    }
}

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

描述

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。 在这条路线中，必须包含第 i 个障碍。 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。 返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

示例 1：

输入：obstacles = [1,2,3,2] 输出：[1,2,3,3] 解释：每个位置的最长有效障碍路线是： - i = 0: [1], [1] 长度为 1 - i = 1: [1,2], [1,2] 长度为 2 - i = 2: [1,2,3], [1,2,3] 长度为 3 - i = 3: [1,2,3,2], [1,2,2] 长度为 3 示例 2：

输入：obstacles = [2,2,1] 输出：[1,2,1] 解释：每个位置的最长有效障碍路线是： - i = 0: [2], [2] 长度为 1 - i = 1: [2,2], [2,2] 长度为 2 - i = 2: [2,2,1], [1] 长度为 1 示例 3：

输入：obstacles = [3,1,5,6,4,2] 输出：[1,1,2,3,2,2] 解释：每个位置的最长有效障碍路线是： - i = 0: [3], [3] 长度为 1 - i = 1: [3,1], [1] 长度为 1 - i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线 - i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线 - i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线 - i = 5: [3,1,5,6,4,2], [1,2] 长度为 2

思路

仔细看题目得出，这题就是求最长递增子序列。。。

直接动态规划：O(n^2)没有通过，二分加贪心通过O(nlogn)。

代码

/**
 * @author mikusugar
 */
public class N4 {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int maxL = 0;
        int[] dp = new int[obstacles.length];
        int[] ans = new int[obstacles.length];
        for (int i = 0; i < obstacles.length; i++) {
            int num = obstacles[i];
            int left = 0, right = maxL;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] <= num)
                    left = mid + 1;
                else
                    right = mid;
            }
            dp[left] = num;
            if (left == maxL) {
                maxL++;
            }
            ans[i] = left + 1;
        }
        return ans;
    }
}