Չորս Leetcode լուծման հզորություն


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Երկու սիգմա
Բիթի մանիպուլյացիա Մաթեմատիկա

Բառը

Խնդիրի հայտարարություն

Մեզ տրված է ամբողջ թիվ, և մենք պետք է ստուգենք ՝ արդյոք թիվը 4-ի ուժն է, թե ոչ: Թիվը 4-ի ուժն է, եթե գոյություն ունի ամբողջ թիվ a այնպիսին է, որ,  num = 4 ^ ա.

Օրինակ

16
true
5
false

Մոտեցում 1 (կոպիտ ուժ)

Թիվը 4-ի ուժ է, թե ոչ ստուգելու ակնհայտ ձևը 4-ի բոլոր ճարպերը հանելն է `բազմիցս բաժանելով թիվը 4-ի վրա, մինչև այն բաժանվում է 4-ի: Վերջապես ստուգեք, արդյոք մնացած թիվը հավասար է 1-ի, թե ոչ: Եթե ​​դա 1 է, ապա ակնհայտ է, որ 4-ից բացի այլ գործոն գոյություն չունի, հետևաբար թիվը 4-ի ուժն էր, եթե 1-ը չէ, ապա թիվը 4-ի ուժ չէ:

Իրականացում չորս Leetcode լուծման հզորության համար

C ++ ծրագիր

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

bool isPowerOfFour(int n) 
{
     if (n == 0) return false;

     while (n % 4 == 0) n /= 4;

     if(n==1) return true;
     else return false;
}

int main() 
{
   int n=16;
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

Java ծրագիր

import java.util.*;
class Rextester{
    
   public static boolean isPowerOfFour(int n) 
   {     
         if (n == 0) return false;
        
         while (n % 4 == 0) n /= 4;
         
         if(n==1) return true;
         else return false;
        
    }
    
    public static void main(String args[])
    {
       	int n=16;
        System.out.println(isPowerOfFour(n));
    }
}
true

Բարդության վերլուծություն չորս Leetcode լուծույթի հզորության համար

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

O (logN): Տրված թիվը յուրաքանչյուր անգամ բաժանում ենք 4-ի: Ուստի ամենավատ դեպքում օղակը կգործի logN (հիմք 4) անգամ: Այսպիսով, մենք կարող ենք ասել, որ ժամանակի բարդությունը O է (logN):

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

O (1): Լրացուցիչ հիշողություն չի օգտագործվում:

Մոտեցում 2 (նախահաշվարկ)

Մենք գիտենք, որ ամբողջ թվերի (32-բիթ) տիրույթում շատ սահմանափակ թվեր կլինեն, որը 4-ի ուժն է: Ինչպե՞ս:
Տեսնենք.

Մեզ տրվել է x ամբողջ թիվ, հետեւաբար ՝ x <= 2 ^ 31-1
Այսպիսով, այս միջակայքում 4-ի առավելագույն հզորությունը կլինի ՝ log4 (2 ^ 31-1) = 15

Այժմ մենք կարող ենք հեշտությամբ պահել այս 15 համարները ՝ կատարելով նախահաշվարկ:
Ուստի այժմ յուրաքանչյուր թվի համար անընդհատ ժամանակում կարող ենք գտնել `դա 4-ի ուժ է, թե ոչ:

Իրականացում չորս Leetcode լուծման հզորության համար

C ++ ծրագիր

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

set<int> nums;

bool isPowerOfFour(int n) 
{
    return nums.count(n);
}

int main() 
{
    int n=15;
    int x = 1;
    nums.insert(x);
    for (int i = 1; i < n + 1; ++i) 
    {
      x = x * 4;
      nums.insert(x);
    }
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

Java ծրագիր

import java.util.*;
class Rextester{
    
    static int n = 15;
    static List<Integer> nums = new ArrayList<Integer>();
    static{
            int x = 1;
            nums.add(x);
            for (int i = 1; i < n + 1; ++i) 
            {
              x = x * 4;
              nums.add(x);
            }
    }
    
    public static boolean isPowerOfFour(int n) 
    {
         return nums.contains(n);
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

Բարդության վերլուծություն չորս Leetcode լուծույթի հզորության համար

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

O (1): Մենք ունենք բոլոր համարները, որոնք մեր ծրագրում պահվում են 4-ի հզորությունը: Հետևաբար, մենք կարող ենք որոնել տրված համարը և անընդհատ ժամանակում վերադարձնել ճիշտ կամ կեղծ:

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

O (1): 32-բիթանոց ամբողջական մուտքի համար հիշողության մեջ պահվում է ընդամենը 15 համար, այսինքն `հաստատուն տարածություն կամ O (1):

Մոտեցում 3 (Բիթի մանիպուլյացիա)

Բիթի մանիպուլյացիայի միջոցով մենք կարող ենք շատ արդյունավետ լուծել այս խնդիրը:
Մենք գիտենք, որ համարը պետք է լինի 4-ի, այն նաև պետք է լինի 2-ի: Մենք արդեն քննարկել ենք, որ մի շարք պետք է լինի 2-ի հզորություն Երկու լեյկոդ լուծույթի հզորություն օգտագործելով բիթ մանիպուլյացիա:

Այսպիսով, եկեք նախ ստուգենք, արդյոք թիվը երկուսի ուժ է. X> 0 և x & (x - 1) == 0:
Այժմ մենք կարող ենք վերլուծել, որ եթե թիվը 2-ի զույգ ուժ է, ապա դա կլինի 4-ի, իսկ եթե թիվը 2-ի կենտ հզորություն է, ապա դա չի լինի 4-ի:
Երկուական ներկայացման դեպքում այս թիվը պարունակում է միայն մեկ-բիթանոց զույգ դիրքում (1 հզորություն) կամ կենտ դիրքում (ոչ 4 հզորություն):

Չորս Leetcode լուծման հզորություն

Հետևաբար, եթե մենք կատարենք բիթային թվով և (4… .101010) թվով (հիմք 10) թվից (2-ի հզորություն), արդյունքը կլինի զրո:
Մենք կարող ենք կիրառել վերը նշված հասկացությունը ՝ գրելով երկրորդ համարը տասնվեցերորդում որպես (aaaaaaaa) (հիմք 16):

Իրականացում չորս Leetcode լուծման հզորության համար

C ++ ծրագիր

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

bool isPowerOfFour(int n) 
{
    return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

Java ծրագիր

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

Բարդության վերլուծություն չորս Leetcode լուծույթի հզորության համար

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

O (1): Bitwise և անընդհատ գործողություն է:

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

O (1): Մշտական ​​տարածություն:

Մոտեցում 4 (բիթի մանիպուլյացիա + մաթեմատիկա)

Մենք գիտենք, որ եթե համարը 4-ի ուժ է, ապա դա կլինի նույնիսկ 2-ի ուժ: Հաշվի առնելով x = 2 ^ a- ի երկու դեպքերը ՝
a = 2k կամ a = 2k + 1

Եթե ​​այս երկու թվերը բաժանենք 3-ի, մենք կստանանք մնացորդը հետևյալ կերպ.
2 ^ 2k mod 3 = 4 ^ k mod 3 = (3 + 1) ^ k mod 3 = 1
2 ^ (2k + 1) mod 3 = 2 × 4 ^ k mod 3 = 2 × (3 + 1) ^ k mod 3 = 2

Հետևաբար, համարը 4-ի հզորություն ունենալու վերջնական պայմանը պետք է լինի.

x- ը 2-ի և x% 3 == 1-ի հզորությունն է

Իրականացում չորս Leetcode լուծման հզորության համար

C ++ ծրագիր

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

bool isPowerOfFour(int n) 
{
     return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

Java ծրագիր

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

Բարդության վերլուծություն չորս Leetcode լուծույթի հզորության համար

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

O (1): Մշտական ​​ժամանակ:

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

O (1): Մշտական ​​տարածություն: