算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项

2023-12-07 11:52

本文主要是介绍算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


前言:本次分享题目全部来自力扣网,大家可以自行选择挑战,详细链接:

118. 杨辉三角 - 力扣(LeetCode)

88. 合并两个有序数组 - 力扣(LeetCode)

26. 删除有序数组中的重复项 - 力扣(LeetCode)

目录

一.杨辉三角

思路:

完整代码:

二.合并俩个有序数组

思路:

完整代码:

三.删除有序数组中的重复项

思路:

完整代码:


一.杨辉三角

题目:给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行(1 <= numRows <= 30)

注意:在「杨辉三角」中,每个数是它左上方和右上方的数的和

示例一:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 示例二:

输入: numRows = 1
输出: [[1]]

思路:

我们可以将杨辉三角图形进行转个方向,改为一个阶梯型的可能更适合我们理解,对于这样的阶梯型的数据,我们很自然就会联想到二维数组,那杨辉三角可不可以用二维数组实现呢?

对于每一行数据,第一个和最后一个都是1,剩下的数据都是上一行的同一位置的数据加上前一个数据,也就是说我们在实现每一行的数据的时候都需要用到上一行的数据。为了更高效的完成上述的过程我们可以使用二维的顺序表代替二维数组进行操作。

在确定了使用二维顺序表后,我们需要定义一个总的顺序表去存放每一行对应的顺序表,用外层for循环确定到底有多少行,用内层for循环确定每一行的元素,以上就确定了本题的大概框架。

对于几个细节需要注意:

总结观察杨辉三角,所有1的位置都是在每一行的开头和结尾,开头很简单内层for循环 j=0 ;的时候就是开头位置,而每一行的最后一个元素,我们仔细观察他的坐标就会发现,他的行数和列数相等,也就是外层for循环的循环变量 i 与内层for循环变量 j 相等的时候,总结来说当循环变量 (j == 0 || j == i) 的时候我们就对行顺序表添加元素 “1” 

对于非1的数据,我们需要访问上一行的数据,通过 .get( i-1) 可以拿到上一行的顺序表,拿到上一行的顺序表后再分别拿到这一行的 j 位置和 j-1 位置的元素,然后相加,相加后的结果就是我们要的值,最后再将这个值使用 .add 添加到这一行的顺序表中就可以

完整代码:

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();for (int i = 0; i < numRows; i++) {//新定义一行List<Integer> row = new ArrayList<>();for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {row.add(1);}else {//添加上一行的数据(上一行的j-1和j位置)row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));}}//每一次将新的一行加入总的二维顺序表中ret.add(row);}return ret;}
}

二.合并俩个有序数组

题目:给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

示例一:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 

示例二:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 

 示例三:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1]

思路:

对于一个数组,我们要将其合并到一个全新的数组中,我们可以使用俩个指针,分别指向俩个数组,然后对比俩个指针谁的值小,小的值就放入新数组中,并且指针后移

对于放入数据一共有4种情况,我们分别对应处理一下:

  1. nums1 的数据小于 nums2 的数据:将 nums1 的数据放入新数组,并且指针pA后移
  2. nums1 的数据大于 nums2 的数据:将 nums2 的数据放入新数组,并且指针pB后移
  3. nums1 的数据已经排除完了,但是 nums2 还有元素:将 nums2 的元素放入新数组,并且指针pB后移
  4.  nums2 的数据已经排除完了,但是 nums1 还有元素:将nums1的元素放入新数组,并且指针pA后移

我们使用一个while循环来包含所有的情况遍历,然后每一次判断都将一个数据通过临时变量放入新数组中,为了和服题目要求,将最后的结果再覆盖到数组1中

完整代码:

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int pA = 0;int pB = 0;int cur = 0;int[] sordNum = new int[m + n];while (pA < m || pB < n) {if (pA == m) {//nums1已满,放入nums2cur = nums2[pB++];} else if (pB == n) {//nums2已满,放入nums1cur = nums1[pA++];} else if (nums1[pA] < nums2[pB]) {//nums1的数据小于nums2cur = nums1[pA++];} else {//nums1的数据大于等于nums2cur = nums2[pB++];}sordNum[pA + pB - 1] = cur;}for (int j = 0; j != m + n; ++j) {nums1[j] = sordNum[j];}}
}

三.删除有序数组中的重复项

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

示例一:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]

示例二:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]

思路:

对于这里的删除,我们可以巧妙的利用,具体来说我们可以将不重复的元素放在数组前面,然后我们只返回这部分不重复的元素,这样就变相的达到了删除的目标

完整代码:

class Solution {public int removeDuplicates(int[] nums) {//快慢指针int left = 0;int right = 1;while(right < nums.length){if(nums[left] != nums[right]){left++;nums[left] = nums[right];}right++;}return left + 1;}
}



  本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见

这篇关于算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/465771

相关文章

MySQL 8 中的一个强大功能 JSON_TABLE示例详解

《MySQL8中的一个强大功能JSON_TABLE示例详解》JSON_TABLE是MySQL8中引入的一个强大功能,它允许用户将JSON数据转换为关系表格式,从而可以更方便地在SQL查询中处理J... 目录基本语法示例示例查询解释应用场景不适用场景1. ‌jsON 数据结构过于复杂或动态变化‌2. ‌性能要

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更