当前位置: 首页 > 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;等号左边就是普通的键的写法…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...