Leetcode周赛 | 2023-8-6

2023-8-6

  • 题1
    • 体会
    • 我的代码
  • 题2
    • 我的超时代码
    • 题目
    • 体会
    • 我的代码
  • 题3
    • 体会
    • 我的代码

题1

在这里插入图片描述
在这里插入图片描述

体会

在这里插入图片描述
这道题完全就是唬人,只要想明白了,只要有两个连续的数的和,大于target,那么一定可以,两边一次切一个就好了。

我的代码

题2

我的超时代码

尽力了,想不出来别的方法,只能通过一半的测试用例,其他超时。

将向左和向下的代码去掉后,因为我觉得向左和向右是无意义的,通过的用例多了一些,但还是超时。

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0self.mm = 0i = j = 0mini = infself.dfs(grid,i,j,mini,note,m,n)return self.mmdef dfs(self,grid,i,j,mini,note,m,n):if i < 0 or i >= m or j < 0 or j >= n :returnif grid[i][j] == 2 :returntemp = [[p[0]-i,p[1]-j] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))if mini <= self.mm :returnif i == m-1 and j == n-1 :self.mm = max(self.mm,mini)return                grid[i][j] = 2self.dfs(grid,i+1,j,mini,note,m,n)self.dfs(grid,i-1,j,mini,note,m,n)self.dfs(grid,i,j+1,mini,note,m,n)self.dfs(grid,i,j-1,mini,note,m,n)grid[i][j] = 0

改成了动态规划的方法,还是解答错误,但是通过的用例更多了
(983 / 1035)

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0dp = [[0]*(n) for _ in range(m)]for i in range(0,m):for j in range(0,n):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == 0 and j != 0:kk = dp[i][j-1]elif j == 0 and i!=0:kk =  dp[i-1][j]elif j == 0 and i==0:kk =  infelse :kk = max(dp[i-1][j],dp[i][j-1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kk#return dpreturn dp[-1][-1]

两次动归也不对。

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0dp = [[0]*(n) for _ in range(m)]for i in range(0,m):for j in range(0,n):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == 0 and j != 0:kk = dp[i][j-1]elif j == 0 and i!=0:kk =  dp[i-1][j]elif j == 0 and i==0:kk =  infelse :kk = max(dp[i-1][j],dp[i][j-1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kkdp2 = [[0]*(n) for _ in range(m)]for i in range(m-1,-1,-1):for j in range(n-1,-1,-1):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == m-1 and j != n-1:kk = dp[i][j+1]elif j == n-1 and i!=m-1:kk =  dp[i+1][j]elif j == n-1 and i==m-1:kk =  infelse :kk = max(dp[i+1][j],dp[i][j+1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kk#return dpreturn max(dp[-1][-1],dp2[-1][-1])

题目

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

体会

在这里插入图片描述
不能用DP的原因:

因为不仅可以向右和向下走,还可以向上和向左,所以不能dp。

从来没接触过这道题的解法,也看不懂。

class UnionFind:def __init__(self, n):self.parent = list(range(n))def find(self, a):a = self.parent[a]acopy = awhile a != self.parent[a]:a = self.parent[a]while acopy != a:self.parent[acopy], acopy = a, self.parent[acopy]return adef merge(self, a, b):pa, pb = self.find(a), self.find(b)if pa == pb: return Falseself.parent[pb] = pareturn Trueclass Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:n = len(grid)dist = [[inf] * n for _ in range(n)]tmp = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j]])for i, j in tmp:dist[i][j] = 0while tmp:i, j = tmp.popleft()for dx, dy in pairwise([-1, 0, 1, 0, -1]):if 0 <= i + dx < n and 0 <= j + dy < n and dist[i+dx][j+dy] == inf:dist[i+dx][j+dy] = dist[i][j] + 1tmp.append((i+dx, j+dy))l, r = 0, 2 * n - 2while l <= r:m = (l + r) // 2union = UnionFind(n * n)for i in range(n):for j in range(n):if dist[i][j] >= m:if i < n - 1 and dist[i+1][j] >= m: union.merge(i * n + j, (i + 1) * n + j)if j < n - 1 and dist[i][j+1] >= m: union.merge(i * n + j, i * n + j + 1)if union.find(0) == union.find(n * n - 1): l = m + 1else: r = m - 1return r

我的代码

题3

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

体会

在这里插入图片描述

class Solution:def findMaximumElegance(self, items: List[List[int]], k: int) -> int:items.sort(reverse=True)chosen = set()to_delete = []tot = 0for i in range(k):x, t = items[i]tot += xif t in chosen: heappush(to_delete, x)else: chosen.add(t)ans = tot + len(chosen) ** 2for i in range(k, len(items)):x, t = items[i]if t not in chosen and len(to_delete):chosen.add(t)tot -= heappop(to_delete)tot += xans = max(ans, tot + len(chosen) ** 2)return ans

我的代码

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/78258.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

应急响应-勒索病毒的处理思路

0x00 关于勒索病毒的描述 勒索病毒入侵方式&#xff1a;服务弱口令&#xff0c;未授权&#xff0c;邮件钓鱼&#xff0c;程序木马植入&#xff0c;系统漏洞等 勒索病毒的危害&#xff1a;主机文件被加密&#xff0c;且几乎难以解密&#xff0c;对主机上的文件信息以及重要资产…

NAT协议(网络地址转换协议)详解

NAT协议&#xff08;网络地址转换协议&#xff09;详解 为什么需要NATNAT的实现方式静态NAT动态NATNAPT NAT技术的优缺点优点缺点 NAT协议是将IP数据报头中的IP地址转换为另外一个IP地址的过程&#xff0c;主要用于实现私有网络访问公有网络的功能。这种通过使用少量的IP地址代…

【源码分析】Nacos自动注册源码分析

文章目录 服务注册&#xff08;AP协议&#xff09;服务发现&#xff08;CP协议&#xff09;Nacos是如何整合到SpringCloudAlibaba的&#xff1f; 服务注册&#xff08;AP协议&#xff09; Nacos提供了NamingService的registerInstance方法来提供服务注册的功能。 因此只要我们…

vue v-slot指令

目录 定义语法使用场景场景一场景二场景三tips只有一个默认插槽时 定义 在Vue中&#xff0c; v-slot 指令用于定义插槽的模板内容。它用于在父组件中传递内容到子组件中的插槽。 v-slot 指令可以用于 标签或组件标签上&#xff0c;以便在子组件中使用插槽。 语法 使用 v-slo…

16-1_Qt 5.9 C++开发指南_多语言界面

文章目录 1. 多语言界面设计概述2. tr()函数的使用3. 生成语言翻译文件4. 使用Qt Linguist 翻译 ts 文件5. 调用翻译文件改变界面语言5.1 生成qm文件5.2 项目启动时设置界面语言5.3 动态切换语言 1. 多语言界面设计概述 有些软件需要开发多语言界面版本&#xff0c;如中文版和…

自动化测试框架?数据驱动vs关键字驱动,该怎么做?

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 对于自动化测试框…

BI报表工具有哪些作用?奥威BI全面剖析数据

BI报表工具有哪些作用&#xff1f;主要的作用是通过整合多业务来源数据&#xff0c;全面分析挖掘数据&#xff0c;来帮助企业实现数据化运营、支持智能决策、实现数据资产沉淀和增值、进行数据挖掘和预测分析、提高数据可读性和数据可视化程度等&#xff0c;从而提高企业的竞争…

【C++学习】STL容器——list

目录 一、list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list 迭代器失效 二、list的模拟实现 2.1 模拟实现list 三、list和vector的对比…

Java版知识付费平台免费搭建 Spring Cloud+Spring Boot+Mybatis+uniapp+前后端分离实现知识付费平台qt

&#xfeff;Java版知识付费源码 Spring CloudSpring BootMybatisuniapp前后端分离实现知识付费平台 提供职业教育、企业培训、知识付费系统搭建服务。系统功能包含&#xff1a;录播课、直播课、题库、营销、公司组织架构、员工入职培训等。 提供私有化部署&#xff0c;免费售…

CNN成长路:从AlexNet到EfficientNet(01)

一、说明 在 10年的深度学习中&#xff0c;进步是多么迅速&#xff01;早在 2012 年&#xff0c;Alexnet 在 ImageNet 上的准确率就达到了 63.3% 的 Top-1。现在&#xff0c;我们超过90%的EfficientNet架构和师生训练&#xff08;teacher-student&#xff09;。 如果我们在 Ima…

【Kubernetes部署篇】基于Ubuntu20.04操作系统搭建K8S1.23版本集群

文章目录 一、集群架构规划信息二、系统初始化准备(所有节点同步操作)三、安装kubeadm(所有节点同步操作)四、初始化K8S集群(master节点操作)五、添加Node节点到K8S集群中六、安装Calico网络插件七、测试CoreDNS可用性 一、集群架构规划信息 pod网段&#xff1a;10.244.0.0/16…

HTTP——九、基于HTTP的功能追加协议

HTTP 一、基于HTTP的协议二、消除HTTP瓶颈的SPDY1、HTTP的瓶颈Ajax 的解决方法Comet 的解决方法SPDY的目标 2、SPDY的设计与功能3、SPDY消除 Web 瓶颈了吗 三、使用浏览器进行全双工通信的WebSocket1、WebSocket 的设计与功能2、WebSocket协议 四、期盼已久的 HTTP/2.01、HTTP/…

卡尔曼滤波 | Matlab实现无迹kalman滤波仿真

文章目录 效果一览文章概述研究内容程序设计参考资料效果一览 文章概述 卡尔曼滤波 | Matlab实现无迹kalman滤波仿真 研究内容 无迹kalman滤波(UKF)不是采用的将非线性函数线性化的做法。无迹kalman仍然采用的是线性kalman滤波的架构,对于一步预测方程,使用无迹变换(UT)来…

visio,word添加缺少字体,仿宋_GB2312、楷体_GB2312、方正小标宋简体等字体下载

一. 内容简介 visio,word添加缺少字体,仿宋_GB2312、楷体_GB2312、方正小标宋简体等字体下载 二. 软件环境 2.1 visio 三.主要流程 3.1 下载字体 http://www.downza.cn/ 微软官方给的链接好多字体没有&#xff0c;其他好多字体网站&#xff0c;就是给你看个样式&#xff…

vue3中CompositionApi理解与使用

CompositionApi&#xff0c;组合式API&#xff0c;相当于react中hooks&#xff0c;函数式。 优势&#xff1a;1&#xff0c;增加了代码的复用性&#xff08;类似mixin&#xff0c;slot&#xff0c;高阶组件功能&#xff09; 2&#xff0c;代码可读性更好。可以将处理逻辑和视图…

Elasticsearch:语义搜索 - Semantic Search in python

当 OpenAI 于 2022 年 11 月发布 ChatGPT 时&#xff0c;引发了人们对人工智能和机器学习的新一波兴趣。 尽管必要的技术创新已经出现了近十年&#xff0c;而且基本原理的历史甚至更早&#xff0c;但这种巨大的转变引发了各种发展的“寒武纪大爆炸”&#xff0c;特别是在大型语…

数字孪生的「三张皮」问题:数据隐私、安全与伦理挑战

引言 随着数字化时代的来临&#xff0c;数据成为了当今社会的宝贵资源。然而&#xff0c;数据的广泛使用也带来了一系列隐私、安全与伦理挑战。数字孪生作为一种虚拟的数字化实体&#xff0c;通过收集和分析大量数据&#xff0c;模拟和预测现实世界中的各种情境&#xff0c;为…

【云原生|Docker系列第3篇】Docker镜像的入门实践

欢迎来到Docker入门系列的第三篇博客&#xff01;在前两篇博客中&#xff0c;我们已经了解了什么是Docker以及如何安装和配置它。本篇博客将重点介绍Docker镜像的概念&#xff0c;以及它们之间的关系。我们还将学习如何拉取、创建、管理和分享Docker镜像&#xff0c;这是使用Do…

循环结构进阶

二重循环 import java.util.Scanner;public class Demo01 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 二重循环 外循环班级 内循环学生for (int i1; i<3; i) { // 外循环班级System.out.println("请输入第" i "…

Leetcode-每日一题【剑指 Offer 17. 打印从1到最大的n位数】

题目 一只青蛙一次可以跳上1级台阶&#xff0c;也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97&#xff08;1000000007&#xff09;&#xff0c;如计算初始结果为&#xff1a;1000000008&#xff0c;请返回 1。 示例 1&#xff1a; 输…