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

leetCode 2578. 最小和分割 + 排序 + 贪心 + 奇偶分组(构造最优解)

2578. 最小和分割 - 力扣(LeetCode)


给你一个正整数 num ,请你将它分割成两个非负整数 num1 和 num2 ,满足:

  • num1 和 num2 直接连起来,得到 num 各数位的一个排列。
    • 换句话说,num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
  • num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意:

  • num 保证没有前导 0 。
  • num1 和 num2 中数位顺序可以与 num 中数位顺序不同。


思路分析总结来自:(https://leetcode.cn/problems/split-with-minimum-sum/)

  • 1.满足nums1 和 nums2的位数小于<= bit_len(num) / 2 尽可能最短
  • 2.依次给nums1 和 nums2 分配较小的数给高位

(1)用一个 nums数组 来存放num的各个位的数字,然后 sort排序,再根据思路分析将其转化为num1 num2

class Solution {
public:int splitNum(int num) {vector<int> nums;while(num){nums.push_back(num%10);num = num / 10;}sort(nums.begin(),nums.end());int num1=0,num2=0;for(int i=0;i<nums.size();i++) {if(i%2==0) num1 = num1 * 10 + nums[i];else num2 = num2 * 10 + nums[i];}return num1 + num2;}
};

这段文字来自这篇博客:位运算&1,」」1,「「1

n&1 就是判断 n 是否为奇数.

  • n 为奇数时,对应的二进制数最低位一定为1,n&1的结果就是1。
  • n为偶数时,相应的最低位为0,n&1的结果就是0。
  • n&1 ==1 或者写 n%2 == 1 或者写 n%2

可以将i%2 == 1 写成 i&1

class Solution {
public:int splitNum(int num) {vector<int> nums;while(num){nums.push_back(num%10);num = num / 10;}sort(nums.begin(),nums.end());int num1=0,num2=0;for(int i=0;i<nums.size();i++) {if(i&1) num2 = num2 * 10 + nums[i];else num1 = num1 * 10 + nums[i];}return num1 + num2;}
};

(2) 将num先转成字符串,接着根据思路分析,拼接两个字符串s1和s2,最后转成int,相加后返回

class Solution {
public:int splitNum(int num) {string s = to_string(num);sort(s.begin(),s.end());string s1,s2;for(int i=0;i<s.size();i++) {// if(i&1) s2 += s[i];// else s1 += s[i];i&1?s2 += s[i] : s1 += s[i];}return stoi(s1) + stoi(s2);}
};

(3)将num先转成字符串,接着根据思路分析,获得num1和num2,相加后返回

class Solution {
public:int splitNum(int num) {string s = to_string(num);sort(s.begin(),s.end());int num1=0,num2=0;for(int i=0;i<s.size();i++) {// if(i&1==1) num2 = num2 * 10 + s[i]-'0';// else num1 = num1 * 10 + s[i]-'0';i&1? num2 = num2 * 10 + s[i]-'0' : num1 = num1 * 10 + s[i]-'0';}return num1 + num2;}
};

(4)将(3)进行进一步优化,省去三目运算

class Solution {
public:int splitNum(int num) {string s = to_string(num);sort(s.begin(),s.end());int a[2]{};for(int i=0;i<s.size();i++) {// a[i % 2] = a[i % 2] * 10 + s[i] - '0'; a[i&1] = a[i&1] * 10 + s[i]-'0';}return a[0] + a[1];}
};
  • 时间复杂度:O(mlog⁡m),其中 m 为 num 转成字符串后的长度。
  • 空间复杂度:O(m)

相关文章:

leetCode 2578. 最小和分割 + 排序 + 贪心 + 奇偶分组(构造最优解)

2578. 最小和分割 - 力扣&#xff08;LeetCode&#xff09; 给你一个正整数 num &#xff0c;请你将它分割成两个非负整数 num1 和 num2 &#xff0c;满足&#xff1a; num1 和 num2 直接连起来&#xff0c;得到 num 各数位的一个排列。 换句话说&#xff0c;num1 和 num2 中所…...

自定义实现图片裁剪

要实现这个功能&#xff0c;首先需要创建一个自定义的View&#xff0c;然后在该View中绘制背景框和裁剪后的图片。以下是一个简单的实现&#xff1a; 1. 创建一个名为CustomImageView的自定义View类&#xff0c;继承自View&#xff1a; import android.content.Context; impor…...

开发语言工具编程系统化教程入门和初级专辑课程上线

开发语言工具编程系统化教程入门和初级专辑课程上线 学习编程捷径&#xff1a;&#xff08;不论是正在学习编程的大学生&#xff0c;还是IT人士或者是编程爱好者&#xff0c;在学习编程的过程中用正确的学习方法 可以达到事半功倍的效果。对于初学者&#xff0c;可以通过下面…...

【Truffle】二、自定义合约测试

一、准备测试 上期我们自己安装部署了truffle&#xff0c;并且体验了测试用例的整个测试流程&#xff0c;实际开发中&#xff0c;我们可以对自己的合约进行测试。 我们首先先明白自定义合约测试需要几个文件 合约文件&#xff1a;既然要测试合约&#xff0c;肯定要有合约的源码…...

场景交易额超40亿,海尔智家三翼鸟开始收获

文 | 螳螂观察 作者 | 余一 随着双十一的到来&#xff0c;国内的消费情绪再次被点燃。在这类大促之下&#xff0c;品牌们就像一个个天体&#xff0c;不断引动着市场潮汐&#xff0c;期待自己能触发更大的“海潮效应”。 所谓“海潮效应”是指&#xff0c;海水因天体的引力而…...

众和策略可靠吗?股票扛杆怎么玩?

可靠 股票扛杆是一种出资战略&#xff0c;经过假贷资金来增加出资金额&#xff0c;从而进步出资收益。这种战略在股票商场中被广泛运用&#xff0c;但一起也伴随着一定的危险。在本文中&#xff0c;咱们将从多个视点来剖析股票扛杆怎么玩。 首要&#xff0c;扛杆出资的原理是…...

解决连接Mysql出现ERROR 2013 (HY000): Lost connection to MySQL server at ‘waiting

在上一篇中解决Mysql ER_ACCESS_DENIED_ERROR: Access denied for user ‘root‘‘localhost‘ (using password: YES)-CSDN博客 写了mysql的密码报错问题&#xff0c;在执行 mysql -u root -p 出现了这个错误&#xff0c; ERROR 2013 (HY000): Lost connection to MySQL se…...

Hadoop YARN功能介绍--资源管理、调度任务

Hadoop YRAN介绍 YARN是一个通用资源管理系统平台和调度平台&#xff0c;可为上层应用提供统一的资源管理和 调度。 他的引入为集群在利用率、资源统一管理和数据共享等方面带来了好处。 1.资源管理系统 集群的硬件资源&#xff0c;和程序运行无关&#xff0c;比如内存、cu…...

从AlexNet到chatGPT的演进过程

一、演进 AlexNet&#xff08;2012&#xff09;&#xff1a; AlexNet是深度学习领域的重要突破&#xff0c;包括5个卷积层和3个全连接层。使用ReLU激活函数和Dropout正则化&#xff0c;获得了ImageNet图像分类比赛的胜利。引入了GPU加速训练&#xff0c;大幅提高了深度神经网络…...

Unity如何实现bHaptics TrackSuit震动衣的SDK接入

前言 TrackSuit是bHaptisc公司旗下的一款震动衣,包括X16,X40等不同型号,是一款尖端的无线高级触觉背心,采用人体工程学设计,具有40个精确的触觉反馈点。通过无缝的跨平台支持和无限制、无滞后的游戏体验,增强您的VR冒险体验。用于PC或者VR游戏中高度还原真实射击触感。官…...

识别flink的反压源头

背景 flink中最常见的问题就是反压&#xff0c;这种情况下我们要正确的识别导致反压的真正的源头&#xff0c;本文就简单看下如何正确识别反压的源头 反压的源头 首先我们必须意识到现实中轻微的反压是没有必要去优化的&#xff0c;因为这种情况下是由于偶尔的流量峰值,Task…...

Spring是如何解决bean循环依赖的问题的

在Spring框架中&#xff0c;循环依赖是指两个或多个Bean之间相互依赖&#xff0c;形成了一个闭环的依赖关系。当存在循环依赖时&#xff0c;Bean的创建过程会陷入死循环&#xff0c;导致应用程序无法启动或出现异常。 说到循环依赖&#xff0c;首先我先说说bean的三级缓存 在S…...

[移动通讯]【Carrier Aggregation-9】【 Radio Resource Control (RRC) Aspects】

前言&#xff1a; CA 分析辅助工具&#xff1a; UE Capabilities 目录&#xff1a; 总体流程 Radio Resource Control (RRC) Aspects SCell addition and removal Handover 一 总体流程 1.1 CA 总体流程 1.2 CA 和 NSA 区别 NSA 我理解也是一种特殊的CA 方案&…...

故障预测与健康管理(PHM)的由来以及当前面临的挑战

故障预测与健康管理&#xff08;PHM&#xff09;作为一项关键技术&#xff0c;旨在帮助企业在事故发生之前较长时间内实现故障预测与健康管理&#xff0c;达到“治未病”的效果。PHM的发展源于对设备可靠性和安全性的追求&#xff0c;以及对预测性维护的需求。然而&#xff0c;…...

【ChatGPT瀑布到水母】AI 在驱动软件研发的革新与实践

这里写目录标题 前言内容简介作者简介专家推荐读者对象目录直播预告 前言 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了金融、商业、教育、娱乐等领域的运作方式。数据分析、人工智能和云计算等新兴技术&#xff0c;也在不…...

【Django】项目模型

Django的基本命令 django-admin 命令含义startproject启动Django项目startapp启动Django应用check检查项目完整性runserver本地运行项目shell进入Django项目的Python Shell环境test 进行Django用例测试makemigrations创建模型变更的迁移文件migrate执行makemigrations…...

字符集详解

常见字符集介绍 字符集基础知识&#xff1a; 计算机底层不可以直接存储字符的。 计算机中底层只能存储二进制(0、1) 。 二进制是可以转换成十进制的。 结论&#xff1a;计算机底层可以表示成十进制编号。计算机可以给人类字符进行编号存储&#xff0c;这套编号规则就是字符…...

Vert.x学习笔记-什么是Vert.x

Vert.x介绍 用官网的一句话来总结&#xff1a;Vert.x是用于在JVM上构建响应式应用程序的工具包&#xff0c;项目初期的目标是成为“JVM版的Node.js”&#xff0c;但是后续的发展逐渐偏离了初期的目标&#xff0c;变成了一个给JVM提供量身定制的异步编程基础框架的工具包。 Ver…...

AcWing 第127场周赛 构造矩阵

构造题目&#xff0c;考虑去除掉最后一行最后一列先进行考虑&#xff0c;假设除了最后一行和最后一列都已经排好了&#xff08;你可以随便排&#xff09;&#xff0c;那么分析知最后一个数字由限制以外其他都已经确定了&#xff0c;无解的情况是k为-1 并且n&#xff0c;m的奇偶…...

Seata入门系列【15】@GlobalLock注解使用场景及源码分析

1 前言 在Seata 中提供了一个全局锁注解GlobalLock&#xff0c;字面意思是全局锁&#xff0c;搜索相关文档&#xff0c;发现资料很少&#xff0c;所以分析下它的应用场景和基本原理&#xff0c;首先看下源码中对该注解的说明&#xff1a; // 声明事务仅在单个本地RM中执行 //…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...