leetcode253场周赛---记第一次AK
5838. 检查字符串是否为数组前缀
今天的题目都太水了。。。
T4就模板题目，改都不用改。。。
ak之后排名还没之前做三题高。。。
题目描述
给你一个字符串
s和一个字符串数组words，请你判断s是否为words的前缀字符串。字符串
s要成为 words 的前缀字符串，需要满足：s可以由words中的前k（k为正数）个字符串按顺序相连得到，且k不超过words.length。如果
s是words的前缀字符串，返回true；否则，返回false。
解题思路
遍历就行，注意下几种特殊情况。
class Solution {
public boolean isPrefixString(String s, String[] words) {
int sidx=0;
int widx=0;
int k=0;
while(sidx<s.length()&&k<words.length) {
if(s.charAt(sidx)!=words[k].charAt(widx))
return false;
sidx++;
widx++;
if(widx==words[k].length()) {
k++;
widx=0;
}
}
if(sidx<s.length())
return false;
return (k>0&&widx==0)?true:false;
}
}
5839. 移除石子使总数最小
题目描述
给你一个整数数组piles，数组下标从 0 开始，其中 piles[i]表示第i堆石子中的石子数量。另给你一个整数k，请你执行下述操作恰好k次：
选出任一石子堆piles[i]，并从中移除floor(piles[i] / 2)颗石子。
注意：你可以对同一堆石子多次执行此操作。
返回执行k次操作后，剩下石子的最小总数。
floor(x)为小于或等于x 的最大整数。（即，对x向下取整）。
解题思路
优先队列，从小到大排序。每次移除最大的石子。
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
for(int n:piles) {
q.add(n);
}
while(k>0) {
int temp = q.poll();
temp -= (int) Math.floor(1.0*temp/2);
q.add(temp);
k--;
}
int sum = 0;
for(int n:q) {
sum+=n;
}
return sum;
}
}
5840. 使字符串平衡的最小交换次数
题目描述
给你一个字符串
s，下标从 0 开始，且长度为偶数n。字符串恰好由n / 2个开括号'['和n / 2个闭括号']'组成。只有能满足下述所有条件的字符串才能称为平衡字符串：
- 字符串是一个空字符串，或者
- 字符串可以记作
AB，其中A和B都是平衡字符串，或者- 字符串可以写成
[C]，其中C是一个平衡字符串。
你可以交换任意两个下标所对应的括号任意次数。返回使
s变成平衡字符串所需要的最小交换次数
解题思路
找规律题
记录总共count个不匹配的括号。
count ∈ [ 1 , 2 ] \in[1,2] ∈[1,2]，交换次数为1
count ∈ [ 3 , 4 ] \in[3,4] ∈[3,4]，交换次数为2
count ∈ [ n , n + 1 ] \in[n,n+1] ∈[n,n+1]，交换次数为Round(n/2)
class Solution {
public int minSwaps(String s) {
Stack<Character> st = new Stack<>();
int count = 0;
int i=0;
while(i<s.length()) {
if(s.charAt(i)=='[')
st.add('[');
else if(s.charAt(i)==']') {
if(st.isEmpty())
count++;
else
st.pop();
}
i++;
}
return (int) Math.round(1.0*count/2);
}
}
5841. 找出到每个位置为止最长的有效障碍赛跑路线
题目描述
你打算构建一些障碍赛跑路线。给你一个下标从 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对应的最长障碍赛跑路线的长度。
解题思路
这题就和之前的最长子序列的题一样。。。
l[i]：记录连续递增长度为i的子序列。
遍历obstacles当obstacles[i]大于等于l最后一个时，加入队尾。否则，二分查找第一个大于obstacles[i]的下标进行替换。
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
List<Integer> l = new LinkedList<>();
l.add(obstacles[0]);
int[] ans = new int[obstacles.length];
ans[0] = l.size();
for(int i=1;i<obstacles.length;i++) {
if(obstacles[i]>=l.get(l.size()-1)) {
l.add(obstacles[i]);
ans[i]=l.size();
}else {
int idx = BinirySearch(l,obstacles[i]);
l.remove(idx);
l.add(idx, obstacles[i]);
ans[i]=idx+1;
}
}
// for(int i=0;i<l.size();i++) {
// ans[i]=l.get(i);
// }
return ans;
}
private int BinirySearch(List<Integer> nums, int t) {
int l=0;
int r=nums.size();
while(l<r) {
int m = l+(r-l)/2;
if(t>nums.get(m)) {
l=m+1;
}else if(t<nums.get(m)) {
r=m;
}else {
l=m+1;
}
}
return l;
}
}
