当前位置:网站首页>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).
边栏推荐
- Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
- Base dice (dynamic programming + matrix fast power)
- Chapter 1 overview of MapReduce
- Bidirectional linked list - all operations
- Cmake error: could not create named generator visual studio 16 2019 solution
- 视频压缩编码和音频压缩编码基本原理
- Story of [Kun Jintong]: talk about Chinese character coding and common character sets
- 音视频开发面试题
- Raspberry pie 4B installation opencv3.4.0
- 解决Intel12代酷睿CPU单线程调度问题(二)
猜你喜欢
本地可视化工具连接阿里云centOS服务器的redis
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
第6章 Rebalance详解
第一章 MapReduce概述
我在字节跳动「修电影」
Chapter III principles of MapReduce framework
软通乐学-js求字符串中字符串当中那个字符出现的次数多 -冯浩的博客
Raspberry pie 4B installation opencv3.4.0
Click QT button to switch qlineedit focus (including code)
字节跳动新程序员成长秘诀:那些闪闪发光的宝藏mentor们
随机推荐
第5章 NameNode和SecondaryNameNode
Tree of life (tree DP)
Chapter 5 yarn resource scheduler
300th weekly match - leetcode
Codeforces Round #799 (Div. 4)A~H
Bisphenol based CE Resin Industry Research Report - market status analysis and development prospect forecast
ffmpeg命令行使用
Cmake error: could not create named generator visual studio 16 2019 solution
Simple records of business system migration from Oracle to opengauss database
Tencent interview algorithm question
(lightoj - 1354) IP checking (Analog)
Tert butyl hydroquinone (TBHQ) Industry Research Report - market status analysis and development prospect forecast
SQL quick start
Browser print margin, default / borderless, full 1 page A4
Codeforces Round #771 (Div. 2)
How to insert mathematical formulas in CSDN blog
Chapter 1 overview of MapReduce
QT realizes window topping, topping state switching, and multi window topping priority relationship
Codeforces - 1526C1&&C2 - Potions
两个礼拜速成软考中级软件设计师经验