刷题打卡第三天
一、（困难题）239. 滑动窗口最大值
二、（简单题）1422. 分割字符串的最大得分
三、（简单题）1046. 最后一块石头的重量
一、（困难题）239. 滑动窗口最大值
难，第一次提交运算超时了，想不出来怎么解决，看了题解才做出来。
原题链接：239. 滑动窗口最大值
题目描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
/
解题思路：
可以使用最大堆来取出窗口中的最大值，但是问题就在于如何清空堆中不属于窗口内的数；
我们让最大堆中存放的是数组，数组第一个元素存放窗口值，第二个元素存放下标。
接下来的做法就是不着急清空窗口外值，先把移动窗口后会新加入元素以及下标存入最大堆，使用peek()检查最大值的下标是否在窗口内，不在就用poll()将堆顶节点删除，重复操作直到得到滑动窗口内的最大值。
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //数组长度 int len = nums.length; //最大堆：存放数组，int[]{num,index},int[0]为值，int[1]表示下标 //按最大堆规律比较排序时，先比较值，值相同才比较下标 PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>(){ public int compare(int[] a,int[] b){ return b[0] != a[0]?b[0]-a[0]: b[1]-a[1]; } }); for(int i = 0;i < k; ++i){ que.offer(new int[]{nums[i],i}); } int[] max = new int[len-k+1];//窗口一共滑动 nums.length-k+1次 max[0] = que.peek()[0];//将堆顶最大值复制给max数组，不删除任何堆节点 for(int i = k;i < len; ++i){ que.offer(new int[]{nums[i],i});//将窗口滑动后，右边的新值放入最大堆 //peek()复制出堆顶的最大值，不删除堆中任何节点 //如果这个最大值的下标小于窗口左边界，即不在窗口内，用poll()删除 while(que.peek()[1] < (i-k+1)){ que.poll(); } max[i-k+1] = que.peek()[0];//将窗口中最大值复制给max } return max; } }
提交结果：
二、（简单题）1422. 分割字符串的最大得分
这是今天的的第二题，第一道移动窗口的题还算有点思路，虽然运行超时，最后只能看题解，结果第二道简单题我也想不出来，看题解后嫌弃自己太蠢…
加油…屡败屡战。
原题链接：1422. 分割字符串的最大得分
题目描述：
给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大得分。
「分割字符串的得分为左子字符串中 0 的数量加上右子字符串中 1 的数量。
/
示例 1：
输入：s = “011101”
输出：5
解释： 将字符串 s 划分为两个非空子字符串的可行方案有：
左子字符串 = “0” 且右子字符串 = “11101”， 得分 = 1 + 4 = 5
左子字符串 = “01” 且 右子字符串 = “1101”，得分 = 1 + 3 = 4
左子字符串 = “011” 且 右子字符串 = “101”，得分 = 1 + 2 = 3
左子字符串 = “0111” 且右子字符串 = “01”， 得分 = 1 + 1 = 2
左子字符串 = “01110” 且 右子字符串 = “1”，得分 = 2 + 1 = 3
/
示例 2：
输入：s = “00111”
输出：5
解释：当 左子字符串 = “00” 且 右子字符串 = “111” 时，
我们得到最大得分 = 2 +3 = 5
/
示例 3：
输入：s = “1111”
输出：3
解题思路：
第一次循环：
先算出第一种划分方案（左串只有一个字符时）的得分；
第二次循环：
循环算出当前的下一种划分方案的得分，与当前方案得分作比较，记录较高的得分。
最后返回所有方案中最高得分
实现代码：
class Solution { public int maxScore(String s) { int n = s.length(); //字符串长度 int sum = 0; //某种方案的得分 if(s.charAt(0) == '0'){ //计算第一种方案左子串得分 ++sum; } for(int i = 1; i < n; ++i){ //累加第一种方案右子串得分 if(s.charAt(i) == '1') ++sum; } int curr = sum; //记录当前方案得分 for(int i = 1;i < n-1 ;++i){ //循环计算所有方案 if(s.charAt(i) == '1'){ //左字串增加‘1’，右字串减少‘1’时。 --curr; //当前方案比前一方案得分减一 }else{ //左字串增加‘0’，右字串减少‘0’时。 ++curr; //当前方案比前一方案得分加一 } sum = Math.max(sum,curr);//记录前后方案中较高的得分 } return sum; //返回所有方案中最高的方案得分 } }
提交结果：
三、（简单题）1046. 最后一块石头的重量
更新于（2022.9.16 ； 20 ：12）
原题链接：1046. 最后一块石头的重量
题目描述：
解题思路：
用最大堆存放数组，每次取两个元素进行比较，同时记录元素个数的变化，相互抵消后数量减少2，没有完全抵消，将剩下的一个元素放进最大堆排序，数量减少1；
当记录的数量剩下一个时，返回堆顶元素，当最后两个元素相互抵消，数量归零，直接返回0；
解题代码：
class Solution { public int lastStoneWeight(int[] stones) { int len = stones.length; //记录数组元长度； if(len < 2) return stones[0];//如果只有一个元素，直接返回单个元素 //创建优先队列（默认最小堆），重写比较器，设置为最大堆 PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ return b-a; } }); //增强for循环，所有数组元素进入最大堆进行排序 for(int stone : stones){ que.offer(stone); } int x,y; while(true){ //剩下最后一个元素，停止循环 if(len==1) break; //从堆中取出最重的两个石头 x = que.poll(); y = que.poll(); if((x-y) == 0){//相互抵消 len -= 2; //长度减2 //长度归零，直接返回0 if(len == 0) return 0; //没有完全粉碎，新重量进堆，长度减1 }else if((x-y) > 0){ que.offer(x-y); --len; }else{ que.offer(y-x); --len; } } return (int)que.poll();//返回堆中最后一个元素； } }
提交结果：
贵在坚持：
