leetcode 天池X LeetCode
admin
2024-03-30 08:05:33
0

leetcode 算法天池举办,菜鸡总结一下吧。

221021天池-02. 光线反射

这道题还是比较简单的,直接就是一个暴搜。会有下面的性质方便编码,假设当前的位置是(x, y) , x增量和y的增量是(dirx, diry):

  • 如果是L镜子,那么会把原来的增量改变为(diry, dirx), 并且移动到(x + diry, y + dirx)的格子。
  • 如果是R镜子,那么会把原来的增量改变为(-diry, -dirx), 并且移动到(x - diry, y - dirx)的格子。
  • 否则,增量不变,移动到(x + dirx, y + diry)的格子。

也就是说,这里的增量可以表示一种朝向,初始增量为(1, 0),表示朝下走。碰见左镜子,增量为(0, 1),就变成朝右走了。同理如果朝上走的光为(-1, 0), 碰见左镜子,就会向左走(0, -1)。也就是增量为(0, -1)。这样可以总结为上面的规律。

代码就很简单了。

class Solution {
public:int n, m;vectorgrid;int dfs(int dirx, int diry, int x, int y) {if (x < 0 || x == n || y < 0 || y == m) {return 0;}if (grid[x][y] == 'L') {return dfs(diry, dirx, x + diry, y + dirx) + 1;} else if (grid[x][y] == 'R') {return dfs(-diry, -dirx, x - diry, y - dirx) + 1;} else {return dfs(dirx, diry, x + dirx, y + diry) + 1; }}int getLength(vector& grid) {n = grid.size(), m = grid[0].size();this->grid = grid;return dfs(1, 0, 0, 0);}
};

[221021天池-03. 整理书架](221021天池-03. 整理书架)

题目很简单,但是我没想到,以为是子序列的题目,最后发现是单调栈。忏愧,学的还是不扎实。

字典序最小,那么如果前面的比后面的大,前面的还能仍的话,就可以直接丢弃了。这样字典序是最小的。

实现方面的话,需要统计每一个字符还剩下多少,还有就是需要统计每一个字符在栈里有多少,如果大于等于limit了,就直接扔掉就行了。

class Solution {
public:        vector arrangeBookshelf(vector& order, int limit) {unordered_mapleft;                // 总共剩下的数量,也就是总的减去 丢掉 的。int n = order.size();for (int x : order) {left[x]++;}stacks;unordered_mapinS;for (int x: order) {if (inS[x] == limit) {left[x]--;continue;}while(!s.empty() && s.top() > x && left[s.top()] > limit) { // 栈顶元素大直接删除,但是需要足够数量left[s.top()]--;inS[s.top()]--;s.pop();}s.push(x);inS[x]++;}vectorans;while (!s.empty()) {ans.push_back(s.top()); s.pop(); }reverse(ans.begin(), ans.end());return ans;}
};

221021天池-04. 意外惊喜

初始一看以为是分组背包问题,高兴了一下,结果写完代码,直接tle。真的是意外惊喜,还是两个意外惊喜。这个和2218. 从栈中取出 K 个硬币的最大面值和题目很类似,但是数据量比他大,并且多了一个递增的条件。就不能使用分组背包的代码了。

先放上代码,题解明天在写吧。

package main// https://space.bilibili.com/206214
func brilliantSurprise(a [][]int, lim int) (ans int) {dp := make([]int, lim+1)var f func([][]int, []int)f = func(a [][]int, tot []int) {if len(a) == 1 {s := 0for i, v := range a[0] {if i >= lim {break}s += vans = max(ans, dp[lim-(i+1)]+s)}return}tmp := append([]int{}, dp...)m := len(a) / 2for i, r := range a[:m] {for j := lim; j >= len(r); j-- {dp[j] = max(dp[j], dp[j-len(r)]+tot[i])}}f(a[m:], tot[m:])dp = tmpfor i, r := range a[m:] {for j := lim; j >= len(r); j-- {dp[j] = max(dp[j], dp[j-len(r)]+tot[m+i])}}f(a[:m], tot[:m])}tot := make([]int, len(a))for i, r := range a {for _, v := range r {tot[i] += v}}f(a, tot)return
}func max(a, b int) int {if b > a {return b}return a
}

相关内容

热门资讯

nova 4刷安卓系统,体验全... 最近手机界可是热闹非凡呢!听说华为nova 4要刷安卓系统了,这可真是让人兴奋不已。你有没有想过,你...
如果当初没有安卓系统,科技世界... 想象如果没有安卓系统,我们的生活会是怎样的呢?是不是觉得有点不可思议?别急,让我们一起穿越时空,探索...
安卓电视装win系统,系统转换... 亲爱的读者们,你是否曾想过,在你的安卓电视上装一个Windows系统,让它瞬间变身成为一台功能强大的...
安卓手机还原系统好处,重拾流畅... 你有没有遇到过安卓手机卡顿、运行缓慢的情况?别急,今天就来给你揭秘一下安卓手机还原系统的那些好处,让...
安卓系统能跑win吗,探索跨平... 你有没有想过,你的安卓手机里能不能装上Windows系统呢?这听起来是不是有点像科幻电影里的情节?别...
安卓车载系统蓝牙设置,畅享智能... 你有没有发现,现在开车的时候,手机和车载系统之间的互动越来越频繁了呢?这不,今天就来给你详细说说安卓...
奥利奥安卓系统,探索新一代智能... 你有没有想过,一块小小的奥利奥饼干竟然能和强大的安卓系统扯上关系?没错,今天就要来聊聊这个跨界组合,...
微信使用安卓系统,功能解析与操... 你有没有发现,现在用微信的人越来越多了呢?尤其是安卓系统的用户,简直就像潮水一样涌来。今天,就让我带...
体验最新原生安卓系统,极致体验... 你有没有想过,手机系统就像是我们生活的调味品,有时候换一种口味,生活都会变得有趣起来呢?最近,我体验...
安卓系统能玩原神,尽享奇幻冒险... 你有没有想过,在安卓系统上也能畅玩《原神》这样的热门游戏呢?没错,就是那个画面精美、角色丰富、玩法多...
安卓写手机银行系统,基于安卓平... 你有没有想过,手机银行系统在我们日常生活中扮演了多么重要的角色呢?每天刷刷手机,就能轻松管理账户,转...
僵尸之夜恐怖安卓系统,揭秘恐怖... 僵尸之夜,恐怖安卓系统来袭!想象一个寂静的夜晚,你正沉浸在美梦中,突然,一阵诡异的铃声打破了夜的宁静...
谷歌框架和安卓系统,构建智能移... 你有没有想过,为什么你的手机那么聪明,能帮你找到路线,还能帮你拍出美美的照片呢?这都要归功于一个超级...
安卓系统和oppo系统哪个流畅... 你有没有想过,手机系统哪个更流畅呢?安卓系统和OPPO系统,这两个名字听起来就让人心动。今天,咱们就...
安卓怎么用微软系统,利用微软系... 你是不是也和我一样,对安卓手机上的微软系统充满了好奇?想象那熟悉的Windows界面在你的安卓手机上...
安卓系统如何安装nfc,安卓系... 你有没有想过,用手机刷公交卡、支付账单,是不是比掏出钱包来得酷炫多了?这就得归功于NFC技术啦!今天...
ios系统可以转安卓,跨平台应... 你有没有想过,你的iPhone手机里的那些宝贝应用,能不能搬到安卓手机上继续使用呢?没错,今天就要来...
iOSapp移植到安卓系统,i... 你有没有想过,那些在iOS上让你爱不释手的app,是不是也能在安卓系统上大放异彩呢?今天,就让我带你...
现在安卓随便换系统,探索个性化... 你知道吗?现在安卓手机换系统简直就像换衣服一样简单!没错,就是那种随时随地、随心所欲的感觉。今天,就...
安卓系统安装按钮灰色,探究原因... 最近发现了一个让人头疼的小问题,那就是安卓手机的安装按钮突然变成了灰色,这可真是让人摸不着头脑。你知...