LeetCode数组题

devtools/2024/11/28 20:54:54/

参考链接

代码随想录
讲解视频链接

数组题

1、(两数之和)给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
思考点:

  1. 为什么要把数组下标作为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。(二分法、有序、无重复元素)
思考点:

  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),直至文件结束。输出每个指定区间内元素的总和。
思考点:

  1. 用hasNextInt来循环获取输入值
  2. 前缀和 在涉及计算区间和的问题时非常有用,重复利用计算过的子数组之和,从而降低区间查询需要累加计算的次数。
  3. 要统计 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();}
}

http://www.ppmy.cn/devtools/137756.html

相关文章

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

捉虫笔记(七)-再探谁把系统卡住了

捉虫笔记&#xff08;七&#xff09;-再探谁把系统卡住 1、内核调试 在实体物理机上&#xff0c;内核调试的第一个门槛就是如何建立调试链接。 这里我选择的建立网络连接进行内核调试。 至于如何建立网络连接后续文章再和大家分享。 2、如何分析 在上一篇文章中&#xff0c;我们…

追加docker已运行容器添加或修改端口映射方法

docker run可以指定端口映射 【】docker run -d -p 80:80 --name name 但是容器一旦生成&#xff0c;就没有一个命令可以直接修改。通常间接的办法是&#xff0c;保存镜像&#xff0c;再创建一个新的容器&#xff0c;在创建时指定新的端口映射。 【】 docker stop A 【】 doc…

经典游戏:飞机大战游戏python设计与实现

《飞机大战》是一款经典的二维飞行射击游戏&#xff0c;其核心玩法是控制玩家飞机与敌机作战&#xff0c;通过击落敌机获取分数并尽量避免被敌机击中。根据提供的代码&#xff0c;飞机大战的设计和实现可以分为以下几个主要部分&#xff1a;游戏初始化、游戏界面设计、玩家控制…

【MySQL】MySQL8.0新特性整理

MySQL 8.0 引入了许多新特性和改进&#xff0c;旨在提升性能、安全性和易用性。以下是一些主要的新特性&#xff1a; 1. 默认字符集和排序规则 默认字符集&#xff1a;MySQL 8.0 的默认字符集从 latin1 更改为 utf8mb4&#xff0c;支持更多的字符和表情符号。排序规则&#x…

计算机网络的功能

目录 信息交换 资源共享 分布式处理 可靠性增强 集中管理 信息交换 计算机网络最基本的功能之一是允许不同设备之间的数据通信。这包括电子邮件的发送和接收、即时消息的传递、文件传输等。通过网络&#xff0c;用户可以轻松地与全球各地的其他人进行沟通和协作。 信息交…

【贪心算法第二弹——2208.将数组和减半的最小操作数】

1.题目解析 题目来源 2208.将数组和减半的最小操作数——力扣 测试用例 2.算法原理(贪心策略) 3.实战代码 class Solution { public:int halveArray(vector<int>& nums) {priority_queue<double> hash;double sum 0.0;for(auto e : nums){hash.push(e);sum …

PostgreSQL 三种关库模式

PostgreSQL 三种关库模式 基础信息 OS版本&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本&#xff1a;16.2 pg软件目录&#xff1a;/home/pg16/soft pg数据目录&#xff1a;/home/pg16/data 端口&#xff1a;5777PostgreSQL 提供了三种关库模式&…