输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用arr拼出来的最大数字。-天翼云

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

2024-05-09 09:22:03 阅读次数：46

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。
返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

从左往右，存在回溯。单决策递归。代码用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;
}

执行结果如下：

2022-08-04：输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用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();

执行结果如下：

2022-08-04：输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用arr拼出来的最大数字。来自字节。

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。 返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。 返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

相关文章

Python高维统计建模变量选择:SCAD平滑剪切绝对偏差惩罚、Lasso惩罚函数比较

​Python是如何表示时间的？2个模块、3种方式，1文看懂~

薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选， 每个礼物有一个价值，范围在0 ~ 10^9之间， 薯队长可以从中挑选k个礼物。

找到非负数组中拥有“最大或的结果“的最短子数组，返回最短长度。

【C语言】探索数据的存储（上篇）

MFC编程 -- 判断是否按下ctrl和shift键

【编译原理实验】 -- 词法分析程序设计原理与实现（C语言实现）

小团生日收到妈妈送的两个一模一样的数列作为礼物！ 他很开心的把玩，不过不小心没拿稳将数列摔坏了！ 现在他手上的两个数列分别为A和B，长度分别为n和m。

一场电影开始和结束时间可以用一个小数组来表示[“07:30“,“12:00“]，已知有2000场电影开始和结束都在同一天，这一天从00:00开始到23:59结束，一定要选3场完全不冲突的电影来观看，返回最大的观影时间。

不规则数独问题。

作者介绍

最新文章

Python高维统计建模变量选择:SCAD平滑剪切绝对偏差惩罚、Lasso惩罚函数比较

​Python是如何表示时间的？2个模块、3种方式，1文看懂~

薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选， 每个礼物有一个价值，范围在0 ~ 10^9之间， 薯队长可以从中挑选k个礼物。

找到非负数组中拥有“最大或的结果“的最短子数组，返回最短长度。

【C语言】探索数据的存储（上篇）

MFC编程 -- 判断是否按下ctrl和shift键

热门文章

java学习第三天笔记-运算符10-短路逻辑运算符56

Filter&Listener笔记

ESLint：可组装的JavaScript和JSX检查工具

java学习第二天笔记-java基础概念08-数据类型-30

Golang：使用标准库crypto/aes实现AES加密和解密

VSCode与Prettier代码格式化工具的使用

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

前端项目实战119-menu中 url改变侧边栏改变

O(1) 时间插入、删除和获取随机元素。

【QT】QT调色板类

好客租房67-render-props模式-3演示mouseover的组件的复用

C# File、FileInfo、Directory、DirectoryInfo

【Java】Idea控制台中文乱码问题完全解决方案

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

输入:去重数组arr，里面的数只包含0~9。limit，一个数字。返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

Python是如何表示时间的？2个模块、3种方式，1文看懂~

薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选，每个礼物有一个价值，范围在0 ~ 10^9之间，薯队长可以从中挑选k个礼物。

小团生日收到妈妈送的两个一模一样的数列作为礼物！他很开心的把玩，不过不小心没拿稳将数列摔坏了！现在他手上的两个数列分别为A和B，长度分别为n和m。

Python是如何表示时间的？2个模块、3种方式，1文看懂~

薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选，每个礼物有一个价值，范围在0 ~ 10^9之间，薯队长可以从中挑选k个礼物。