字节高频算法面试题:小于 n 的最大数
问题描述(感觉n的位数需要大于等于2,因为n的位数=1的话会有点问题,“且无重复”是指nums中存在重复,但是最后返回的小于n最大数是可以重复使用nums中的元素的):

思路:
先对nums倒序排序 + 暴力回溯 + 剪枝优化

代码(含详细注释):
class Solution {public int ans = 0;public int getMaxNum(int[] nums, int n) { // 默认n的位数大于等于2// ① 降序排序Arrays.sort(nums);int left = 0, right = nums.length - 1;while (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}// ② 试图寻找一个小于n的整数(位数和n一样)String nStr = String.valueOf(n);boolean isFound = dfs(nums, nStr, new ArrayList<>(), true);// ③ 比如这种情况,nums: 9 8 7, n: 123,nums中最小的数都比n要大,那么isFound是falseif (!isFound) {for (int i = 0; i < nStr.length() - 1; i++) {ans = ans * 10 + nums[0]; // 比n少一位,然后由nums的最大元素组装而成}}return ans;}public boolean dfs(int[] nums, String nStr, List<Integer> path, boolean preIsEqual) {if (path.size() == nStr.length()) { // 递归出口。如果当前路径的数字已经达到整数n的位数了long pathSum = 0;for (int i = 0; i < path.size(); i++) {pathSum = pathSum * 10 + path.get(i);}// 如果 path: 444, n: 444 全部位置的数字相等也不行if (pathSum < Integer.parseInt(nStr)) {ans = (int) pathSum;return true; // 表示已经找到了}return false; // 有可能是, path: 444, n: 444,全部位置的数字相等也不行}for (int i = 0; i < nums.length; i++) {if (preIsEqual) { // 如果前面几位的数字,path对应的数和n对应位的数相等, 如: path:44_, n:444// 如果前面几位的数字,path对应的数和n对应位的数相等,且当前位数字nums[i]>n对应的位的数,那就剪枝if (nums[i] > nStr.charAt(path.size()) - '0') continue;// 否则可以加入路径path.add(nums[i]);boolean curFlag = dfs(nums, nStr, path, nums[i] == nStr.charAt(path.size()-1) - '0');if (curFlag) return true; // 找到了,直接返回path.remove(path.size() - 1);} else { // 如果前面几位的数字,path对应的数和n对应位的数完全不相等或者不都相等, 如: path:44_, n:543path.add(nums[i]);// 如果前面几位的数字,path对应的数和n对应位的数完全不相等或者不都相等, 那么后面的递归都将是不相等的boolean curFlag = dfs(nums, nStr, path, false);if (curFlag) return true; // 找到了,直接返回path.remove(path.size() - 1);}}return false; // 没找到}
}
测试
测试类
class SolutionTest {public static void test(int[] nums, int n, int expected) {Solution solution = new Solution();int result = solution.getMaxNum(nums, n);if (result != expected) {System.out.println("测试失败!");System.out.println("输入数组: " + arrayToString(nums));System.out.println("目标数: " + n);System.out.println("期望结果: " + expected);System.out.println("实际结果: " + result);System.out.println("------------------------");} else {System.out.println("测试通过: " + arrayToString(nums) + " -> " + n + " = " + result);}}private static String arrayToString(int[] arr) {StringBuilder sb = new StringBuilder("[");for (int i = 0; i < arr.length; i++) {sb.append(arr[i]);if (i < arr.length - 1) {sb.append(", ");}}sb.append("]");return sb.toString();}public static void main(String[] args) {// 基本测试test(new int[]{1, 2, 9, 8}, 100, 99);test(new int[]{4, 5}, 445, 444);test(new int[]{4, 5}, 45, 44);// 边界情况test(new int[]{1, 9}, 10, 9);test(new int[]{9, 8}, 9, 8);test(new int[]{9}, 100, 99);// 所有数字都大于目标数test(new int[]{9, 8, 7}, 123, 99);test(new int[]{9, 8, 7}, 12, 9);// 复杂数字组合test(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3000, 2999);test(new int[]{1, 2, 8, 9}, 2990, 2989);// 相同数字test(new int[]{4}, 445, 444);test(new int[]{4}, 45, 44);test(new int[]{4}, 4445, 4444);// 大数测试test(new int[]{9}, 100000, 99999);test(new int[]{8, 9}, 99000, 98999);// 特殊数字组合test(new int[]{1, 2, 3}, 300, 233);test(new int[]{2, 8}, 290, 288);test(new int[]{2, 8, 9}, 289, 288);// 多位数测试test(new int[]{6, 7, 8, 9}, 9877, 9876);test(new int[]{6, 7, 8, 9}, 9868, 9867);// 相邻数字test(new int[]{8, 9}, 1000, 999);test(new int[]{8, 9}, 999, 998);// 混合数字test(new int[]{5, 9}, 6000, 5999);test(new int[]{5, 8, 9}, 5990, 5989);test(new int[]{5, 8, 9}, 5900, 5899);// 包含零test(new int[]{0, 9}, 100, 99);test(new int[]{0, 9}, 1000, 999);// 特殊序列test(new int[]{1, 2, 3, 4, 5, 6}, 54322, 54321);test(new int[]{0, 2, 3, 4, 5, 6}, 54321, 54320);// 重复数字test(new int[]{6, 6, 6, 6}, 6667, 6666);test(new int[]{5, 6}, 6666, 6665);// 极限情况test(new int[]{9}, 1000000, 999999);test(new int[]{9}, 100000, 99999);// 连续数字test(new int[]{1, 2, 3, 4, 5}, 12346, 12345);test(new int[]{1, 2, 3, 4}, 12345, 12344);}
}
结果

相关文章:
字节高频算法面试题:小于 n 的最大数
问题描述(感觉n的位数需要大于等于2,因为n的位数1的话会有点问题,“且无重复”是指nums中存在重复,但是最后返回的小于n最大数是可以重复使用nums中的元素的): 思路: 先对nums倒序排序 暴力回…...
ElasticSearch常见面试题汇总
一、ElasticSearch基础: 1、什么是Elasticsearch: Elasticsearch 是基于 Lucene 的 Restful 的分布式实时全文搜索引擎,每个字段都被索引并可被搜索,可以快速存储、搜索、分析海量的数据。 全文检索是指对每一个词建立一个索引…...
Spring Boot如何实现防盗链
一、什么是盗链 盗链是个什么操作,看一下百度给出的解释:盗链是指服务提供商自己不提供服务的内容,通过技术手段绕过其它有利益的最终用户界面(如广告),直接在自己的网站上向最终用户提供其它服务提供商的…...
工作中常用springboot启动后执行的方法
前言: 工作中难免会遇到一些,程序启动之后需要提前执行的需求。 例如: 初始化缓存:在启动时加载必要的缓存数据。定时任务创建或启动:程序启动后创建或启动定时任务。程序启动完成通知:程序启动完成后通…...
力扣-图论-3【算法学习day.53】
前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非…...
Linux上的C语言编程实践
说明: 这是个人对该在Linux平台上的C语言学习网站笨办法学C上的每一个练习章节附加题的解析和回答 ex1: 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后运行它看看发生了什么。 vim ex1.c打开 ex1.c 文件。假如我们删除 return 0…...
芝法酱学习笔记(1.3)——SpringBoot+mybatis plus+atomikos实现多数据源事务
一、前言 1.1 业务需求 之前我们在讲解注册和登录的时候,有一个重要的技术点忽略了过去。那就是多数据源的事务问题。 按照我们的业务需求,monitor服务可能涉及同时对监控中心数据库和企业中心数据库进行操作,而我们希望这样的操作在一个事…...
【计算机网络】实验12:网际控制报文协议ICMP的应用
实验12 网际控制报文协议ICMP的应用 一、实验目的 验证ping命令和tracert命令的工作原理。 二、实验环境 Cisco Packet Tracer模拟器 三、实验过程 1.构建网络拓扑并进行信息标注,将所需要配置的IP地址写在对应的主机或者路由器旁边,如图1所示。 图…...
收缩 tempdb 数据库
1、 本文内容 注解使用 ALTER DATABASE 命令使用 DBCC SHRINKDATABASE 命令使用 DBCC SHRINKFILE 命令运行收缩操作时出现错误 8909 适用于: SQL ServerAzure SQL 托管实例 本文讨论可用于收缩 SQL Server 中 tempdb 数据库的各种方法。 可以使用下列任一方法来…...
kubesphere搭建 postgres15
创建configMap POSTGRES_PASSWORD数据库密码 PGDATA数据目录 创建【有状态副本集】工作负载 1.创建基本信息 2.容器组设置 配置环境变量 3.存储设置 完成之后点击下一步 配置服务 创建服务 配置基本信息 配置服务信息 外部访问选择nodePort,然后点击…...
解决npm问题用到的资源,错误原因和方法
资源: 1.node版本管理工具nvm: 下载地址:https://nvm.uihtm.com/nvm-1.1.12-setup.zip 使用方法:https://nvm.uihtm.com/ 2.node各版本: https://nodejs.org/en/about/previous-releases 3.nodejs: 下载地址:https://…...
【uni-app 微信小程序】新版本发布提示用户进行更新
知识准备 uni.getUpdateManager文档介绍 不支持APP与H5,所以在使用的时候要做好平台类型的判断,如何判断,参考条件编译处理多端差异 代码参考 export const updateApp () > {const updateManager uni.getUpdateManager()updateManag…...
Redis性能优化18招
Redis性能优化的18招 目录 前言选择合适的数据结构避免使用过大的key和value[使用Redis Pipeline](#使用Redis Pipeline)控制连接数量合理使用过期策略使用Redis集群充分利用内存优化使用Lua脚本监控与调优避免热点key使用压缩使用Geo位置功能控制数据的持久化尽量减少事务使…...
ElasticSearch 与向量数据库的结合实践:突破亿级大表查询瓶颈20241204
💡 ElasticSearch 与向量数据库的结合实践:突破亿级大表查询瓶颈 📚 引言 随着业务规模的不断扩大,传统关系型数据库在处理 亿级大表 时,性能瓶颈愈加凸显。关键词检索、模糊查询、多条件筛选等需求逐步升级ÿ…...
C#实现一个HttpClient集成通义千问-流式输出内容提取
返回对象处理 返回对象分析 根据流式返回的数据处理 内容对象 {"choices": [{"delta": { "content": "", "role": "assistant" },"index": 0,"logprobs": null,"finish_reason"…...
微信小程序后台搭建—node+mysql
想必大家都有一个困扰,想要用微信小程序作为前端,但是后端不知道如何用node连接微信小程序,我最近也一直困扰许久,所以我就想用node写后端接口在连接微信小程序,记录一下学习笔记 前言 前端:微信小程序 后端:nodeexp…...
断点续传+测试方法完整示例
因为看不懂网上的断点续传案例,而且又不能直接复制使用,干脆自己想想写了一个。 上传入参类: import com.fasterxml.jackson.annotation.JsonIgnore; import io.swagger.annotations.ApiModel; import io.swagger.annotations.ApiModelProp…...
C# 中的静态构造函数和实例构造函数的区别
在C#中,静态构造函数和实例构造函数在类的初始化过程中扮演着不同的角色。下面我将详细介绍这两种构造函数的区别: 实例构造函数(Instance Constructor): 实例构造函数用于初始化类的实例(对象)…...
如何在UI自动化测试中创建稳定的定位器?
如何在UI自动化测试中创建稳定的定位器? 前言1. 避免使用绝对路径2. 避免在定位器中使用索引3. 避免多个类名的定位器4. 避免动态和自动生成的ID5. 确保定位器唯一6. 处理隐藏元素的策略7. 谨慎使用基于文本的定位器8. 使用AI创建稳定的定位器 总结 前言 在自动化测…...
【5G】5G技术组件 5G Technology Components
5G的目标设置非常高,不仅在数据速率上要求达到20Gbps,在容量提升上要达到1000倍,还要为诸如大规模物联网(IoT, Internet of Things)和关键通信等新服务提供灵活的平台。这些高目标要求5G网络采用多种新技术…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
FOPLP vs CoWoS
以下是 FOPLP(Fan-out panel-level packaging 扇出型面板级封装)与 CoWoS(Chip on Wafer on Substrate)两种先进封装技术的详细对比分析,涵盖技术原理、性能、成本、应用场景及市场趋势等维度: 一、技术原…...
