当前位置: 首页 > news >正文

LeetCode 每日一题 2024/1/22-2024/1/28

记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步


目录

      • 1/22 670. 最大交换
      • 1/23 2765. 最长交替子数组
      • 1/24 2865. 美丽塔 I
      • 1/25 2859. 计算 K 置位下标对应元素的和
      • 1/26 2846. 边权重均等查询
      • 1/27 2861. 最大合金数
      • 1/28 365. 水壶问题


1/22 670. 最大交换

分解 排序
找到最先不同的位置

def maximumSwap(num):""":type num: int:rtype: int"""l = []ori = numwhile num>0:l.append(num%10)num//=10n = len(l)tmp = [v for v in l]tmp.sort()loc = -1for i in range(n-1,-1,-1):if tmp[i]!=l[i]:loc = ibreakif loc==-1:return orifor i in range(n):if tmp[loc]==l[i]:l[loc],l[i] = l[i],l[loc]breakans = 0for v in l[::-1]:ans = ans*10+vreturn ans

1/23 2765. 最长交替子数组

找到最初满足条件两个数
继续判断重复的有多少

def alternatingSubarray(nums):""":type nums: List[int]:rtype: int"""l = 0n = len(nums)ans =-1while l<n-1:if nums[l+1]!=nums[l]+1:l+=1continues = ll+=2while l<n and nums[l]==nums[l-2]:l+=1ans = max(ans,l-s)l-=1return ans

1/24 2865. 美丽塔 I

遍历每个坐标为峰值的情况
非递减单调栈
先从左往右依次入栈
pre[i]记录i位置为峰顶
左侧能够达到的最大值
同理从右往左相同处理suf[i]记录右侧能够达到最大值
相加减去重复的当前位置即为i位置为峰顶的结果

def maximumSumOfHeights(maxHeights):""":type maxHeights: List[int]:rtype: int"""n= len(maxHeights)ans = 0pre,suf=[0]*n,[0]*nst1,st2=[],[]for i in range(n):while st1 and maxHeights[i]<maxHeights[st1[-1]]:st1.pop()if st1:pre[i]=pre[st1[-1]]+(i-st1[-1])*maxHeights[i]else:pre[i]=(i+1)*maxHeights[i]st1.append(i)for i in range(n-1,-1,-1):while st2 and maxHeights[i]<maxHeights[st2[-1]]:st2.pop()if st2:suf[i]=suf[st2[-1]]+(st2[-1]-i)*maxHeights[i]else:suf[i]=(n-i)*maxHeights[i]st2.append(i)ans = max(ans,pre[i]+suf[i]-maxHeights[i])return ans

1/25 2859. 计算 K 置位下标对应元素的和

func判断位置i是否有k个置位
通过num与num-1相与去除最低位的一个置位
mem存储已经判断过的数值 1位满足 0位不满足

def sumIndicesWithKSetBits(nums, k):""":type nums: List[int]:type k: int:rtype: int"""def func(num):tag = 0while tag<k and num>0:num = num&(num-1)tag+=1if tag==k and num==0:return Truereturn Falseans = 0for i,num in enumerate(nums):if func(i):ans+=numreturn ans

1/26 2846. 边权重均等查询

cnt[i][j]记录节点i到节点0的路径上权重为j的边数
对于两个节点a,b
lca为a,b最近公共祖先
那么在a,b路径上,权重为j的边数为cnt[a][j]+cnt[b][j]-2*cnt[lca][j]
权重最大为26 遍历每一种情况

def minOperationsQueries(n, edges, queries):""":type n: int:type edges: List[List[int]]:type queries: List[List[int]]:rtype: List[int]"""m,w=len(queries),26nei = [{} for i in range(n)]for ed in edges:nei[ed[0]][ed[1]]=ed[2]nei[ed[1]][ed[0]]=ed[2]q = [[] for i in range(n)]for i in range(m):q[queries[i][0]].append([queries[i][1],i])q[queries[i][1]].append([queries[i][0],i])cnt=[[0 for _ in range(w+1)] for _ in range(n)]visited = [0 for _ in range(n)]uf = [0 for _ in range(n)]lca = [0 for _ in range(m)]def find(uf,i):if uf[i]==i:return iuf[i] = find(uf,uf[i])return uf[i]def tarjan(node,parent):if parent!=-1:cnt[node] = cnt[parent][:]cnt[node][nei[node][parent]]+=1uf[node] = nodefor c in nei[node].keys():if c==parent:continuetarjan(c,node)uf[c]=nodefor [nd,ind] in q[node]:if node!=nd and not visited[nd]:continuelca[ind] = find(uf,nd)visited[node]=1tarjan(0,-1)ans = [0 for i in range(m)]for i in range(m):totalcnt,maxcnt = 0,0for j in range(1,w+1):t = cnt[queries[i][0]][j]+cnt[queries[i][1]][j]-2*cnt[lca[i]][j]maxcnt = max(maxcnt,t)totalcnt +=tans[i] = totalcnt-maxcntreturn ans

1/27 2861. 最大合金数

遍历每一台机子的情况
二分找到能够产生最大合金数

def maxNumberOfAlloys(n, k, budget, composition, stock, cost):""":type n: int:type k: int:type budget: int:type composition: List[List[int]]:type stock: List[int]:type cost: List[int]:rtype: int"""ans = 0for c in composition:l,r = 0,budget+stock[0]while l<r:mid = (l+r+1)>>1s = 0for x,y,z in zip(c,stock,cost):s += max(0,mid*x-y)*zif s<=budget:l = midelse:r = mid-1ans = max(ans,l)return ans

1/28 365. 水壶问题

裴蜀定理
https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593?fromtitle=%E8%B4%9D%E7%A5%96%E5%AE%9A%E7%90%86&fromid=5185441
每次操作
只会让桶的水总量增加x,y 或者减少x,y
找到x,y最大公约数并判断z是否是它的倍数

def canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity):""":type jug1Capacity: int:type jug2Capacity: int:type targetCapacity: int:rtype: bool"""import mathif jug1Capacity+jug2Capacity<targetCapacity:return Falseif jug1Capacity==0 or jug2Capacity==0:return targetCapacity==0 or jug1Capacity+jug2Capacity==targetCapacityreturn targetCapacity%math.gcd(jug1Capacity,jug2Capacity)==0

相关文章:

LeetCode 每日一题 2024/1/22-2024/1/28

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 1/22 670. 最大交换1/23 2765. 最长交替子数组1/24 2865. 美丽塔 I1/25 2859. 计算 K 置位下标对应元素的和1/26 2846. 边权重均等查询1/27 2861. 最大合金数1/28 365. 水壶…...

好用的学习与开发工具

1. 首推 UTools 官网地址 uTools官网 - 新一代效率工具平台 介绍 uTools 是一个极简、插件化的现代桌面软件&#xff0c;通过自由选配丰富的插件&#xff0c;打造得心应手的工具集合。 通过快捷键&#xff08;默认 alt space &#xff09;就可以快速呼出这个搜索框。你可…...

(自用)learnOpenGL学习总结-高级OpenGL-立方体贴图

ok终于来到了立方体贴图了&#xff0c;在这里面我们可以加入好看的天空包围盒&#xff0c;这样的画我们的背景就不再是黑色的了&#xff01; 首先&#xff0c;立方体贴图和前面的sampler2D贴图一样&#xff0c;不过是6个2D组成的立方体而已。 那么为什么要把6个组合在一起呢&…...

【计算机网络】——TCP协议

&#x1f4d1;前言 本文主要是【计算机网络】——传输层TCP协议的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &#x1f304;每日一句…...

sql优化的方法

目录 一、准备数据 1.1、创建表结构 1.2、创建存储过程 二、索引介绍 2.1、类型介绍 2.2、建立索引 2.3、建立复合索引 2.4、查看所有建立的索引 2.5、删除索引 三、EXPLAIN分析参数说明 四、SQL优化案例 4.1、避免使用SELECT * 4.2、慎用UNION关键字 4.4、避免使…...

C++ Qt开发:运用QJSON模块解析数据

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QJson组件的实现对JSON文本的灵活解析…...

MySQL数据库基础合集

MySQL数据库基础合集 目录 MySQL数据库基础合集SQL关键字DDL关键字DML关键字DQL关键字DCL关键字约束关键字 SQL基础数据类型整数类型字符类型浮点类型时间类型 数据定义语言DDL1.查看数据库2.创建库3.删除库4.切换库5.创建表6.删除表7.查看表8.查看表属性9.插入列10.修改列11.设…...

oracle19.22的patch已发布

2024年01月16日&#xff0c;oracle发布了19.22的patch 具体patch如下 Reserved for Database - Do not edit or delete (Doc ID 19202401.9) 文档ID规则如下 19&#xff08;版本&#xff09;年份&#xff08;202x&#xff09;(季度首月01,04,07,10).9 往期patch no信息和下…...

HTML+CSS:3D轮播卡片

效果演示 实现了一个3D翻转的卡片动画&#xff0c;其中每个卡片都有不同的图片和不同的旋转角度。整个动画循环播放&#xff0c;无限次。整个页面的背景是一个占据整个屏幕的背景图片&#xff0c;并且页面内容被隐藏在背景图片之下。 Code <div class"container"…...

ES 分词器

概述 分词器的主要作用将用户输入的一段文本&#xff0c;按照一定逻辑&#xff0c;分析成多个词语的一种工具 什么是分词器 顾名思义&#xff0c;文本分析就是把全文本转换成一系列单词&#xff08;term/token&#xff09;的过程&#xff0c;也叫分词。在 ES 中&#xff0c;Ana…...

从0开始搭建若依微服务项目 RuoYi-Cloud(保姆式教程完结)

文章接上一章&#xff1a; 从0开始搭建若依微服务项目 RuoYi-Cloud&#xff08;保姆式教程 一&#xff09;-CSDN博客 四. 项目配置与启动 当上面环境全部准备好之后&#xff0c;接下来就是项目配置。需要将项目相关配置修改成当前相关环境。 数据库配置 新建数据库&#xff…...

Linux true/false区分

bash的数值代表和其它代表相反&#xff1a;0表示true&#xff1b;非0代表false。 #!/bin/sh PIDFILE"pid"# truenginx进程运行 falsenginx进程未运行 checkRunning(){# -f true表示普通文件if [ -f "$PIDFILE" ]; then# -z 字符串长度为0trueif [ -z &qu…...

一些著名的软件都用什么语言编写?

1、操作系统 Microsoft Windows &#xff1a;汇编 -> C -> C 备注&#xff1a;曾经在智能手机的操作系统&#xff08;Windows Mobile&#xff09;考虑掺点C#写的程序&#xff0c;比如软键盘&#xff0c;结果因为写出来的程序太慢&#xff0c;实在无法和别的模块合并&…...

外卖跑腿系统开发:构建高效、安全的服务平台

在当今快节奏的生活中&#xff0c;外卖跑腿系统的开发已成为技术领域的一个重要课题。本文将介绍如何使用一些常见的编程语言和技术框架&#xff0c;构建一个高效、安全的外卖跑腿系统。 1. 技术选择 在开始开发之前&#xff0c;我们需要选择适合的技术栈。常用的技术包括&a…...

【MQ02】基础简单消息队列应用

基础简单消息队列应用 在上一课中&#xff0c;我们已经学习到了什么是消息队列&#xff0c;有哪些消息队列&#xff0c;以及我们会用到哪个消息队列。今天&#xff0c;就直接进入主题&#xff0c;学习第一种&#xff0c;最简单&#xff0c;但也是最常用&#xff0c;最好用的消息…...

CTF CRYPTO 密码学-7

题目名称&#xff1a;敲击 题目描述&#xff1a; 让我们回到最开始的地方 0110011001101100011000010110011101111011011000110110010100110011011001010011010100110000001100100110001100101101001101000011100001100011001110010010110100110100011001000011010100110000…...

随机森林和决策树区别

随机森林&#xff08;Random Forest&#xff09;和决策树&#xff08;Decision Tree&#xff09;是两种不同的机器学习算法&#xff0c;其中随机森林是基于决策树构建的一种集成学习方法。以下是它们之间的主要区别&#xff1a; 决策树: 单一模型: 决策树是一种单一模型&#…...

新建VM虚拟机-安装centOS7-连接finalshell调试

原文 这里有问题 首先进入/etc/sysconfig/network-scripts/目录 cd /etc/sysconfig/network-scripts/ 然后编辑文件 ifcfg-ens33 vi ifcfg-ens33...

936. 戳印序列

Problem: 936. 戳印序列 文章目录 思路解题方法复杂度Code 思路 这道题目要求我们通过使用印章来印刷目标字符串&#xff0c;使得目标字符串最终变成全为’?‘的字符串。我们可以使用贪心的思想来解决这个问题。 首先&#xff0c;我们需要找到所有可以匹配印章的位置&#xff…...

20240129收获

今天终于发现《八部金刚功》第五部我一直做的是错的&#xff0c;嗨。这里这个写法非常聪明&#xff0c;创立的数组&#xff0c;以及用obj[key] item[key]这样的写法&#xff0c;这个写法充分展示了js常规写法中只有等号右边会去参与运算&#xff0c;等号左边就是普通的键的写法…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...