ToB企服应用市场:ToB评测及商务社交产业平台

标题: 力扣150题 [打印本页]
作者: 来自云龙湖轮廓分明的月亮    时间: 3 天前
标题: 力扣150题
88. 归并两个有序数组

给你两个按 非递减顺序 分列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表现 nums1 和 nums2 中的元素数目。
请你 归并 nums2 到 nums1 中，使归并后的数组同样按 非递减顺序 分列。
**留意：**最终，归并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，此中前 m 个元素表现应归并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
  1. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  2. 输出：[1,2,2,3,5,6]
  3. 解释：需要合并 [1,2,3] 和 [2,5,6] 。
  4. 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
复制代码
示例 2：
  1. 输入：nums1 = [1], m = 1, nums2 = [], n = 0
  2. 输出：[1]
  3. 解释：需要合并 [1] 和 [] 。
  4. 合并结果是 [1] 。
复制代码
示例 3：
  1. 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
  2. 输出：[1]
  3. 解释：需要合并的数组是 [] 和 [1] 。
  4. 合并结果是 [1] 。
  5. 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
复制代码
提示：

**进阶：**你可以计划实现一个时间复杂度为 O(m + n) 的算法办理此题目吗？
  1. import org.junit.Test;
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  7. public class Merge {
  10.     public void merge(int[] nums1, int m, int[] nums2, int n) {
  11.         // 从后向前遍历
  12.         int pos1 = m-1;
  13.         int post2 = n-1;
  14.         int pos = nums1.length-1;
  15.         while (pos1 >= 0 && post2 >= 0) {
  16.             if(nums1[pos1] > nums2[post2]){
  17.                 nums1[pos--] = nums1[pos1--];
  18.             }else{
  19.                 nums1[pos--] = nums2[post2--];
  20.             }
  21.         }
  23.         while (post2 >= 0) {
  24.             nums1[pos--] = nums2[post2--];
  25.         }
  27.         for (int i = 0; i < nums1.length; i++) {
  28.             System.out.println(nums1[i]+" ");
  29.         }
  31.     }
  33.     public static void main(String[] args) {
  34.         Merge merge = new Merge();
  35.         Scanner scanner = new Scanner(System.in);
  36.         System.out.println("======请输入n的val======");
  37.         int n = scanner.nextInt();
  38.         System.out.println("======请输入m的val======");
  39.         int m = scanner.nextInt();
  40.         int[] nums1 = new int[n+m];
  41.         int[] nums2 = new int[m];
  43.         System.out.println("======请输入nums1[]的元素======");
  45.         for(int i=0;i<n;i++){
  46.             nums1[i] = scanner.nextInt();
  47.         }
  49.         System.out.println("======请输入nums2[]的元素======");
  51.         for(int i=0;i<m;i++){
  52.             nums2[i] = scanner.nextInt();
  53.         }
  55.         merge.merge(nums1,n,nums2,m);
  56.     }
  58. }
复制代码
27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数目。
假设 nums 中不等于 val 的元素数目为 k，要通过此题，您需要实行以下操作：

用户评测：
评测机将使用以下代码测试您的办理方案：
  1. int[] nums = [...]; // 输入数组
  2. int val = ...; // 要移除的值
  3. int[] expectedNums = [...]; // 长度正确的预期答案。
  4.                             // 它以不等于 val 的值排序。
  6. int k = removeElement(nums, val); // 调用你的实现
  8. assert k == expectedNums.length;
  9. sort(nums, 0, k); // 排序 nums 的前 k 个元素
  10. for (int i = 0; i < actualLength; i++) {
  11.     assert nums[i] == expectedNums[i];
  12. }
复制代码
假如所有的断言都通过，你的办理方案将会 通过。
示例 1：
  1. 输入：nums = [3,2,2,3], val = 3
  2. 输出：2, nums = [2,2,_,_]
  3. 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
  4. 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
复制代码
示例 2：
  1. 输入：nums = [0,1,2,2,3,0,4,2], val = 2
  2. 输出：5, nums = [0,1,4,0,3,_,_,_]
  3. 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
  4. 注意这五个元素可以任意顺序返回。
  5. 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
复制代码
提示：

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  4. public class Remove {
  6.     public int removeElement(int[] nums, int val) {
  7.         // 首先排序
  8.         Arrays.sort(nums);
  9.         int left = 0,right = 0;
  10.         while(right < nums.length) {
  11.             if(nums[right] == val){
  12.                 right++;
  13.                 continue;
  14.             }
  15.             nums[left++] = nums[right++];
  16.         }
  17.         return left;
  18.     }
  20.     public static void main(String[] args) {
  21.         Scanner scanner = new Scanner(System.in);
  22.         System.out.println("======请输入数组长度======");
  23.         int len = scanner.nextInt();
  24.         System.out.println("======请输入要移除的值======");
  25.         int val = scanner.nextInt();
  26.         System.out.println("======请输入数组元素======");
  27.         int[] nums = new int[len];
  28.         for(int i=0;i<len;i++){
  29.             nums[i] = scanner.nextInt();
  30.         }
  31.         Remove remove = new Remove();
  32.         int length = remove.removeElement(nums, val);
  33.         System.out.println("======答案======");
  34.         for(int i=0;i<length;i++){
  35.             System.out.println(nums[i]);
  36.         }
  37.     }
  38. }
复制代码
26. 删除有序数组中的重复项

给你一个 非严酷递增分列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 同等 。然后返回 nums 中唯一元素的个数。
思量 nums 的唯一元素的数目为 k ，你需要做以下事情确保你的题解可以被通过：

判题标准:
系统会用下面的代码来测试你的题解:
  1. int[] nums = [...]; // 输入数组
  2. int[] expectedNums = [...]; // 长度正确的期望答案
  4. int k = removeDuplicates(nums); // 调用
  6. assert k == expectedNums.length;
  7. for (int i = 0; i < k; i++) {
  8.     assert nums[i] == expectedNums[i];
  9. }
复制代码
假如所有断言都通过，那么您的题解将被 通过。
示例 1：
  1. 输入：nums = [1,1,2]
  2. 输出：2, nums = [1,2,_]
  3. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
复制代码
示例 2：
  1. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  2. 输出：5, nums = [0,1,2,3,4]
  3. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
复制代码
提示：

  1. public class removeDuplicates {
  3.     public int removeDuplicates(int[] nums) {
  4.         int left = 1;
  5.         int right = 1;
  6.         while(right<nums.length){
  7.             if(nums[right] != nums[right-1]){
  8.                 nums[left++] = nums[right];
  9.             }
  10.             right++;
  11.         }
  12.         return left;
  13.     }
  15.     public static void main(String[] args) {
  16.         int[] nums = new int[]{1,1,1,1,1,2,3,4,5,5,5,5,6,6,6,6,6,6,6};
  17.         removeDuplicates removeDuplicates = new removeDuplicates();
  18.         int len = removeDuplicates.removeDuplicates(nums);
  20.         for(int i=0; i<len; i++){
  21.             System.out.print(nums[i]+" ");
  22.         }
  23.     }
  24. }
复制代码
80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数高出两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
阐明：
为什么返回数值是整数，但输出的答案是数组呢？
请留意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
  1. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  2. int len = removeDuplicates(nums);
  4. // 在函数里修改输入数组对于调用者是可见的。
  5. // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  6. for (int i = 0; i < len; i++) {
  7.     print(nums[i]);
  8. }
复制代码
示例 1：
  1. 输入：nums = [1,1,1,2,2,3]
  2. 输出：5, nums = [1,1,2,2,3]
  3. 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
复制代码
示例 2：
  1. 输入：nums = [0,0,1,1,1,1,2,3,3]
  2. 输出：7, nums = [0,0,1,1,2,3,3]
  3. 解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
复制代码
提示：


  • 1 <= nums.length <= 3 * 104
  • -104 <= nums <= 104
  • nums 已按升序分列
  1. public class removeDuplicates {
  3.     public int removeDuplicates(int[] nums) {
  4.         int left = 2;
  5.         int right = 2;
  6.         while(right<nums.length){
  7.             if(nums[right]!=nums[left-2]){
  8.                 nums[left++] = nums[right];
  9.             }
  10.             right++;
  11.         }
  12.         return left;
  13.     }
  15.     public static void main(String[] args) {
  16.         int[] nums = new int[]{1,2,3,3,3,4,5,6};
  17.         removeDuplicates removeDuplicates = new removeDuplicates();
  18.         int len = removeDuplicates.removeDuplicates(nums);
  20.         for(int i=0; i<len; i++){
  21.             System.out.print(nums[i]+" ");
  22.         }
  23.     }
  24. }
复制代码
169. 多数元素

给定一个大小为 n 的数组 nums ，返回此中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组优劣空的，并且给定的数组总是存在多数元素。
示例 1：
  1. 输入：nums = [3,2,3]
  2. 输出：3
复制代码
示例 2：
  1. 输入：nums = [2,2,1,1,1,2,2]
  2. 输出：2
复制代码
提示：


  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums <= 109
**进阶：**实验计划时间复杂度为 O(n)、空间复杂度为 O(1) 的算法办理此题目。
  1. public class MostNumber {
  3.     public int majorityElement(int[] nums) {
  4.         int res = nums[0];
  5.         int count = 1;
  6.         for(int i=1;i<nums.length;i++){
  7.             if(count==0){
  8.                 res = nums[i];
  9.             }
  10.             if(res == nums[i]){
  11.                 count++;
  12.             }else{
  13.                 count--;
  14.             }
  15.         }
  16.         return res;
  17.     }
  19.     public static void main(String[] args) {
  20.         int[] nums = new int[]{2,2,1,1,1,2,2};
  21.         int[] nums1 = new int[10];
  22.         MostNumber mostNumber = new MostNumber();
  23.         System.out.println(mostNumber.majorityElement(nums));
  24.     }
  25. }
复制代码
189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，此中 k 优劣负数。
示例 1:
  1. 输入: nums = [1,2,3,4,5,6,7], k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右轮转 1 步: [7,1,2,3,4,5,6]
  5. 向右轮转 2 步: [6,7,1,2,3,4,5]
  6. 向右轮转 3 步: [5,6,7,1,2,3,4]
复制代码
示例 2:
  1. 输入：nums = [-1,-100,3,99], k = 2
  2. 输出：[3,99,-1,-100]
  3. 解释:
  4. 向右轮转 1 步: [99,-1,-100,3]
  5. 向右轮转 2 步: [3,99,-1,-100]
复制代码
提示：


  • 1 <= nums.length <= 105
  • -231 <= nums <= 231 - 1
  • 0 <= k <= 105
进阶：


  • 尽可能想出更多的办理方案，至少有 三种 不同的方法可以办理这个题目。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法办理这个题目吗？
  1. public class rotateArray {
  3.     public void rotate(int[] nums, int k) {
  4.         k = k%nums.length;
  5.         int[] nums1 = new int[nums.length];
  6.         for(int i = 0; i < nums.length; i++){
  7.             nums1[(i+k)%nums.length] = nums[i];
  8.         }
  9.         for(int i = 0; i < nums.length; i++){
  10.             System.out.println(nums1[i]);
  11.         }
  12.     }
  14.     public void reverse(int[] nums, int start, int end) {
  15.         while(start < end){
  16.             int tmp = nums[start];
  17.             nums[start] = nums[end];
  18.             nums[end] = tmp;
  19.             start++;
  20.             end--;
  21.         }
  22.     }
  24.     public void rotate2(int[] nums, int k) {
  25.         k = k%nums.length;
  26.         reverse(nums, 0, nums.length-1);
  27.         reverse(nums, 0, k-1);
  28.         reverse(nums, k, nums.length-1);
  30.         for(int i = nums.length-1; i >= 0; i--){
  31.             System.out.print(nums[i]+" ");
  32.         }
  33.     }
  35.     public static void main(String[] args) {
  36.         int[] nums = {1,2,3,4,5,6,7};
  37.         rotateArray rotateArray = new rotateArray();
  38.         rotateArray.rotate2(nums, 3);
  39.     }
  41. }
复制代码
121. 交易股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices 表现一支给定股票第 i 天的代价。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。计划一个算法来盘算你所能获取的最大利润。
返回你可以从这笔生意业务中获取的最大利润。假如你不能获取任何利润，返回 0 。
示例 1：
  1. 输入：[7,1,5,3,6,4]
  2. 输出：5
  3. 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
复制代码
示例 2：
  1. 输入：prices = [7,6,4,3,1]
  2. 输出：0
  3. 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
复制代码
提示：


  • 1 <= prices.length <= 105
  • 0 <= prices <= 104
  1. public class buy {
  3.     public int maxProfit(int[] prices) {
  4.         int res = Integer.MIN_VALUE;
  5.         int min = Integer.MAX_VALUE;
  6.         for(int i = 0; i< prices.length; i++){
  7.             min = Math.min(min,prices[i]);
  8.             res = Math.max(res,prices[i]-min);
  9.         }
  10.         return res;
  11.     }
  13.     public static void main(String[] args) {
  14.         int[] nums = new int[]{7,1,5,3,6,4};
  15.         buy b1 = new buy();
  16.         int maxProfit = b1.maxProfit(nums);
  17.         System.out.println(maxProfit);
  18.     }
  20. }
复制代码
122. 交易股票的最佳时机 II

给你一个整数数组 prices ，此中 prices 表现某支股票第 i 天的代价。
在每一天，你可以决定是否购买和/或出售股票。你在任何时间 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
  1. 输入：prices = [7,1,5,3,6,4]
  2. 输出：7
  3. 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
  4. 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
  5. 最大总利润为 4 + 3 = 7 。
复制代码
示例 2：
  1. 输入：prices = [1,2,3,4,5]
  2. 输出：4
  3. 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
  4. 最大总利润为 4 。
复制代码
示例 3：
  1. 输入：prices = [7,6,4,3,1]
  2. 输出：0
  3. 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
复制代码
提示：


  • 1 <= prices.length <= 3 * 104
  • 0 <= prices <= 104
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int res = 0;
  4.         for(int i=1;i<prices.length;i++){
  5.             if(prices[i]-prices[i-1]>0){
  6.                 res += prices[i]-prices[i-1];
  7.             }
  8.         }
  9.         return res;
  10.     }
  11. }
复制代码
55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否可以或许到达最后一个下标，假如可以，返回 true ；否则，返回 false 。
示例 1：
  1. 输入：nums = [2,3,1,1,4]
  2. 输出：true
  3. 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
复制代码
示例 2：
  1. 输入：nums = [3,2,1,0,4]
  2. 输出：false
  3. 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
复制代码
提示：


  • 1 <= nums.length <= 104
  • 0 <= nums <= 105
  1. public class Jump {
  3.     public boolean canJump(int[] nums) {
  4.         int len = nums.length;
  5.         int now = 0;
  6.         for(int i = 0; i < len; i++) {
  7.             // 目前可以到达的最远的地方
  8.             if(nums[i] == 0 && now == i){
  9.                 break;
  10.             }
  11.             now = Math.max(now,i+nums[i]);
  12.         }
  13.         now++;
  14.         if(now < len) return false;
  16.         return true;
  17.     }
  19.     public static void main(String[] args) {
  20.         int[] nums = {3,2,1,0,4};
  21.         System.out.println(new Jump().canJump(nums));
  22.     }
  24. }
复制代码
45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums 表现从索引 i 向前跳转的最大长度。换句话说，假如你在 nums 处，你可以跳转到恣意 nums[i + j] 处:


  • 0 <= j <= nums
  • i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
  1. 输入: nums = [2,3,1,1,4]
  2. 输出: 2
  3. 解释: 跳到最后一个位置的最小跳跃数是 2。
  4.      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
复制代码
示例 2:
  1. 输入: nums = [2,3,0,1,4]
  2. 输出: 2
复制代码
提示:


  • 1 <= nums.length <= 104
  • 0 <= nums <= 1000
  • 标题保证可以到达 nums[n-1]
  1. public class JumpGame {
  3.     public int jump(int[] nums) {
  4.         int len = nums.length-1;
  5.         int maxDistance = 0;
  6.         int end = 0;
  7.         int res = 0;
  8.         for(int i = 0 ; i < len ; i++){
  9.             maxDistance = Math.max(maxDistance,i+nums[i]);
  10.             if(i == end){
  11.                 end = maxDistance;
  12.                 res++;
  13.             }
  14.         }
  15.         return res;
  16.     }
  18.     public static void main(String[] args) {
  20.         int[] nums = new int[]{2,3,1,1,4};
  21.         JumpGame jumpGame = new JumpGame();
  22.         System.out.println(jumpGame.jump(nums));
  23.     }
  25. }
复制代码
274. H 指数

给你一个整数数组 citations ，此中 citations 表现研究者的第 i 篇论文被引用的次数。盘算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研职员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。假如 h 有多种可能的值，h 指数 是此中最大的那个。
示例 1：
  1. 输入：citations = [3,0,6,1,5]
  2. 输出：3
  3. 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
  4.      由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
复制代码
示例 2：
  1. 输入：citations = [1,3,1]
  2. 输出：1
复制代码
提示：


  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations <= 1000
  1. class Solution {
  2.     public int hIndex(int[] citations) {
  3.         Arrays.sort(citations);
  4.         int h = 0;
  5.         int pos = citations.length -1;
  6.         while(pos>=0 && citations[pos] > h){
  7.             h++;
  8.             pos--;
  9.         }
  10.         return h;
  11.     }
  12. }
复制代码
238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，此中 answer 等于 nums 中除 nums 之外其余各元素的乘积 。
标题数据 保证 数组 nums之中恣意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。
示例 1:
  1. 输入: nums = [1,2,3,4]
  2. 输出: [24,12,8,6]
复制代码
示例 2:
  1. 输入: nums = [-1,1,0,-3,3]
  2. 输出: [0,0,9,0,0]
复制代码
提示：


  • 2 <= nums.length <= 105
  • -30 <= nums <= 30
  • 保证 数组 nums之中恣意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个标题吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
  1. public class productExceptSelf {
  3.     public int[] productExceptSelf(int[] nums){
  4.         // 计算Left
  5.         int[] Left = new int[nums.length];
  6.         Left[0] = 1;
  7.         for (int i = 1; i < nums.length; i++){
  8.             Left[i] = Left[i-1]*nums[i-1];
  9.         }
  11.         int[] Right = new int[nums.length];
  12.         Right[nums.length-1] = 1;
  13.         for(int i = nums.length-2; i >= 0; i--){
  14.             Right[i] = Right[i+1]*nums[i+1];
  15.         }
  17.         for(int i = 0;i<nums.length;i++){
  18.             nums[i] = Left[i]*Right[i];
  19.         }
  20.         return nums;
  21.     }
  24.     public static void main(String[] args) {
  25.         productExceptSelf p = new productExceptSelf();
  26.         int[] nums = new int[]{4,5,1,8,2};
  27.         int[] res = p.productExceptSelf(nums);
  28.         for (int i=0;i<res.length;i++){
  29.             System.out.print(res[i]+" ");
  30.         }
  31.     }
  33. }
复制代码
134. 加油站

在一条环路上有 n 个加油站，此中第 i 个加油站有汽油 gas 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost 升。你从此中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，假如你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。假如存在解，则 保证 它是 唯一 的。
示例 1:
  1. 输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
  2. 输出: 3
  3. 解释:
  4. 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
  5. 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
  6. 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
  7. 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
  8. 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
  9. 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
  10. 因此，3 可为起始索引。
复制代码
示例 2:
  1. 输入: gas = [2,3,4], cost = [3,4,3]
  2. 输出: -1
  3. 解释:
  4. 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
  5. 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
  6. 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
  7. 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
  8. 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
  9. 因此，无论怎样，你都不可能绕环路行驶一周。
复制代码
  1. public class GasStation {
  2.     public int canCompleteCircuit(int[] gas, int[] cost) {
  3.         int total = 0;
  4.         int pos = 0;
  5.         int tank = 0;
  6.         for(int i=0;i<gas.length;i++){
  7.             total += gas[i] - cost[i];
  8.             tank += gas[i] - cost[i];
  9.             if(tank <= 0){
  10.                 pos = i+1;
  11.                 tank = 0;
  12.             }
  13.         }
  14.         return total < 0 ? -1 : pos;
  15.     }
  17.     // 测试用例
  18.     public static void main(String[] args) {
  19.         GasStation solution = new GasStation();
  21.         // 示例 1
  22.         int[] gas1 = {3,1,1};
  23.         int[] cost1 = {1,2,2};
  24.         System.out.println("起始站点: " + solution.canCompleteCircuit(gas1, cost1));
  25.     }
  26. }
复制代码
135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表现每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：


  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，盘算并返回需要准备的 最少糖果数目 。
示例 1：
  1. 输入：ratings = [1,0,2]
  2. 输出：5
  3. 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
复制代码
示例 2：
  1. 输入：ratings = [1,2,2]
  2. 输出：4
  3. 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
  4.      第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
复制代码
提示：


  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings <= 2 * 104
  1. public class CandyDistribution {
  2.     public static int candy(int[] ratings) {
  3.         int[] candy = new int[ratings.length];
  4.         int res = 0;
  5.         for (int i = 0; i < ratings.length; i++) {
  6.             candy[i] = 1;
  7.         }
  9.         // 从左到右遍历
  10.         for(int i = 1;i < candy.length; i++){
  11.             if(ratings[i]>ratings[i-1]){
  12.                 candy[i] = candy[i-1]+1;
  13.             }
  14.         }
  16.         // 从右到左遍历
  17.         for(int i = candy.length - 2; i >= 0; i--){
  18.             if(ratings[i]>ratings[i+1]){
  19.                 candy[i] = Math.max(candy[i],candy[i+1]+1);
  20.             }
  21.         }
  23.         for(int c : candy){
  24.             res += c;
  25.         }
  26.         return res;
  27.     }
  29.     public static void main(String[] args) {
  30.         // 示例 1
  31.         int[] ratings1 = {1, 0, 2};
  32.         System.out.println("最少糖果数: " + candy(ratings1)); // 输出: 5
  33.     }
  34. }
复制代码
42. 接雨水

给定 n 个非负整数表现每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水。
示例 1：
  1. 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出：6
  3. 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
复制代码
示例 2：
  1. 输入：height = [4,2,0,3,2,5]
  2. 输出：9
复制代码
提示：


  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height <= 105
题解1：
  1. public class trap {
  3.     public int trap_01(int[] height) {
  4.         int len = height.length;
  5.         int[] pre = new int[len];
  6.         pre[0] = height[0];
  7.         int[] suf = new int[len];
  8.         suf[len-1] = height[len-1];
  9.         // 计算左前缀
  10.         for(int i = 1; i < height.length; i++) {
  11.             pre[i] = Math.max(pre[i-1], height[i]);
  12.         }
  13.         // 计算右前缀
  14.         for(int i = len-2; i >= 0; i--) {
  15.             suf[i] = Math.max(suf[i+1], height[i]);
  16.         }
  18.         // 统计
  19.         int res = 0;
  20.         for(int i=0;i<height.length;i++){
  21.             if(pre[i] < suf[i]){
  22.                 res += pre[i] - height[i];
  23.             }else{
  24.                 res += suf[i] - height[i];
  25.             }
  26.         }
  27.         return res;
  28.     }
  30.     public static void main(String[] args) {
  31.         trap t = new trap();
  32.         int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  33.         System.out.println(t.trap_01(height));
  34.     }
  36. }
复制代码
优化版本，一次遍历：
  1. public class trap {
  2.     public int trap_02(int[] height){
  3.         // 双指针
  4.         int left = 0,right = height.length-1;
  5.         int res = 0;
  6.         int leftMax = height[0];
  7.         int rightMax = height[height.length-1];
  8.         while(left < right){
  9.             // 更新leftMax和rightMax的值
  10.             leftMax = Math.max(leftMax, height[left]);
  11.             rightMax = Math.max(rightMax, height[right]);
  12.             if(leftMax < rightMax){
  13.                 res += leftMax - height[left];
  14.                 left++;
  15.             }else{
  16.                 res += rightMax - height[right];
  17.                 right--;
  18.             }
  19.         }
  20.         return res;
  21.     }
  23.     public static void main(String[] args) {
  24.         trap t = new trap();
  25.         int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  26.         System.out.println(t.trap_02(height));
  27.     }
  29. }
复制代码
151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**留意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包罗任何额外的空格。
示例 1：
  1. 输入：s = "the sky is blue"
  2. 输出："blue is sky the"
复制代码
示例 2：
  1. 输入：s = "  hello world  "
  2. 输出："world hello"
  3. 解释：反转后的字符串中不能存在前导空格和尾随空格。
复制代码
示例 3：
  1. 输入：s = "a good   example"
  2. 输出："example good a"
  3. 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
复制代码
提示：


  • 1 <= s.length <= 104
  • s 包罗英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词
**进阶：**假如字符串在你使用的编程语言中是一种可变数据类型，请实验使用 O(1) 额外空间复杂度的 原地 解法。
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  4. public class reverseWords {
  7.     public String reverseWords(String s) {
  8.         String[] split = s.trim().split(" ");
  9.         String[] filter = Arrays.stream(split)
  10.                 .filter(e -> !e.isEmpty())
  11.                 .toArray(String[]::new);
  12.         int left = 0;
  13.         int right = filter.length - 1;
  14.         while (left < filter.length/2) {
  15.             String tmp = filter[right];
  16.             filter[right] = filter[left];
  17.             filter[left] = tmp;
  18.             left++;
  19.             right--;
  20.         }
  21.         return String.join(" ", filter);
  22.     }
  25.     public static void main(String[] args) {
  26.         reverseWords r = new reverseWords();
  27.         System.out.println(r.reverseWords("a good   example"));
  28.     }
  30. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4