Գտեք տարբերության Leetcode լուծումը  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Google
ալգորիթմները կոդավորում Հեշինգ հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions String

Այս խնդրում մեզ երկու են տալիս տողերը, Երկրորդ տողը առաջանում է առաջին լարի նիշերը պատահականորեն խառնելու միջոցով և ցանկացած լրացուցիչ պատահական դիրքում լրացուցիչ նիշ ավելացնելով: Մենք պետք է վերադարձնենք երկրորդ նարին ավելացված լրացուցիչ նիշը: Նիշերը միշտ կլինեն փոքրատառ անգլերեն տառեր:

Օրինակ  

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

Թիվ 1 բացատրություն

Լրացուցիչ նիշը, որն ավելացվում է լարին b 'f' է որպես տող a չի պարունակում այն:

Թիվ 2 բացատրություն

String տողերի ժամանակ ունի 4 «ա» տառ ունի 5. Այսպիսով, լրացուցիչ տառը «ա» է:

Մոտեցում (Տեսակավորում)  

Մենք կարող ենք տեսակավորել երկու տողերը, այնուհետև երկուսն էլ տառ առ տառ կրկնել ՝ գտնելու առաջին դիրքը, որտեղ նրանք տարբերվում են: Երկրորդ լարը միշտ կունենա մեկը հավելյալ բնավորություն Այսպիսով, մենք միշտ կգտնենք տողային կետ a և b տարբերվում է Այնուամենայնիվ, կարող է լինել դեպք, երբ տողը b տեսակավորումից հետո տողի յուրաքանչյուր նիշ է համընկնում a մեջ, բայց ի վերջո ունի մեկ լրացուցիչ բնույթ: Մենք պետք է կարգավորենք այս մեկ հատուկ դեպքը:

Գտեք տարբերության Leetcode լուծումը

Ալգորիթմ

  1. Տեսակավորեք երկու տողերը, a և b, Քանի որ java- ում դա հնարավոր չէ, մենք նախ դրանք վերածում ենք վերածելու char զանգվածներ
  2. Ավելի կարճ տողի ներկա յուրաքանչյուր նիշի համար մենք տառ առ տառ ստուգում ենք.
    • Եթե ​​նիշի նիշը հավասար չէ տողի համապատասխան նիշին b:
      • վերադարձնել այս բնավորությունը:
  3. Վերադարձեք լարի վերջին նիշը քանի որ դա լրացուցիչ բնույթ է
  4. Տպեք արդյունքը
Տես նաեւ,
Գտեք թվերի զույգ թվով համարներ Leetcode լուծում

Գտեք տարբերությունը Leetcode լուծման իրականացումը

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;
}

Java ծրագիր

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

Գտեք տարբերության Leetcode լուծման բարդության վերլուծություն

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

O (NlogN), որտեղ N = ավելի երկար տողի երկարությունը: Մենք տեսակավորում ենք տողերը / բնույթի զանգվածները, որոնք O (NlogN) ժամանակ են պահանջում:

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

ՎՐԱ) ջավայում ու Ո (1) C ++ - ով, երբ տողերը վերածում ենք char raանգվածներ ջավայում:

Մոտեցում (Hashing)  

Երկու տողերում էլ մենք կարող ենք յուրաքանչյուր բնույթ ունենալ իր հաճախականությամբ և գտնել հաճախականությամբ տարբերվող նիշը: Քանի որ մենք ունենք եզակի նիշերի անընդհատ քանակ: Այս ալգորիթմը ավելի արագ է, քան վերը քննարկվածը: Որպես արդյունավետ իրականացում ՝ մենք կարող ենք ստեղծել հեշ սեղան և ավելացնել տողի յուրաքանչյուր նիշի հաճախականությունը a և նվազեցնել տողի յուրաքանչյուր նիշի հաճախականությունը b. Սա մեզ կմնա այն դեպքում, երբ ուղիղ մեկ նիշի հաճախականությունը կա ոչ զրոյական և սա կլինի լարի լրացուցիչ նիշը b.

Ալգորիթմ

  1. Նախաձեռնեք հեշ աղյուսակ ՝ բոլոր նիշերի հաճախականությունը պահելու համար, ինչպես հաճախություն
  2. Լարի յուրաքանչյուր նիշի համար a:
    • ավելացնել իր հաճախականությունը hash աղյուսակում
  3. Լարի յուրաքանչյուր նիշի համար b:
    • նվազեցնել իր հաճախականությունը հեշ աղյուսակում
    • Եթե ​​դրա հաճախականությունը հավասար է -1:
      • վերադարձնել այս բնավորությունը
  4. Վերադարձնել '-' ֆունկցիայի շարահյուսությունը պահպանելու համար
  5. Տպեք արդյունքը
Տես նաեւ,
Հաշվեք և փոխեք հարցումները Երկուական զանգվածի վրա

Գտեք տարբերությունը Leetcode լուծման իրականացումը

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;
}

Java ծրագիր

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

Գտեք տարբերության Leetcode լուծման բարդության վերլուծություն

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

ՎՐԱ), N = ավելի երկար տողի չափը, քանի որ երկու լարերի միջով անցնում ենք մեկ անգամ ՝ դրանց բնույթի հաճախականությունները թարմացնելու համար:

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

Ո (1), Չնայած նիշերն իրենց հաճախականությամբ պահելու համար օգտագործում ենք hashtable, անկախ մուտքից, մենք օգտագործում ենք անընդհատ տարածք: Այսպիսով, տիեզերական բարդությունը կայուն է: