软件开发专业哪个学校好_网店策划书模板_长春网站建设技术托管_外链查询

一. 学习文章及资料

二. 学习内容

1. K次取反后最大化的数组和

(1) 贪心策略：

使用了两次贪心

局部最优：让绝对值大的负数变为正数，当前数值达到最大
全局最优：整个数组和达到最大
如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大

局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了）
全局最优：整个 数组和 达到最大

(2) 解题步骤：

1. 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
2. 从前向后遍历，遇到负数将其变为正数，同时K--
3. 如果K还大于0，那么反复转变数值最小的元素，将K用完
4. 求和

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {if (nums.length == 1) return nums[0];int sum=0;// 排序：先把负数处理了Arrays.sort(nums);// 贪心点, 通过负转正, 消耗尽可能多的kfor(int i=0;i<nums.length&&k>0;i++){if(nums[i]<0){nums[i]*=-1;k--;}}if(k%2==1){Arrays.sort(nums);nums[0]*=-1;} for(int i=0;i<nums.length;i++){sum+=nums[i];}return sum;}
}

2. 加油站

(1) 暴力解法：

遍历每一个加油站为起点的情况，模拟一圈。

如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。

(2) 贪心算法(从全局进行贪心选择):

情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的

情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。

情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum=0;int min=Integer.MAX_VALUE;// 从起点出发，油箱里的油量最小值for(int i=0;i<cost.length;i++){int res=gas[i]-cost[i];curSum+=res;if(min>curSum) min=curSum;}if(curSum<0) return -1;            // 情况1                        if(min>=0) return 0;               // 情况2for(int i=cost.length-1;i>=0;i--){ // 情况3int res=gas[i]-cost[i];min+=res;if(min>=0) return i;}return -1;}
}

(3) 贪心算法

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因从i之前开始一定不行
全局最优：找到可以跑一圈的起始位置

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int start=0;int curSum=0;int totalSum=0;for(int i=0;i<gas.length;i++){curSum+=gas[i]-cost[i];totalSum+=gas[i]-cost[i];if(curSum<0){ // 当前累加rest[i]和 curSum一旦小于0start=i+1;// 起始位置更新为i+1curSum=0; // curSum从0开始}}if(totalSum<0) return -1; // 说明怎么走都不可能跑一圈了return start;}
}

3. 分发糖果

(1) 解题思路：

一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边

1.先确定右边评分大于左边的情况（也就是从前向后遍历）

局部最优：只要右边评分比左边大，右边的孩子就多一个糖果
全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1

2.确定左孩子大于右孩子的情况一定要从后向前遍历！

3.如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。

局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。
全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。

(2) 解题步骤：

1. 先确定右孩子大于左孩子情况(从前向后遍历)
2. 再确认左孩子大于右孩子的情况(后向前遍历)
3. 取两遍遍历较大的那个，只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多

class Solution {public int candy(int[] ratings) {int[] candyVec=new int[ratings.length];Arrays.fill(candyVec,1);//先确定右孩子大于左孩子情况(从前向后遍历)for(int i=1;i<ratings.length;i++){ //从第二个开始if(ratings[i]>ratings[i-1]){ //右评分大于左candyVec[i]=candyVec[i-1]+1;}}//再确认左孩子大于右孩子的情况(后向前遍历)for(int i=ratings.length-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyVec[i]=Math.max(candyVec[i],candyVec[i+1]+1);}}int result=0;for(int c:candyVec){result+=c;}return result;}
}