Leetcode Weekly Contest 253（字符串、贪心、二分）
题目链接：
写在前面：
本次周赛做出第一题和第二题。
1、
难度：Easy
代码：
class Solution {
public boolean isPrefixString(String s, String[] words) {
char[] arr=s.toCharArray();
StringBuilder sb=new StringBuilder();
for(String word:words){
sb.append(word);
if(sb.length()>=arr.length){
break;
}
}
if(sb.length()!=arr.length){
return false;
}
int i=0,j=0;
for( ;i<arr.length;i++,j++){
if(arr[i]!=sb.charAt(j)){
return false;
}
}
return true;
}
}
2、
难度：Medium
题目大意：
详见题意。
思路：
贪心 ，每次选择数组中最大的元素来进行操作。
代码
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);
for(int n:piles){
pq.offer(n);
}
while(k-->0){
int n=pq.poll();
n-=n/2;
pq.offer(n);
}
int res=0;
while(!pq.isEmpty()){
res+=pq.poll();
}
return res;
}
}
3、
难度：Medium
题目大意：
括号匹配。
思路：
找规律，推导数学公式。参考。
代码
class Solution {
public int minSwaps(String s) {
char[] arr=s.toCharArray();
int misMatch=0;
for(char c:arr){
if(c==[){
misMatch++;
}
else{
if(misMatch>0){
misMatch--;
}
}
}
return (misMatch+1)/2;
}
}
4、
难度：Hard
题目大意：
详见题目。
思路
动态规划会超时，需要用二分+贪心，这一题与类似，可以参考。本题还参考了。
代码
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] nums) {
int n=nums.length;
int[] d=new int[n+1];
//d[i]表示长度为i的最长递增子序列的最后一个元素的最小值
int len=1;//最长递增子序列的长度
d[1]=nums[0];
int[] res=new int[n];
res[0]=len;
for(int i=1;i<n;i++){
if(nums[i]>=d[len]){
len++;
d[len]=nums[i];
res[i]=len;
}
else{
int l=0,r=len;
while(l<r){
//寻找小于等于nums[i]的元素的最大下标
int mid=l+(r-l+1)/2;
if(d[mid]>nums[i]){
r=mid-1;
}
else{
l=mid;
}
}
d[l+1]=nums[i];
res[i]=l+1;
}
}
return res;
}
}