花都区建设网站,珠海有什么网站,digging into wordpress,华为弹性云服务器创建wordpress1 我为什么要写这个总结
1.1 字节笔试题
小明在玩一场通关游戏#xff0c;初始血量为1#xff0c;关卡有怪兽或者有血包#xff08;正数就是血包可回血数#xff0c;负数说明是怪兽的伤害值#xff09;#xff0c;当捡到血包时会加血量#xff0c;碰到怪兽时会掉血初始血量为1关卡有怪兽或者有血包正数就是血包可回血数负数说明是怪兽的伤害值当捡到血包时会加血量碰到怪兽时会掉血现在指定初始血量为x关卡是一个数组小明必须按照数组的顺序玩游戏当碰到一个怪兽时他可以选择将这个怪兽扔到数组末尾小明可以无限次地将怪兽移到数组末尾,问小明最少移动几次就能存活,如果无论怎么移动都不能存活则返回-1 假设关卡是这样的[-200,-300,400]则返回-1假如是这样的[200,100,-250,-60,-70,100]则返回1只需要把-250挪到尾部
思路当发现自己血量不足时就从当前已经遍历过的所有关卡中选择耗费血量最多的那个关卡并且放到最后一关如果即使这样挪开了耗血量最大的一关自身血量还是为负则直接返回-1说明无法通关
2 总结
2.1 什么是局部最优
贪心关注的是局部最优这里当前最优指当前遍历的所有元素中的最优解也是局部最优的一种而一般的最有解又涉及到数据的最值而且随着元素的不断向右扩展可能这个最优值是不断变化的所以一般可以使用堆来动态维护它的最值。
2.2 解贪心类题目的一些分类
分为相向双指针同向双指针以及最值堆等类型
2.2.1 相向双指针和同向双指针的解题思路的区别 相向双指针通常用于处理排序数组中的问题比如找出两个数的和等于特定值如LeetCode题目167. 两数之和 II - 输入有序数组或者反转数组如LeetCode题目344. 反转字符串。对于这类问题两个指针分别从数组的头部和尾部出发根据指向元素的大小关系向中间移动直到两个指针相遇。 同向双指针通常用于处理数组或字符串中需要连续元素满足特定条件的问题比如找出满足特定和的最小子数组如LeetCode题目209. 长度最小的子数组或者找出最长的满足特定条件的子串如LeetCode题目424. 替换后的最长重复字符。对于这类问题一个指针快指针用于遍历数组或字符串另一个指针慢指针用于维护满足条件的区间。
2.2.2 在LeetCode上与同向双指针和贪心策略相关的题目有很多。举两个例子 题目 209. 长度最小的子数组: 在一个正整数数组中寻找长度最小的连续子数组其和至少为特定值。解决这个问题的方法是维持一个滑动窗口窗口的左右边界就是同向的双指针。右指针向右移动以增加子数组的和当子数组的和达到或超过目标值时尝试将左指针向右移动以减小子数组的长度。 题目 424. 替换后的最长重复字符: 给定一个字符串和一个整数k找出可以通过最多替换k个字符以得到的最长的重复字符子串。解决这个问题的方法同样是维持一个滑动窗口窗口的左右边界就是同向的双指针。右指针向右移动以增加子串的长度当子串中最多的字符数量加上k小于子串的长度时左指针向右移动。
2.3 一部分需要预处理的题目
2.3.1 可能需要排序
分发饼干
2.3.2 可能需要hashMap统计字符最后一次出现的位置
划分字母区间
3 使用堆解决问题的贪心策略
3.1 leetcode1046. 最后一块石头的重量
3.2 leetcode 1642. 可以到达的最远建筑
leetcode 1642. 可以到达的最远建筑
标准答案 // 砖块优先砖块数量不足时考虑将当前替代最小高度的梯子改用砖块替代public int furthestBuilding(int[] heights, int bricks, int ladders) {int nheights.length;//大根堆PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-(o2-o1));int i;int sum0;//表示当前需要的梯子数量int sum_bri0;for(i1;in;i){int diffheights[i]-heights[i-1];if(diff0){pq.offer(diff);sum_bridiff;//砖块的数量之和if(sum_bribricks){sum_bri-pq.poll();sum;}if(sumladders){return i-1;}}}return n-1;}//每次先放梯子当梯子数量不足时将当前使用过的梯子中替代阶梯数最少的梯子找出来用对应砖头替换替换出来的梯子拿到当前使用public int furthestBuilding(int[] heights, int bricks, int ladders) {int nheights.length;//int[]:PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-(o1-o2));int i;int sum0;//表示当前需要的砖块数量for(i1;in;i){int diffheights[i]-heights[i-1];if(diff0){pq.offer(diff);if(pq.size()ladders){sumpq.poll();}if(sumbricks){return i-1;}}}return n-1;}我的答案(有几个特别长的case过不了)java
public int furthestBuilding2(int[] heights, int bricks, int ladders) {int nheights.length;PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-(o1-o2));int i;for(i1;in;){int diffheights[i-1]-heights[i];// System.out.println(i:i,diff:diff,heights[i-1]:heights[i-1],heights[i]:heights[i]);if(diff0){int diffAbs-diff;if(ladders0){ladders--;pq.add(diffAbs);}else if(bricksdiffAbs){bricks-diffAbs;}else{int newdInteger.MAX_VALUE;if(!pq.isEmpty()){newdpq.peek();}if(bricksnewd){pq.poll();bricks-newd;ladders;ii-1;}else{break;}}}i;}return i-1;}这里还有一个二分查找的方法 每太整明白
3.3 121. 买卖股票的最佳时机虽然使用堆的方法不是最优解但是方便和其他题目对比得出最优解
3.3.1 这个题和3.1以及3.2有什么异同呢
同都涉及到取最值而且最值都是可能变化的 不同3.1以及3.2中的题目一个最值只能使用一次一旦使用就得poll操作而本题中的最值可以复用。正式这个特性导致了前者只能使用堆来维护最值因为可能需要多次取最值即使用到多个最值poll操作只能靠堆维护虽说本题也多次最最值但是可以重用最值没有poll操作。
class Solution {// 使用堆维护最小值public int maxProfit(int[] prices) {int nprices.length;//表示到第i天时股票的历史最低点价格PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-(o1-o2));int max0;for(int i0;in;i){pq.add(prices[i]);maxMath.max(max,prices[i]-pq.peek());}return max;}// 方法使用dp维护已经遍历值得最小值public int maxProfit3(int[] prices) {int nprices.length;//表示到第i天时股票的历史最低点价格int[]fnew int[n];f[0]prices[0];int max0;for(int i1;in;i){f[i]Math.min(f[i-1],prices[i]);maxMath.max(max,prices[i]-f[i]);}return max;}// 方法使用一个变量维护已经遍历值得最小值public int maxProfit(int[] prices) {int nprices.length;//表示到第i天时股票的历史最低点价格int minprices[0];int max0;for(int i1;in;i){minMath.min(min,prices[i]);maxMath.max(max,prices[i]-min);}return max;}// 使用单调栈维护已经遍历序列的最小值public int maxProfit2(int[] prices) {int nprices.length;DequeIntegerstnew ArrayDeque();int max0;st.add(prices[0]);for(int i1;in;i){int pprices[i];if(!st.isEmpty()pst.peekLast()){maxMath.max(st.peekLast()-st.peekFirst(),max);while(!st.isEmpty()st.peekLast()p){st.pollLast();}}st.addLast(p);}if(!st.isEmpty()){maxMath.max(st.peekLast()-st.peekFirst(),max);}return max;}
}3.3 871题最低加油次数和
3.4 630课程表III
4 使用相向双指针解决问题的贪心策略
4.1 167. 两数之和 II - 输入有序数组
思路双指针解决偏差
class Solution {public int[] twoSum(int[] numbers, int target) {int nnumbers.length;int i0,jn-1;while(ij){int sumnumbers[i]numbers[j];if(sumtarget){j--;}else if(sumtarget){i;}else{return new int[]{i1,j1};}}return new int[]{i1,j1};}}4.2 11. 盛最多水的容器
思路容器能盛的水取决于短板不断移动双指针中代表较小数值的那个指针直到两个指针相遇其中得到的所有可能的盛水量中取最大值即可。
class Solution {public int maxArea(int[] height) {int nheight.length;int i0,jn-1;int max-1;while(ij){int s(j-i)*Math.min(height[i],height[j]);maxMath.max(max,s);if(height[i]height[j]){j--;}else{i;}}return max;}
}5 同向双指针与贪心策略
5.1 763. 划分字母区间找出数组中满足特定条件的子序列
class Solution {public ListInteger partitionLabels(String s) {int ns.length();int[]mpnew int[26];for(int i0;in;i){mp[s.charAt(i)-a]i;}ListIntegerresnew ArrayList();int start0,end0;for(int i0;in;i){endMath.max(end,mp[s.charAt(i)-a]);if(endi){res.add(i-start1);starti1;}}return res;}
}
