(78)删除有序数组中的重复项(79)排序矩阵查找

文章目录

  • 1. 每日一言
  • 2. 题目(78)删除有序数组中的重复项
    • 2.1 解题思路
    • 2.2 代码
  • 3. 题目(79)排序矩阵查找
    • 3.1 解题思路
    • 3.1.1 暴力查找
      • 暴力查找代码
    • 3.1.2 二分查找
      • 二分查找代码
    • 3.1.3 贪心
      • 贪心代码
  • 4. 结语


1. 每日一言

水晶帘动微风起,满架蔷薇一院香。 —高骈-


2. 题目(78)删除有序数组中的重复项

题目链接:删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。

  • 示例 1:
    输入:nums = [1,1,2]
    输出:2, nums = [1,2,_]
    解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

  • 示例 2:
    输入:nums = [0,0,1,1,1,2,2,3,3,4]
    输出:5, nums = [0,1,2,3,4]
    解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列


2.1 解题思路

使用双指针法

  1. 一个指针fast用于遍历数组元素,另一个指针slow用来指示当前有效的元素位置。
  2. 当fast指向的元素与slow指向的元素相同时,表示有重复元素,fast继续向前移动。
  3. 当fast指向的元素与slow指向的元素不同时,表示发现了新的不重复元素,将其复制到slow的下一个位置,然后同时移动fast和slow指针。
  4. 最终返回slow加1,即为去重后数组的长度。

2.2 代码

int removeDuplicates(int* nums, int numsSize) {
    int fast = 0;
    int slow = 0;
    while(fast < numsSize) {
        if(nums[fast] == nums[slow]) {
            fast++;
        } else {
            slow++;
            nums[slow] = nums[fast++];
        }
    }

    return slow+1;
}

3. 题目(79)排序矩阵查找

题目链接:排序矩阵查找

给定M×N矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。

  • 示例:
    现有矩阵 matrix 如下:
    [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
    ]
    给定 target = 5,返回 true。
    给定 target = 20,返回 false。

3.1 解题思路

3.1.1 暴力查找

通过两层嵌套的循环遍历整个矩阵,将目标值与矩阵中的每一个元素进行比较。如果找到了与目标值相等的元素,则返回true;否则遍历完整个矩阵后,返回false。

暴力查找代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){
    for(int i = 0; i < matrixSize; i++) {
        for(int j = 0; j < matrixColSize;j++) {
            if(matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

3.1.2 二分查找

在每行进行二分查找,对每一行进行有序数组的二分查找。如果找到了与目标值相等的元素,则返回 true;否则在遍历完整个矩阵后,返回 false。

二分查找代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){
    for(int i = 0; i < matrixSize;i++) {
        int left = 0;
        int right = matrixColSize-1;
        while(left <= right) {

            int mid = left + (right - left)/2;

            if(matrix[i][mid] < target) {
                left = mid + 1;
            } else if(matrix[i][mid] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
    }
    return false;
}

3.1.3 贪心

通过维护两个指针i和j,它们的初始位置分别为矩阵的右上角元素。然后根据当前元素与目标值的大小关系,逐步向左下角移动指针,直到找到目标值或者超出矩阵边界。

具体来说,如果当前元素大于目标值,则目标值不可能在当前元素所在的列,因此j减1;如果当前元素小于目标值,则目标值不可能在当前元素所在的行,因此i加1。通过这种方式,可以迅速缩小搜索范围,直到找到目标值或者遍历完整个矩阵。

贪心代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){
    int i = 0;
    int j = matrixColSize - 1;
    while(i < matrixSize && j >= 0) {
        if(matrix[i][j] > target) {
            --j;
        } else if(matrix[i][j] < target) {
            ++i;
        } else {
            return true;
        }
    } 
    return false;
}


4. 结语

请给自己些耐心,不要急于求成。
山外青山楼外楼,莫把百尺当尽头。
保持空杯心态加油努力吧!


都看到这里啦!真棒(*^▽^*)

可以给作者一个免费的赞赞吗,这将会鼓励我继续创作,谢谢大家

编程小白写作,如有纰漏或错误,欢迎指正


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

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

相关文章

使用阿里云试用Elasticsearch学习:使用内置模型 lang_ident_model_1 创建管道并使用

文档&#xff1a;https://www.elastic.co/guide/en/machine-learning/current/ml-nlp-deploy-model.html 部署刚刚下载好的内置模型 部署内存不够用 还得花钱&#xff0c;拉几把倒吧。就用自带的吧。 测试模型 POST _ml/trained_models/lang_ident_model_1/_infer {"doc…

MySQL-触发器:触发器概述、触发器的创建、查看删除触发器、 触发器的优缺点

触发器 触发器1. 触发器概述2. 触发器的创建2.1 创建触发器语法2.2 代码举例 3. 查看、删除触发器3.1 查看触发器3.2 删除触发器 4. 触发器的优缺点4.1 优点4.2 缺点4.3 注意点 注&#xff1a;此为笔者学习尚硅谷-宋红康MySQL的笔记&#xff0c;其中包含个人的笔记和理解&#…

HarmonyOS实战开发-横竖屏切换

介绍 本实例展示如何使用媒体查询&#xff0c;通过ohos.mediaquery 接口完成在不同设备上显示不同的界面效果。 效果预览 使用说明 1.在竖屏设备上&#xff0c;首页展示新闻列表&#xff0c;点击新闻进入详情界面。 2.在横屏设备上&#xff0c;首页左侧展示新闻列表&#x…

RT-Thread内核简介

1、RT-Thread 内核介绍 RT-Thread 内核架构图,内核处于硬件层之上,内 核部分包括内核库、实时内核实现 内核库是为了保证内核能够独立运行的一套小型的类似 C 库的函数实现子集。这部分根据编译器的不 同自带 C 库的情况也会有些不同,当使用 GNU GCC 编译器时,会携带…

STM32外设配置以及一些小bug总结

USART RX的DMA配置 这里以UART串口1为例&#xff0c;首先点ADD添加RX和TX配置DMA&#xff0c;然后模式一般会选择是normal&#xff0c;这个模式是当DMA的计数器减到0的时候就不做任何动作了&#xff0c;还有一种循环模式&#xff0c;是计数器减到0之后&#xff0c;计数器自动重…

【GD32】MQ-3酒精检测传感器

2.31 MQ-3酒精检测传感器 MQ-3气体传感器所使用的气敏材料是在清洁空气中电导率较低的二氧化锡(Sn0)。当传感器所处环境中存在酒精蒸气时&#xff0c;传感器的电导率随空气中酒精蒸气浓度的增加而增大。使用简单的电路即可将电导率的变化转换为与该气体浓度相对应的输出信号。…

嵌入式STM32F407CET6移植OpenHarmony系统方法

第一:【实验目的】 1、STM32F407CET6开发版移植鸿蒙系统的方式 第二:【实验原理】 涉及到原理图添加原理图--普通STM32F407原理图第三:【实验步骤】 一、下载LiteOs源码,复制到到虚拟机中并解压 https://gitee.com/LiteOS/LiteOS

政安晨:【Keras机器学习实践要点】(二十九)—— 半监督图像分类使用具有SimCLR对比性预训练的方法

目录 介绍 半监督学习 对比学习 设置 超参数设置 数据集 图像增强 编码器结构 有监督基线模型 用于对比预训练的自我监督模型 对预训练编码器进行有监督微调 与基准线的比较 进一步改进 架构 超参数 相关工作 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x…

Guava里一些比较常用的工具

随着java版本的更新提供了越来越多的语法和工具来简化日常开发&#xff0c;但是我们一般用的比较早的版本所以体验不到。这时就用到了guava这个包。guava提供了很多方便的工具方法&#xff0c;solar框架就依赖了guava的16.0.1版本&#xff0c;这里稍微介绍下。 一、集合工具类…

20240413,类和对象

对象&#xff1a;一切都可为对象&#xff0c;类&#xff1a;相同特性的对象&#xff1b;面向对象特性&#xff1a;封装&#xff0c;继承&#xff0c;多态 一&#xff0c;封装 CLASS 类名 { 访问权限 &#xff1a;属性/行为 } 实例化&#xff1a;通过一个类&#xff0c;创建一…

0101tomcat部署war访问mysql失败-容器间通信-docker项目部署

文章目录 一、简介二、部署1、mysql数据迁移2、docker部署redis3、docker部署tomcat并运行war包 三、报错四、解决1 分析2 解决 结语 一、简介 最近参与开发一个项目&#xff0c;其中一部分系统需要迁移。从阿里云迁移到实体服务器&#xff0c;使用docker部署。系统使用Java语…

11 Php学习:函数

PHP 内建函数Array 函数 PHP Array 函数是 PHP 核心的组成部分。无需安装即可使用这些函数。 创建 PHP 函数 当您需要在 PHP 中封装一段可重复使用的代码块时&#xff0c;可以使用函数。下面详细解释如何创建 PHP 函数并举例说明。 创建 PHP 函数的语法 PHP 函数的基…

TCP-IP详解卷一:协议——阅读总结

该内容适合程序员查看 第1章 概述 1.1 引言 WAN全称是 Wide Area Network&#xff0c;中文名为广域网。 LAN全称是 Local Area Network&#xff0c;中文名为局域网。 1.2分层 ICP/IP协议族通常被认为是一个四层协议系统 分层协议应用层Telnet、FTP和e-mail运输层TCP和UDP网…

shell 调用钉钉通知

使用场景&#xff1a;机器能访问互联网&#xff0c;运行时间任务后通知使用 钉钉建立单人群 手机操作&#xff0c;只能通过手机方式建立单人群 电脑端 2. 配置脚本 #!/bin/bash set -e## 上图中 access_token字段 TOKEN KEYWORDhello # 前文中设置的关键字 function call_…

机器学习——自动驾驶

本章我们主要学习以下内容: 阅读自动驾驶论文采集数据根据论文搭建自动驾驶神经网络训练模型在仿真环境中进行自动驾驶 论文介绍 本文参考自2016年英伟达发表的论文《End to End Learning for Self-Driving Cars》 📎end2end.pdf

Redis从入门到精通(十七)多级缓存(二)Lua语言入门、OpenResty集群的安装与使用

文章目录 前言6.4 Lua语法入门6.4.1 初识Lua6.4.2 Hello World6.4.3 变量6.4.3.1 Lua的数据类型6.4.3.2 声明变量 6.4.4 循环6.4.5 函数6.4.6 条件控制 6.5 实现多级缓存6.5.1 安装和启动OpenResty6.5.2 实现ajax请求反向代理至OpenResty集群6.5.2.1 反向代理配置6.5.2.2 OpenR…

chromium 协议栈 cronet ios 踩坑案例

1、请求未携带 Accept-Language http header 出现图片加载失败 现象&#xff1a; 访问 https://www.huawei.com/cn/?ic_mediumdirect&ic_sourcesurlent 时出现图片加载失败的问题 预期结果&#xff1a; 原因&#xff1a; 网络库删除了添加 Accept-Language header 的逻…

openssl 如何从pfx格式证书 获取证书序列号信息

已知&#xff1a;一个个人证书文件 test.pfx 求&#xff1a;如何通过openssl查看其对应证书的序列号信息&#xff1f; 踩坑之&#xff1a;unable to load certificate! openssl x509 -in xxx.cert -noout -serial 命令可查看证书序列号&#xff0c;但是这个-in 的输入必须是私…

Android开发:Camera2+MediaRecorder录制视频后上传到阿里云VOD

文章目录 版权声明前言1.Camera1和Camera2的区别2.为什么选择Camera2&#xff1f; 一、应用Camera2MediaPlayer实现拍摄功能引入所需权限构建UI界面的XMLActivity中的代码部分 二、在上述界面录制结束后点击跳转新的界面进行视频播放构建播放界面部分的XMLActivity的代码上述代…

基于Python的深度学习的中文情感分析系统(V2.0),附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…