您现在的位置是:首页 >
当前栏目
小于 n 的最大数
小于 最大数
2023-06-13 09:11:15 时间
文章目录
1.问题描述
数组 A 中给定可以使用的 1~9 的数,返回由数组 A 中的元素组成的小于 n 的最大数。
示例 1:A={1, 2, 9, 4},n=2533,返回 2499。
示例 2:A={1, 2, 5, 4},n=2543,返回 2542。
示例 3:A={1, 2, 5, 4},n=2541,返回 2525。
示例 4:A={1, 2, 9, 4},n=2111,返回 1999。
示例 5:A={5, 9},n=5555,返回 999。
2.难度等级
medium。
3.热门指数
★★★★☆
出题公司:字节跳动。
4.解题思路
此题需要用到贪心和回溯。
从高位开始遍历,对每一位先尝试使用相同数字,除了最后一位。如果没有相同的数字时,尝试是否有比当前数字更小的,有的话选更小的数字里最大的,剩下的用最大数字。都没有就向前回溯看前一个有没有更小的。如果一直回溯到第一个数字都没有更小的数字,就用位数更少的全都是最大数字的数。
5.实现示例
5.1 C++
5.2 Golang
// getMaxDigitLtD 获取小于指定数字的数字。
func getMaxDigitLtD(digits []int, digit int) int {
for i := len(digits) - 1; i>=0; i-- {
if digits[i] < digit {
return digits[i]
}
}
return 0
}
// getMaxNumLtN 获取小于 n 的最大数。
func getMaxNumLTN(digits []int, n int) int {
var ndigits []int
// 获取 n 的每一位数字。
for n > 0 {
ndigits = append(ndigits, n%10)
n /= 10
}
// 排序给定的数字数组。
sort.Ints(digits)
// 数字写入 map 用于查看是否存在。
m := make(map[int]struct{})
for _, v := range digits {
m[v] = struct{}{}
}
// 目标数的每一位数字。
tdigits := make([]int, len(ndigits))
// 从高位遍历,尽可能地取相同值,除了最后一位。
for i:= len(ndigits) - 1; i >= 0; i-- {
if i > 0 {
// 存在相同数字。
if _, ok := m[ndigits[i]]; ok {
tdigits[i] = ndigits[i]
continue
}
// 存在小于当前位的最大数字。
if d := getMaxDigitLtD(digits, ndigits[i]); d > 0 {
tdigits[i] = d
break
}
}
if i == 0 {
// 存在小于当前数字的最大数字。
if d := getMaxDigitLtD(digits, ndigits[i]); d > 0 {
tdigits[i] = d
break
}
}
// 回溯
for i++; i < len(ndigits); i++ {
tdigits[i] = 0
if d := getMaxDigitLtD(digits, ndigits[i]); d > 0 {
tdigits[i] = d
break
}
// 最高位也没有小于其的最大数字。
if i == len(ndigits) - 1 {
tdigits = tdigits[:len(tdigits)-1]
}
}
break
}
// 拼接目标数。
var target int
for i := len(tdigits) - 1; i >= 0; i-- {
target *=10
if tdigits[i] > 0 {
target += tdigits[i]
continue
}
target += digits[len(digits)-1]
}
return target
}
验证代码:
package main
import (
"fmt"
"sort"
)
func main() {
fmt.Println(getMaxNumLTN([]int{1,2,9,4}, 2533))
fmt.Println(getMaxNumLTN([]int{1,2,5,4}, 2543))
fmt.Println(getMaxNumLTN([]int{1,2,5,4}, 2541))
fmt.Println(getMaxNumLTN([]int{1,2,9,4}, 2111))
fmt.Println(getMaxNumLTN([]int{5,9}, 5555))
}
运行输出:
2499
2542
2525
1999
999
参考文献
相关文章
- 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
- 牛客刷题系列之初阶版(自守数,返回小于 N 的质数个数,第一个只出现一次的字符)
- 看我是如何用C#编写一个小于8KB的贪吃蛇游戏的
- 2023-01-08:小红定义一个仅有r、e、d三种字符的字符串中, 如果仅有一个长度不小于2的回文子串,那么这个字符串定义为“好串“。 给定一个正整数n,输出
- 每日一题(2022-05-05)——乘积小于 K 的子数组
- MySQL中小于等于操作的使用(mysql小于等于)
- 12Oracle:12以下的操作(oracle小于等于)
- 小小输入法是可以挂接任意【形码】、【音形码】、【音码】的全功能平台,支持所有编码集(包括大、小键盘数字), 支持编码方案小于48键,编码长度小于64个的各种输入法。您无需再去寻找98五笔、二笔、大手笔、一笔等等的输入法软件,一个小小即可胜任这一切!喜欢内置就内置,喜欢外挂就外挂,自由选择。
- 10Oracle数据库版本低于10(oracle小于)
- 小于SQL Server:用大于小于实现精准查找(sqlserver 大于)
- MySQL中使用lt操作符进行小于比较的条件查询(mysql中 lt)
- MySQL处理XML小于符号的方法(mysql xml小于)
- 深入浅出MySQL,轻松掌握不小于的数据处理能力(mysql 不小于)
- Oracle中小于运算符的应用(oracle中小于)
- Oracle数据库中的小于等于运算(oracle中不大于)
- Redis计数器数量小于预期为什么(redis计数器比实际小)
- 只能输入小于最大数且是正整数的脚本
- js判断选择时间不能小于当前时间的示例代码