2021-12-16:给定两个数a和b, 第1轮,把1选择给a或者b, 第2轮,把2选择给a或者b, ... 第i轮,把i选择给
2023-04-18 15:35:01 时间
2021-12-16:给定两个数a和b,
第1轮,把1选择给a或者b,
第2轮,把2选择给a或者b,
第i轮,把i选择给a或者b。
想让a和b的值一样大,请问至少需要多少轮?
来自字节跳动。
答案2021-12-16:
这道题很难想。
求差s。a=(sum+s)/2,b=(sum-s)/2。sum=1+2+……+i。i用倍增法。
时间复杂度:O(logN)。
空间复杂度:O(1)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
a := 19019
b := 8439284
ret := minStep2(a, b)
fmt.Println(ret)
}
func minStep2(a, b int) int {
if a == b {
return 0
}
s := a - b
if s < 0 {
s = -s
}
// 找到sum >= s, 最小的i
begin := best(s << 1)
for (begin*(begin+1)/2-s)%2 != 0 {
begin++
}
return begin
}
func best(s2 int) int {
L := 0
R := 1
for R*(R+1) < s2 {
L = R
R *= 2
}
ans := 0
for L <= R {
M := (L + R) / 2
if M*(M+1) >= s2 {
ans = M
R = M - 1
} else {
L = M + 1
}
}
return ans
}
执行结果如下:
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class38/Code01_FillGapMinStep.java)
相关文章
- 在企业微信抓住12亿微信客户的下一个十年
- Ubuntu16安装Nvidia驱动(GTX1060显卡)
- Anaconda3+CUDA10.1+CUDNN7.6+TensorFlow2.6安装(Ubuntu16)
- 耕耘技术收获“三好”口碑 浪潮云海2020成绩单
- 大数据开发工程师基本功修炼之Linux学习笔记(二)
- 2021年云计算主要趋势预测,7个分析结论,互联网未来可期
- 大数据开发工程师基本功修炼之Linux学习笔记(三)
- 2021云计算“奇点”将迎二次爆发,五大新趋势凸显
- 关于那颗6G卫星,我表示“一脸懵圈”
- Ubuntu16桌面版编译和安装OpenCV4
- 车险合规要求再升级,评驾保险SaaS平台破解经销商难题
- 2021中国云计算市场展望:行业变革的三大关键
- 大数据开发工程师基本功修炼之Linux学习笔记(四)
- 中国首个ISO/IEC人工智能国际标准项目获批立项
- 加速AI之旅,成为企业领袖,你还需这几步
- 五部委印发《国家新一代人工智能标准体系建设指南》
- 工信部修订人工智能等行业标准项目计划
- 【图解Linux内核】Page Cache
- 全球5G标准专利声明 我国企业占比超过30%
- 用GitHub Actions制作Docker镜像