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
}

相关内容

热门资讯

安卓系统所有手机通用,揭秘所有... 你有没有发现,现在市面上各种各样的手机,品牌琳琅满目,让人挑花了眼?不过,不管你用的是哪个品牌的手机...
安卓系统变ios系统好用吗,体... 你有没有想过,为什么有些人从安卓手机换到了苹果的iPhone,而且好像换了之后整个人都精神焕发呢?没...
华为安卓系统文件删除,轻松掌握... 你有没有遇到过这种情况?手机里的文件突然不见了,尤其是华为安卓系统里的那些重要文件,真是让人心头一紧...
安卓1.5系统软件,初代智能革... 你有没有想过,手机里的那些看似普通的系统,其实背后藏着无数的故事呢?今天,就让我带你走进安卓1.5系...
安卓 代替系统音效设置,打造个... 你有没有发现,手机里的那些系统音效有时候真的让人有点烦躁呢?比如那个每次接电话时“叮咚”一声,或者是...
安卓系统整体性,构建移动设备的... 你知道吗?在智能手机的世界里,安卓系统就像是个全能的魔术师,它不仅拥有丰富的魔法,还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过,在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢?没错,就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过,用手机也能轻松编曲?没错,就是那个你每天不离手的安卓系统手机!现在,我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现,现在的车载导航系统越来越智能了?尤其是那些搭载了安卓系统的车载导航,简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了,这可怎么办?别急,今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗,这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...