蓝桥杯 每日2题 day5

碎碎念:哦哈呦,到第二天也是哦哈哟,,学前缀和差分学了半天!day6堂堂连载!

0.单词分析

14.单词分析 - 蓝桥云课 (lanqiao.cn)

关于这题就差在input前加一个sorted,记录一下下。接下来就是用字典把字母和出现次数绑定,然后用sorted的key lambda排序。感觉写过两次了不再赘述

1.棋盘

15.棋盘 - 蓝桥云课 (lanqiao.cn)

前缀和与差分

焦灼两天~!还是没写出来,,那个边界搞死人,,先差分再求前缀和!!真没招了半懂半不懂的

差分:在数据变化的第一个数+1,在数据变化的下一个-1

前缀和:想一下矩阵图

n,m = map(int, input().split())
lis = [[0]*(n+2) for _ in range(n+2)]
# 构建差分
for t in range(m):
    x1,y1,x2,y2 = map(int, input().split())
    lis[x1][y1] += 1
    lis[x1][y2+1] -= 1
    lis[x2+1][y1] -= 1
    lis[x2+1][y2+1] += 1
# 计算差分的前缀和,直接在原数组上计算
for i in range(1,n+1):       # 注意边界,前缀和从1开始计算 [1-n]
    for j in range(1,n+1):
        lis[i][j] = (lis[i-1][j] + lis[i][j-1] - lis[i-1][j-1] + lis[i][j])%2    
# 算一个矩形的加和,翻一次+1,结果为偶数则为白(0),为奇数就是黑(1)
        print(lis[i][j],end='')
    print()

关于前缀和与差分学习了这篇文章:

Python数据结构与算法篇(二)-- 前缀和与差分数组_python 前缀和数组-CSDN博客

质量真的是高啊,,膜拜,,推荐大家去看

练习1 303. 区域和检索 - 数组不可变 - 力扣(LeetCode)

class NumArray:

    def __init__(self, nums: List[int]):
        self.myarray = [0]
        for i in range(len(nums)):
            self.myarray.append(self.myarray[i]+nums[i])
 


    def sumRange(self, left: int, right: int) -> int:
        return self.myarray[right+1]-self.myarray[left]

练习2 304. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode)

对什么时候+1什么时候-1要注意:初始化时多建立一行一列是为了处理边界情况。计算矩形数字和时对引用的行和列要+1,是因为前缀和二维表比原始数据二维表多了一行一列,需要加上保证引用对应。

图是灵茶山大佬的。

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.presum = [[0]*(n+1) for i in range(m+1)]
        for i in range(m):
            for j in range(n):
                self.presum[i+1][j+1] = self.presum[i+1][j] + self.presum[i][j+1] - self.presum[i][j] + matrix[i][j]
            


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        ans = self.presum[row2+1][col2+1] - self.presum[row2+1][col1] - self.presum[row1][col2+1] + self.presum[row1][col1]
        return ans

练习3 1109. 航班预订统计 - 力扣(LeetCode)

 差分与前缀和的部分

  1. 差分

    • 差分数组 d 初始化为长度为 n 的全0数组,其中 n 是飞机的座位数。
    • 对于每一条预订信息 bookings[i]在 bookings[i][0] - 1 的位置(注意要减1,因为数组是从0开始索引的)加上预订的座位数 bookings[i][2],在 bookings[i][1] 的位置减去预订的座位数。这样,d 数组就表示了每一天座位数的变化量。
    • 为什么要这么做呢?因为对于每一段连续的预订,我们只需要在起始和结束位置进行标记,而不需要对中间的每一天都进行遍历。这样可以大大减少计算量。
  2. 前缀和

    • 计算出差分数组 d 后,我们需要求出每一天结束时的实际座位数。这可以通过计算前缀和来实现。
    • 遍历 d 数组,从第二个元素开始(索引为1),每一个元素都加上前一个元素的值。这样,d[i] 就表示了第 i 天结束时的剩余座位数。

边界的设置

在代码中,边界的设置主要体现在差分数组 d 的初始化以及差分操作的细节上。

  1. 初始化

    • d 数组被初始化为长度为 n 的全0数组。这是因为一开始每个座位都是空的,所以初始剩余座位数都是0。
  2. 差分操作

    • 在 bookings[i][0] - 1 的位置加上预订的座位数时,没有特别的边界检查,因为题目保证 bookings[i][0] 是在有效范围内的(即 1 <= bookings[i][0] <= n)。
    • 在 bookings[i][1] 的位置减去预订的座位数时,有一个边界检查 if bookings[i][1] < n:。这是因为如果 bookings[i][1] 等于 n,实际上是不需要进行减法的,因为第 n 天之后没有更多的天了。
    • bookings[i][1] 的位置不需要再减1,是因为它代表的是预订的结束位置(座位号),而不是数组的索引。当我们在差分数组 d 中进行减法操作时,我们实际上是在标记结束位置之后的第一天,将预订的座位数减去。这样做是因为我们想要保持结束位置当天(即 bookings[i][1])的座位数不变,因为预订在当天结束时仍然有效。
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        lis = [0]*n    
        for i in range(len(bookings)):    # 计算差分数组
            lis[bookings[i][0]-1] += bookings[i][2]    
            if bookings[i][1] < n:    # 判断边界
                lis[bookings[i][1]] -= bookings[i][2]
        for i in range(1,n):    # lis[0]是初始值
            lis[i] += lis[i-1]
        return lis

            
        

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

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

相关文章

【饿了么笔试题汇总】[全网首发]2024-04-12-饿了么春招笔试题-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新饿了么近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x…

决策树与随机森林实验报告(纯Python实现)

一、实验内容简介 该实验主要利用ID3算法和已有的数据建立决策树和随机森林&#xff0c;并利用决策树和随机森林来预测未知数据的值。本实验使用Python实现。 二、算法说明 下面介绍几个基础但很重要的概念&#xff1a; 决策树&#xff1a;决策树是在已知各种情况发生概率的…

如何恢复 iPhone 删除的照片?

照片是iPhone空间不足的主要原因&#xff0c;因此许多用户选择删除一些重复或不喜欢的图片来释放设备。然而&#xff0c;人们在清洁过程中不小心遗漏了自己喜欢的照片的情况很常见。如果你找不到这些珍贵的照片&#xff0c;你一定很难过。其实&#xff0c;您不必担心这个问题&a…

Android 纵向双选日历

这个日历的布局分两部分&#xff0c;一部分是显示星期几的LinearLayout&#xff0c;另外就是一个RecyclerView&#xff0c;负责纵向滚动了。 工具类&#xff1a; implementation com.blankj:utilcode:1.17.3上activity_calendar代码&#xff1a; <?xml version"1.0&…

【教资】总结经验篇

4月.12日概述 今天是2024年上半学期中小学出成绩的一天&#xff0c;查到成绩的那一刻是灰常让人激动的&#xff0c;很开心&#xff0c;特此记下此时的真实感受&#xff0c;我也没有去问别人怎么样&#xff0c;特此针对自己以记之&#xff0c;加上最近有点摆烂&#xff0c;所以…

重磅!李彦宏内部讲话曝光,百度AI闭源策略引爆争议!|TodayAI

最近&#xff0c;百度公司创始人、董事长兼CEO李彦宏的一次内部讲话内容被公之于众。在这次讲话中&#xff0c;李彦宏表达了几个与行业普遍看法相左的观点&#xff0c;尤其在开源与闭源策略的选择上&#xff0c;引发了业界的广泛关注和讨论。 李彦宏在讲话中明确指出了百度对开…

gitlab、jenkins安装及使用文档二

安装 jenkins IP地址操作系统服务版本192.168.75.137Rocky9.2jenkins 2.450-1.1 jdk 11.0.22 git 2.39.3192.168.75.138Rocky9.2gitlab-ce 16.10.0 结合上文 jenkins安装 前期准备&#xff1a; yum install -y epel-release yum -y install net-tools vim lrzsz wget…

git知识

如何将develop分支合并到master分支 #简单版 git checkout master git pull origin master git merge origin/develop # 解决可能的冲突并提交 git push origin master#复杂版 git checkout master # 拉取远程 master 分支的最新代码并合并到本地 git pull origin master # 拉…

网页内容生成图片,这18般武艺你会几种呢?

前言 关于【SSD系列】&#xff1a; 前端一些有意思的内容&#xff0c;旨在3-10分钟里&#xff0c; 500-1000字&#xff0c;有所获&#xff0c;又不为所累。 网页截图&#xff0c;windows内置了快捷命令和软件&#xff0c;chrome开发者工具也能一键截图&#xff0c;html2canva…

【Linux杂货铺】文件系统

目录 &#x1f308;前言&#x1f308; &#x1f4c1; 硬盘 &#x1f4c2; 物理结构 &#x1f4c2; 存储结构 &#x1f4c2; CHS定址法 &#x1f4c2; 操作系统对硬盘的管理和抽象 &#x1f4c1; 文件系统 &#x1f4c2; 分区 &#x1f4c2; 分组 &#x1f4c2; inode号 分配…

DL00295-基于AirSim仿真环境的无人机深度强化学习算法路径规划完整实现含详细说明文档

-创建了一个开放的AI Gym环境&#xff0c;包括多旋翼和固定翼无人机的运动学模型。 -提供了一些UE4环境来训练和测试深度强化学习DRL导航策略。 -基于AirSim和SB3。 完整代码链接见文末。 DL00295-基于AirSim仿真环境的无人机深度强化学习算法路径规划完整实现含详细说明文档

力扣HOT100 - 189. 轮转数组

解题思路&#xff1a; 三次反转。 先反转一次&#xff0c;再根据 k 拆分成两部分各反转一次。 class Solution {public void rotate(int[] nums, int k) {k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}pu…

【QT教程】QT6 Web性能优化

QT6 Web性能优化 使用AI技术辅助生成 QT界面美化视频课程 QT性能优化视频课程 QT原理与源码分析视频课程 QT QML C扩展开发视频课程 免费QT视频课程 您可以看免费1000个QT技术视频 免费QT视频课程 QT统计图和QT数据可视化视频免费看 免费QT视频课程 QT性能优化视频免费看 免费…

MURF1040CT-ASEMI快恢复二极管MURF1040CT

编辑&#xff1a;ll MURF1040CT-ASEMI快恢复二极管MURF1040CT 型号&#xff1a;MURF1040CT 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220F 最大平均正向电流&#xff08;IF&#xff09;&#xff1a;10A 最大循环峰值反向电压&#xff08;VRRM&#xff09;&#xff1a;4…

kubectl_入门_Pod配置以及生命周期

Pod配置以及生命周期 1. Pod结构定义 每个pod中都可以包含一个或多个容器&#xff0c;这些容器可以分为两类 用户程序所在的容器&#xff0c;数量可多可少Pause容器&#xff0c;这是每个Pod都会有的一个根容器&#xff0c;它的作用有两个 可以以它为根据&#xff0c;评估整个…

工业相机飞拍功能的介绍(转载学习)

转载至&#xff1a; https://baijiahao.baidu.com/s?id1781438589726948322&wfrspider&forpc

【Python使用】嘿马头条完整开发md笔记第5篇:数据库,1 Redis事务【附代码文档】

嘿马头条项目从到完整开发笔记总结完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;课程简介&#xff0c;ToutiaoWeb虚拟机使用说明1 产品介绍,2 原型图与UI图,3 技术架构,4 开发,1 需求,2 注意事项。数据库&#xff0c;理解ORM1 简介,2 安装,3 数据库连接…

基于SSM学生考勤管理系统需求(内附设计LW + PPT+ 源码下载)

摘 要 高校的不断扩张让在校学生数量不断的增加&#xff0c;对于教师和管理人员的需求也在不断地增强&#xff0c;对日常的学生考勤管理的工作量也在日益增加&#xff0c;传统的人工点名签到的考勤管理模式已经给无法适用于当前高校考勤管理的需求&#xff0c;同时手动录入的…

一、flask入门和视图

run启动参数 模板渲染 后端给前端页面传参 前端页面设置css from flask import Flask, render_template,jsonify# 创建flask对象 app = Flask(__name__)# 视图函数 + 路由route @app.route("/") def hello_world():# 响应,返回给前端的数据return "hello worl…

股票价格预测 | Python股票价格数据导入和处理

文章目录 文章概述代码设计导入处理文章概述 股票价格预测 | Python股票价格数据导入和处理 代码设计 导入 import os import numpy as np import csv import pandas as pd import matplotlib.pyplot