参考链接
代码随想录
讲解视频链接
数组题
1、(两数之和)给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
思考点:
- 为什么要把数组下标作为value,值作为key?
map.containsKey检查是否存在这个key
,所以将值作为key
//暴力法
class Solution {public int[] twoSum(int[] nums, int target) {int length = nums.length;int i,j;for (i = 0;i<length;i++){for(j = i+1;j<length;j++){if(nums[i] + nums[j] == target){return new int[]{i, j};}}}return null;}
}
//哈希表法
class Solution {public int[] twoSum(int[] nums, int target) {// 创建一个 HashMap 用于存储值 -> 索引的映射HashMap<Integer,Integer> map = new HashMap<>();//遍历数组for (int i =0;i<nums.length;i++){int complement = target - nums[i]; // 计算目标值需要的另一个数// 检查 Map 中是否已存在所需的数if (map.containsKey(complement)) {return new int[]{map.get(complement), i}; // 返回两个索引}// 当前值存入 Mapmap.put(nums[i], i);}throw new IllegalArgumentException("No solution found");}
}
704、给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。(二分法、有序、无重复元素)
思考点:
- 左闭右闭和左开右闭的核心思想应该是
区间合法性
——在设置循环条件时,是否取等号取决于它能否取到等号,right取值也是同理
2.说明:当左闭右开时,right要取值为nums.length,如果取nums.length-1,那么只有一个元素的情况,怎么取左闭右开呢?
//左闭右闭写法
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int middle = left + (right - left) / 2; // 防止溢出if (nums[middle] > target) {// 在左侧right = middle - 1;} else if (nums[middle] < target) {// 在右侧left = middle + 1;} else {// 找到目标值return middle;}}// 未找到目标值,返回 -1return -1;}
}
//左闭右开
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length;while (left < right) {int middle = left + (right - left) / 2; // 防止溢出if (nums[middle] > target) {// 在左侧right = middle ;} else if (nums[middle] < target) {// 在右侧left = middle + 1;} else {// 找到目标值return middle;}}// 未找到目标值,返回 -1return -1;}
}
27、 移除元素
1.实际这个问题是考双指针解法定义快慢指针
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
//暴力解法:一个for循环遍历数组元素 ,第二个for循环更新数组
//找到val值位置,将其后元素往前移动一位
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {public int removeElement(int[] nums, int val) {int size = nums.length;for (int i =0;i<size;i++){if(nums[i]==val){for(int j = i +1;j< size;j++){nums[j-1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
}
//双指针法
class Solution {public int removeElement(int[] nums, int val) {int slow = 0;for (int fast = 0;fast< nums.length; fast++){if( nums[fast] != val){nums[slow] = nums[fast];slow ++;}}return slow;}
}
977、 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
思考点:
1.数组有序,且最大值出现在数组的两端,可以考虑用双指针法,这里是重点考虑结果集也需要一个指针k指向结果集终止位置,不能依靠fast指针进行填充,因为当出现slow指针数平方大于fast时,fast位置是不变的,会导致结果集同一位置覆盖赋值。
class Solution {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = result.length - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {// 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置result[index--] = nums[left] * nums[left];++left;} else {result[index--] = nums[right] * nums[right];--right;}}return result;}
}
209.长度最小的子数组
思考点:
循环索引下标使用的是终止位置,如果使用起始位置其实和暴力解法无异。
//暴力解法:result设置一个很大的数,防止就算整个序列相加都无法满足条件
class Solution {public int minSubArrayLen(int target, int[] nums) {int result = nums.length + 1;//设置为最大值,防止不存在符合条件的子数组int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for(int i = 0;i<nums.length;i++){sum =0;for(int j=i;j<nums.length;j++){sum +=nums[j];if(sum>=target){subLength = j-i+1;result = result < subLength? result:subLength;}}}// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列return result == nums.length + 1 ? 0 : result;}
}
//滑动窗口
class Solution {public int minSubArrayLen(int target, int[] nums) {int result = nums.length + 1;//设置为最大值,防止不存在符合条件的子数组int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度int start = 0;for(int end = 0;end<nums.length;end++){sum += nums[end];while(sum >=target){subLength = end - start + 1;result = result < subLength? result:subLength;sum -= nums[start];start++;}}return result == nums.length + 1 ? 0 : result;}
}
59、螺旋矩阵:给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思考点
:确定循环不变量原则,保持一个区间;每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。
class Solution {public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int loop;int startx = 0; // 起始 x 坐标int starty = 0; // 起始 y 坐标int offset = 1; // 控制每一圈终止位置int count = 1; // 用于计数自增// 确定圈数if (n % 2 == 1) {loop = n / 2 + 1;} else {loop = n / 2;}while (loop-- > 0) {int i = startx; // 当前层的起始行int j = starty; // 当前层的起始列// 从左到右填充for (; j < n - offset; j++) {matrix[startx][j] = count++;}// 从上到下填充for (; i < n - offset; i++) {matrix[i][j] = count++;}// 从右到左填充for (; j > starty; j--) {matrix[i][j] = count++;}// 从下到上填充for (; i > startx; i--) {matrix[i][j] = count++;}// 更新边界offset++;startx++;starty++;// 如果 n 是奇数,填充中心点if (n % 2 == 1) {matrix[n / 2][n / 2] = count;}}return matrix;}
}
58、区间和:第一行输入为整数数组 Array 的长度 n,接下来 n 行,每行一个整数,表示数组的元素。随后的输入为需要计算总和的区间下标:a,b (b > = a),直至文件结束。输出每个指定区间内元素的总和。
思考点:
- 用hasNextInt来循环获取输入值
- 前缀和 在涉及计算区间和的问题时非常有用,重复利用计算过的子数组之和,从而降低区间查询需要累加计算的次数。
- 要统计 vec[i] 这个数组上的区间和。先做累加,即 p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] vec = new int[n];int[] p = new int[n];int presum = 0;for (int i =0;i<n ;i++){vec[i] = scanner.nextInt();presum += vec[i];p[i] = presum;} while(scanner.hasNextInt()){int a = scanner.nextInt();int b = scanner.nextInt();if (a ==0){System.out.println(p[b]);}else{System.out.println(p[b] - p[a-1]);}}scanner.close();}
}
44、开发商购买土地
思考点:
1.使用区间和的思想,将第一列作为区间和col的第一个元素,第一列加第二列作为col的第二个元素
2.切割也是一个连续的区间和,从第一列到第m列[1,m],col[m-1] - col[i]表示从第i列开始切
3.最后只要记录最小值输出即可
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] matrix = new int[n][m];for (int i = 0;i< n; i++){for(int j = 0;j<m;j++){matrix[i][j]=scanner.nextInt();}}//行区间和int sum =0;int[] row = new int[n];for (int i=0;i<n;i++){for(int j = 0;j<m;j++){sum += matrix[i][j];}row[i] = sum;sum = 0;}//列区间和int[] col = new int[m];for (int j=0;j<m;j++){for(int i = 0;i<n;i++){sum += matrix[i][j];}col[j] = sum;sum = 0;}int[] p = new int[n];for(int i = 0;i<n ;i++){sum += row[i];p[i] = sum;}sum = 0;int[] b = new int[m];for(int j = 0;j<m ;j++){sum += col[j];b[j] = sum;}int result = Integer.MAX_VALUE;//随便设置的一个较大值int distance ;//切割距离//先比行for(int i=0;i<n;i++){distance = Math.abs(p[i] - (p[n - 1] - p[i])); // 两部分绝对差值result = result < distance ? result : distance;}//再比列for(int j=0;j<m;j++){distance = Math.abs(b[j] - (b[m - 1] - b[j])); // 两部分绝对差值result = result < distance ? result : distance;}System.out.println(result);scanner.close();}
}