当前位置:网站首页>LeetCode 1558. Get the minimum number of function calls of the target array
LeetCode 1558. Get the minimum number of function calls of the target array
2022-07-06 16:43:00 【Daylight629】
1558. Get the minimum number of function calls to the target array
Give you a nums
The size is the same and the initial value is 0 Array of arr
, Please call the above function to get the integer array nums
.
Please return and will arr
become nums
Minimum number of function calls .
The answer is guaranteed in 32 Bits within signed integers .
Example 1:
Input :nums = [1,5]
Output :5
explain : Add... To the second number 1 :[0, 0] become [0, 1] (1 operations ).
Multiply all numbers by 2 :[0, 1] -> [0, 2] -> [0, 4] (2 operations ).
Add... To both numbers 1 :[0, 4] -> [1, 4] -> [1, 5] (2 operations ).
The total number of operations is :1 + 2 + 2 = 5 .
Example 2:
Input :nums = [2,2]
Output :3
explain : Add... To both numbers 1 :[0, 0] -> [0, 1] -> [1, 1] (2 operations ).
Multiply all numbers by 2 : [1, 1] -> [2, 2] (1 operations ).
The total number of operations is : 2 + 1 = 3 .
Example 3:
Input :nums = [4,2,5]
Output :6
explain :( initial )[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] (nums Array ).
Example 4:
Input :nums = [3,2,2,4]
Output :7
Example 5:
Input :nums = [2,4,8,16]
Output :8
Tips :
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
Two 、 Method 1
greedy
class Solution {
public int minOperations(int[] nums) {
int ret = 0, maxn = 0;
for (int num : nums) {
maxn = Math.max(maxn, num);
while (num != 0) {
if ((num & 1) != 0) {
ret++;
}
num >>= 1;
}
}
if (maxn != 0) {
while (maxn != 0) {
ret++;
maxn >>= 1;
}
ret--;
}
return ret;
}
}
Complexity analysis
Time complexity :O(n×m), among nn It's an array nums The length of ,m Is the maximum number of bits of the binary representation of the elements in the array , These elements in this question are 32 Bit signed integers , therefore m<32.
Spatial complexity :O(1).
边栏推荐
- Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
- 新手必会的静态站点生成器——Gridsome
- 解决Intel12代酷睿CPU单线程调度问题(二)
- Audio and video development interview questions
- Summary of FTP function implemented by qnetworkaccessmanager
- Detailed explanation of FLV format
- Chapter III principles of MapReduce framework
- 第一章 MapReduce概述
- 软通乐学-js求字符串中字符串当中那个字符出现的次数多 -冯浩的博客
- sublime text 代码格式化操作
猜你喜欢
Remove the border when input is focused
Kubernetes cluster deployment
第一章 MapReduce概述
Submit several problem records of spark application (sparklauncher with cluster deploy mode)
Chapter 5 namenode and secondarynamenode
(lightoj - 1323) billiard balls (thinking)
Problem - 922D、Robot Vacuum Cleaner - Codeforces
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
SQL quick start
字节跳动新程序员成长秘诀:那些闪闪发光的宝藏mentor们
随机推荐
MP4格式详解
SF smart logistics Campus Technology Challenge (no T4)
本地可视化工具连接阿里云centOS服务器的redis
300th weekly match - leetcode
Anaconda下安装Jupyter notebook
Kubernetes cluster deployment
Hbuilder X格式化快捷键设置
QT implementation window gradually disappears qpropertyanimation+ progress bar
Hbuilder x format shortcut key settings
(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
Raspberry pie 4B installation opencv3.4.0
input 只能输入数字,限定输入
Codeforces Round #771 (Div. 2)
Basic principles of video compression coding and audio compression coding
Market trend report, technical innovation and market forecast of double-sided foam tape in China
两个礼拜速成软考中级软件设计师经验
Ffmpeg command line use
第5章 NameNode和SecondaryNameNode
Gridhome, a static site generator that novices must know
(lightoj - 1369) answering queries (thinking)