将数量减少为零的Leetcode解决方案的步骤数


难度级别 易得奖学金
经常问 亚马逊 谷歌 停留时间 微软
位操作

问题“将数字减少到零的步数”解决方案指出,给定一个 整数。 找到将给定整数转换为0的最小步骤数。您可以执行两个步骤之一,将1减去或将整数除以2。问题看似简单,但在通过解决方案之前,我们将看到一些示例。

将数量减少为零的Leetcode解决方案的步骤数

n = 14
6

说明:将给定整数(= 14)减小为0的最小步骤数需要6个步骤。 首先,将14除以2。现在剩下7,然后减去1。现在得到的数字是6。再次除以2。然后我们减去1三次,将整数(= 3)减小为0。

8
4

说明:我们使用3除法和1减法将8减为0。第一个步骤将8减为4,然后将4减为2,将2减为1。然后我们简单地从1减去1以获得0。

将步骤数减少到零Leetcode解决方案的步骤的蛮力方法

这个问题很标准,在各种测试中已经被问过几次了。 问题的蛮力解决方案不足以在时限内解决问题。 蛮力解决方案使用递归作为解决方案。 对于每个整数,因为我们有两个可能的运算。 我们都执行它们,然后递归调用修改后的整数。 解决方案的时间复杂度将是指数级的,因此对于大输入而言效率不高。 编码后的解决方案将导致运行时错误,因为包含小数部分的数字将永远无法减少为0。

将步数减少到零的Leetcode解决方案的优化方法

该问题是众所周知的标准问题之一。 如果仅在遇到奇数时减去1,就可以轻松解决该问题。 当我们得到偶数时,将数字除以2。 因此,问题的解决方案取决于整数的奇偶校验。 当数字为偶数时,为什么要除以2? 因为将数字减半比减1总是更好或同样好,那为什么不除以奇数呢? 因为这样我们最终将得到十进制整数,使用这两种操作无论如何都不能将其减小为0。

优化的代码,将步数减少到零Leetcode解决方案

C ++代码

#include <bits/stdc++.h>
using namespace std;

int numberOfSteps (int num) {
    int cnt = 0;
    while(num){
        if(num&1)num--;
        else num/=2;
        cnt++;
    }
    return cnt;
}

int main(){
    cout<<numberOfSteps(14);
}
6

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numberOfSteps (int num) {
        int cnt = 0;
        while(num > 0){
            if(num%2 == 1)num--;
            else num/=2;
            cnt++;
        }
        return cnt;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    System.out.print(numberOfSteps(14));
  }
}
6

复杂度分析

时间复杂度

O(logN), 因为只要得到偶数,我们就将整数除以2。 然后,通过从中减去1,将每个奇数转换为偶数。 因此,时间复杂度是对数的。

空间复杂度

O(1), 因为我们使用了一个变量,那就是恒定空间。 因此,空间复杂度也是恒定的。