2022-08-04: Input: deduplicated array arr, the numbers in it only contain 0~9.limit, a number.Return: The maximum number that can be spelled out with arr if the requirement is smaller than limit.from

2022-08-04：输入:去重数组arr,The numbers inside only contain0~9.limit,一个数字.
返回:要求比limit小的情况下,能够用arrSpell out the largest number.
来自字节.

答案2022-08-04：

从左往右,backtracking.单决策递归.代码用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![]);
// }

// method of violent attempts
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
    // Designed for counting！
    // 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;
    }
}

// Which numbers can be chosen,都在arr里,arr是有序的,[3,6,8,9]
// limit : <= limit And as big as possible！ 68886
// offset : 10000
// 1000
// 100
// offset 下标用！
fn process2(arr: &mut Vec<i32>, limit: i32, offset: i32) -> i32 {
    
    // 之前的数字和limit完全一样,且limitAll numbers are the same
    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 {
    
        // Find out the numbers,True and current numberscur一样!
        let mut ans = process2(arr, limit, offset / 10);
        if ans != -1 {
    
            return ans;
        } else if near0 > 0 {
    
            // Although the follow-up was unsuccessful,But I can still go down myself！You can also choose a smaller number
            near0 -= 1;
            return (limit / (offset * 10)) * offset * 10
                + (arr[near0 as usize] * offset)
                + rest(arr, offset / 10);
        } else {
    
            // Subsequent unsuccessful,I can't go down any further myself！宣告失败,往上返回！
            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,且最大的数字,在arrThe position in is returned
// if all numbers are greater thannum,返回-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;
// method of violent attempts
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
  // Designed for counting！
  // 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;
  }
}
// Which numbers can be chosen,都在arr里,arr是有序的,[3,6,8,9]
// limit : <= limit And as big as possible！ 68886
// offset : 10000
// 1000
// 100
// offset 下标用！
function process2(arr, limit, offset) {
    
  // 之前的数字和limit完全一样,且limitAll numbers are the same
  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) {
    
    // Find out the numbers,True and current numberscur一样!
    var ans = process2(arr, limit, Math.floor(offset / 10));
    if (ans != -1) {
    
      return ans;
    } else if (near0 > 0) {
    
      // Although the follow-up was unsuccessful,But I can still go down myself！You can also choose a smaller number
      near0--;
      return (
        Math.floor(limit / (offset * 10)) * offset * 10 +
        arr[near0] * offset +
        rest(arr, Math.floor(offset / 10))
      );
    } else {
    
      // Subsequent unsuccessful,I can't go down any further myself！宣告失败,往上返回！
      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,且最大的数字,在arrThe position in is returned
// if all numbers are greater thannum,返回-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代码