[LeetCode周赛复盘] 第 103 场双周赛20230429

[LeetCode周赛复盘] 第 103 场双周赛20230429

    • 一、本周周赛总结
    • 2656. K 个元素的最大和
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 2657. 找到两个数组的前缀公共数组
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 2658. 网格图中鱼的最大数目
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 2659. 将数组清空
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 参考链接

一、本周周赛总结

  • T1 贪心等差数列求和。
  • T2 哈希表模拟。
  • T3 最大权连通分量。
  • T4 树状数组。
    在这里插入图片描述

2656. K 个元素的最大和

2656. K 个元素的最大和

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 不难看出每次都应该选最大的值。
  • 且每次更新完后最大值+1。
  • 那么最后的结果就是选k个数,从mx开始直到mx+k-1

3. 代码实现

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        return (mx+mx+k-1)*k // 2 

2657. 找到两个数组的前缀公共数组

2657. 找到两个数组的前缀公共数组

1. 题目描述

在这里插入图片描述

2. 思路分析

 通过样例可以看出来,公共元组不考虑下标,即跟元素顺序无关,数相同即可。
  • 当跟顺序无关时,一般考虑排序或者计数。这题显然计数更合适。
  • 由于AB都是0~n-1的排列,即不重复,那么前缀出现相同元素,则数量一定是2。
  • 那么无脑cnt,出现2就贡献一个答案即可。

3. 代码实现

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        cnt = Counter()
        ans = []
        s = 0
        for x,y in zip(A,B):
            cnt[x] += 1
            if cnt[x] == 2:
                s += 1
            cnt[y] += 1
            if cnt[y] == 2:
                s += 1
            ans.append(s)
        return ans 

2658. 网格图中鱼的最大数目

2658. 网格图中鱼的最大数目

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 这题放在T3还标个hard,可能是出题人摆烂了吧。
  • 200. 岛屿数量

3. 代码实现

DIRS = ((0,1),(0,-1),(1,0),(-1,0))
class Solution:
    def findMaxFish(self, g: List[List[int]]) -> int:
        m,n = len(g),len(g[0])
        def inside(x,y):
            return 0<=x<m and 0<=y<n 
        
        def bfs(x,y):
            s = g[x][y]
            if not s :
                return 0
            g[x][y] = 0 
            q = deque([(x,y)])
            while q:
                x,y = q.popleft()
                for dx,dy in DIRS:
                    a,b = x+dx,y+dy 
                    if inside(a,b) and g[a][b]:
                        s += g[a][b]
                        g[a][b] = 0
                        q.append((a,b))
            return s         
       
        return max(bfs(i,j) for i in range(m) for j in range(n)) 

2659. 将数组清空

2659. 将数组清空

1. 题目描述

在这里插入图片描述

在这里插入图片描述

2. 思路分析

  • 观察发现,数据操作过程中,大小关系相邻的元素,相对位置在循环里是不变的。
  • 那么处理完pre开始处理cur时,只需要分类讨论下标:
    • pre在cur前边,则只需要移动一下这之间的数。然后删除cur。
    • pre在cur后边,那需要移动这俩数外边的所有数。
  • 发现数字大小关系确定即可,数字值不重要。
  • 因此用树状数组维护每个下标上有几个数(初始一个,删除则-1)。
  • 然后计算两个区间内的数字数量即可。

3. 代码实现

class BinIndexTree:
    def __init__(self, size_or_nums):  # 树状数组,下标需要从1开始
        # 如果size 是数字,那就设置size和空数据;如果size是数组,那就是a
        if isinstance(size_or_nums, int):
            self.size = size_or_nums
            self.c = [0 for _ in range(self.size + 5)]
            # self.a = [0 for _ in range(self.size + 5)]
        else:
            self.size = len(size_or_nums)
            # self.a = [0 for _ in range(self.size + 5)]
            self.c = [0 for _ in range(self.size + 5)]
            for i, v in enumerate(size_or_nums):
                self.add_point(i + 1, v)

    def add_point(self, i, v):  # 单点增加,下标从1开始
        # self.a[i] += v
        while i <= self.size:
            self.c[i] += v
            i += i & -i

    def sum_interval(self, l, r):  # 区间求和,下标从1开始,计算闭区间[l,r]上的和
        return self.sum_prefix(r) - self.sum_prefix(l - 1)

    def sum_prefix(self, i):  # 前缀求和,下标从1开始
        s = 0
        while i >= 1:
            s += self.c[i]
            # i -= i&-i
            i &= i - 1
        return s   

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        tree = BinIndexTree(n)
        for i in range(1,n+1):
            tree.add_point(i,1)
        
        p = 1
        for _,i in sorted([(v,i) for i,v in enumerate(nums,start=1)]):
            if i >= p:
                ans += tree.sum_interval(p,i)
            else:
                ans += tree.sum_prefix(i) + tree.sum_interval(p,n)
       
            tree.add_point(i,-1)
            p = i 
        return ans       

参考链接

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Docker consul

目录 一、Docker consul的容器服务和发现 ①服务注册与发现的含义 ②什么是consul 二、服务部署 ①部署consul服务 &#xff08;1&#xff09;查看集群信息 &#xff08;2&#xff09;通过http api获取集群信息 ②部署registrator服务器 &#xff08;1&#xff09;安装…

计算机视觉毕业后找不到工作怎么办?怒刷leetcode,还是另寻他路?

文章目录 一、计算机视觉毕业后找不到工作怎么办&#xff1f;二、大环境&#xff1a;前两年的泡沫太大三、还是要把自己的基本功搞扎实&#xff0c;真正的人才什么时候都紧缺四、转换思路&#xff0c;另投他坑五、要有毅力&#xff0c;心态放平六、最后的建议 一、计算机视觉毕…

应急加固初试(windows sever 2008)

前言 红中(hong_zh0) CSDN内容合伙人、2023年新星计划web安全方向导师、 华为MindSpore截至目前最年轻的优秀开发者、IK&N战队队长、 吉林师范大学网安大一的一名普通学生、搞网安论文拿了回大挑校二、 阿里云专家博主、华为网络安全云享专家、腾讯云自媒体分享计划博主 …

【服务器】威联通NAS文件共享 - 搭建SFTP服务并内网穿透实现在外远程访问

Yan-英杰的主页 悟已往之不谏 知来者之可追 C程序员&#xff0c;2024届电子信息研究生 目录 前言 1. 威联通NAS启用SFTP 2. 测试局域网访问 3. 内网穿透 3.1 威联通安装cpolar内网穿透 3.2 创建隧道 3.3 测试公网远程访问 4. 配置固定公网TCP端口地址 4.1 保留一个固定TCP…

chatGPT+Midjourney制作绘画本

chatGPTMidjourney制作绘画本 灵感来源&#xff1a;https://www.bilibili.com/video/BV1N24y1F7ga/?spm_id_from888.80997.embed_other.whitelist&vd_source6dd97671c42eb7cf111063714216bd0b 最终效果&#xff1a; 绘本故事 故事塑造能力弱的人可以使用chatGPT来帮助编…

JAVAWeb11-服务器渲染技术 -JSP-01-JSP基础

1. 现状 1、JSP 使用情况 2、Thymeleaf 使用情况, 通常和 SpringBoot 结合(也会讲) 3、Vue 使用情况 2. 学 JSP 前&#xff0c;老师要说的几句话 目前主流的技术是 前后端分离 (比如: Spring Boot Vue/React), 我们会讲的.[看一下]JSP 技术使用在逐渐减少&#xff…

C. Maximum Subrectangle(思维 + 考察两个数组相乘得到的矩阵的含义)

Problem - C - Codeforces 给定两个正整数数组 a 和 b&#xff0c;长度分别为 n 和 m。 定义矩阵 c 为一个 nm 的矩阵&#xff0c;其中 ci,jai⋅bj。 你需要在矩阵 c 中找到一个子矩形&#xff0c;使得它的元素之和最多为 x&#xff0c;并且它的面积&#xff08;即元素总数&a…

【Redis】Redis分布式锁的10个坑

文章目录 前言1. 非原子操作&#xff08;setnx expire&#xff09;2.被别的客户端请求覆盖&#xff08; setnx value为过期时间&#xff09;3. 忘记设置过期时间4. 业务处理完&#xff0c;忘记释放锁5. B的锁被A给释放了6. 释放锁时&#xff0c;不是原子性7. 锁过期释放&…

【Linux内核解析-linux-5.14.10-内核源码注释】MM内存管理内核启动初始化源码解析

源码 这是Linux内核中的mm_init函数的代码&#xff0c;其作用是初始化内存管理相关的组件和数据结构。 static: 这是一个函数声明修饰符&#xff0c;表示该函数只在当前文件中可见。 void __init: 这是函数的返回类型和修饰符&#xff0c;表示该函数是内核初始化代码。 page…

Redis缓存(双写一致性问题)

Redis缓存&#xff08;双写一致性问题&#xff09; 1 什么是缓存?1.1 为什么要使用缓存1.2 如何使用缓存 2 添加缓存2.1 、缓存模型和思路2.2、代码如下 3 缓存更新策略3.1 、数据库缓存不一致解决方案&#xff1a;3.2 、数据库和缓存不一致采用什么方案 4 实现商铺和缓存与数…

( 字符串) 647. 回文子串 ——【Leetcode每日一题】

❓647. 回文子串 难度&#xff1a;中等 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&#xff0c;即使…

作业区域工服穿戴识别算法 yolov7

作业区域工服穿戴识别系统基于yolov7视频智能图像识别技术&#xff0c;作业区域工服穿戴识别算法模型利用深度学习技术&#xff0c;不需人为干预自动识别现场施工作业人员未按要求穿工作服行为&#xff0c;代替后台工作人员执勤时的人眼判断。YOLOv7 研究团队提出了基于 ELAN 的…

浅谈网络流

网络流 流网络&#xff1a; G ( V , E ) G(V,E) G(V,E)是一个有向图&#xff0c;网络中有两个特殊点&#xff1a;源点s与汇点t。容量用 c c c表示&#xff0c;流量用 f f f表示 流网络G中满足两个性质&#xff1a;1、容量限制(通过一条边的流量不会超过该边的容量)&#xff…

音视频技术开发周刊 | 291

每周一期&#xff0c;纵览音视频技术领域的干货。 新闻投稿&#xff1a;contributelivevideostack.com。 谷歌将 AI 芯片团队并入云计算部门 追赶微软和亚马逊 OpenAI推出的ChatGPT获得一定成功&#xff0c;微软是OpenAI的重要投资者&#xff0c;它将ChatGPT植入必应搜索&#…

基于STATCOM的风力发电机稳定性问题仿真分析(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

thinkphp6 JWT报错 ‘“kid“ empty, unable to lookup correct key‘解决办法

文章目录 JWT简介安装问题先前的代码解决办法修改后的完整代码 JWT简介 JWT全称为Json Web Token&#xff0c;是一种用于在网络应用之间传递信息的简洁、安全的方式。JWT标准定义了一种简洁的、自包含的方法用于通信双方之间以JSON对象的形式安全的传递信息。由于它的简洁性、可…

关于SpringBoot整合Websocket实现简易对话聊天窗

前言 官网链接&#xff1a;Websocket Websocket 是什么&#xff1f;它可以将两个独立的浏览器窗口作为通信的两端。 这种形式的通信与传统的 HTTP、TCP 所不同。传统的 HTTP 请求—响应协议是无法实现实时通信的&#xff0c;也就是说&#xff0c;只能由客户端向服务端发送请求…

英语中主语从句的概念及其用法,例句(不断更新)

主语从句的原理 主语从句是一种充当整个句子主语的从句&#xff0c;主语从句构成的句子&#xff0c;是要以引导词开头的。它可以用名词性从属连词、关系代词或关系副词引导。主语从句通常位于谓语动词之前&#xff0c;用于表示动作、状态或事件的主体。 以下是一些常用的引导主…

MiniGPT-4,开源了!

上个月GPT-4发布时&#xff0c;我曾写过一篇文章分享过有关GPT-4的几个关键信息。 当时的分享就提到了GPT-4的一个重要特性&#xff0c;那就是多模态能力。 比如发布会上演示的&#xff0c;输入一幅图&#xff08;手套掉下去会怎么样&#xff1f;&#xff09;。 GPT-4可以理解…

推荐几个可以免费使用的ChatGPT工具

在ChatGPT相关API推出之后&#xff0c;各种工具如雨后春笋一般层出不穷&#xff0c;这篇文章就列举一些日常使用到的工具。 工具列表 OpenAI 在线读取任意网页内容包括视频&#xff08;YouTube&#xff09;&#xff0c;并根据这些内容回答你提出的相关问题或总结相关内容支持…
最新文章