Քանակը քայլերի է նվազեցնել մի շարք է զրո Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Google Hrt Microsoft
Բիթի մանիպուլյացիա

Խնդիրը համարը քայլերի նվազեցնել համարը զրոյի 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 լուծման

Խնդիրը բավականին ստանդարտ է և մի քանի անգամ հարցվել է տարբեր փորձարկումների ժամանակ: Խնդրի բիրտ ուժի լուծումը բավարար չէ խնդրի լուծման համար սահմանված ժամկետում: Brute force լուծումը լուծման համար օգտագործում է ռեկուրս: Յուրաքանչյուր ամբողջ թվով, քանի որ մենք ունենք երկու հնարավոր գործողություն: Մենք կատարում ենք երկուսն էլ, այնուհետև ռեկուրսիվորեն կանչում ենք փոփոխված ամբողջ թվին: Լուծման համար ժամանակի բարդությունը ցուցիչ կլինի, ուստի մեծ ներդրումների համար արդյունավետ չէ: Լուծումը, երբ ծածկագրվում է, կհանգեցնի գործարկման ժամանակ սխալի, քանի որ տասնորդական մաս պարունակող թվերը երբեք ի վիճակի չեն լինի հասցնել 0-ի:

Օպտիմիզացված մոտեցում մի շարք քայլերի `թվերը զրոյական կոդավոր լուծման իջեցնելու համար

Խնդիրը ստանդարտ խնդիրներից մեկն է, որոնք շատ լայնորեն հայտնի են: Խնդիրը կարելի է հեշտությամբ լուծել, եթե 1-ը հանենք միայն այն ժամանակ, երբ կենտ թվին ենք հանդիպում: Եվ թիվը բաժանենք 2-ի, երբ կստանանք զույգ թիվ: Այսպիսով, խնդրի լուծումը կախված է ամբողջ թվաքանակի պարիտետից: Ինչու ենք մենք բաժանում 2-ից, երբ թիվը զույգ է: Քանի որ միշտ ավելի լավ է կամ հավասարապես նուրբ է թիվը կրճատել `այն կիսով չափ դարձնելով, քան հանել 1-ը: Այդ դեպքում ինչո՞ւ կենտ թվերը չենք բաժանում: Քանի որ այդ դեպքում մենք, ի վերջո, կունենանք տասնորդական ամբողջ թվեր, որոնք այս երկու գործողությունները ոչ մի կերպ օգտագործելով, հնարավոր չէ հասցնել 0-ի:

Քայլերի քանակի օպտիմիզացված ծածկագիր ՝ թիվը համարյա զրոյական լուծման լուծում իջեցնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (logN), քանի որ ամբողջ թիվը բաժանում ենք 2-ի ՝ ամեն անգամ, երբ զույգ թիվ ենք ստանում: Յուրաքանչյուր կենտ թիվ այնուհետև փոխարկվում է զույգի, դրանից հանելով 1: Այսպիսով, ժամանակի բարդությունը ստացվում է լոգարիթմական:

Տիեզերական բարդություն

O (1), քանի որ մենք օգտագործել ենք մեկ փոփոխական, դա հաստատ տարածություն է: Այսպիսով տարածության բարդությունը նույնպես հաստատուն է: