將數量減少為零的Le​​etcode解決方案的步驟數


難度級別 容易獎學金
經常問 亞馬遜 谷歌 HRT Microsoft微軟
位操作

問題“將數字減少到零的步數”解決方案指出,給定一個 整數。 找到將給定整數轉換為0的最小步驟數。您可以執行兩個步驟之一,將1減去或將整數除以2。問題看似簡單,但在通過解決方案之前,我們將看到一些示例。

將數量減少為零的Le​​etcode解決方案的步驟數

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), 因為我們使用了一個變量,那就是恆定空間。 因此,空間複雜度也是恆定的。