最近周赛的压轴题都是dp,总结一下
leetcode-trie树专题
trie树,又称单词查找树,前缀树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计,自动补全等。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
leetcode 第24场双周赛
哎 每次都只能做出来前前前前面三道,左后一道永远卡住,永远排名几百
leetcode 55 跳跃游戏, 45 跳跃游戏II
leetcode 678 有效的括号字符串
给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
- 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
一个空字符串也被视为有效字符串。
字符串大小将在 [1,100] 范围内。
leetcode 649 Dota2 参议员
Dota2 的世界里有两个阵营:Radiant(天辉)和 Dire(夜魇)
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中,每一位参议员都可以行使两项权利中的一项:
禁止一名参议员的权利:
参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。宣布胜利:
如果参议员发现有权利投票的参议员都是同一个阵营的,他可以宣布胜利并决定在游戏中的有关变化。
leetcode 面试题16.03 交点
给定两条线段(表示为起点$start = {X1, Y1}$和终点 $end = {X2, Y2}$ ),如果它们有交点,请计算其交点,没有交点则返回空值。
要求浮点型误差不超过$10^{-6}$。若有多个交点(线段重叠)则返回 X 值最小的点,X 坐标相同则返回 Y 值最小的点。
leetcode 355 设计推特
设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近十条推文。你的设计需要支持以下的几个功能:
postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户
二维费用的背包问题
完全背包问题的模型如下:
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 $v_i$,重量是 $m_i$,价值是 $w_i$。求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值。
混合背包
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
- 第一类物品只能用1次(s<0时)(01背包);
- 第二类物品可以用无限次(s=0时)(完全背包);
- 第三类物品最多只能用 $s_i$ 次(s>0时)(多重背包);
每种体积是 $v_i$,价值是 $w_i$。
- 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。