ስኩርት (x) Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ google ግራፍ የ Microsoft በ Uber
የሁለትዮሽ ፍለጋ ሒሳብ

አርዕስቱ እንደሚለው ፣ የቁጥሩን ካሬ መሠረት ማግኘት አለብን ፡፡ ቁጥሩ ነው ይበል x, ከዚያ ስኩርት (x) እንደዚህ ያለ ቁጥር ነው ስኩርት (x) * ስኩርት (x) = x. የቁጥሩ ስኩዌር ሥር የተወሰነ የአስርዮሽ እሴት ከሆነ ታዲያ የካሬው ሥሩን ወለል ዋጋ መመለስ አለብን።

ለምሳሌ

4
2
7
2

አቀራረብ (አስቀድሞ የተገነቡ ተግባራት)

ሒሳብ የ C ++ ቤተመፃህፍት እና lang. የሂሳብ የጃቫ ቤተመፃህፍት የቁጥር ካሬውን መሠረት ለመመለስ ቀድሞ የተገነቡ ተግባራት አሏቸው ፡፡ ማመልከት እንችላለን ፎቅ () ማንኛውንም የአስርዮሽ እሴት ለማስቀረት።

አልጎሪዝም

  1. ቁጥሩ ከ 2 በታች ከሆነ እራሱን ይመልሱ
  2. ይደውሉ ስኩርት () ሥራ
  3. የተገኘውን እሴት ወለል ያድርጉ
  4. ውጤቱን ያትሙ

የ Sqrt (x) Leetcode መፍትሔ አፈፃፀም

C ++ ፕሮግራም

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

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return floor(sqrt(x));
}

int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

የጃቫ ፕሮግራም

import java.lang.Math;

class sqrt_x
{
    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return (int)Math.floor(Math.sqrt(x));
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ስኩርት (x) ን ለማግኘት የአልጎሪዝም ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (logN) ስኩርት () ተግባር ይጠቀማል ኒውተን-ራፋሰን የ O (logN) የጊዜ ውስብስብነት ያለው የቁጥር ካሬ ስሩን ለማስላት ዘዴ።

የቦታ ውስብስብነት

ኦ (1). ቋሚ ቦታ ለተለዋጮች ጥቅም ላይ ይውላል።

አቀራረብ (የሁለትዮሽ ፍለጋ)

እዚህ ፣ እኛ በመጀመር ላይ ባሉ ቁጥሮች ብዛት ላይ የሁለትዮሽ ፍለጋን ማመልከት እንችላለን 1 ወደ ላይ መውጣት x / 2x = የተሰጠው ቁጥር። እዚህ ፣ ከ ‹ይልቅ› በተመረጠው የተመረጠ ቅደም ተከተል ላይ የሁለትዮሽ ፍለጋን እንተገብራለን ደርድር.

የቀኝ ወሰን እንደ ተቀናብሯል x / 2 ምክንያቱም ለእያንዳንዱ ቁጥር x ፣ ከ 2 ይበልጣል ፣ የካሬ ስራቸው ወለል ከ x / 2. ያነሰ ይሆናል ፣ በሁለትዮሽ ፍለጋ ውጤት ላይ በመመርኮዝ ከመጀመሪያው የናሙና ቦታ ግራ ወይም ቀኝ ግማሾችን መዝለል እንችላለን።

ስኩርት (x)

አልጎሪዝም

  1. ፍጠር ሁለትዮሽ ፍለጋ () የ sqrt (x) ተግባር መመለሻ ወለል
  2. ተለዋዋጭ ያስጀምሩ ተመኘች ውጤቱን ለማከማቸት
  3. ቁጥሩ ከ 2 በታች ከሆነ እራሱን ይመልሱ
  4. የመጀመሪያ ስም ግራቀኝ እንደ 1 እና x / 2 ዋጋዎች በቅደም ተከተል
  5. ድረስ ግራ <= ቀኝ:
    • የዚህን ክልል መሃል ያግኙ ፣ መካከለኛ = ግራ + ቀኝ / 2
    • አጋማሽ ካሬ እኩል ከሆነ x,  የካሬው ሥር እንደ ሆነ ይመልሱ
    • የካሬው አጋማሽ ካነሰ x፣ ግራ = አጋማሽ + 1 ን በማቀናጀት ወደ ቀኝ ግማሽ ይዝለሉ
    • አለበለዚያ በቀኝ = መካከለኛ - 1 በማቀናጀት ወደ ግራ ግማሽ ይዝለሉ እና ይህን እሴት በ ውስጥ ያስቀምጡ ተመኘች
  6. ውጤቱን ያትሙ

የ Sqrt (x) Leetcode መፍትሔ አፈፃፀም

C ++ ፕሮግራም

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

int binarySearch(int x)
{
    int left = 1 , right = x / 2 , mid , ans;
    long temp;

    while(left <= right)
    {
        mid = (left + (right - left) / 2);
        temp = (long)mid * (long)mid;
        //mid * mid can be large, so use long
        if(temp == x)
            return mid;
        if(temp < x)
            ans = mid , left = mid + 1;
        else
            right = mid - 1;
    }
    return ans;
}

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return binarySearch(x);
}


int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

የጃቫ ፕሮግራም

import java.lang.Math;

class sqrt_x
{
    static int binarySearch(int x)
    {
        int left = 1 , right = x / 2 , mid , ans = 0;
        long temp;

        while(left <= right)
        {
            mid = (left + (right - left) / 2);
            temp = (long)mid * (long)mid;
            //mid * mid can be large, so use long
            if(temp == x)
                return mid;
            if(temp < x)
            {
                ans = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ans;
    }

    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return binarySearch(x);
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ስኩርት (x) ን ለማግኘት የአልጎሪዝም ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (logN) ፣ የሁለትዮሽ ፍለጋው የናሙና ቦታውን እስከ ግማሽው ድረስ እየከፈለ እንደቀጠለ ነው። በጣም በከፋ ሁኔታ ውስጥ ፣ እስከ ማካካስ ይችላል የ logN ንፅፅሮች.

የቦታ ውስብስብነት

ኦ (1). እንደገና, ለተለዋዋጮች ቋሚ ቦታ ጥቅም ላይ ይውላል.