动态规划算法 - 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模板网!

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

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

相关文章

  • c语言——俄罗斯方块

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

    2024年02月05日
    浏览(44)
  • pygame俄罗斯方块游戏

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

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

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

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

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

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

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

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

    代码图: 结果图:

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

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

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

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

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

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

    2024年02月13日
    浏览(35)
  • 前端技术搭建俄罗斯方块(内含源码)

    上周我们实通过前端基础实现了扫雷游戏,今天还是继续按照我们原定的节奏来带领大家完成俄罗斯方块游戏,功能也比较简单简单,也是想借助这样一个简单的功能,然后来帮助大家了解我们JavaScript在前端中的作用, 在前面的文章当中我们也提及到我们在本系列的专栏是

    2024年02月08日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包