የልዩ ኮድ መፍትሄውን ይፈልጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን google
ሃምሽንግ ሕብረቁምፊ

በዚህ ችግር ውስጥ ሁለት ተሰጠን ሕብረቁምፊዎች. ሁለተኛው ሕብረቁምፊ የመጀመሪያውን ሕብረቁምፊ ገጸ-ባህሪያትን በዘፈቀደ በማወዛወዝ እና ከዚያ በማናቸውም የዘፈቀደ አቀማመጥ ላይ አንድ ተጨማሪ ቁምፊ በማከል ነው የተፈጠረው። ወደ ሁለተኛው ሕብረቁምፊ የታከለውን ተጨማሪ ቁምፊ መመለስ ያስፈልገናል። ገጸ-ባህሪያቱ ሁል ጊዜ አነስተኛ የእንግሊዝኛ ፊደላት ይሆናሉ ፡፡

ለምሳሌ

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

ማብራሪያ # 1

ወደ ሕብረቁምፊ የታከለው ተጨማሪ ቁምፊ b እንደ ‹ክር› ነው a አልያዘም ፡፡

ማብራሪያ # 2

ሕብረቁምፊ ገመድ እያለ 4 'ሀ' ፊደላት አሉት አለው 5. ስለዚህ ፣ ተጨማሪው ደብዳቤ ‹ሀ› ነው ፡፡

አቀራረብ (መደርደር)

እነሱ የሚለያዩበትን የመጀመሪያውን ቦታ ለመፈለግ ሁለቱን ሕብረቁምፊዎች መደርደር እና በመቀጠል ሁለቱን በደብዳቤ መላክ እንችላለን ፡፡ ሁለተኛው ሕብረቁምፊ ሁል ጊዜ አንድ ይኖረዋል ተጨማሪ ባህሪ ስለዚህ ፣ እኛ ሁል ጊዜ አንድ ገመድ የት እናገኛለን ab ይለያል ፡፡ ሆኖም ፣ ክር ያለበት ሁኔታ ሊኖር ይችላል b ከተደረደሩ በኋላ እያንዳንዱን ቁምፊ በሕብረቁምፊ ይዛመዳል a ውስጥ ግን በመጨረሻ አንድ ተጨማሪ ባህሪ አለው። ይህንን አንድ ልዩ ጉዳይ ማስተናገድ ያስፈልገናል ፡፡

የልዩ ኮድ መፍትሄውን ይፈልጉ

አልጎሪዝም

  1. ሁለቱንም ክሮች ለይ ab. በጃቫ ውስጥ ስለማይቻል መጀመሪያ ወደ ውስጥ እንለውጣቸዋለን የቻር ድርድሮች
  2. በአጭሩ ሕብረቁምፊ ውስጥ ላሉት እያንዳንዱ ቁምፊዎች በደብዳቤ በቼክ ምርመራ እናደርጋለን-
    • በሕብረቁምፊ ውስጥ ያለው ቁምፊ ከሆነ በሕብረቁምፊ ውስጥ ካለው ተጓዳኝ ቁምፊ ጋር እኩል አይደለም b:
      • ይህንን ባህሪ ይመልሱ ፡፡
  3. የመጨረሻውን የሕብረቁምፊ ቁምፊ ይመልሱ ተጨማሪ ባህሪው ስለሆነ
  4. ውጤቱን ያትሙ

የልዩ ኮድ መፍትሄን አፈላላጊ አተገባበር

C ++ ፕሮግራም

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

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

የጃቫ ፕሮግራም

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

የልኬት ኮድ መፍትሄን የመፈለግ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (NlogN), የት N = ረዥሙ ገመድ። የ O (NlogN) ጊዜ የሚወስዱትን ሕብረቁምፊዎች / የቻር ድርድርዎች እናደርጋቸዋለን ፡፡

የቦታ ውስብስብነት

ኦ (ኤን) በጃቫ እና ኦ (1) ሕብረቁምፊዎቹን ወደ ውስጥ እንደለወጥን በ C ++ ውስጥ char ድርድር ጃቫ ውስጥ

አቀራረብ (ሀሺንግ)

በሁለቱም ሕብረቁምፊዎች ውስጥ እያንዳንዱን ገጸ-ባህሪ ከድግግሞሽ ጋር ሃሽ ማድረግ እና በድግግሞሽ የሚለየውን ገጸ-ባህሪን ማግኘት እንችላለን ፡፡ እኛ የማያቋርጥ ልዩ ቁምፊዎች ስላለን። ይህ ስልተ ቀመር ከላይ ከተወያየው የበለጠ ፈጣን ነው ፡፡ እንደ ቀልጣፋ አተገባበር እኛ መፍጠር እንችላለን ሃሽ ሠንጠረዥ እና በህብረቁምፊ ውስጥ ላሉት ለእያንዳንዱ ቁምፊ ድግግሞሽ ይጨምሩ a እና በህብረቁምፊ ውስጥ ላሉት ለእያንዳንዱ ቁምፊ ድግግሞሹን ቀንሷል b. ይህ በትክክል የአንድ ገጸ-ባህሪ ድግግሞሽ ባለበት ሁኔታ ውስጥ ያስቀረናል ዜሮ ያልሆነ እና ይህ በሕብረቁምፊው ውስጥ ያለው ተጨማሪ ቁምፊ ይሆናል b.

አልጎሪዝም

  1. የሁሉም ቁምፊዎች ድግግሞሽ ለማከማቸት የሃሽ ሰንጠረዥን ያስጀምሩ መደጋገም
  2. በሕብረቁምፊ ውስጥ ላለ እያንዳንዱ ቁምፊ a:
    • በሃሽ ሰንጠረዥ ውስጥ ድግግሞሹን ይጨምሩ
  3. በሕብረቁምፊ ውስጥ ላለ እያንዳንዱ ቁምፊ b:
    • በሃሽ ሰንጠረዥ ውስጥ ድግግሞሹን ቀንሷል
    • የእሱ ድግግሞሽ እኩል ከሆነ -1:
      • ይህንን ባህሪ ይመልሱ
  4. የተግባር አገባብ ለመጠበቅ '-' ይመለሱ
  5. ውጤቱን ያትሙ

የልዩ ኮድ መፍትሄን አፈላላጊ አተገባበር

C ++ ፕሮግራም

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

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

የጃቫ ፕሮግራም

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

የልኬት ኮድ መፍትሄን የመፈለግ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን)የቁምፊ ድግግሞሾቻቸውን ለማዘመን አንድ ጊዜ በሁለቱም ክሮች ውስጥ ስናልፍ ፣ ረዥሙ ገመድ N = መጠኑ።

የቦታ ውስብስብነት

ኦ (1). ገጸ-ባህሪያትን ከብዛታቸው ጋር ለማከማቸት ሀሽታብ የምንጠቀም ቢሆንም ግብዓቱ ምንም ይሁን ምን ቋሚ ቦታን እንጠቀማለን ፡፡ ስለዚህ, የቦታ ውስብስብነት ቋሚ ነው.