首页 > 基础资料 博客日记
Java LeetCode篇-深入了解关于数组的经典解法
2023-12-22 21:29:41基础资料围观226次
🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
文章目录
1.0 轮转数组
题目：
给定一个整数数组
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]
1.1 使用移位的方式
先创建一个新的数组来记录需要进行右轮转的元素，然后将数组前面剩余的元素进行遍历 "移" 到后面，即覆盖。如例题1：先将 [5,6,7] 这 k 个元素使用新的数组来暂时存放，接着将 [1,2,3,4] 从后往前遍历，即将 4 移到原来 7 的位置，3 移到 原来 6 的位置，2 移到原来 5 的位置......即 nums[nums.length - i ] = nums[ nums.length - k - i ] ，i 从 1 开始直到 i == nums.length - k 时，则结束循环。最后，将需要轮转的元素进行数组 temp[] 下标一个个对应赋值到 nums[] 数组中即可。
代码如下：
public static void rotate(int[] nums,int k) { if(nums.length == 1 || nums.length == 0) { return; } k %= nums.length; int[] temp = new int[k]; System.arraycopy(nums,nums.length - k, temp, 0,k); System.arraycopy(nums,0,nums,k,nums.length - k); for(int i = 0;i < temp.length ; i++) { nums[i] = temp[i]; } }这里使用了相关的 API ，总体上来说思路是一样的。一般来说，这种算法时间复杂度会较高。
1.2 使用三次数组逆转法
使用三次逆转法，让数组旋转k次
1. 整体逆置
2. 逆转子数组[0, k - 1]
3. 逆转子数组[k, size - 1]
代码如下：
public static void fun(int[] arr, int k) { k %= arr.length; rotate(arr,0,arr.length - 1); rotate(arr,0,k-1); rotate(arr,k, arr.length-1); } public static void rotate(int[] arr,int left, int right) { while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } }流程图如下：
2.0 消失的数字
题目：
数组
nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n) 时间内完成吗？示例 1：
输入：[3,0,1] 输出：2示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
2.1 使用相减法
定义 int sum ，然后遍历 0 到 n 的所有整数都加起来，接着再跟将 nums 的所以数字加起来进行比较，两者相减即可得出 nums 数组中 "消失的数字" 。如例题：numsSum = 3 + 0 + 1 , nSum = 0 + 1 + 2 + 3，再接着 nSum - numsSum == 2 ，两者相减即可得到消失的数字为: 2 。
代码如下：
public static int disappearing1(int[] arr) { int sum1 = 0; int sum2 = 0; for (int i = 0; i < arr.length; i++) { sum1 += i; sum2 += arr[i]; } return (sum1 += arr.length) - sum2; }缺陷：如果数组中元素比较多，相加完成之后容易溢出。
2.2 使用异或的方式
采用异或的方式解决，因为两个相同的数字异或的结果是 0，因此：将 0~N 之间的数字，与数组中的每个数字异或，最终的结果就是丢失的数字。
代码如下：
public static int disappearing(int[] arr) { int data = 0; for (int i = 0; i < arr.length; i++) { data ^= arr[i]; data ^= i; } data ^= arr.length; return data; }分析：可以将将其理解为 “消消乐” ，即若两个数相同就抵消为 0 ，那么现在目前有两个袋子，一个袋子装满了 0 到 n 张卡片，其中每一种只有一片，也就是说，该袋子里面就有 n + 1 张卡片，在另一个袋子里面装有 0 到 n 张中缺少了一张卡片，即该袋子中有 n 张卡片，接着进行每一次将分别从两个袋子拿出不同的卡片进行对比，如果相同的话则抵消掉了，不相同的话，得保存起来。就这样一直对比下去，最终会发现留下来的就是另一个袋子所缺少的卡片了。
3.0 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组
nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你 合并
nums2到nums1中，使合并后的数组同样按 非递减顺序 排列。示例 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 中的元素。
3.1 使用三指针方式
定义三个指针分别为：i 指向 nums1 中的最后一个有效元素，j 指向 nums2 中最后一个有效元素，k 指向 nums1 中最后一个索引位置。接着 nums[i] 与 nums[j] 进行比较大小，得出较大的元素就放到 nums[k] 中，以此类推，直到 i < 0 或者 j < 0 时，则循环停止。最后来判断，若 i > 0 ，本来剩余的元素就在 nums1 中，则不用再继续下去了，任务结束了；若 j > 0 ，需要将 nums2 中的元素进行遍历拷贝到 nums1 中。
代码如下：
public void merge(int[] nums1, int m, int[] nums2, int n) { int k = nums1.length - 1; int i = m - 1; int j = n - 1; while(i >= 0 && j >= 0) { if(nums1[i] > nums2[j]) { nums1[k] = nums1[i]; k--; i--; }else if(nums1[i] <= nums2[j]) { nums1[k] = nums2[j]; k--; j--; } } if(j >= 0) { System.arraycopy(nums2,0,nums1,0,j+1); } }
3.2 使用合并排序方式
这个思路很简单，可以直接将 nums2 中的元素拷贝到 nums1 中，然后直接排序即可。这里就不过多赘述了。
4.0 删除有序数组中的重复项
题目：
给你一个 非严格递增排列 的数组
nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。示例 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。不需要考虑数组中超出新长度后面的元素。
4.1 使用双指针方式
先定义两个指针分别指向，一个指针： i = 0 ，一开始时指向数组中第一个元素；另一个指针：j = 1。分两种情况来解决，第一种情况是，当 nums[i] == nums[j] 时，继续让 j 走下去，直到 j == nums.length 时，则结束循环；第二种情况是，当 nums[i] != nums[j] 时，让 nums[i + 1] = nums[j] ，i++，j++ ，同样直到 j == nums.length 时，则结束循环。最后返回 i+1 即可。
代码如下：
public int removeDuplicates(int[] nums) { int i = 0; int j = i + 1; while (j < nums.length) { if (nums[i] == nums[j]) { j++; } else if (nums[i] != nums[j]) { nums[i+1] = nums[j]; i++; j++; } } return i + 1; }
5.0 移除元素
题目：
给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用
O(1)额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,3,0,4] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
5.1 使用双指针方式
先定义两个指针，对于 left 这个指针来说，一开始指向数组下标为 0 ；对于 right 这个指针来说，一开始指向数组下标也为 0 处，然后 rigth 一直 right++ 自加，在这个过程中，需要先判断，若 nums[right] != val 时，则需要将这个值拷贝到 nums[left] 中 ，left++ ，right++ ;若 nums[right] == val 时，right++ 即可，直到 right == nums.length 时，则结束循环。
代码如下：
public int removeElement(int[] nums, int val) { int n = nums.length; int left = 0; for (int i = 0; i < n; i++) { if (nums[i] != val) { nums[left] = nums[i]; left++; } } return left; }
6.0 杨辉三角
题目：
给定一个非负整数
numRows，生成「杨辉三角」的前numRows行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows = 1 输出: [[1]]
6.1 使用二维数组的方式
可以把这个问题看成是一个二维数组，外层循环为 k 行数(层数)，内层为 l 列数。当 l == 0 或者 k == l 时，该二维数组中存放的是 1 ；其他情况则为当前的数值为：上一层行数同一列的 data1 + 上一层行数少一列的 data2 。
代码如下：
public List<List<Integer>> generate(int numRows) { List<List<Integer>> i = new ArrayList<>(); for (int k = 0; k < numRows; k++) { List<Integer> j = new ArrayList<>(); for (int l = 0; l <= k ; l++) { if ( l == 0 || k == l) { j.add(1); } else { j.add(i.get(k-1).get(l) + i.get(k-1).get(l-1)); } } i.add(j); } return i; }需要注意的是，实现集合来实现，而不是数组。
需要了解相关集合的内容可以点击该链接：进阶JAVA篇-深入了解 List 系列集合-CSDN博客
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
上一篇：运算符--原码、反码、补码
下一篇：教你用Java编写一个简单的小游戏
相关文章
最新发布
点击排行
本站推荐
