赞
踩
代码随想录的Java算法学习笔记
数组是存放在连续内存空间上的相同类型数据的集合。
数组下标都是从0开始的,数组的元素是不能删的,只能覆盖
前提是数组为有序数组且数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的
//测试 public class test01 { public static void main(String[] args) { int[] arr = {1, 4, 7, 9, 14, 17, 25, 29}; int target = 1; int result = search(arr, target) + 1; if (result == 0) { System.out.println("数组中不包含这个数字"); } else { System.out.println("查找的数字在数组中的位置为第" + result + "位"); } } // 二分查找,左闭右开区间 public static int search(int[] nums, int target) { //定义左右边界 int left = 0, right = nums.length; while (left < right) { // 计算中间元素的索引 int mid = (left + right)/2; if (nums[mid] == target) return mid; else if (nums[mid] < target) // target在右半部分,更新左边界 left = mid + 1; else if (nums[mid] > target) // target在左半部分,更新右边界 right = mid; } // 没有找到目标值,返回-1 return -1; } } /* 时间复杂度:O(log n) 空间复杂度:O(1) */
//测试 public class test02 { public static void main(String[] args) { /* 给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 你不需要考虑数组中超出新长度后面的元素。*/ int[] arr = {3, 2, 2, 3}; int val = 3; System.out.println(removeElement(arr, val)); } // 快慢指针 public static int removeElement(int[] nums, int val) { // 定义一个慢指针 slowindex,并初始化为 0 int slowindex = 0; // 遍历数组 nums,i即为快指针 for (int i = 0; i < nums.length; i++) { // 如果当前元素不等于 val if (nums[i] != val) { // 将当前元素赋值给慢指针位置的元素 nums[slowindex] = nums[i]; // 慢指针向后移动一位 slowindex++; } } // 返回慢指针的值作为新的数组长度 return slowindex; } } /* 时间复杂度:O(n) 空间复杂度:O(1) */
//测试 public class test03 { public static void main(String[] args) { /* * 给你一个按非递减顺序排序的整数数组 nums, * 返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 * * 示例 1: * 输入:nums = [-4,-1,0,3,10] * 输出:[0,1,9,16,100] * 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100] * * 示例 2: * 输入:nums = [-7,-3,2,3,11] * 输出:[4,9,9,49,121] */ int[] nums = {-4, -1, 2, 3, 10}; int[] arr = sortedSquares(nums); //强化for循环遍历数组 for (int num : arr) { System.out.println(num); } } //双指针法 /* 数组其实是有序的, 只不过负数平方之后可能成为最大数了。 那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。 此时可以考虑双指针法了,i指向起始位置,j指向终止位置。 定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。 如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; */ public static int[] sortedSquares(int[] nums) { //定义左指针 l,并初始化为 0 int l = 0; //定义右指针 r,并初始化为数组长度减 1 int r = nums.length - 1; //定义结果数组res,长度与nums相同 int[] res = new int[nums.length]; //定义结果数组的索引 j,并初始化为数组长度减 1 int j = nums.length - 1; // 当左指针小于等于右指针时循环 while (l <= r) { //如果左指针指向的元素平方大于右指针指向的元素平方 if (nums[l] * nums[l] > nums[r] * nums[r]) { //将左指针指向的元素平方赋值给结果数组的当前位置,并将左指针向右移动一位 //j--就是先使用j的数值再将j减小一位 res[j--] = nums[l] * nums[l++]; } else { //将右指针指向的元素平方赋值给结果数组的当前位置,并将右指针向左移动一位 res[j--] = nums[r] * nums[r--]; } } //返回结果数组 return res; } } /* 时间复杂度:O(n) */
滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
//测试 public class test04 { public static void main(String[] args) { /* 给定一个含有 n 个正整数的数组和一个正整数 s, 找出该数组中满足其和 ≥ s 的长度最小的连续子数组, 并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。 */ int s = 7; int[] nums = {2, 3, 1, 2, 4, 3}; System.out.println(minSubArrayLen(s, nums)); } // 滑动窗口 public static int minSubArrayLen(int s, int[] nums) { //定义左指针 left,并初始化为 0 int left = 0; //定义和sum,并初始化为 0 int sum = 0; //定义结果 result,并初始化为整数的最大值 int result = Integer.MAX_VALUE; // 遍历数组 nums,右指针 right 从 0 到 nums.length-1 for (int right = 0; right < nums.length; right++) { //将右指针指向的元素加到和 sum 中 //sum += nums[right];等同于sum =sum+ nums[right]; sum += nums[right]; //当和sum大于等于s时循环 while (sum >= s) { //更新结果 result,取当前子数组长度与 result 的较小值 result = Math.min(result, right - left + 1); // 将左指针指向的元素从和sum中减去,并将左指针向右移动一位 sum -= nums[left++]; } } //如果结果 result 仍为整数的最大值,则返回 0,否则返回 result return result == Integer.MAX_VALUE ? 0 : result; } } /* 时间复杂度:O(n) 空间复杂度:O(1) */
模拟顺时针画矩阵的过程:
坚持每条边左闭右开的原则
//测试 public class test05 { public static void main(String[] args) { /* 给定一个正整数 n,生成一个包含 1 到 n^2 所有元素, 且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] */ int[][] arrs = generateMatrix(4); for (int i = 0; i < arrs.length; i++) { for (int j = 0; j < arrs.length; j++) { System.out.print(arrs[i][j]+" "); } System.out.println(); } } public static int[][] generateMatrix(int n) { // 控制循环次数 int loop = 0; int[][] res = new int[n][n]; // 每次循环的开始点(start, start) int start = 0; // 定义填充数字 int count = 1; int i, j; //判断边界后,loop从1开始 //此处loop先进行比较再自增 while (loop++ < n / 2) { // 模拟上侧从左到右 for (j = start; j < n - loop; j++) { res[start][j] = count++; } // 模拟右侧从上到下 for (i = start; i < n - loop; i++) { res[i][j] = count++; } // 模拟下侧从右到左 for (; j >= loop; j--) { res[i][j] = count++; } // 模拟左侧从下到上 for (; i >= loop; i--) { res[i][j] = count++; } start++; } if (n % 2 == 1) { res[start][start] = count; } return res; } } /* 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间 空间复杂度 O(1) */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。