Иқтидори чор ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Ду Sigma
Манипулясияи каме Матем

Изҳороти мушкилот

Ба мо як адади бутун медиҳанд ва мо бояд тафтиш кунем, ки рақам қудрати 4 аст ё не. Агар адади бутун вуҷуд дошта бошад, адад қудрати 4 дорад a чунин,  num = 4 ^ a.

мисол

16
true
5
false

Муносибати 1 (Force Brute)

Усули возеҳи санҷидани он, ки рақам 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

Мураккабии вақт

O (logN): Мо рақами додашударо ҳар дафъа ба 4 тақсим мекунем. Аз ин рӯ, дар бадтарин ҳолат, давр logN (base 4) -ро кор мекунад. Аз ин рӯ, мо гуфта метавонем, ки мураккабии вақт O (logN) аст.

Мураккабии фазо 

О (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

Мураккабии вақт

О (1): Мо ҳамаи рақамҳоро дорем, ки қувваи 4 дар барномаи мо маҳфуз аст. Аз ин рӯ, мо метавонем адади додашударо ҷустуҷӯ кунем ва дар вақти доимӣ рост ё дурӯғро баргардонем.

Мураккабии фазо 

О (1): Барои вуруди 32-bit Integer танҳо дар рақам 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

Мураккабии вақт

О (1): Bitwise ва ин як амалиёти доимист.

Мураккабии фазо 

О (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 бояд чунин бошад:

х қудрати 2 ва х% 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

Мураккабии вақт

О (1): Вақти доимӣ.

Мураккабии фазо 

О (1): Фазои доимӣ.