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

2022-08-04：输入:去重数组arr，里面的数只包含0~9。limit，一个数字。

返回:要求比limit小的情况下，能够用arr拼出来的最大数字。

来自字节。

答案2022-08-04：

从左往右，存在回溯。单决策递归。代码用rust和typescript编写。

代码用rust编写。代码如下：

代码语言：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编写。代码如下：

代码语言：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();

执行结果如下：

在这里插入图片描述

---

左神java代码

typescript rust

0 人点赞