Java快速开发学习

锁清秋

leetcode-数组

概要：需要了解一下知识：

  • 排序:选择排序;插入排序;归并排序;快速排序
  • 查找:二分查找法
  • 数据结构:栈;队列;堆

一、二分法查找

  2.     private int sort(int key, int[] target, int left, int right) {
  3.         if (left > right)
  4.             return -1;
  5.         int mid = (left + right) / 2;
  6.         if (key < target[mid])
  7.             return sort(key, target, left, mid - 1);
  8.         if (key > target[mid])
  9.             return sort(key, target, mid + 1, right);
  10.         else
  11.             return mid;
  12.     }

2. 移动零

  2. 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 
  4.  示例: 
  6. 输入: [0,1,0,3,12]
  7. 输出: [1,3,12,0,0] 
  9.  说明: 
  12.  必须在原数组上操作，不能拷贝额外的数组。 
  13.  尽量减少操作次数。 
  15.  Related Topics 数组 双指针
  1.         public void moveZeroes(int[] nums) {
  2.             /**
  3.              * 存放非零元素的前驱指针，
  4.              *     即：
  5.              *         在[0,pre)前闭后开区间存放的都是非零元素
  6.              *         在[pre,...]前闭后开区间存放的都是零元素
  7.              */
  8.             int pre = 0;
  9.             /**
  10.              * 移动指针
  11.              */
  12.             int cur = 0;
  13.             while (cur < nums.length) {
  14.                 if (nums[cur] != 0) {
  15.                     if (pre != cur)//只有指针不相等的时候才进行交换，要不然每次相同位置也都进行交换
  16.                         //元素交换
  17.                         LeetCodeUtils.swap(nums, pre, cur);
  18.                     pre++;
  19.                 }
  20.                 cur++;
  21.             }
  22.         }

3. 移除元素

  1. 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 
  3.  不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 
  5.  元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 
  9.  示例 1: 
  11.  给定 nums = [3,2,2,3], val = 3,
  13. 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
  15. 你不需要考虑数组中超出新长度后面的元素。
  18.  示例 2: 
  20.  给定 nums = [0,1,2,2,3,0,4,2], val = 2,
  22. 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
  24. 注意这五个元素可为任意顺序。
  26. 你不需要考虑数组中超出新长度后面的元素。
  31.  说明: 
  33.  为什么返回数值是整数，但输出的答案是数组呢? 
  35.  请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
  37.  你可以想象内部操作如下: 
  39.  // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
  40. int len = removeElement(nums, val);
  42. // 在函数里修改输入数组对于调用者是可见的。
  43. // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  44. for (int i = 0; i < len; i++) {
  45.     print(nums[i]);
  46. }
  48.  Related Topics 数组 双指针
  2.     public int removeElement(int[] nums, int val) {
  3.         int pre = 0;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             if (nums[i]!=val)
  6.                 nums[pre++] = nums[i];
  7.         }
  8.         return pre;
  9.     }

4. 删除排序数组中的重复项

  2. 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 
  4.  不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 
  8.  示例 1: 
  10.  给定数组 nums = [1,1,2], 
  12. 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
  14. 你不需要考虑数组中超出新长度后面的元素。 
  16.  示例 2: 
  18.  给定 nums = [0,0,1,1,1,2,2,3,3,4],
  20. 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
  22. 你不需要考虑数组中超出新长度后面的元素。
  27.  说明: 
  29.  为什么返回数值是整数，但输出的答案是数组呢? 
  31.  请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
  33.  你可以想象内部操作如下: 
  35.  // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  36. int len = removeDuplicates(nums);
  38. // 在函数里修改输入数组对于调用者是可见的。
  39. // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
  40. for (int i = 0; i < len; i++) {
  41.     print(nums[i]);
  42. }
  44.  Related Topics 数组 双指针
  2.         public int removeDuplicates(int[] nums) {
  3.             /**
  4.              * 前 [0,pre) 个全为不重复元素
  5.              */
  6.             int pre = 0;
  7.             for (int i = 0; i < nums.length; i++) {
  8.                 if (nums[pre] < nums[i])
  9.                     nums[++pre] = nums[i];
  10.             }
  11.             return pre + 1;
  12.         }

5. 删除排序数组中的重复项 II

  1. 给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 
  3.  不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 
  7.  说明： 
  9.  为什么返回数值是整数，但输出的答案是数组呢？ 
  11.  请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 
  13.  你可以想象内部操作如下： 
  16. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  17. int len = removeDuplicates(nums);
  19. // 在函数里修改输入数组对于调用者是可见的。
  20. // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
  21. for (int i = 0; i < len; i++) {
  22.     print(nums[i]);
  23. } 
  27.  示例 1： 
  30. 输入：nums = [1,1,1,2,2,3]
  31. 输出：5, nums = [1,1,2,2,3]
  32. 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。
  35.  示例 2： 
  38. 输入：nums = [0,0,1,1,1,1,2,3,3]
  39. 输出：7, nums = [0,0,1,1,2,3,3]
  40. 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面
  41. 的元素。
  46.  提示： 
  49.  0 <= nums.length <= 3 * 104 
  50.  -104 <= nums[i] <= 104 
  51.  nums 按递增顺序排列 
  53.  Related Topics 数组 双指针
  2.         public int removeDuplicates(int[] nums) {
  3.             /**
  4.              * [0,pre) 范围是每个最多出现两次的元素
  5.              */
  6.             int pre = 0;
  7.             //标记是否为第一次相同
  8.             Boolean isFirst = true;
  9.             for (int i = 1; i < nums.length; i++) {
  10.                 /**
  11.                  * 第一次相同，将isFirst设置为false
  12.                  * 并放入 [0,pre)
  13.                  */
  14.                 if (nums[pre] == nums[i] && isFirst) {
  15.                     nums[++pre] = nums[i];
  16.                     isFirst = false;
  17.                 } else if (nums[pre] < nums[i]) {//不同，就也放入 [0,pre)，并将标记 isFirst设置为true
  18.                     nums[++pre] = nums[i];
  19.                     isFirst = true;
  20.                 }
  21.             }
  22.             return pre + 1;
  23.         }

6. 颜色分类

  1. 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
  3.  此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
  5.  注意: 
  6. 不能使用代码库中的排序函数来解决这道题。 
  8.  示例: 
  10.  输入: [2,0,2,1,1,0]
  11.  输出: [0,0,1,1,2,2] 
  13.  进阶： 
  16.  一个直观的解决方案是使用计数排序的两趟扫描算法。 
  17.  首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 
  18.  你能想出一个仅使用常数空间的一趟扫描算法吗？ 
  20.  Related Topics 排序 数组 双指针
  2.         public void sortColors(int[] nums) {
  3.             /**
  4.              * [0,left)存放0
  5.              */
  6.             int left = 0;
  7.             /**
  8.              * (right,nums.length]存放2
  9.              */
  10.             int right = nums.length - 1;
  11.             for (int i = 0; i <= right; ) {
  12.                 //首先判断当前元素是否为2，如果是
  13.                 //就将当前元素交换到末尾
  14.                 if (nums[i] == 2) {
  15.                     swap(nums, i, right--);
  16.                 }
  18.                 /**
  19.                  * 接下来的操作就类似于 “移动零”操作;只不过是将0移动到前面
  20.                  *     将0移动到前面，将1移动到后面
  21.                  *      即：当前元素是 1 的时候向前移动
  22.                  *          当前元素是 0 的时候，将当前元素
  23.                  */
  24.                 if (nums[i] == 1) {
  25.                     i++;
  26.                 } else if (nums[i] == 0) {
  27.                     swap(nums, left++, i++);
  28.                 }
  29.             }
  30.         }

7. 合并两个有序数组

  1. 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 
  5.  说明： 
  8.  初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 
  9.  你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 
  14.  示例： 
  17. 输入：
  18. nums1 = [1,2,3,0,0,0], m = 3
  19. nums2 = [2,5,6],       n = 3
  21. 输出：[1,2,2,3,5,6] 
  25.  提示： 
  28.  -10^9 <= nums1[i], nums2[i] <= 10^9 
  29.  nums1.length == m + n 
  30.  nums2.length == n 
  32.  Related Topics 数组 双指针
  2.         public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.             //题目说nums1 有足够的空间（nums1.length == m + n）来保存 nums2 中的元素，相当于自带了一个空数组
  4.             int l = m - 1;//第一个元素元素指针
  5.             int r = n - 1;//第二个数组元素指针
  6.             int i = m + n - 1;
  7.             while (r >= 0 && l >= 0) {
  8.                 if (nums1[l] >= nums2[r]) {
  9.                     nums1[i] = nums1[l--];
  10.                 } else {
  11.                     nums1[i] = nums2[r--];
  12.                 }
  13.                 i--;
  14.             }
  15.             while (r >= 0) {
  16.                 nums1[i--] = nums2[r--];
  17.             }
  18.         }

8. 数组中的第K个最大元素

  1. 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
  3.  示例 1: 
  5.  输入: [3,2,1,5,6,4] 和 k = 2
  6. 输出: 5
  9.  示例 2: 
  11.  输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
  12. 输出: 4 
  14.  说明: 
  16.  你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 
  17.  Related Topics 堆 分治算法
  2.         public int findKthLargest(int[] nums, int k) {
  3.       //维护一个 k 大小的优先队列便可
  4.             PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
  5.             for (int num : nums) {
  6.                 if (heap.size() < k)
  7.                     heap.add(num);
  8.                 else if (heap.peek() < num) {
  9.                     heap.poll();
  10.                     heap.add(num);
  11.                 }
  12.             }
  13.             return heap.peek();
  14.         }

9. 两数之和 II - 输入有序数组

  1. 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 
  3.  函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 
  5.  说明: 
  8.  返回的下标值（index1 和 index2）不是从零开始的。 
  9.  你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 
  12.  示例: 
  14.  输入: numbers = [2, 7, 11, 15], target = 9
  15. 输出: [1,2]
  16. 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 
  17.  Related Topics 数组 双指针 二分查找
  2.         public int[] twoSum(int[] numbers, int target) {
  3.             HashMap<Integer, Integer> map = new HashMap<>();
  4.             for (int i = 0; i < numbers.length; i++) {
  5.                 if (map.containsKey(target - numbers[i]))
  6.                     return new int[]{map.get(target - numbers[i]) + 1, i + 1};
  7.                 else
  8.                     map.put(numbers[i], i);
  9.             }
  10.             return new int[]{};
  11.         }

10. 验证回文串

  1. 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 
  3.  说明：本题中，我们将空字符串定义为有效的回文串。 
  5.  示例 1: 
  7.  输入: "A man, a plan, a canal: Panama"
  8. 输出: true
  11.  示例 2: 
  13.  输入: "race a car"
  14. 输出: false
  16.  Related Topics 双指针 字符串

11. 反转字符串中的元音字母

  1. 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
  5.  示例 1：
  7.  输入："hello"
  8. 输出："holle"
  11.  示例 2：
  13.  输入："leetcode"
  14. 输出："leotcede"
  18.  提示：
  21.  元音字母不包含字母 "y" 。
  23.  Related Topics 双指针 字符串
  2.         public String reverseVowels(String s) {
  3.             if (s.length() <= 0)
  4.                 return "";
  5.             HashSet<Character> set = new HashSet<>(Arrays.asList('a', 'i', 'o', 'u', 'e', 'A', 'I', 'O', 'U', 'E'));
  6.             char[] c = s.toCharArray();
  7.             int l = 0, r = s.length() - 1;
  8.             while (l < r) {
  9.                 while (l < r && !set.contains(c[l])) {
  10.                     l++;
  11.                 }
  12.                 while (l < r && !set.contains(c[r])) {
  13.                     r--;
  14.                 }
  15.                 if (l < r) {
  16.                     char temp = c[l];
  17.                     c[l++] = c[r];
  18.                     c[r--] = temp;
  19.                 }
  20.             }
  21.             return new String(c);
  22.         }