成都网站制作scgc,小程序数据库怎么建立,做网站是不是太麻烦了,邢台太行中学收费题目
给你两个字符串 s 和 p #xff0c;其中 p 是 s 的一个 子序列 。同时#xff0c;给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 removable #xff0c;该数组是 s 中下标的一个子集#xff08;s 的下标也 从 0 开始 计数#xff09;。
请你找出一个整数…
题目
给你两个字符串 s 和 p 其中 p 是 s 的一个 子序列 。同时给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 removable 该数组是 s 中下标的一个子集s 的下标也 从 0 开始 计数。
请你找出一个整数 k0 k removable.length选出 removable 中的 前 k 个下标然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足在执行完上述步骤后 p 仍然是 s 的一个 子序列 。更正式的解释是对于每个 0 i k 先标记出位于 s[removable[i]] 的字符接着移除所有标记过的字符然后检查 p 是否仍然是 s 的一个子序列。
返回你可以找出的 最大 k 满足在移除字符后 p 仍然是 s 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串生成过程中可能会移除原字符串中的一些字符也可能不移除但不改变剩余字符之间的相对顺序。
示例 1
输入s “abcacb”, p “ab”, removable [3,1,0] 输出2 解释在移除下标 3 和 1 对应的字符后“abcacb” 变成 “accb” 。 “ab” 是 “accb” 的一个子序列。 如果移除下标 3、1 和 0 对应的字符后“abcacb” 变成 “ccb” 那么 “ab” 就不再是 s 的一个子序列。 因此最大的 k 是 2 。
示例 2
输入s “abcbddddd”, p “abcd”, removable [3,2,1,4,5,6] 输出1 解释在移除下标 3 对应的字符后“abcbddddd” 变成 “abcddddd” 。 “abcd” 是 “abcddddd” 的一个子序列。
示例 3
输入s “abcab”, p “abc”, removable [0,1,2,3,4] 输出0 解释如果移除数组 removable 的第一个下标“abc” 就不再是 s 的一个子序列。
解题思路 先写一个函数判断移除了前k个下标以后的s是否还满足p 是 s 的一个 子序列。 因为移除下标的个数具有单调性移除的下标越多那么仍然满足子序列就越困难因此使用二分法找出最多移除多少个下标使得p 仍然是 s 的一个 子序列。
代码
class Solution {public boolean re(String stringBuilder, String p,SetInteger set) {int j0;for (int i0;istringBuilder.length();i){if (jp.length())return true;if(set.contains(i)) continue;if(stringBuilder.charAt(i)p.charAt(j))j;}return jp.length();}public int maximumRemovals(String s, String p, int[] removable) {HashSetInteger set new HashSet();StringBuilder builder new StringBuilder(s);int l0,rremovable.length-1;while (lr){int mid(r-l)/2l;for (int i 0; i mid; i) {set.add(removable[i]);}if(re(s,p,set)){lmid1;}else{rmid-1;}set.clear();}return l;}
}
