没有合适的资源？快使用搜索试试~ 我知道了~

首页"宫水三叶的刷题日记：序列 DP合集-优先推荐指数，从简到难，持续更新"

"宫水三叶的刷题日记：序列 DP合集-优先推荐指数，从简到难，持续更新"

需积分: 0 0 下载量 79 浏览量更新于2024-03-25 收藏 2.04MB PDF 举报

The Serial DP1 in the brushing diary of Gong Shui San Ye; 2. Find "Serial DP" from the category directory in the sidebar; 3. Brush the questions in order of "recommended index" from high to low, and if the recommended index is the same, then according to the difficulty from easy to hard; 4. After getting the question number, go back to this collection for verification; 🍭 For more exciting content, please follow: WeChat Official Account / Github / LeetCode / Zhihu. This is the original special topic of the WeChat Official Account "Gong Shui San Ye's Brushing Diary" - "Serial DP" collection. The last update of this collection was on October 7, 2021, and it will be updated every 2-4 weeks. Follow the Official Account and reply "Serial DP" to the background to get the latest download link. 💡💡 Below are the best practices for using this collection: Learning algorithms: 1. Open the online directory (Github version) and find "Serial DP" in the sideba.

代码：

class Solution {

int[] tree;

int lowbit(int x) {

return x & -x;

}

public int maxEnvelopes(int[][] es) {

int n = es.length;

if (n == 0) return n;

// 由于我们使用了 g 记录高度，因此这里只需将 w 从小到达排序即可

Arrays.sort(es, (a, b)->a[0] - b[0]);

// 先将所有的 h 进行离散化

Set<Integer> set = new HashSet<>();

for (int i = 0; i < n; i++) set.add(es[i][1]);

int cnt = set.size();

int[] hs = new int[cnt];

int idx = 0;

for (int i : set) hs[idx++] = i;

Arrays.sort(hs);

for (int i = 0; i < n; i++) es[i][1] = Arrays.binarySearch(hs, es[i][1]) + 1;

// 创建树状数组

tree = new int[cnt + 1];

// f(i) 为考虑前 i 个物品，并以第 i 个物品为结尾的最大值

int[] f = new int[n];

int ans = 1;

for (int i = 0, j = 0; i < n; i++) {

// 对于 w 相同的数据，不更新 tree 数组

if (es[i][0] != es[j][0]) {

// 限制 j 不能越过 i，确保 tree 数组中只会出现第 i 个信封前的「历史信封」

while (j < i) {

for (int u = es[j][1]; u <= cnt; u += lowbit(u)) {

tree[u] = Math.max(tree[u], f[j]);

}

j++;

}

f[i] = 1;

for (int u = es[i][1] - 1; u > 0; u -= lowbit(u)) {

f[i] = Math.max(f[i], tree[u] + 1);

}

ans = Math.max(ans, f[i]);

}

return ans;

}

• 时间复杂度：处理每个物品时更新「树状数组」复杂度为O(log n)。整体复杂度为

O(n log n)

• 空间复杂度：O(n)

🍭

更多精彩内容，欢迎关注：公众号 / Github / LeetCode / 知乎 **

题题目描述目描述

这是 LeetCode 上的 368. 最大整除子集最大整除子集，难度为中等中等。

Tag : 「序列 DP」

给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，

子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或

• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]

输出：[1,2]

解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]

输出：[1,2,4,8]

剩余57页未读，继续阅读

胡说先森

粉丝: 577
资源: 280

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

"宫水三叶的刷题日记：序列 DP合集-优先推荐指数，从简到难，持续更新"

"宫水三叶的刷题日记：线性DP1，推荐指数从大到小刷题

GSM-R系统业务触发详解：从DP1到DP5

易语言数据操作支持库一2.0#50版特性介绍

[宫水三叶的刷题日记]：线性 DP1

[宫水三叶的刷题日记]：状压 DP1

[宫水三叶的刷题日记]：背包 DP1

[宫水三叶的刷题日记]：数位DP1

[宫水三叶的刷题日记]：状态机 DP1

dp1-2020-g3-12:dp1-2020-g3-12由GitHub Classroom创建

dp1-2020-g2-02：dp1-2020-g2-02由GitHub Classroom创建

最新资源