2022-08-04：输入:去重数组arr，里面的数只包含0~9。limit，一个数字。 返回:要求比limit小的情况下，能够用arr拼出来的最大数字。 来自字节。
答案2022-08-04：
从左往右，存在回溯。单决策递归。代码用rust和typescript编写。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let max: i32 = 3000;
let test_time: i32 = 100;
println!("测试开始");
for i in 0..max {
let mut arr = random_array();
for j in 0..test_time {
let ans1 = max_number1(&mut arr, i);
let ans2 = max_number2(&mut arr, i);
if ans1 != ans2 {
println!("ans1 = {:?}", ans1);
println!("ans2 = {:?}", ans2);
println!("出错了!");
break;
}
}
}
println!("测试结束");
}
//let mut tmp:i32 = 0;
static mut tmp: i32 = 0;
// lazy_static! {
// static ref ARRAY: Mutex<Vec<u8>> = Mutex::new(vec![]);
// }
// 暴力尝试的方法
fn max_number1(arr: &mut Vec<i32>, mut limit: i32) -> i32 {
unsafe {
tmp = 0;
}
arr.sort();
limit -= 1;
let mut offset = 1;
while offset <= limit / 10 {
offset *= 10;
}
process1(arr, 0, offset, limit);
if unsafe { tmp == 0 } {
let mut rest = 0;
offset /= 10;
while offset > 0 {
rest += arr[(arr.len() as i32 - 1) as usize] * offset;
offset /= 10;
}
return rest;
}
return unsafe { tmp };
}
fn process1(arr: &mut Vec<i32>, num: i32, offset: i32, limit: i32) {
if offset == 0 {
if num <= limit {
unsafe {
tmp = get_max(tmp, num);
}
}
} else {
for cur in arr.clone().iter() {
process1(arr, num * 10 + cur, offset / 10, limit);
}
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 正式方法
fn max_number2(arr: &mut Vec<i32>, mut limit: i32) -> i32 {
// arr里面是不重复的数字，且只包含0~9
arr.sort();
limit -= 1;
// <= limit 且最大的数字
// 68886
// 10000
// 为了取数而设计的！
// 457
// 100
let mut offset = 1;
while offset <= limit / 10 {
offset *= 10;
}
let mut ans = process2(arr, limit, offset);
if ans != -1 {
return ans;
} else {
offset /= 10;
let mut rest = 0;
while offset > 0 {
rest += arr[arr.len() - 1] * offset;
offset /= 10;
}
return rest;
}
}
// 可以选哪些数字，都在arr里，arr是有序的，[3,6,8,9]
// limit : <= limit 且尽量的大！ 68886
// offset : 10000
// 1000
// 100
// offset 下标用！
fn process2(arr: &mut Vec<i32>, limit: i32, offset: i32) -> i32 {
// 之前的数字和limit完全一样，且limit所有数字都一样
if offset == 0 {
return limit;
}
// 当前的数字
// 68886
// 10000
// 6
let mut cur = (limit / offset) % 10;
// 6 arr中 <=6 最近的！
let mut near0 = near(arr, cur);
if near0 == -1 {
return -1;
} else if arr[near0 as usize] == cur {
// 找出来的数字，真的和当前数字cur一样!
let mut ans = process2(arr, limit, offset / 10);
if ans != -1 {
return ans;
} else if near0 > 0 {
// 虽然后续没成功，但是我自己还能下降！还能选更小的数字
near0 -= 1;
return (limit / (offset * 10)) * offset * 10
+ (arr[near0 as usize] * offset)
+ rest(arr, offset / 10);
} else {
// 后续没成功，我自己也不能再下降了！宣告失败，往上返回！
return -1;
}
} else {
// arr[near] < cur
return (limit / (offset * 10)) * offset * 10
+ (arr[near0 as usize] * offset)
+ rest(arr, offset / 10);
}
}
// 比如offset = 100
// 一共3位数
// 那么就把arr中最大的数字x，拼成xxx，返回
// 比如offset = 10000
// 一共5位数
// 那么就把arr中最大的数字x，拼成xxxxx，返回
fn rest(arr: &mut Vec<i32>, mut offset: i32) -> i32 {
let mut rest = 0;
while offset > 0 {
rest += arr[arr.len() - 1] * offset;
offset /= 10;
}
return rest;
}
// 在有序数组arr中，找到<=num，且最大的数字，在arr中的位置返回
// 如果所有数字都大于num，返回-1
// [3,6,9] num = 4 3
// [5,7,9] num = 4 -1
fn near(arr: &mut Vec<i32>, num: i32) -> i32 {
let mut l = 0;
let mut r = arr.len() as i32 - 1;
let mut m = 0;
let mut near = -1;
while l <= r {
m = (l + r) / 2;
if arr[m as usize] <= num {
near = m;
l = m + 1;
} else {
r = m - 1;
}
}
return near;
}
// 为了测试
fn random_array() -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _ in 0..rand::thread_rng().gen_range(0, 10) + 1 {
arr.push(0);
}
let mut cnt: Vec<bool> = vec![];
for _ in 0..10 {
cnt.push(false);
}
for i in 0..arr.len() as i32 {
arr[i as usize] = rand::thread_rng().gen_range(0, 10);
while cnt[arr[i as usize] as usize] {
arr[i as usize] = rand::thread_rng().gen_range(0, 10);
}
cnt[arr[i as usize] as usize] = true;
}
return arr;
}
执行结果如下：
代码用typescript编写。代码如下：
var tmp = 0;
// 暴力尝试的方法
function maxNumber1(arr, limit) {
tmp = 0;
arr.sort();
limit--;
var offset = 1;
while (offset <= Math.floor(limit / 10)) {
offset *= 10;
}
process1(arr, 0, offset, limit);
if (tmp == 0) {
var rest = 0;
offset = Math.floor(offset / 10);
while (offset > 0) {
rest += arr[arr.length - 1] * offset;
offset = Math.floor(offset / 10);
}
return rest;
}
return tmp;
}
function process1(arr, num, offset, limit) {
if (offset == 0) {
if (num <= limit) {
tmp = Math.max(tmp, num);
}
} else {
arr.forEach(function (cur) {
process1(arr, num * 10 + cur, Math.floor(offset / 10), limit);
});
}
}
// 正式方法
function maxNumber2(arr, limit) {
// arr里面是不重复的数字，且只包含0~9
arr.sort();
limit--;
// <= limit 且最大的数字
// 68886
// 10000
// 为了取数而设计的！
// 457
// 100
var offset = 1;
while (offset <= Math.floor(limit / 10)) {
offset *= 10;
}
var ans = process2(arr, limit, offset);
if (ans != -1) {
return ans;
} else {
offset = Math.floor(offset / 10);
var rest = 0;
while (offset > 0) {
rest += arr[arr.length - 1] * offset;
offset = Math.floor(offset / 10);
}
return rest;
}
}
// 可以选哪些数字，都在arr里，arr是有序的，[3,6,8,9]
// limit : <= limit 且尽量的大！ 68886
// offset : 10000
// 1000
// 100
// offset 下标用！
function process2(arr, limit, offset) {
// 之前的数字和limit完全一样，且limit所有数字都一样
if (offset == 0) {
return limit;
}
// 当前的数字
// 68886
// 10000
// 6
var cur = Math.floor(limit / offset) % 10;
// 6 arr中 <=6 最近的！
var near0 = near(arr, cur);
if (near0 == -1) {
return -1;
} else if (arr[near0] == cur) {
// 找出来的数字，真的和当前数字cur一样!
var ans = process2(arr, limit, Math.floor(offset / 10));
if (ans != -1) {
return ans;
} else if (near0 > 0) {
// 虽然后续没成功，但是我自己还能下降！还能选更小的数字
near0--;
return (
Math.floor(limit / (offset * 10)) * offset * 10 +
arr[near0] * offset +
rest(arr, Math.floor(offset / 10))
);
} else {
// 后续没成功，我自己也不能再下降了！宣告失败，往上返回！
return -1;
}
} else {
// arr[near] < cur
return (
Math.floor(limit / (offset * 10)) * offset * 10 +
arr[near0] * offset +
rest(arr, Math.floor(offset / 10))
);
}
}
// 比如offset = 100
// 一共3位数
// 那么就把arr中最大的数字x，拼成xxx，返回
// 比如offset = 10000
// 一共5位数
// 那么就把arr中最大的数字x，拼成xxxxx，返回
function rest(arr, offset) {
var rest = 0;
while (offset > 0) {
rest += arr[arr.length - 1] * offset;
offset = Math.floor(offset / 10);
}
return rest;
}
// 在有序数组arr中，找到<=num，且最大的数字，在arr中的位置返回
// 如果所有数字都大于num，返回-1
// [3,6,9] num = 4 3
// [5,7,9] num = 4 -1
function near(arr, num) {
var l = 0;
var r = arr.length - 1;
var m = 0;
var near = -1;
while (l <= r) {
m = Math.floor((l + r) / 2);
if (arr[m] <= num) {
near = m;
l = m + 1;
} else {
r = m - 1;
}
}
return near;
}
// 为了测试
function randomArray() {
var arr = new Array(Math.floor(Math.random() * 10) + 1);
var cnt = new Array(10);
for (var i = 0; i < arr.length; i++) {
do {
arr[i] = Math.floor(Math.random() * 10);
} while (cnt[arr[i]]);
cnt[arr[i]] = true;
}
return arr;
}
function main() {
var max = 3000;
var testTime = 100;
console.log("测试开始");
for (var i = 0; i < max; i++) {
var arr = randomArray();
for (var j = 0; j < testTime; j++) {
var ans1 = maxNumber1(arr, i);
var ans2 = maxNumber2(arr, i);
if (ans1 != ans2) {
console.log("出错了!");
console.log("数组为 ：");
arr.forEach(function (num) {
console.log(num + " ");
});
console.log();
console.log("数字为 ：" + i);
console.log(ans1);
console.log(ans2);
break;
}
}
}
console.log("测试结束");
}
main();
执行结果如下：
京公网安备 11010502036488号