1.二分查找

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import org.junit.Test;/*** Description: 704. 二分查找** @Author sun* @Create 2024/11/20 11:10* @Version 1.0*/
public class T1_2 {public static int search(int[] nums, int target) {// 初始化l，r左闭右闭的区间int l = 0, r = nums.length - 1;// 当满足要求时进行二分，需要加等号while (l <= r) {// 定中点，防止溢出，相当于（l + r）/ 2int mid = l + (r - l) / 2;if (target > nums[mid]) {l = mid + 1;} else if (target < nums[mid]) {r = mid - 1;} else {return mid;}}// 如果跳出循环了还没结果就返回-1return -1;}public static void main(String[] args) {int[] nums = {-1, 0, 3, 5, 9, 12};int target = 9;System.out.println(search(nums, target));}
}

2.思路

左闭右闭，while加等号

中点公式：int mid = l + (r - l) / 2;

3.扩展题目

1.搜索插入位置

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 35.搜索插入位置** @Author sun* @Create 2024/11/25 13:39* @Version 1.0*/
public class T1_2_1 {public static int searchInsert(int[] nums, int target) {// 先写出一个二分int l = 0, r = nums.length - 1;while (l <= r) {// 中点int mid = l + (r - l) / 2;if (target > nums[mid]) {l = mid + 1;} else if (target < nums[mid]) {r = mid - 1;} else {return mid;}}// 到这里就是没有找到了，返回应该插入的索引return l;}public static void main(String[] args) {int[] nums = {1, 3, 5, 6};int target = 2;System.out.println(searchInsert(nums, target));}
}

2.思路

在二分的基础上，如果找不到就返回l即可

2.在排序数组中查找元素的第一个和最后一个位置

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import java.util.Arrays;/*** Description: 34. 在排序数组中查找元素的第一个和最后一个位置** @Author sun* @Create 2024/11/25 13:54* @Version 1.0*/
public class T1_2_2 {public static int[] searchRange(int[] nums, int target) {// 判空if (nums == null || nums.length == 0) {return new int[]{-1, -1};}int first = findFirst(nums, target);int last = findLast(nums, target);return new int[]{first, last};}private static int findFirst(int[] nums, int target) {int l = 0, r = nums.length - 1;while (l <= r) {int mid = l + (r - l) / 2;if (target <= nums[mid]) {r = mid - 1;} else {l = mid + 1;}}// 防止越界if (!(l >= 0 && l <= nums.length - 1)) {return -1;}return nums[l] == target ? l : -1;}private static int findLast(int[] nums, int target) {int l = 0, r = nums.length - 1;while (l <= r) {int mid = l + (r - l) / 2;if (target >= nums[mid]) {l = mid + 1;} else {r = mid - 1;}}// 防止越界if (!(r >= 0 && r <= nums.length - 1)) {return -1;}return nums[r] == target ? r : -1;}public static void main(String[] args) {int[] nums = {5, 7, 7, 8, 8, 10};int target = 8;int[] ints = searchRange(nums, target);System.out.println("ints = " + Arrays.toString(ints));}
}

2.思路

在二分的基础上使用大于等于或者小于等于来找到第一个和最后一个元素

需要注意查找之后的数组越界问题

3.x 的平方根

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: x 的平方根** @Author sun* @Create 2024/11/25 14:43* @Version 1.0*/
public class T1_2_3 {public static int mySqrt(int x) {// 判空if (x == 0) {return 0;}// 二分 [0, 1, 2, 3, 4, 5, 6, 7, 8]long l = 0, r = x;while (l <= r) {long mid = l + (r - l) / 2;if (x > mid * mid) {l = mid + 1;} else if (x < mid * mid) {r = mid - 1;} else {return (int) mid;}}return (int) r;}public static void main(String[] args) {int i = mySqrt(2147395599);System.out.println("i = " + i);}
}

2.思路

x的平方根范围就是0到本身，对这些数字进行标准二分查找即可，只不过要注意一下类型转换

4.有效的完全平方数

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 367. 有效的完全平方数** @Author sun* @Create 2024/11/25 15:20* @Version 1.0*/
public class T1_2_4 {public static boolean isPerfectSquare(int num) {// 一个数是否是完全平方数，就可以判断0到当前这个数的平方中能不能找到这个数// 【0， 1， 2， 3， 4】 4long l = 0, r = num;while (l <= r) {long mid = l + (r - l) / 2;if (num > mid * mid) {l = mid + 1;} else if (num < mid * mid) {r = mid - 1;} else {return true;}}// 如果找不到就返回falsereturn false;}public static void main(String[] args) {System.out.println("isPerfectSquare(4) = " + isPerfectSquare(16));}
}

2.思路

一个数是否是完全平方数，就可以判断0到当前这个数的平方中能不能找到这个数，就是标准二分，只不过要注意一下类型转换

4.总结

1.标准二分模板

    public static int search(int[] nums, int target) {// 初始化l，r左闭右闭的区间（这里的l和r是下标）int l = 0, r = nums.length - 1;// 当满足要求时进行二分，需要加等号while (l <= r) {// 定中点，防止溢出，相当于（l + r）/ 2int mid = l + (r - l) / 2;// 下面的情况就不一定了// 1.有可能是标准二分// 2.也有可能是大于等于或者小于等于的情况// 3.还有可能是下标即是元素的情况（标准二分变种）}// 如果跳出循环了还没结果就进行单独处理return ？;}

2.移除元素

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 27. 移除元素** @Author sun* @Create 2024/11/20 15:03* @Version 1.0*/
public class T1_3 {public static int removeElement(int[] nums, int val) {// 判空if (nums == null || nums.length == 0) {return 0;}// 快慢指针int slow = 0;for (int fast = 0; fast < nums.length; fast++) {// 如果发现不是目标值，就覆盖if (nums[fast] != val) {nums[slow] = nums[fast];// 慢指针++slow ++;}}// 返回移除后数组的长度return slow;}public static void main(String[] args) {// 【3， 2， 2， 3】 -> 【2， 2】int[] nums = {3, 2, 2, 3};int val = 3;int removed = removeElement(nums, val);// 返回的是移除后数组的长度System.out.println("移除后数组的长度为：" + removed);}
}

2.思路

快慢指针，就是慢指针和快指针首先指向同一个元素，快指针负责移动，快指针根据条件移动慢指针

3.扩展题目

1.删除有序数组中的重复项

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 26. 删除有序数组中的重复项** @Author sun* @Create 2024/11/25 16:27* @Version 1.0*/
public class T1_3_1 {public static int removeDuplicates(int[] nums) {// 快慢指针int slow = 0;for (int fast = 0; fast < nums.length; fast++) {// 当快指针指向的元素跟下一个元素不同时，进行覆盖，注意如果是最后一个元素，一定需要覆盖if (fast == nums.length - 1 || nums[fast] != nums[fast + 1]) {nums[slow] = nums[fast];slow ++;}}return slow;}public static void main(String[] args) {// {1, 1, 2} -> {1, 2}int[] nums = {1, 1, 2};System.out.println("removeDuplicates(nums) = " + removeDuplicates(nums));}
}

2.思路

依然是快慢指针，快指针根据指定条件对慢指针位置进行覆盖

2.移动零

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 283. 移动零** @Author sun* @Create 2024/11/25 16:53* @Version 1.0*/
public class T1_3_2 {public static void moveZeroes(int[] nums) {// 双指针int slow = 0;for (int fast = 0; fast < nums.length; fast++) {// 快指针发现当前元素不是0，就覆盖if (nums[fast] != 0) {nums[slow] = nums[fast];slow ++;}}// 将慢指针到最后填充0for (int i = slow; i < nums.length; i ++) {nums[i] = 0;}}public static void main(String[] args) {int[] nums = {0, 1, 0, 3, 12};moveZeroes(nums);}
}

2.思路

快指针指向非零元素，移动到慢指针的位置

3.比较含退格的字符串

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 844. 比较含退格的字符串** @Author sun* @Create 2024/11/25 17:03* @Version 1.0*/
public class T1_3_3 {public static boolean backspaceCompare(String s, String t) {// 处理并比较String handleS = handle(s);String handleT = handle(t);return handleS.equals(handleT);}/*** 使用双指针法处理** @param str* @return*/private static String handle(String str) {char[] charArray = str.toCharArray();int slow = 0;for (int fast = 0; fast < charArray.length; fast++) {// 当快指针指向的不是#时，就覆盖，慢指针++if (charArray[fast] != '#') {charArray[slow] = charArray[fast];slow ++;} else {// 当快指针指向的是#时，慢指针回退，最多回退到0if (slow > 0) {slow --;}}}// 构造最终的结果return slow > 0 ? new String(charArray, 0, slow) : "";}public static void main(String[] args) {String s = "ab#c", t = "ad#c";System.out.println("backspaceCompare(s, t) = " + backspaceCompare(s, t));}
}

2.思路

使用双指针模拟，当快指针指向的不是#时，就覆盖，慢指针++，当快指针指向的是#时，慢指针回退，最多回退到0

3.有序数组的平方

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import java.util.Arrays;/*** Description: 977. 有序数组的平方** @Author sun* @Create 2024/11/25 18:53* @Version 1.0*/
public class T1_4 {public static int[] sortedSquares(int[] nums) {// 创建一个新数组，用于存放结果int[] res = new int[nums.length];// 使用双指针，依次将最大的元素放到数组最后int index = nums.length - 1;int l = 0, r = nums.length - 1;while (l <= r) {// 求平方int left = nums[l] * nums[l];int right =nums[r] * nums[r];// 比较if (left >= right) {res[index--] = left;l ++;} else {res[index--] = right;r --;}}return res;}public static void main(String[] args) {int[] nums = {-4, -1, 0, 3, 10};System.out.println("sortedSquares(nums) = " + Arrays.toString(sortedSquares(nums)));}
}

2.思路

新开一个数组，使用双指针依次比较出最大的值，放入新数组即可

4.长度最小的子数组

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;/*** Description: 209. 长度最小的子数组** @Author sun* @Create 2024/11/25 19:16* @Version 1.0*/
public class T1_5 {public static int minSubArrayLen(int target, int[] nums) {int left = 0;// 窗口内部的和int sum = 0;int ans = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {// 向窗口中添加元素sum += nums[right];// 只要窗口中的元素和大于等于 target，则进行处理，使窗口中的元素和小于targetwhile (sum >= target) {// 统计最小长度ans = Math.min(ans, right - left + 1);// 移动左指针，使窗口中的元素和小于targetsum -= nums[left];left ++;}// 如果发现最后一个元素都添加到窗口中了，ans还没变，就说明没有满足要求的子数组if (right == nums.length - 1 && ans == Integer.MAX_VALUE) {return 0;}}return ans;}public static void main(String[] args) {int target = 7;int[] nums = {2, 3, 1, 2, 4, 3};System.out.println("minSubArrayLen(target, nums) = " + minSubArrayLen(target, nums));}
}

2.思路

这里使用了滑动窗口来解决，首先就是循环往窗口中放入元素，直到达到某个条件，对这个条件进行相应的处理，然后移动左指针，使得不满足这个条件，最后还需要考虑如果到最后都没有办法达到这个条件，应该怎么处理

3.扩展题目

1.水果成篮

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import java.util.*;/*** Description: 904. 水果成篮** @Author sun* @Create 2024/11/25 20:22* @Version 1.0*/
public class T1_5_1 {public static int totalFruit(int[] fruits) {// 滑动窗口定义：只能包含两种类型的水果int left = 0;int ans = -1;Map<Integer, Integer> map = new HashMap<>();for (int right = 0; right < fruits.length; right++) {// 向窗口中放入元素map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);// 不满足窗口定义while (map.size() > 2) {// 统计数量ans = Math.max(ans, right - left);// 滑动窗口Integer count = map.get(fruits[left]);if (count == 1) {map.remove(fruits[left]);} else {map.put(fruits[left], count - 1);}left ++;}// 最后再统计一下if (right == fruits.length - 1) {return Math.max(ans, right - left + 1);}}return ans;}public static void main(String[] args) {int[] fruits = {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};System.out.println("totalFruit(fruits) = " + totalFruit(fruits));}
}

2.思路

使用HashMap作为滑动的窗口，还是老套路，循环向窗口中添加元素，直到不满足窗口要求，此时对窗口进行处理，然后移动左指针，使窗口趋于满足条件，最后再统一处理一下一直都满足窗口定义的情况

5.螺旋矩阵II

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import java.util.Arrays;/*** Description: 59.螺旋矩阵II** @Author sun* @Create 2024/11/26 11:26* @Version 1.0*/
public class T1_6 {public static int[][] generateMatrix(int n) {int[][] res = new int[n][n];// 初始化边界int top = 0, bottom = n - 1;int left = 0, right = n - 1;int num = 1;while (true) {// 从左到右for (int i = left; i <= right; i++) {res[top][i] = num++;if (num > n * n) {return res;}}// 上边界下移top++;// 从上到下for (int i = top; i <= bottom; i++) {res[i][right] = num++;if (num > n * n) {return res;}}// 有边界左移right--;// 从右到左for (int i = right; i >= left; i--) {res[bottom][i] = num++;if (num > n * n) {return res;}}// 下边界上移bottom--;// 从下到上for (int i = bottom; i >= top; i--) {res[i][left] = num++;if (num > n * n) {return res;}}// 左边界右移left++;}}public static void main(String[] args) {int[][] ints = generateMatrix(1);System.out.println("ints = " + Arrays.deepToString(ints));}
}

2.思路

首先定义边界，然后直接循环，循环内每次移动都按照左闭右闭的规则，然后每移动一次都移动一下边界

3.扩展题目

1.螺旋矩阵

1.答案

package com.sunxiansheng.suanfa.daimasuixianglu;import java.util.ArrayList;
import java.util.List;/*** Description: 54. 螺旋矩阵** @Author sun* @Create 2024/11/26 12:22* @Version 1.0*/
public class T1_6_1 {public static List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();int m = matrix.length;int n = matrix[0].length;// 定义边界int top = 0, bottom = m - 1;int left = 0, right = n - 1;// 记录总共的元素个数int total = m * n;int count = 1;// 循环遍历while (true) {// 从左到右for (int i = left; i <= right; i++) {res.add(matrix[top][i]);if (++ count > total) {return res;}}// 上边界下移top++;// 从上到下for (int i = top; i <= bottom; i++) {res.add(matrix[i][right]);if (++ count > total) {return res;}}// 右边界左移right--;// 从右到左for (int i = right; i >= left; i--) {res.add(matrix[bottom][i]);if (++ count > total) {return res;}}// 下边界上移bottom--;// 从下到上for (int i = bottom; i >= top; i--) {res.add(matrix[i][left]);if (++ count > total) {return res;}}// 左边界右移left++;}}public static void main(String[] args) {int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};List<Integer> list = spiralOrder(matrix);System.out.println("list = " + list);}
}

2.思路

首先定义四个边界，然后循环遍历，区间是左闭右闭，每次移动都移动边界，循环退出的条件就使用一个计数器来做即可

6.区间和

1.答案（acm模式）

import java.util.*;
import java.lang.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取长度int n = sc.nextInt();// 记录到数组中int[] arr = new int[n];for (int i = 0; i < n; i ++) {arr[i] = sc.nextInt();}// 求出前缀和，key代表指定的下标，value代表到这个下标的和Map<Integer, Integer> map = new HashMap();int sum = 0;for (int i = 0; i < n; i ++) {// 求出前缀和sum += arr[i];map.put(i, sum);}while(sc.hasNextInt()) {// 读取区间int a = sc.nextInt();int b = sc.nextInt();// 计算区间和int res = map.get(b) - map.getOrDefault(a - 1, 0);System.out.println(res);}}
}

2.思路

一个区间（a，b）的和其实就是b的前缀和减去a-1的前缀和，只要计算出前缀和然后套公式即可