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$\in [1,2]$，交换次数为1
count$\in [3,4]$，交换次数为2
count$\in [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;
	}
}