*二分查找
题目链接
https://leetcode.cn/problems/binary-search/
左闭右闭区间实现
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
/** * 左闭右闭写法 * * @param nums * @param target * @return */ public static int search1(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; int right = nums.length - 1; // 要是没有等号的话，在{5}里面找5就会出问题了 while (left <= right) { int center = (left + right) / 2; if (target == nums[center]) { return center; } else if (target > nums[center]) { left = center + 1; } else { right = center - 1; } } return -1; }
左闭右开区间实现
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
/** * 左闭右开写法 * * @param nums * @param target * @return */ public static int search2(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; // 区别点 int right = nums.length; // 区别点 while (left < right) { int center = (left + right) / 2; if (target == nums[center]) { return center; } else if (target > nums[center]) { left = center + 1; } else { // 区别点 // 虽然已经知道center位置的元素不是要找的元素，但是因为是左闭右开，因此right还是指向center // 后面无论怎么循环，都不会再使用到center这个为止，因为center = (left + right) / 2永远小于right right = center; } } return -1; }
*移除元素
题目链接
https://leetcode.cn/problems/remove-element/
暴力求解
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
public static int removeElement(int[] nums, int val) { int sameNum = 0; int i = 0; while (i < nums.length - sameNum) { if (val == nums[i]) { // 将后面的元素前移过来 for (int j = i; j < nums.length - 1 - sameNum; j++) { nums[j] = nums[j + 1]; } sameNum++; } if (val == nums[i]) { // 前移过来的数值和val一样，将i-- i--; } i++; } return nums.length - sameNum; }
双指针
- 时间复杂度：O(n)
- 空间复杂度：O(1)
【思想】
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，将快指针的值赋给慢指针
slow：新数组存储值的索引，因为每次存储完新数组的值，都会将slow++，因此最后直接返回slow即可，需要返回slow+1
fast：用来去前面探索那些不是val的值，然后将这个值赋给slow对应的位置
/** * 双指针 * * @param nums * @param val * @return */ public static int removeElement1(int[] nums, int val) { int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != val) { // 如果快指针找的数值不是val，就需要将其存储到新数组中 // 同时slow++，以便存储下一个新数组的值 nums[slow++] = nums[fast]; } } return slow; }
相向双指针法
- 时间复杂度：O(n)
- 空间复杂度：O(1)
上面的实现方法并没有改变元素的相对位置，相向双指针方法改变了元素相对位置，但是确保移动最少元素
/** * 想向双指针 * * @param nums * @param val * @return */ public static int removeElement(int[] nums, int val) { int slow = 0, fast = nums.length - 1; while (slow <= fast) { // slow赋值为第一个等于val的索引 while (slow <= fast) { if (nums[slow] != val) { slow++; } else { break; } } // fast赋值为最后一个等于val的索引 while (fast >= slow) { if (nums[fast] == val) { fast--; } else { break; } } if (slow < fast) { nums[slow++] = nums[fast--]; } } // slow最后一定指向的是 新数组末尾元素的下一个元素 return slow; }
*有序数组的平方
题目链接
https://leetcode.cn/problems/squares-of-a-sorted-array/
暴力求解
- 先对数组的每个元素求平方
- 对数组升序排序
时间复杂度：O(n)+排序算法的时间复杂度
双指针
【思路】
数组本身就是非递减顺序的，只不过负数在平方之后可能会变大，因此只需要用两端来比较就能知道那个数字的平方更大
- 时间复杂度：O(n)
- 空间复杂度：O(n)
public static int[] sortedSquares(int[] nums) { int left = 0, right = nums.length - 1; // 用于存储排序之后的结果 int[] result = new int[nums.length]; for (int i = nums.length - 1; i >= 0; i--) { int leftValue = nums[left]; int rightValue = nums[right]; if (leftValue * leftValue >= rightValue * rightValue) { result[i] = leftValue * leftValue; left++; } else { result[i] = rightValue * rightValue; right--; } System.out.println(Arrays.toString(result)); } return result; }
*长度最小的子数组
题目链接
https://leetcode.cn/problems/minimum-size-subarray-sum/
暴力求解
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
注意，子数组是原数组中连续的几个元素的集合
public int minSubArrayLen(int target, int[] nums) { // 最小子数组长度 int minLen = nums.length + 1; for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; if (sum >= target) { // 已经>=target，可以暂停了 if ((j - i + 1) < minLen) { minLen = j - i + 1; break; } } } } return minLen == nums.length + 1 ? 0 : minLen; }
部分案例已经超出时间限制
滑动窗口
- 时间复杂度：O(n)：不能以为for里放一个while就是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
- 空间复杂度：O(1)
/** * 滑动窗口 * * @param target * @param nums * @return */ public int minSubArrayLen1(int target, int[] nums) { // 最小子数组长度 int minLen = nums.length + 1; int i = 0; int sum = 0; for (int j = 0; j < nums.length; j++) { // j++，窗口终止位置后移一位，sum添加相应的元素 sum += nums[j]; while (sum >= target) { // 窗口内的元素总和已经超过target，尝试将窗口的起始位置后移，即i++ if ((j - i + 1) < minLen) { minLen = j - i + 1; } // sum移除窗口起始位置的元素值 sum -= nums[i++]; } } return minLen == nums.length + 1 ? 0 : minLen; }
螺旋矩阵
【思想】
这道题主要是考代码能力，注意每次循环都是左开右闭就行
【我写的程序】
public static int[][] generateMatrix1(int n) { int[][] result = new int[n][n]; int curNum = 1; int target = n * n; int initN = n; // 圈数 int cirCleNum = 0; while (curNum <= target) { if (curNum == target) { result[cirCleNum][cirCleNum] = curNum; System.out.println("---------------------填中心---------------------"); for (int i = 0; i < result.length; i++) { System.out.println(Arrays.toString(result[i])); } break; } // 填上边 for (int i = 0; i < n - 1; i++) { result[cirCleNum][i + cirCleNum] = curNum++; } System.out.println("---------------------填上边---------------------"); for (int i = 0; i < result.length; i++) { System.out.println(Arrays.toString(result[i])); } // 填右边 for (int i = 0; i < n - 1; i++) { result[i + cirCleNum][initN - 1 - cirCleNum] = curNum++; } System.out.println("---------------------填右边---------------------"); for (int i = 0; i < result.length; i++) { System.out.println(Arrays.toString(result[i])); } // 填下边 for (int i = n - 1; i > 0; i--) { result[initN - 1 - cirCleNum][i + cirCleNum] = curNum++; } System.out.println("---------------------填下边---------------------"); for (int i = 0; i < result.length; i++) { System.out.println(Arrays.toString(result[i])); } // 填左边 for (int i = n - 1; i > 0; i--) { result[i + cirCleNum][cirCleNum] = curNum++; } System.out.println("---------------------填左边---------------------"); for (int i = 0; i < result.length; i++) { System.out.println(Arrays.toString(result[i])); } System.out.println("======================================================================"); cirCleNum += 1; n -= 2; } return result; }
【别人的代码】
public int[][] generateMatrix(int n) { int loop = 0; // 控制循环次数 int[][] res = new int[n][n]; int start = 0; // 每次循环的开始点(start, start) int count = 1; // 定义填充数字 int i, j; while (loop++ < n / 2) { // 判断边界后，loop从1开始 // 模拟上侧从左到右 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; }
