当前位置:网站首页>LeetCode每日一题(1362. Closest Divisors)
LeetCode每日一题(1362. Closest Divisors)
2022-07-03 09:01:00 【wangjun861205】
Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
Example 1:
Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
Example 2:
Input: num = 123
Output: [5,25]
Example 3:
Input: num = 999
Output: [40,25]
Constraints:
- 1 <= num <= 10^9
最优解当然是 n² = num + 1 或者 n² = num + 1, 因为 1 <= num <= 1000000000, 那我们的 n 自然不会大于 40000, 有了这个条件托底, 我们就算用最简单的方法从 40000 一路试到 1 也可以, 当然, 最好是把 n 先判断出来
impl Solution {
pub fn closest_divisors(num: i32) -> Vec<i32> {
if num == 1 {
return vec![1, 2];
}
let num = num as i64;
// 指数
let mut e = 1u32;
loop {
if 2i64.pow(e) >= num {
break;
}
e += 1;
}
// 计算出n的上限
let n = 2i64.pow(e / 2 + e % 2);
let mut a = i64::MAX;
let mut b = 0;
for v in (1..=n).rev() {
if (num + 1) % v == 0 {
if ((num + 1) / v - v).abs() < (a - b).abs() {
a = (num + 1) / v;
b = v;
}
}
if (num + 2) % v == 0 {
if ((num + 2) / v - v).abs() < (a - b).abs() {
a = (num + 2) / v;
b = v;
}
}
}
vec![a as i32, b as i32]
}
}
边栏推荐
- Spark 概述
- [point cloud processing paper crazy reading classic version 13] - adaptive graph revolutionary neural networks
- Tag paste operator (#)
- Just graduate student reading thesis
- Utilisation de hudi dans idea
- Move anaconda, pycharm and jupyter notebook to mobile hard disk
- [point cloud processing paper crazy reading frontier version 11] - unsupervised point cloud pre training via occlusion completion
- MySQL installation and configuration (command line version)
- Crawler career from scratch (I): crawl the photos of my little sister ① (the website has been disabled)
- Excel is not as good as jnpf form for 3 minutes in an hour. Leaders must praise it when making reports like this!
猜你喜欢
【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs
【点云处理之论文狂读经典版14】—— Dynamic Graph CNN for Learning on Point Clouds
[kotlin learning] operator overloading and other conventions -- overloading the conventions of arithmetic operators, comparison operators, sets and intervals
npm install安装依赖包报错解决方法
Trial of the combination of RDS and crawler
Jenkins learning (III) -- setting scheduled tasks
There is no open in default browser option in the right click of the vscade editor
Utilisation de hudi dans idea
【Kotlin学习】高阶函数的控制流——lambda的返回语句和匿名函数
Install third-party libraries such as Jieba under Anaconda pytorch
随机推荐
Powerdesign reverse wizard such as SQL and generates name and comment
Overview of database system
[point cloud processing paper crazy reading classic version 11] - mining point cloud local structures by kernel correlation and graph pooling
Linxu learning (4) -- Yum and apt commands
Flink学习笔记(十一)Table API 和 SQL
Flink学习笔记(九)状态编程
Excel is not as good as jnpf form for 3 minutes in an hour. Leaders must praise it when making reports like this!
【Kotlin学习】类、对象和接口——定义类继承结构
Spark cluster installation and deployment
2022-2-13 learning xiangniuke project - version control
Use the interface colmap interface of openmvs to generate the pose file required by openmvs mvs
[solution to the new version of Flink without bat startup file]
Numerical analysis notes (I): equation root
Go language - IO project
State compression DP acwing 91 Shortest Hamilton path
[kotlin learning] operator overloading and other conventions -- overloading the conventions of arithmetic operators, comparison operators, sets and intervals
[point cloud processing paper crazy reading frontier version 11] - unsupervised point cloud pre training via occlusion completion
Install database -linux-5.7
MySQL installation and configuration (command line version)
【点云处理之论文狂读经典版8】—— O-CNN: Octree-based Convolutional Neural Networks for 3D Shape Analysis