门户网站建设费用,马鞍山网站设计制作,泰安网络安装,新手如何学代码题目
1005、K次取反后最大化的数组和
给定一个整数数组 A#xff0c;我们只能用以下方法修改该数组#xff1a;我们选择某个索引 i 并将 A[i] 替换为 -A[i]#xff0c;然后总共重复这个过程 K 次。#xff08;我们可以多次选择同一个索引 i。#xff09;
以这种方式修改…题目
1005、K次取反后最大化的数组和
给定一个整数数组 A我们只能用以下方法修改该数组我们选择某个索引 i 并将 A[i] 替换为 -A[i]然后总共重复这个过程 K 次。我们可以多次选择同一个索引 i。
以这种方式修改数组后返回数组可能的最大和。
示例 1
输入A [4,2,3], K 1 输出5 解释选择索引 (1,) 然后 A 变为 [4,-2,3]。 示例 2
输入A [3,-1,0,2], K 3 输出6 解释选择索引 (1, 2, 2) 然后 A 变为 [3,1,0,2]。 示例 3
输入A [2,-3,-1,5,-4], K 2 输出13 解释选择索引 (1, 4) 然后 A 变为 [2,3,-1,5,4]。 提示
1 A.length 10000 1 K 10000 -100 A[i] 100
class Solution {public int largestSumAfterKNegations(int[] nums, int K) {// 将数组按照绝对值大小从大到小排序注意要按照绝对值的大小nums IntStream.of(nums).boxed().sorted((o1, o2) - Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len nums.length; for (int i 0; i len; i) {//从前向后遍历遇到负数将其变为正数同时K--if (nums[i] 0 K 0) {nums[i] -nums[i];K--;}}// 如果K还大于0那么反复转变数值最小的元素将K用完if (K % 2 1) nums[len - 1] -nums[len - 1];return Arrays.stream(nums).sum();}
}class Solution {public int largestSumAfterKNegations(int[] A, int K) {if (A.length 1) return k % 2 0 ? A[0] : -A[0];Arrays.sort(A);int sum 0;int idx 0;for (int i 0; i K; i) {if (i A.length - 1 A[idx] 0) {A[idx] -A[idx];if (A[idx] Math.abs(A[idx 1])) idx;continue;}A[idx] -A[idx];}for (int i 0; i A.length; i) {sum A[i];}return sum;}
}134、加油站
在一条环路上有 N 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1。
说明:
如果题目有解该答案即为唯一答案。 输入数组均为非空数组且长度相同。 输入数组中的元素均为非负数。 示例 1: 输入:
gas [1,2,3,4,5] cost [3,4,5,1,2] 输出: 3 解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油 开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油 开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油 开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油 开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油 开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。 因此3 可为起始索引。 示例 2: 输入:
gas [2,3,4]
cost [3,4,3]
输出: -1
解释: 你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油。开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油。开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油。你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。因此无论怎样你都不可能绕环路行驶一周。
// 解法1
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum 0;int min 0;for (int i 0; i gas.length; i) {sum (gas[i] - cost[i]);min Math.min(sum, min);}if (sum 0) return -1;if (min 0) return 0;for (int i gas.length - 1; i 0; i--) {min (gas[i] - cost[i]);if (min 0) return i;}return -1;}
}// 解法2
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum 0;int totalSum 0;int index 0;for (int i 0; i gas.length; i) {curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if (curSum 0) {index (i 1) % gas.length ; curSum 0;}}if (totalSum 0) return -1;return index;}
}135、分发糖果
老师想给孩子们分发糖果有 N 个孩子站成了一条直线老师会根据每个孩子的表现预先给他们评分。
你需要按照以下要求帮助老师给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。 相邻的孩子中评分高的孩子必须获得更多的糖果。 那么这样下来老师至少需要准备多少颗糖果呢
示例 1:
输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。 示例 2:
输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这已满足上述两个条件。
class Solution {/**分两个阶段1、起点下标1 从左往右只要 右边 比 左边 大右边的糖果左边 12、起点下标 ratings.length - 2 从右往左 只要左边 比 右边 大此时 左边的糖果应该 取本身的糖果数符合比它左边大 和 右边糖果数 1 二者的最大值这样才符合 它比它左边的大也比它右边大*/public int candy(int[] ratings) {int len ratings.length;int[] candyVec new int[len];candyVec[0] 1;for (int i 1; i len; i) {candyVec[i] (ratings[i] ratings[i - 1]) ? candyVec[i - 1] 1 : 1;}for (int i len - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}int ans 0;for (int num : candyVec) {ans num;}return ans;}
}
