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

这篇具有很好参考价值的文章主要介绍了算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享


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

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

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

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

目录

一.杨辉三角

思路:

完整代码:

二.合并俩个有序数组

思路:

完整代码:

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

思路:

完整代码:


一.杨辉三角

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

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

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

示例一:

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

 示例二:

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

思路:

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

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

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

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

对于几个细节需要注意:

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

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

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

完整代码:

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]

思路:

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

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

对于放入数据一共有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已满,放入nums2
                cur = nums2[pB++];
            } else if (pB == n) {//nums2已满,放入nums1
                cur = nums1[pA++];
            } else if (nums1[pA] < nums2[pB]) {//nums1的数据小于nums2
                cur = nums1[pA++];
            } else {//nums1的数据大于等于nums2
                cur = 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]

思路:

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

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享

完整代码:

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;
    }
}



 算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享 本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项,算法题库,Java_SE,算法,windows,数据结构,java,经验分享文章来源地址https://www.toymoban.com/news/detail-751320.html

到了这里,关于算法详解:杨辉三角 | 合并俩个有序数组 | 删除有序数组中的重复项的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C练习——杨辉三角

    题目: 打印近似杨辉三角,行数n自选 百度找的杨辉三角,参考一下: 解析: 把它的全部元素左对齐,就可以看成近似杨辉三角的样子 1 1  1 1  2  1 1  3  3  1 1  4  6  4  1 ……  每个数等于它上方两数之和 每行数字左右对称,由1开始逐渐变大 行数与列数相同,第n行有

    2024年01月17日
    浏览(36)
  • 打印杨辉三角

    这个公式,不好算,我觉得还是杨辉三角算起来方便:c#代码如下:    double 打印杨辉三角(int n)//n必须是偶数,展开项是n+1,中间项是n/2,此处返回中间项的概率202306131722         {             //for (int i = 0; i n; i++)             //{             //    //这种方法直接算,使

    2024年02月09日
    浏览(36)
  • 每日一题,杨辉三角

    给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。 示例 1: 示例 2:

    2024年02月04日
    浏览(36)
  • [LeetCode] #118 杨辉三角

    给定一个非负整数  numRows , 生成「杨辉三角」的前  numRows   行。 在「杨辉三角」中, 每个数是它左上方和右上方的数的和。 杨辉三角:  

    2024年02月15日
    浏览(34)
  • 动态规划-杨辉三角

    该算法题分别是: 118. 杨辉三角。 119. 杨辉三角 II 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 1.2.1 示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 1.2.2 示例 2: 输入: numRows = 1 输出: [[1]] 1.2.3 提示: 1 = numRows = 30 来源:力扣(LeetCode) 链接:https://

    2024年02月13日
    浏览(40)
  • 【LeetCode】118. 杨辉三角

    题目链接 直觉解法: 以下的理论介绍 可以说和 本题的 代码实现 毫无关系。 这个版本 需要注意 列表的边界 思路: 前一行 两端 补0 模拟。 结合 动图 理解 题目 说明至少 一行,可以跳过 第一行的处理 官方版本

    2024年02月07日
    浏览(38)
  • 杨辉三角(Java)

     实现思路:我们可以先把杨辉三角想象成一个空的二维数组,然后再给它赋值输出即可。 关键在于如何赋值:仔细观察上图可以得出除了 每一行第一个数以及最后一个数(都是1) , 中间的数字规律就是: a[ i ][ j ] = a[ i - 1 ][ j - 1 ] + a[ i - 1 ][ j ] 实现代码: 相信大家更多的

    2024年02月08日
    浏览(35)
  • 【C语言】-- 杨辉三角

    目录 一.什么是杨辉三角? 二.实现方法 1.直角三角形版 2.等腰三角形版 杨辉三角形,又称贾宪三角形,帕斯卡三角形,是二项式系数在三角形中的一种几何排列。 形如: 我们不难看出其存在明显的规律。 即:图片的 两个斜边都是数字1 , 其余的数都等于 它所在层的肩上(

    2024年02月13日
    浏览(45)
  • LC-杨辉三角-记忆版

    上一篇:LC-杨辉三角 上一篇讲了杨辉三角的算法,不过之前的算法存在一个问题,比如: 我们可以看到计算a[5][3]和a[5][4]时都需要a[4][3]的值,之前我们是需要每次用到都重新计算,这样就比较耗时,有没有办法记住已经算过的值呢,当下次用的时候直接获取就不用重新计算

    2024年02月13日
    浏览(34)
  • leetcode-杨辉三角ii

    119. 杨辉三角 II 题解: 首先,我们需要创建一个列表来存储杨辉三角的每一行。 然后,我们需要计算每一行的元素。每一行的每个元素都是上一行的两个相邻元素的和。第一个和最后一个元素总是1。 最后,我们返回第rowIndex行。

    2024年01月19日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包