网站首页 > java教程 正文
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();
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_05_3_week/Code01_MaxNumberUnderLimit.java)
- 上一篇： JavaScript去除数组重复元素的几种方法
- 下一篇： 不产生新的数组，删除数组里的重复元素
猜你喜欢
- 2024-11-22 Excel多列去重的两种方式
- 2024-11-22 js 数组去重复
- 2024-11-22 想要优雅的Excel数据去重，还得是unique函数
- 2024-11-22 自从学了深入解析java虚拟机:FullGC和字符串去重后，我无敌了
- 2024-11-22 携程 & 蘑菇街 & bilibili:手写数组去重、扁平化函数
- 2024-11-22 java数组的拷贝及Arrays类
- 2024-11-22 简单学Python——NumPy库7——排序和去重
- 2024-11-22 VBA数组与字典解决方案第44讲:利用字典排重，并提取不重复值
- 2024-11-22 php怎么用array_unique()函数去除数组中重复的值?
- 2024-11-22 List怎么去重?还只会用Set互换吗?一篇文章帮你打开“新世界”
欢迎 你 发表评论:
- 最近发表
-
- 五，网络安全IDA Pro反汇编工具初识及逆向工程解密实战
- 「JAVA8」- Lambda 表达式（java lambda表达式原理）
- 深入探讨Java代码保护:虚拟机保护技术的新时代
- Nginx反向代理原理详解(图文全面总结)
- 逆向拆解日本IT，哪些Java技术栈薪资溢价高
- mybatis 逆向工程使用姿势不对，把表清空了，心里慌的一比
- Spring Boot集成ProGuard轻松实现Java 代码混淆， Java 应用固若金汤
- 从 Java 代码逆向工程生成 UML 类图和序列图
- 人与人相处:尊重是标配，靠谱是高配，厚道是顶配
- Windows系统安装日期如何修改（windows10怎么修改安装日期）
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论，来添加一个吧(●'◡'●)