桦甸市建设局网站,网站推广中h1标签的重要性,甘肃省城乡建设厅网站首页,上海网站托管88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 排列。
**注意#xff1a;**…88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
**注意**最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。示例 2
输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3
输入nums1 [0], m 0, nums2 [1], n 1
输出[1]
解释需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-109 nums1[i], nums2[j] 109
**进阶**你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗
import org.junit.Test;import java.util.Arrays;
import java.util.Scanner;public class Merge {public void merge(int[] nums1, int m, int[] nums2, int n) {// 从后向前遍历int pos1 m-1;int post2 n-1;int pos nums1.length-1;while (pos1 0 post2 0) {if(nums1[pos1] nums2[post2]){nums1[pos--] nums1[pos1--];}else{nums1[pos--] nums2[post2--];}}while (post2 0) {nums1[pos--] nums2[post2--];}for (int i 0; i nums1.length; i) {System.out.println(nums1[i] );}}public static void main(String[] args) {Merge merge new Merge();Scanner scanner new Scanner(System.in);System.out.println(请输入n的val);int n scanner.nextInt();System.out.println(请输入m的val);int m scanner.nextInt();int[] nums1 new int[nm];int[] nums2 new int[m];System.out.println(请输入nums1[]的元素);for(int i0;in;i){nums1[i] scanner.nextInt();}System.out.println(请输入nums2[]的元素);for(int i0;im;i){nums2[i] scanner.nextInt();}merge.merge(nums1,n,nums2,m);}}27. 移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作
更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。
用户评测
评测机将使用以下代码测试您的解决方案
int[] nums [...]; // 输入数组
int val ...; // 要移除的值
int[] expectedNums [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k removeElement(nums, val); // 调用你的实现assert k expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i 0; i actualLength; i) {assert nums[i] expectedNums[i];
}如果所有的断言都通过你的解决方案将会 通过。
示例 1
输入nums [3,2,2,3], val 3
输出2, nums [2,2,_,_]
解释你的函数函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。示例 2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,4,0,3,_,_,_]
解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。提示
0 nums.length 1000 nums[i] 500 val 100
import java.util.Arrays;
import java.util.Scanner;public class Remove {public int removeElement(int[] nums, int val) {// 首先排序Arrays.sort(nums);int left 0,right 0;while(right nums.length) {if(nums[right] val){right;continue;}nums[left] nums[right];}return left;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);System.out.println(请输入数组长度);int len scanner.nextInt();System.out.println(请输入要移除的值);int val scanner.nextInt();System.out.println(请输入数组元素);int[] nums new int[len];for(int i0;ilen;i){nums[i] scanner.nextInt();}Remove remove new Remove();int length remove.removeElement(nums, val);System.out.println(答案);for(int i0;ilength;i){System.out.println(nums[i]);}}
}26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums 请你** 原地** 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums [...]; // 输入数组
int[] expectedNums [...]; // 长度正确的期望答案int k removeDuplicates(nums); // 调用assert k expectedNums.length;
for (int i 0; i k; i) {assert nums[i] expectedNums[i];
}如果所有断言都通过那么您的题解将被 通过。
示例 1
输入nums [1,1,2]
输出2, nums [1,2,_]
解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2
输入nums [0,0,1,1,1,2,2,3,3,4]
输出5, nums [0,1,2,3,4]
解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示
1 nums.length 3 * 104-104 nums[i] 104nums 已按 非严格递增 排列
public class removeDuplicates {public int removeDuplicates(int[] nums) {int left 1;int right 1;while(rightnums.length){if(nums[right] ! nums[right-1]){nums[left] nums[right];}right;}return left;}public static void main(String[] args) {int[] nums new int[]{1,1,1,1,1,2,3,4,5,5,5,5,6,6,6,6,6,6,6};removeDuplicates removeDuplicates new removeDuplicates();int len removeDuplicates.removeDuplicates(nums);for(int i0; ilen; i){System.out.print(nums[i] );}}
}80. 删除有序数组中的重复项 II
给你一个有序数组 nums 请你** 原地** 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明
为什么返回数值是整数但输出的答案是数组呢
请注意输入数组是以**「引用」**方式传递的这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说不对实参做任何拷贝
int len removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i 0; i len; i) {print(nums[i]);
}示例 1
输入nums [1,1,1,2,2,3]
输出5, nums [1,1,2,2,3]
解释函数应返回新长度 length 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。示例 2
输入nums [0,0,1,1,1,1,2,3,3]
输出7, nums [0,0,1,1,2,3,3]
解释函数应返回新长度 length 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。提示
1 nums.length 3 * 104-104 nums[i] 104nums 已按升序排列
public class removeDuplicates {public int removeDuplicates(int[] nums) {int left 2;int right 2;while(rightnums.length){if(nums[right]!nums[left-2]){nums[left] nums[right];}right;}return left;}public static void main(String[] args) {int[] nums new int[]{1,2,3,3,3,4,5,6};removeDuplicates removeDuplicates new removeDuplicates();int len removeDuplicates.removeDuplicates(nums);for(int i0; ilen; i){System.out.print(nums[i] );}}
}169. 多数元素
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109
**进阶**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
public class MostNumber {public int majorityElement(int[] nums) {int res nums[0];int count 1;for(int i1;inums.length;i){if(count0){res nums[i];}if(res nums[i]){count;}else{count--;}}return res;}public static void main(String[] args) {int[] nums new int[]{2,2,1,1,1,2,2};int[] nums1 new int[10];MostNumber mostNumber new MostNumber();System.out.println(mostNumber.majorityElement(nums));}
}189. 轮转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
示例 1:
输入: nums [1,2,3,4,5,6,7], k 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入nums [-1,-100,3,99], k 2
输出[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]提示
1 nums.length 105-231 nums[i] 231 - 10 k 105
进阶
尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
public class rotateArray {public void rotate(int[] nums, int k) {k k%nums.length;int[] nums1 new int[nums.length];for(int i 0; i nums.length; i){nums1[(ik)%nums.length] nums[i];}for(int i 0; i nums.length; i){System.out.println(nums1[i]);}}public void reverse(int[] nums, int start, int end) {while(start end){int tmp nums[start];nums[start] nums[end];nums[end] tmp;start;end--;}}public void rotate2(int[] nums, int k) {k k%nums.length;reverse(nums, 0, nums.length-1);reverse(nums, 0, k-1);reverse(nums, k, nums.length-1);for(int i nums.length-1; i 0; i--){System.out.print(nums[i] );}}public static void main(String[] args) {int[] nums {1,2,3,4,5,6,7};rotateArray rotateArray new rotateArray();rotateArray.rotate2(nums, 3);}}121. 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。提示
1 prices.length 1050 prices[i] 104
public class buy {public int maxProfit(int[] prices) {int res Integer.MIN_VALUE;int min Integer.MAX_VALUE;for(int i 0; i prices.length; i){min Math.min(min,prices[i]);res Math.max(res,prices[i]-min);}return res;}public static void main(String[] args) {int[] nums new int[]{7,1,5,3,6,4};buy b1 new buy();int maxProfit b1.maxProfit(nums);System.out.println(maxProfit);}}122. 买卖股票的最佳时机 II
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。
最大总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
最大总利润为 4 。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0。提示
1 prices.length 3 * 1040 prices[i] 104
class Solution {public int maxProfit(int[] prices) {int res 0;for(int i1;iprices.length;i){if(prices[i]-prices[i-1]0){res prices[i]-prices[i-1];}}return res;}
}55. 跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示
1 nums.length 1040 nums[i] 105
public class Jump {public boolean canJump(int[] nums) {int len nums.length;int now 0;for(int i 0; i len; i) {// 目前可以到达的最远的地方if(nums[i] 0 now i){break;}now Math.max(now,inums[i]);}now;if(now len) return false;return true;}public static void main(String[] args) {int[] nums {3,2,1,0,4};System.out.println(new Jump().canJump(nums));}}45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i]i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2提示:
1 nums.length 1040 nums[i] 1000题目保证可以到达 nums[n-1]
public class JumpGame {public int jump(int[] nums) {int len nums.length-1;int maxDistance 0;int end 0;int res 0;for(int i 0 ; i len ; i){maxDistance Math.max(maxDistance,inums[i]);if(i end){end maxDistance;res;}}return res;}public static void main(String[] args) {int[] nums new int[]{2,3,1,1,4};JumpGame jumpGame new JumpGame();System.out.println(jumpGame.jump(nums));}}274. H 指数
给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义h 代表“高引用次数” 一名科研人员的 h 指数 是指他她至少发表了 h 篇论文并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值h 指数 是其中最大的那个。
示例 1
输入citations [3,0,6,1,5]
输出3
解释给定数组表示研究者总共有 5 篇论文每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇 至少 被引用了 3 次其余两篇论文每篇被引用 不多于 3 次所以她的 h 指数是 3。示例 2
输入citations [1,3,1]
输出1提示
n citations.length1 n 50000 citations[i] 1000
class Solution {public int hIndex(int[] citations) {Arrays.sort(citations);int h 0;int pos citations.length -1;while(pos0 citations[pos] h){h;pos--;}return h;}
}238. 除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法**且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums [1,2,3,4]
输出: [24,12,8,6]示例 2:
输入: nums [-1,1,0,-3,3]
输出: [0,0,9,0,0]提示
2 nums.length 105-30 nums[i] 30保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
**进阶**你可以在 O(1) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。
public class productExceptSelf {public int[] productExceptSelf(int[] nums){// 计算Leftint[] Left new int[nums.length];Left[0] 1;for (int i 1; i nums.length; i){Left[i] Left[i-1]*nums[i-1];}int[] Right new int[nums.length];Right[nums.length-1] 1;for(int i nums.length-2; i 0; i--){Right[i] Right[i1]*nums[i1];}for(int i 0;inums.length;i){nums[i] Left[i]*Right[i];}return nums;}public static void main(String[] args) {productExceptSelf p new productExceptSelf();int[] nums new int[]{4,5,1,8,2};int[] res p.productExceptSelf(nums);for (int i0;ires.length;i){System.out.print(res[i] );}}}134. 加油站
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -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 升汽油。
因此无论怎样你都不可能绕环路行驶一周。public class GasStation {public int canCompleteCircuit(int[] gas, int[] cost) {int total 0;int pos 0;int tank 0;for(int i0;igas.length;i){total gas[i] - cost[i];tank gas[i] - cost[i];if(tank 0){pos i1;tank 0;}}return total 0 ? -1 : pos;}// 测试用例public static void main(String[] args) {GasStation solution new GasStation();// 示例 1int[] gas1 {3,1,1};int[] cost1 {1,2,2};System.out.println(起始站点: solution.canCompleteCircuit(gas1, cost1));}
}135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。提示
n ratings.length1 n 2 * 1040 ratings[i] 2 * 104
public class CandyDistribution {public static int candy(int[] ratings) {int[] candy new int[ratings.length];int res 0;for (int i 0; i ratings.length; i) {candy[i] 1;}// 从左到右遍历for(int i 1;i candy.length; i){if(ratings[i]ratings[i-1]){candy[i] candy[i-1]1;}}// 从右到左遍历for(int i candy.length - 2; i 0; i--){if(ratings[i]ratings[i1]){candy[i] Math.max(candy[i],candy[i1]1);}}for(int c : candy){res c;}return res;}public static void main(String[] args) {// 示例 1int[] ratings1 {1, 0, 2};System.out.println(最少糖果数: candy(ratings1)); // 输出: 5}
}42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 1
输入height [0,1,0,2,1,0,1,3,2,1,2,1]
输出6
解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2
输入height [4,2,0,3,2,5]
输出9提示
n height.length1 n 2 * 1040 height[i] 105
题解1
public class trap {public int trap_01(int[] height) {int len height.length;int[] pre new int[len];pre[0] height[0];int[] suf new int[len];suf[len-1] height[len-1];// 计算左前缀for(int i 1; i height.length; i) {pre[i] Math.max(pre[i-1], height[i]);}// 计算右前缀for(int i len-2; i 0; i--) {suf[i] Math.max(suf[i1], height[i]);}// 统计int res 0;for(int i0;iheight.length;i){if(pre[i] suf[i]){res pre[i] - height[i];}else{res suf[i] - height[i];}}return res;}public static void main(String[] args) {trap t new trap();int[] height new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};System.out.println(t.trap_01(height));}}优化版本一次遍历
public class trap {public int trap_02(int[] height){// 双指针int left 0,right height.length-1;int res 0;int leftMax height[0];int rightMax height[height.length-1];while(left right){// 更新leftMax和rightMax的值leftMax Math.max(leftMax, height[left]);rightMax Math.max(rightMax, height[right]);if(leftMax rightMax){res leftMax - height[left];left;}else{res rightMax - height[right];right--;}}return res;}public static void main(String[] args) {trap t new trap();int[] height new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};System.out.println(t.trap_02(height));}}151. 反转字符串中的单词
给你一个字符串 s 请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。
示例 1
输入s the sky is blue
输出blue is sky the示例 2
输入s hello world
输出world hello
解释反转后的字符串中不能存在前导空格和尾随空格。示例 3
输入s a good example
输出example good a
解释如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个。提示
1 s.length 104s 包含英文大小写字母、数字和空格 s 中 至少存在一个 单词
**进阶**如果字符串在你使用的编程语言中是一种可变数据类型请尝试使用 O(1) 额外空间复杂度的 原地 解法。
import java.util.ArrayList;
import java.util.Arrays;public class reverseWords {public String reverseWords(String s) {String[] split s.trim().split( );String[] filter Arrays.stream(split).filter(e - !e.isEmpty()).toArray(String[]::new);int left 0;int right filter.length - 1;while (left filter.length/2) {String tmp filter[right];filter[right] filter[left];filter[left] tmp;left;right--;}return String.join( , filter);}public static void main(String[] args) {reverseWords r new reverseWords();System.out.println(r.reverseWords(a good example));}}
