Leetcode төрт шешімінің күші


Күрделілік дәрежесі оңай
Жиі кіреді Екі Sigma
Бит манипуляциясы математика

Мазмұны

Проблемалық мәлімдеме

Бізге бүтін сан беріледі және санның 4-ке тең екенін немесе болмауын тексеру керек. Егер бүтін сан болса, сан 4-ке тең болады a осылай,  num = 4 ^ a.

мысал

16
true
5
false

1 тәсіл (қатал күш)

Санның 4-ке тең екендігін тексерудің айқын әдісі - 4-ке бөлінгенге дейін санды 4-ке бірнеше рет бөлу арқылы барлық фаторларды алып тастау. Ал қалған санның 4-ге тең екенін немесе болмауын тексеріп шығу керек. Егер ол 1-ге тең болса, онда 1-тен басқа ешқандай фактор жоқ екендігі айқын, демек, сан 4-ке тең болды. Егер ол 4 болмаса, онда сан 1-ке тең емес.

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 төрт шешімінің қуаттылығының күрделілігін талдау

Уақыттың күрделілігі

O (logN): Біз берілген санды әр уақытта 4-ке бөлеміз. Сондықтан нашар жағдайда цикл logN (4-негіз) рет жұмыс істейді. Демек, уақыттың күрделілігі O (logN) деп айтуға болады.

Ғарыштың күрделілігі 

O (1): Қосымша жад қолданылмайды.

2-тәсіл (алдын-ала есептеу)

Біз бүтін (32-биттік) диапазонда 4-ке тең шектеулі сандар болатынын білеміз. Қалай?
Қарайық:

Бізге бүтін х берілді, сондықтан: 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 төрт шешімінің қуаттылығының күрделілігін талдау

Уақыттың күрделілігі

O (1): Бізде бағдарламада сақталған 4-тен тұратын барлық нөмірлер бар. Демек, біз берілген санды іздеп, ақиқат немесе жалғанды ​​тұрақты уақытта қайтара аламыз.

Ғарыштың күрделілігі 

O (1): 32 биттік бүтін енгізу үшін жадта тек 15 сан сақталады, яғни тұрақты кеңістік немесе O (1).

3-тәсіл (Бит манипуляциясы)

Биттік манипуляцияны қолдану арқылы біз бұл мәселені өте тиімді шеше аламыз.
Біз санның 4-ке тең болатынын білеміз, ол 2-ге тең болуы керек. Санның 2 дюймге тең болу шартын біз бұған дейін талқыладық Leetcode екі шешімінің қуаты биттік манипуляцияны қолдану.

Алдымен санның екіге тең екендігін тексерейік: x> 0 және x & (x - 1) == 0.
Енді егер санның жұп күші 2-ге тең болса, онда ол 4-ке тең болады, ал егер тақ 2-ге тең болса, онда ол 4-ке тең болмайды деп талдай аламыз.
Екілік көріністе бұл сан тек жұп позицияда (қуаттылық 1) немесе тақ позицияда (қуаттылықта 4 емес) тек 4 биттік болады.

Leetcode төрт шешімінің күші

Демек, (4… .101010) (10-негіз) санымен санды (2-ті) санмен жүргізсек, нәтиже нөлге тең болады.
Екінші санды он алтылық жүйеге (ааааааааа) деп жазу арқылы (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 төрт шешімінің қуаттылығының күрделілігін талдау

Уақыттың күрделілігі

O (1): Биттік және тұрақты жұмыс.

Ғарыштың күрделілігі 

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 төрт шешімінің қуаттылығының күрделілігін талдау

Уақыттың күрделілігі

O (1): Тұрақты уақыт.

Ғарыштың күрделілігі 

O (1): Тұрақты кеңістік.