代码随想录-暑假算法第一天(数组篇)

news/2024/9/14 1:58:13/ 标签: 算法, 数据结构, java

代码随想录-暑假算法第一天(数组篇)

1. 二分查找

力扣题目链接(opens new window)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

1
2
3

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

1
2
3

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

题解

java">class Solution {public int search(int[] nums, int target) {//左闭右闭区间int left = 0;int right = nums.length-1;while(left <= right){int middle = (left+right)/2;if(nums[middle] > target){right = middle-1;}else if(nums[middle] < target){left = middle + 1;}else if(nums[middle] == target){return middle;}}//没有找到return -1;}
}

总结

  1. 属于基础题目,大家一看就懂了,主要是边界问题

  2. 大家可以使用左闭右闭区间来编写二分查找代码,left<=right,middle的值根据是左区间还是右区间来加减1

2. 移除元素

力扣题目链接(opens new window)

给你一个数组 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。

你不需要考虑数组中超出新长度后面的元素。

暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

java">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--;size--;}}return size;}
}
总结

  1. 特别要注意的是循环的条件,是size,而不是nums.length

  2. 本质就是for循环的双层嵌套

双指针(快慢指针)较为重要

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置

很多同学这道题目做的很懵，就是不理解 快慢指针究竟都是什么含义，所以一定要明确含义，后面的思路就更容易理解了。

java">class Solution {public int removeElement(int[] nums, int val) {//快慢指针法 就是快//慢指针int slowIndex = 0;//for循环for(int i = 0;i < nums.length;i++){//如果不相等//快指针int fastIndex = i;if(nums[fastIndex] != val){nums[slowIndex] = nums[fastIndex];//慢指针移动slowIndex++;}}return slowIndex;}
}
总结

  1. 定义两个指针,即快慢指针,慢指针用于指向新数组的元素,快指针用于遍历数组的全部元素

  2. 如果快指针指向的元素不等于val的值时,就把快指针所指向的数字赋值给慢指针所指向的数字

3.有序数组的平方

力扣题目链接(opens new window)

给你一个按 非递减顺序 排序的整数数组 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]

暴力解法

java">class Solution {public int[] sortedSquares(int[] nums) {for(int i= 0;i<nums.length;i++){nums[i] = nums[i] * nums[i];}//进行排序Arrays.sort(nums);return nums;}
}
总结

  1. 比较简单,就是一步一步的做,先进行平方,在进行排序

  2. 没有什么难点

双指针法

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，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]; 。

java">class Solution {public int[] sortedSquares(int[] nums) {//因为是有序的,使用双指针法//定义一个新的数组int[] arr = new int[nums.length];//因为要从小到大int k = nums.length -1;for(int i = 0,j= nums.length-1;i<=j;){//进行判断if(nums[i] * nums[i] > nums[j] * nums[j]){//加入到新的数组里面arr[k--] = nums[i] * nums[i];i++;}else{//后面的平方大于前面平方的结果(包括相等的结果)arr[k--] = nums[j] * nums[j];j--;}}return arr;}
}
总结

  1. 定义一个大小相等的数组,用于存放元素,因为要从小到大,所以定义一个k,其值为数组的长度减一,即最大下标的元素的大小

  2. 定义两个指针,i,j分别指向头和尾,因为最大的那个数字只在头的位置或者尾巴的位置

  3. 进行判断,如果是前面的平方比后面的平方大,则把平方之后的数字的值添加到新的数组arr里面,然后k–( 从后往前填充),左区间要更新(i++),如果是后面的平方比前面的平方大,则反之,相等情况下也一样

4.长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

滑动窗口法(较为重要)

java">class Solution {public int minSubArrayLen(int target, int[] nums) {//滑动窗口法int result = nums.length +1;//j代表终止位置int sum = 0;for(int j = 0,i=0;j<nums.length;j++){sum = sum + nums[j];while(sum >= target){//更新resultresult = result > (j-i+1)? (j-i+1) : result;//缩小窗口sum = sum - nums[i];//移动起始位置i++;}}return result == (nums.length+1) ? 0  : result;}
}

总结

  1. 类似于一个可以滑动的窗口

  2. j代表终止位置,依次遍历;sum控制窗口之间的数字的和;result控制符合条件的子数组的长度;i代表起始位置,当大于目标数字的时候,(缩小窗口,sum减去i指向的数字),移动i,

5.螺旋矩阵II

力扣题目链接(opens new window)

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

要如何画出这个螺旋排列的正方形矩阵呢？

相信很多同学刚开始做这种题目的时候，上来就是一波判断猛如虎。

结果运行的时候各种问题，然后开始各种修修补补，最后发现改了这里那里有问题，改了那里这里又跑不起来了。

大家还记得我们在这篇文章数组：每次遇到二分法，都是一看就会，一写就废 (opens new window)中讲解了二分法，提到如果要写出正确的二分法一定要坚持循环不变量原则。

而求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

那么我按照左闭右开的原则，来画一圈，大家看一下：

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。

一些同学做这道题目之所以一直写不好，代码越写越乱。

就是因为在画每一条边的时候，一会左开右闭，一会左闭右闭，一会又来左闭右开，岂能不乱。

代码如下，已经详细注释了每一步的目的，可以看出while循环里判断的情况是很多的，代码里处理的原则也是统一的左闭右开。

题解1(我自己的做法一行一列法)较为容易理解

java">class Solution {public int[][] generateMatrix(int n) {//创建一个二维数组,存储数字int[][] arr = new int[n][n];int count = 1;//头部int top = 0;//尾部int bottom = n - 1;//左部int left = 0;//右部int right = n - 1;while (count <= n * n) {//从左往右for (int i = left; i <= right; i++) {arr[top][i] = count++;}top++;//从上往下for (int i = top; i <= bottom; i++) {arr[i][right] = count++;}right--;//从右往左for (int i = right; i >= left; i--) {arr[bottom][i] = count++;}bottom--;//从下往上for (int i = bottom; i >= top; i--) {arr[i][left] = count++;}left++;}return arr;}}

总结

  1. 就只需要注意到当count为n*n的时候才能进入while,要不然会引起数组越界

  2. 法1: while的条件设为count < n*n,并且count初始值为0,之后++count;

  3. 法2: while的条件设为count<=n*n,并且count初始值为1,之后count++;

题解2(官方的解法左闭右开法)较为官方

java">class Solution {public int[][] generateMatrix(int n) {//创建一个二维数组,存储数字int[][] arr = new int[n][n];//规定左闭右开区间//起始点int startX = 0;//int startY = 0;//用于计数int count = 1;int i = 0;int j = 0;//记录圈数int loop = 1;//用于记录终止位置int offset = 1;while(loop <= n /2){for(j = startX;j<n-offset;j++){arr[startX][j] = count++;}for(i = startX;i<n-offset;i++){arr[i][j] = count++;}for(;j>startX;j--){arr[i][j] = count++;}for(;i>startX;i--){arr[i][j] = count++;}//到下一圈,更新新的变量loop++;startX++;//startY++;offset++;}//奇数的特殊情况if(n%2==1){arr[n/2][n/2] = count++;}return arr;}}

总结

  1. 还是比较好理解的

  2. 规定一个标准(左闭右开),顺时针画一个圆,分为四次 ,每一次包头不包尾(左闭右开),while里面的条件是圈数,定义两个变量,分别控制(startX = 0)起始点和终点(offset = n -1);

  3. 当n为奇数时,需要额外判断,如果n为奇数,那么最后一圈,n是进入不到while循环里面的,需要在while循环结束后,手动添加最后一圈(arr[n/2][n/2] = ++count),count为计数器

数组总结篇

  1. 果然还是得多多练习,一看就会,一写就废

  2. 个人感觉数组篇难度不是很大,但是要注意的细节点很多,例如边界的判断…

  3. 在数组篇我学习了较为重要也非常有用的算法,例如二分法(在一个有序的数组里面查找指定的元素),双指针法,滑动窗口法,这些虽然现在可以已经懂了,但是要想完全理解,还是得多多编程

  4. 最后,开开心心的学习编程,充实的过好每一天编程已经成为了我生活的一部分了,


http://www.ppmy.cn/news/1474668.html

相关文章

AIGC爬虫类代码示例：Scrapy和OpenAI API实现抓取内容并生成内容

AIGC爬虫类代码示例：Scrapy和OpenAI API实现抓取内容并生成内容

对于我从事爬虫行业多年的经验来说&#xff0c;编程各种需求代码真是非常吃力且细致的活&#xff0c;随着AI的大火&#xff0c;我在设想有没有可能通过AI自动化程序实现自动抓取生成想要的文本内容。前提我是打算通过结合爬虫技术&#xff08;如Scrapy&#xff09;和生成式AI模…
阅读更多...
【Django项目】基于Python+Django+MySQL的音乐网站系统项目

【Django项目】基于Python+Django+MySQL的音乐网站系统项目

功能介绍 首页&#xff1a;歌曲分类、歌曲搜索、热门歌曲、热门下载、新歌推荐 歌曲排行&#xff1a;歌曲分类、分页功能 用户板块&#xff1a;用户登陆/注册、播放历史 歌曲详情&#xff1a;歌曲播放、当前播放列表、歌曲点评、歌曲播放插件、下载歌曲 系统后台&#xff1a;歌…
阅读更多...
Spring——自动装配Bean

Spring——自动装配Bean

自动装配是Spring满足bean依赖的一种方式 Spring会在上下文中自动寻找&#xff0c;并自动给bean装配属性 在Spring中有三种装配的方式&#xff1a; 1. 在xml中显示配置 2. 在java中显示配置 3. 隐式的自动装配bean【重要】 测试 记得创建Cat、Dog、People类 public clas…
阅读更多...
手撸俄罗斯方块（三）——游戏核心模块设计

手撸俄罗斯方块（三）——游戏核心模块设计

手撸俄罗斯方块——游戏核心模块设计 开始游戏 按照之前的设计&#xff0c;我们需要游戏的必要元素之后即可开始游戏&#xff0c;下面以控制台上运行俄罗斯方块为例进行展开讲解。 import { ConsoleCanvas, ConsoleController, ConsoleColorTheme, Color } from shushanfx/t…
阅读更多...
18.按键消抖模块设计（使用状态机，独热码编码）

18.按键消抖模块设计（使用状态机，独热码编码）

&#xff08;1&#xff09;设计意义&#xff1a;按键消抖主要针对的时机械弹性开关&#xff0c;当机械触点断开、闭合时&#xff0c;由于机械触点的弹性作用&#xff0c;一个按键开关在闭合时不会马上稳定地接通&#xff0c;在断开时也不会一下子就断开。因而在闭合以及断开的瞬…
阅读更多...
Linux rpm和ssh损坏修复

Linux rpm和ssh损坏修复

背景介绍 我遇到的问题可能和你的不一样。但是如果遇到错误一样也可以按此方案尝试修复。 我是想在Linux上安装Oracle&#xff0c;因为必须在离线环境下安装。就在网上搜一篇文章linux离线安装oracle&#xff0c;然后安装教程走&#xff0c;进行到安装oracle依赖包的时候执行了…
阅读更多...
React:useState和useEffect

React:useState和useEffect

最近因为想要开发一个简单的应用才开始接触React。但是并没有系统学习React&#xff0c;所以这篇博客可能会写的不够专业。 1. Hooks 在程序设计语言中&#xff0c;钩子(hook)是一种机制&#xff0c;它可以允许程序在某些预定的事件或位置执行特定的代码。在React中&#xff0c…
阅读更多...
Web 性能入门指南-1.2 分析在线零售 Web 性能及优化方向

Web 性能入门指南-1.2 分析在线零售 Web 性能及优化方向

让顾客满意是零售业成功的秘诀。事实证明&#xff0c;提供快速、一致的在线体验可以显著提高零售商关心的每项指标——从转化率和收入到留存率和品牌认知度。 本文大纲&#xff1a; 页面速度影响在线零售业务数据 如何将您的网站速度与竞争对手进行比较 性能优化入门&#xf…
阅读更多...
超级好用的java http请求工具

超级好用的java http请求工具

kong-http 基于okhttp封装的轻量级http客户端 使用方式 Maven <dependency><groupId>io.github.kongweiguang</groupId><artifactId>kong-http</artifactId><version>0.1</version> </dependency>Gradle implementation …
阅读更多...
独特功能的视频号矩阵系统源码，支持多短视频平台自动发布和定时发布

独特功能的视频号矩阵系统源码，支持多短视频平台自动发布和定时发布

在短视频行业竞争日趋激烈的今天&#xff0c;一个高效的视频发布系统对于内容创作者和营销团队来说至关重要。视频号矩阵系统源码以其独特的功能&#xff0c;为多平台自动发布和定时发布提供了强大的技术支持。 多平台自动化发布&#xff1a;无缝内容分发 视频号矩阵系统源码…
阅读更多...
掌握MOJO命令行：参数解析的艺术

掌握MOJO命令行：参数解析的艺术

在软件开发中&#xff0c;命令行接口&#xff08;CLI&#xff09;是一种与程序交互的强大方式&#xff0c;它允许用户通过终端输入指令和参数来控制程序的行为。对于MOJO语言&#xff0c;即使它是一个假想的编程语言&#xff0c;我们也可以设想它具备解析命令行参数的能力。本文…
阅读更多...
Oracle执行一条SQL的内部过程

Oracle执行一条SQL的内部过程

一、SQL语句根据其功能主要可以分为以下几大类&#xff1a; 1. 数据查询语言&#xff08;DQL, Data Query Language&#xff09; 功能&#xff1a;用于从数据库中检索数据&#xff0c;常用于查询表中的记录。基本结构&#xff1a;主要由SELECT子句、FROM子句、WHERE子句等组成…
阅读更多...
使用Docker、Docker-compose部署单机版达梦数据库（DM8）

使用Docker、Docker-compose部署单机版达梦数据库（DM8）

安装前准备 Linux Centos7安装&#xff1a;https://blog.csdn.net/andyLyysh/article/details/127248551?spm1001.2014.3001.5502 Docker、Docker-compose安装&#xff1a;https://blog.csdn.net/andyLyysh/article/details/126738190?spm1001.2014.3001.5502 下载DM8镜像 …
阅读更多...
Bilibili Android一二面凉经(2024)

Bilibili Android一二面凉经(2024)

BiliBili Android一二面凉经(2024) 笔者作为一名双非二本毕业7年老Android, 最近面试了不少公司, 目前已告一段落, 整理一下各家的面试问题, 打算陆续发布出来, 供有缘人参考。今天给大家带来的是《BiliBili Android一二面凉经(2024)》。 面试职位: 高级Android开发工程师&…
阅读更多...
Openresty+lua 定时函数 ngx.timer.every

Openresty+lua 定时函数 ngx.timer.every

ngx.timer.every 是 OpenResty 中的一个函数&#xff0c;用于创建定时器&#xff0c;以便定期执行某个函数或代码块。它的用法如下&#xff1a; local delay 5 -- 定时器间隔时间&#xff0c;单位为秒ngx.timer.every(delay, function(premature)-- 这里是定时执行的代码块i…
阅读更多...
2.5 C#视觉程序开发实例1----CamManager实现模拟相机采集图片(Form_Vision部分代码)

2.5 C#视觉程序开发实例1----CamManager实现模拟相机采集图片(Form_Vision部分代码)

2.5 C#视觉程序开发实例1----CamManager实现模拟相机采集图片(Form_Vision部分代码) 1 目标效果视频 CamManager 2 增加一个class IMG_BUFFER 用来管理采集的图片 // <summary> /// IMG_BUFFER 用来管理内存图片的抓取队列 /// </summary> public class IMG_BUFF…
阅读更多...
【代码随想录算法训练营第六十二天|卡码网53.寻宝（prim算法和kruskal算法）】

【代码随想录算法训练营第六十二天|卡码网53.寻宝（prim算法和kruskal算法）】

文章目录 53.寻宝prim算法kruskal算法 53.寻宝 prim算法 prim算法三部曲&#xff1a; 1.选择当前最短入树结点&#xff1b;2.更新入树结点&#xff1b;3.更新结点距离最小生成树的距离。 可以把所有已经使用过的结点看作一个整体&#xff0c;然后把他们相接的结点的结点顶点边…
阅读更多...
百日筑基第十八天-一头扎进消息队列1

百日筑基第十八天-一头扎进消息队列1

百日筑基第十八天-一头扎进消息队列1 先对业界消息队列有个宏观的认识 消息队列的现状 当前开源社区用的较多的消息队列主要有 RabbitMQ、RocketMQ、Kafka 和Pulsar 四款。 国内大厂也一直在自研消息队列&#xff0c;比如阿里的 RocketMQ、腾讯的 CMQ 和 TubeMQ、京东的 JM…
阅读更多...
玄机——第五章 linux实战-CMS01 wp

玄机——第五章 linux实战-CMS01 wp

文章目录 一、前言二、概览简介 三、参考文章四、步骤&#xff08;解析&#xff09;准备步骤#1.0步骤#1.1通过本地 PC SSH到服务器并且分析黑客的 IP 为多少,将黑客 IP 作为 FLAG 提交; 步骤#1.2通过本地 PC SSH到服务器并且分析黑客修改的管理员密码(明文)为多少,将黑客修改的…
阅读更多...
Perl 语言开发（八）：子程序和模块

Perl 语言开发（八）：子程序和模块

目录 1. 引言 2. 子程序的基本概念与用法 2.1 子程序的定义和调用 2.2 传递参数 2.3 返回值 2.4 上下文和返回值 3. 模块的基本概念与用法 3.1 模块的定义 3.2 使用模块 3.3 导出符号 3.4 模块的文件结构和命名 4. 实际应用中的子程序与模块 4.1 子程序参数验证与…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站