LeetCode 每日一题 2024/3/18-2024/3/24
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 3/18 303. 区域和检索 - 数组不可变
- 3/19 1793. 好子数组的最大分数
- 3/20 1969. 数组元素的最小非零乘积
- 3/21 2671. 频率跟踪器
- 3/22 2617. 网格图中最少访问的格子数
- 3/23 2549. 统计桌面上的不同数字
- 3/24 322. 零钱兑换
3/18 303. 区域和检索 - 数组不可变
前缀和
nums[x]记录0~x的元素和
计算i~j之间的元素和为nums[j]-nums[i-1]即可
class NumArray(object):def __init__(self, nums):""":type nums: List[int]"""pre = 0self.nums = [0]for n in nums:pre+=nself.nums.append(pre)def sumRange(self, i, j):""":type i: int:type j: int:rtype: int"""return self.nums[j+1]-self.nums[i]
3/19 1793. 好子数组的最大分数
双指针
为了确定l,r 两个都从k开始向左向右移动
比较哪一边的数值较大则往哪边移动
minv记录当前区间最小值
def maximumScore(nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)minv = nums[k]ans = nums[k]l = r = kfor _ in range(n-1):if r == n-1 or l>0 and nums[l-1]>nums[r+1]:l-=1minv = min(minv,nums[l])else:r+=1minv = min(minv,nums[r])ans = max(ans,minv*(r-l+1))return ans
3/20 1969. 数组元素的最小非零乘积
每一次操作 并不会改变元素的和
而在元素和不变的情况下 要想使得乘积最小应该尽可能最大化元素的差值
最大的元素为 2p-1 无论怎么交换 差值不会变大 不考虑
剩余元素可以首尾配对 x与2p-1-x配对 一个数只保留最低位1 剩余的给另一个
可以得到 1 和 2**p-2 两个值相乘
最后乘积为(2p-1)*(2p-2)(2(p-1)-1)
def minNonZeroProduct(p):""":type p: int:rtype: int"""MOD=10**9+7if p==1:return 1def power(x,n):x_init = xb = []while n>0:r = n%2b.insert(0,r)n = n//2for i in range(1,len(b)):x = x*x%MODif b[i]==1:x = x*x_init%MODreturn xbase = 2**pnum = base//2-1x = (base-2)%MODans = 1ans = power(x,num)%MODans = (ans*((base-1)%MOD))%MODreturn ans
3/21 2671. 频率跟踪器
hash表记录次数
num[i]记录数字i出现的次数
cnt[q]记录频率为q的数字个数
class FrequencyTracker(object):def __init__(self):self.num = {}self.cnt = {}def add(self, number):""":type number: int:rtype: None"""self.cnt[self.num.get(number,0)] = self.cnt.get(self.num.get(number,0),0)-1self.num[number] = self.num.get(number,0)+1self.cnt[self.num.get(number,0)] = self.cnt.get(self.num.get(number,0),0)+1def deleteOne(self, number):""":type number: int:rtype: None"""if self.num.get(number,0)==0:returnself.cnt[self.num.get(number,0)]= self.cnt.get(self.num.get(number,0),0)-1self.num[number] = self.num.get(number,0)-1self.cnt[self.num.get(number,0)]= self.cnt.get(self.num.get(number,0),0)+1def hasFrequency(self, frequency):""":type frequency: int:rtype: bool"""return self.cnt.get(frequency,0)>0
3/22 2617. 网格图中最少访问的格子数
对于grid[i][j] 已知到这个位置最少需要f步
向右走 最远到达该行的grid[i][j]+j
向下走 最远到达该列的grid[i][j]+i
在这一行 维持一个最小堆 保存rowh=(f,grid[i][j]+j) 表示上一步走了f的最远可以到达位置
列同理colh
接下来考虑 如何得到grid[i][j]最少需要f
分别处理rowh,colh
对于堆顶最小f 它的距离如果到不了当前的位置i/j 则将其弹出
最后可以得到行、列分别能够到达当前位置的两个最小f 即rowh[0][0],colh[0][0]
对于当前的最小步数f = min(rowh[0][0],colh[0][0])+1
def minimumVisitedCells(grid):""":type grid: List[List[int]]:rtype: int"""import heapqm,n=len(grid),len(grid[0])if m==1 and n==1:return 1colhs = [[] for _ in range(m)]for i,row in enumerate(grid):rowh=[]for j,(g,colh) in enumerate(zip(row,colhs)):while rowh and rowh[0][1]<j:heapq.heappop(rowh)while colh and colh[0][1]<i:heapq.heappop(colh)f = float("inf") if i or j else 1if rowh:f = rowh[0][0]+1if colh:f = min(f,colh[0][0]+1)if g and f<float("inf"):heapq.heappush(rowh,(f,g+j))heapq.heappush(colh,(f,g+i))return f if f<float("inf") else -1
3/23 2549. 统计桌面上的不同数字
n<=100
最差的情况 对于已有数字x 下一天x-1必定会出现在桌面上
x,x-1,x-2…,2
所以在10^9内 如果n>1则2~n都会出现在桌面上
如果n=1 则只有1
def distinctIntegers(n):""":type n: int:rtype: int"""return 1 if n==1 else n-1
3/24 322. 零钱兑换
dp[i]表示凑成金额i需要的最少硬币数
将硬币从小到大排序
依次考虑面值i 是否存在面值i-coin
def coinChange(coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""coins.sort()dp = [float("inf")]*(amount+1)dp[0]=0for i in range(coins[0],amount+1):tmp=float("inf")for j in coins:if j<=i:tmp = min(tmp,dp[i-j])else:breakif tmp<float("inf"):dp[i]=tmp+1return -1 if dp[amount]==float("inf") else dp[amount]
相关文章:
LeetCode 每日一题 2024/3/18-2024/3/24
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/18 303. 区域和检索 - 数组不可变3/19 1793. 好子数组的最大分数3/20 1969. 数组元素的最小非零乘积3/21 2671. 频率跟踪器3/22 2617. 网格图中最少访问的格子数3/23 254…...
Unity 鼠标拖拽3D物体跟随移动的方法
之前我们研究过UI拖拽跟随鼠标移动的方法:https://blog.csdn.net/mr_five55/article/details/135562325 但是该方法不适合3D场景。 假如我们要通过鼠标拖拽3D物体移动,那么可以使用以下控制方法: using System.Collections; using System.…...
数据分析-Pandas分类数据的类别排序和顺序
数据分析-Pandas类别的排序和顺序 数据分析和处理中,难免会遇到各种数据,那么数据呈现怎样的规律呢?不管金融数据,风控数据,营销数据等等,莫不如此。如何通过图示展示数据的规律? 数据表&…...
利用 Claude 3 on Amazon Bedrock 和 Streamlit 的“终极组合”,开发智能对话体验
概述 通过本文,您将学会如何利用 Streamlit 框架快速搭建前端交互界面。该界面将集成图像上传功能,让用户可以方便地提交待处理图片。在后端,我们将借助 Amazon Bedrock 的 Message API,调用 Claude 3 家族中的 Sonnet 模型对图像…...
Golang基础 Label标签与goto跳转
使用方法 Label 和goto是必须的 Label可以声明再函数体的任何地方 Label的作用范围是在函数体中 Label在嵌套函数(闭包)是不可用的. 不管是在闭包里调用闭包外的Label, 还是在闭包外调用闭包里的Label 变量的声明必须在goto之前 示例 package mainimport "fmt"…...
二进制王国(蓝桥杯备赛)【sort/cmp的灵活应用】
二进制王国 题目链接 https://www.lanqiao.cn/problems/17035/learning/?contest_id177 题目描述 思路 这里就要灵活理解字典序排列,虽然string内置可以直接比较字符串字典序,但是在拼接时比较特殊,比如 11的字典序小于110,但…...
活用C语言之宏定义应用大全
零、C语言宏定义知多少 C语言的编程过程中经常会用到宏定义,然而如果你只是使用宏定义做一些常量的定义,那么你不是OUT了就是C语言小白。 那么我们在编程过程中,宏定义都有哪些作用呢? 常量定义 可以作为功能代码的开关 防止头文件被重复…...
【源码】I.MX6ULL移植OpenCV
编译完成的源码: git clone https://gitee.com/wangyoujie11/atkboard_-linux_-driver.git 1.下载源码放在自己的opecv源码目录下 2.QTOpenCV工程代码放置的位置 3.更改.pro工程文件的opencv地址 4.使用命令行编译 前提是自己环境中已经配置好arm-qt的交叉编译…...
pytorch深度学习——dataset(附数据集下载)
在学习深度学习的时候,我们需要考虑如何去处理数据去训练我们的模型,pytorch为我们提供了Dataset和DataLoader两个类来对数据进行处理,前者作用是提供了一种方式来获取数据及其label,后者的作用是为网络提供不同的数据形式。本文主…...
springboot+vue考试管理系统
基于springboot和vue的考试管理系统 001 springboot vue前后端分离项目 本文设计了一个基于Springbootvue的前后端分离的在线考试管理系统,采用M(model)V(view)C(controller)三层体系结构&…...
自动驾驶建图--道路边缘生成方案探讨
自动驾驶建图–道路边缘生成方案探讨 一、背景 对于自动驾驶来说,建图是必不可少的,目前主流厂商技术都在从HD到"无图"进行过渡筹备中,不过想要最终实现真正的"无图"还是有很长的一段路要走。 对于建图来说,…...
图片编辑器中实现文件上传的三种方式和二进制流及文件头校验文件类型
背景 最近在 vue-design-editor 开源项目中实现 psd 等多种文件格式上传解析成模板过程中, 发现搞定设计文件上传没有使用 input 实现文件上传, 所以我研究了一下相关技术, 总结了以下三种文件上传方法 input 文件选择window.showOpenFilePicker 和 window.showDirectoryPicke…...
深度学习,CRNN+CTC和Attention OCR你更青睐哪一种?
深度学习在OCR领域的应用已经取得了瞩目的成果,而选择合适的算法对于提升OCR的识别准确率至关重要。在众多算法中,CRNN和Attention OCR犹如两颗璀璨的明珠,备受瞩目。 CRNN,这位结合了卷积神经网络(CNN)和…...
飞桨AI应用@riscv OpenKylin
在riscv编译安装飞桨PaddlePaddle参见: 算能RISC-V通用云编译飞桨paddlepaddleopenKylin留档_在riscv下进行paddlelite源码编译-CSDN博客 安装好飞桨,就可以用飞桨进行推理了。刚开始计划用ONNX推理,但是在算能云没有装上,所以最…...
在MongoDB建模1对N关系的基本方法
“我在 SQL 和规范化数据库方面拥有丰富的经验,但我只是 MongoDB 的初学者。如何建立一对 N 关系模型?” 这是我从参加 MongoDB 分享日活动的用户那里得到的最常见问题之一。 我对这个问题没有简短的答案,因为方法不只有一种,还有…...
C++基础之运算符重载(十一)
首先为什么要对运算符进行重载?因为C内置的运算符只能作用于一些基本数据类型,而对类和结构体这种自定义数据类型是不管用的。所以这时我们需要对运算符进行重新定义满足一定的运算规则。 运算符重载的三种形式 1.以普通的函数进行重载 #include <…...
初始Java篇(JavaSE基础语法)(2)(逻辑控制)
个人主页(找往期文章包括但不限于本期文章中不懂的知识点):我要学编程(ಥ_ಥ)-CSDN博客 目录 逻辑控制 顺序结构 分支结构 if语句 switch 语句 循环结构 while 循环 for 循环 do while 循环 输入输出 输出到控制台 从键盘输入 …...
家用路由器和企业路由器的区别?
一、家用路由器 家用路由器路由器交换机 它只有一个WAN口和一个LAN口,WAN口接公网一个地址,LAN口接你电脑一个IP地址,完全符合路由器的设计,而因为家里如果用了,说明要接多个电脑,那么如果还需要对每个接口…...
Gin简介(Go web基础知识)
Gin简介 https://geektutu.com/post/quick-go-gin.html我是从这个网站上面摘录的,就是做个笔记,仅分享。膜拜极客兔兔大佬 Go特性: 快速:路由不使用反射,基于Radix树,内存占用少。 中间件:HT…...
HBase的Bulk Load流程
目录 1. 数据准备 2. 文件移动 3. 加载数据 4. Region处理 5. 元数据更新 6. 完成加载 7. 清理 8. 异常处理 LoadIncrementalHFiles(也称为Bulk Load)是HBase中一种将大量数据高效导入到HBase表的机制。以下是LoadIncrementalHFiles的主要流程步…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
