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

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

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]之间。

题解

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循环更新数组。

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循环的工作。

定义快慢指针

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

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

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]

暴力解法

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]; 。

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

滑动窗口法(较为重要)

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){
                //更新result
                result = 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(我自己的做法一行一列法)较为容易理解

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(官方的解法左闭右开法)较为官方

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. 最后,开开心心的学习编程,充实的过好每一天编程已经成为了我生活的一部分了,

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/796016.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

3d为什么删掉模型不能返回?---模大狮模型网

在展览3D模型设计行业中&#xff0c;设计师们经常面临一个关键问题&#xff1a;一旦删除了模型的某些部分&#xff0c;为什么很难或者无法恢复原始状态?这不仅是技术上的挑战&#xff0c;更是设计过程中需要深思熟虑的重要考量。本文将探讨这一问题的原因及其在实际工作中的影…

css画半圆画圆弧

利用border-radius和border完成&#xff1a; <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>test</title> <style> .semicircle {width: 100px;height: 50px;border-radius: 0 0 50px 50px;background:…

更新商品前端接口编写

文章目录 新增页面书写写表单价格符号的显示然后状态的书写后端枚举书写时间书写使用组件 新增页面书写 书写直接复制页面 写表单的绑定信息 然后绑定表单 表单绑定还有表单数据的绑定 标签中ref的作用就是将 该组件注册到vue对象的ref属性中 那么在vue运行的时候,会加载所…

【人工智能】Transformers之Pipeline(一):音频分类(audio-classification)

​​​​​​​ 目录 一、引言 二、音频分类&#xff08;audio-classification&#xff09; 2.1 概述 2.2 技术原理 2.2.1 Wav2vec 2.0模型 2.2.1 HuBERT模型 2.3 pipeline参数 2.3.1 pipeline对象实例化参数 2.3.2 pipeline对象使用参数 2.4 pipeline实战 2.4.1 …

访问 Postman OAuth 2.0 授权的最佳实践

OAuth 2.0 代表了 web 安全协议的发展&#xff0c;便于在多个平台上进行授权服务&#xff0c;同时避免暴露用户凭据。它提供了一种安全的方式&#xff0c;让用户可以授权应用程序访问服务。 在 Postman 中开始使用 OAuth 2.0 Postman 是一个流行的API客户端&#xff0c;支持 …

19 元服务使用心得

Atomic 原子 元数据描述数据的数据 可以理解为鸿蒙版小程序 轻量化 免安装(严格来说需要安装但是较小无感) 独立入口 能够为用户提供一个或者多个便捷的新型应用形态所有文件不超过2M 元服务与应用对比 首包和分包 首包&#xff1a;hap 里面放 首次打开首页和用到的资源 分…

Java常用的API_02(正则表达式、爬虫)

Java正则表达式 七、正则表达式7.1 格式7.1.1 字符类注意字符类示例代码1例2 7.1.2 预定义字符预定义字符示例代码例2 7.1.3 区别总结 7.2 使用Pattern和Matcher类与直接使用String类的matches方法的区别。&#xff08;1&#xff09; 使用Pattern和Matcher类示例代码 &#xff…

oslo_i18n学习小结

背景 代码均为开源代码 基于yoga版本&#xff0c;需要对openstack某服务做翻译&#xff0c;了解到oslo_i18n有翻译功能&#xff0c;配置oslo_i18n来给组件进行翻译 用法 用法 每个服务自己会带一个i18n.py的文件&#xff0c;如果要对日志进行翻译&#xff0c;从i18n导入_&…

AI人工智能作词,为音乐注入未来之力

在当今的音乐世界中&#xff0c;创新的力量不断推动着边界的拓展&#xff0c;而人工智能作词正以其独特的魅力&#xff0c;成为引领音乐走向未来的强大动力。 “妙笔生词智能写歌词软件&#xff08;veve522&#xff09;”无疑是这股浪潮中的璀璨明星。它利用先进的人工智能技术…

Spring Security学习笔记(一)Spring Security架构原理

前言&#xff1a;本系列博客基于Spring Boot 2.6.x依赖的Spring Security5.6.x版本 Spring Security中文文档&#xff1a;https://springdoc.cn/spring-security/index.html 一、什么是Spring Security Spring Security是一个安全控制相关的java框架&#xff0c;它提供了一套全…

某某会员小程序后端性能优化

背景 某某会员小程序后台提供开放平台能力&#xff0c;为三方油站提供会员积分、优惠劵等api。当用户在油站加油&#xff0c;油站收银会调用我们系统为用户发放积分、优惠劵等。用户反馈慢&#xff0c;三方调用发放积分接口性能极低&#xff0c;耗时30s&#xff1b; 接口情况…

在uniapp中如何使用地图

1&#xff0c;技术选择 最好是使用webview html形式加载&#xff0c;避免打包app时的地图加载问题 2&#xff0c;webview使用 使用webview必须按照官方文档,官网地址&#xff1a;https://uniapp.dcloud.net.cn/component/web-view.html <template><view><!…

LabVIEW比例压力控制阀自动测试系统

开发了一套基于LabVIEW编程和PLC控制的比例控制阀自动测试系统。该系统能够实现共轨管稳定的超高压供给&#xff0c;自动完成比例压力控制阀的耐久测试、流量滞环测试及压力-流量测试。该系统操作简便&#xff0c;具有高精度和高可靠性&#xff0c;完全满足企业对自动化测试的需…

80. UE5 RPG 实现UI显示技能冷却进度功能

在上一篇文章里&#xff0c;我们实现了通过GE给技能增加资源消耗和技能冷却功能。UI也能够显示角色能够使用的技能的UI&#xff0c;现在还有一个问题&#xff0c;我们希望在技能释放进去冷却时&#xff0c;技能变成灰色&#xff0c;并在技能冷却完成&#xff0c;技能可以再次使…

Linux安全技术与防火墙

一、安全技术和防火墙 1.1 安全技术 入侵检测系统&#xff1a;特点是不阻断网络访问&#xff0c;主要是提供报警和时候报警&#xff0c;不主动介入。 入侵防御系统&#xff1a;透明模式工作&#xff0c;对数据包、网络监控、服务攻击、木马蠕虫、系统漏洞等等进行准确的分析和…

两个视频怎么剪辑成一个视频?3个方法分享

两个视频怎么剪辑成一个视频&#xff1f;将两个视频剪辑成一个视频&#xff0c;是现代数字内容创作中的高频需求&#xff0c;它不仅简化了素材管理&#xff0c;还能通过创意剪辑提升作品连贯性与表现力。通过精心编排&#xff0c;两个视频片段可以无缝融合&#xff0c;讲述更完…

如何通过兔子和窝窝的故事理解“在机器人学习和研究中的获得成本与维护成本”(节选)

获得成本 掌握一门课程&#xff0c;以最为简单的学校成绩过60为例&#xff0c;需要按要求提交材料&#xff0c;包括作业、报告、实验和考试等&#xff0c;依据学分和考核要求的不同&#xff0c;需要对于花费时间和经历进行完成。 维护成本 考完了&#xff0c;如果被动学习那…

Django 删除单行数据

1&#xff0c;添加模型 from django.db import modelsclass Post(models.Model):title models.CharField(max_length200)content models.TextField()pub_date models.DateTimeField(date published)class Book(models.Model):title models.CharField(max_length100)author…

FastAPI 学习之路(四十七)WebSockets(三)登录后才可以聊天

之前我们是通过前端自动生成的token信息&#xff0c;这次我们通过注册登录&#xff0c;保存到本地去实现。首先&#xff0c;我们实现一个登录页面&#xff0c;放在templates目录下。 <!DOCTYPE html> <html lang"en"> <head><meta charset&quo…

基于PCIe总线架构的2路1GSPS AD、4路1GSPS DA信号处理平台(100%国产化)

板卡概述 PCIE723-165是基于PCIE总线架构的2通道1GSPS采样率14位分辨率、4通道1GSPS采样率16位分辨率信号处理平台&#xff0c;该板卡采用国产16nm FPGA作为实时处理器&#xff0c;支持2路高速采集以及4路高速数据回放&#xff0c;板载2组DDR4 SDRAM大容量数据缓存&#xff0c;…