动态规划算法 - LC354. 俄罗斯套娃信封问题

这篇具有很好参考价值的文章主要介绍了动态规划算法 - LC354. 俄罗斯套娃信封问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

354. 俄罗斯套娃信封问题

困难

给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

注意:不允许旋转信封。

前言

这道题是最长上升子序列的变种题,难点在于:首先需要先对给定的二维数组进行排序后,再求上升子序列。

题解

首先贴出经典的解法,动态规划求上升子序列。

func maxEnvelopes(envelopes [][]int) int {
	n := len(envelopes)
	// w升序,h降序
	sort.Slice(envelopes, func(i, j int) bool {
		ei, ej := envelopes[i], envelopes[j]
		return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
	})

	var dp = make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
	}
	// var res int
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if envelopes[i][1] > envelopes[j][1] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		// res = max(res, dp[i])
	}
	return max(dp...)
}

func max(a ...int) int {
	res := a[0]
	for _, v := range a[1:] {
		if v > res {
			res = v
		}
	}
	return res
}

但是很遗憾,昨天发现这个解法已经无法通过leetcode的所有测试用例了(之前是可以的),看了下官方的题解,原来是出了新的方法求上升子序列,通过二分查找的方式,时间复杂度更低。

func maxEnvelopes(envelopes [][]int) int {
	//n := len(envelopes)
	// w升序,h降序
	sort.Slice(envelopes, func(i, j int) bool {
		ei, ej := envelopes[i], envelopes[j]
		return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
	})

	var dp = make([]int, 0)
	for i := range envelopes {
		h := envelopes[i][1]
		idx := sort.SearchInts(dp, h)
		if idx < len(dp) {
			dp[idx] = h
		} else {
			dp = append(dp, h)
		}
	}

	return len(dp)
}

题解虽然看起来更简单,其实是因为golang已经内置实现sort.SearchInts函数,通过这个函数可以找到h在上升数组dp中的index下标:

(1)如果h在dp中存在,则返回h对应的下标。

(2)如果h大于dp中最大元素,则返回下标=len(dp) (注意⚠️这个下标直接索引会越界),否则返回最小的严格大于h的元素的下标文章来源地址https://www.toymoban.com/news/detail-849076.html

到了这里,关于动态规划算法 - LC354. 俄罗斯套娃信封问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • pygame俄罗斯方块游戏

    1.安装python 2.引入游戏库pygame 3.引入随机数 俄罗斯方块初始形状 这里使用一个二维数组 用来标记俄罗斯相对应的方块形状 代码如下: 游戏移动方向是否可能判断 这里为了不让他出现穿墙,跨过方块下落 都做对应的碰撞判断 具体代码如下: 俄罗斯方块旋转变形代码实现 俄

    2024年02月08日
    浏览(46)
  • c语言——俄罗斯方块

    俄罗斯方块是久负盛名的游戏,它也和贪吃蛇,扫雷等游戏位列经典游戏的⾏列。 《俄罗斯方块》(Tetris,俄文:Тетрис)是一款由俄罗斯人阿列克谢·帕基特诺夫于1984年6月发明的休闲游戏。 该游戏曾经被多家公司代理过。经过多轮诉讼后,该游戏的代理权最终被任天堂

    2024年02月05日
    浏览(46)
  • python制作俄罗斯方块

    作者简介 :一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。 座右铭 :未来是不可确定的,慢慢来是最快的。 个人主页 :极客李华-CSDN博客 合作方式 :私聊+ 这个专栏内容 :BAT等大厂常见后端java开发面试题详细讲解,更新数目10

    2024年02月12日
    浏览(51)
  • 用Pygame写俄罗斯方块

    此文章参考的是吃饭超人的文章 首先我们先打开cmd输入如下令命 然后打开python或者pycharm 输入如下代码

    2024年02月12日
    浏览(39)
  • 用python制作俄罗斯方块

    代码如下,可以直接运行:

    2024年02月11日
    浏览(53)
  • 俄罗斯方块游戏(C语言)

    简介:俄罗斯方块(Tetris)是一款经典的游戏,下面是用C语言实现俄罗斯方块的示例代码: code 这是一个非常简单的俄罗斯方块游戏,只有基本的方块形状和控制操作。如果想要更加完整的游戏体验,可以添加更多的方块形状、音效、背景音乐、计分系统等等。 分析 这份代

    2024年02月07日
    浏览(45)
  • 俄罗斯方块小游戏开发

    代码图: 结果图:

    2024年02月04日
    浏览(56)
  • Javascript 俄罗斯方块 游戏代码

    本俄罗斯方块代码采用 JavaScript 脚本代码写成,简单易懂; 全代码采用静态类及静态变量成员组成; 全脚本通过实现代码全局配置 OLSFK.Options = {...} 定义方块起始坐标及定义各自的旋转点; 从初始化俄罗斯方块界面开始,再监听键盘事件;以及左右,向下及旋转动作判断,

    2024年02月07日
    浏览(48)
  • [C#] 简单的俄罗斯方块实现

    一个控制台俄罗斯方块游戏的简单实现. 已在 github.com/SlimeNull/Tetris 开源. 很简单, 一个二维数组存储当前游戏的方块地图, 用 bool 即可, true 表示当前块被填充, false 表示没有. 然后, 抽一个 “形状” 类, 形状表示当前玩家正在操作的一个形状, 例如方块, 直线, T 形什么的. 一个形

    2024年02月13日
    浏览(40)
  • Java小游戏-俄罗斯方块

    摘 要 随着时代的不断发展,个人电脑也在不断普及,一些有趣的桌面游戏已经成为人们在使用计算机进行工作或工作之余休闲娱乐的首选,从最开始的Windows系统自带的黑白棋、纸牌、扫雷等游戏开始,到现在目不暇接的各种游戏,游戏已经成为人们在使用计算机进行工作或

    2024年02月03日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包