រកដំណោះស្រាយ Leetcode ខុសគ្នា


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន google
ហាសហាស។

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា "រកភាពខុសគ្នា" យើងត្រូវបានផ្តល់ឱ្យពីរ ខ្សែអក្សរ s និង t ។ ខ្សែអក្សរ t ត្រូវបានផលិតដោយការចៃដន្យតួអក្សរនៃខ្សែអក្សរ s និងបន្ថែមតួអក្សរមួយនៅទីតាំងចៃដន្យ។

ភារកិច្ចរបស់យើងគឺស្វែងរកតួអក្សរដែលត្រូវបានបន្ថែមជាខ្សែអក្សរ t ។

ឧទាហរណ៍

s = "abcd", t = "abcde"
e

ការពន្យល់:

រកដំណោះស្រាយ Leetcode ខុសគ្នា

បន្ទាប់ពីរៀបចំតួអក្សរនៃខ្សែអក្សរឡើងវិញវាក្លាយជា“ ការដាក់កម្រិត” ។ ក្នុងនាមជា“ abcd” មានវត្តមាននៅក្នុងខ្សែអក្សរដូច្នេះតួអក្សរដែលត្រូវបានបន្ថែមទៅ t គឺ“ e” ។

ការតម្រៀបវិធីសាស្រ្តសម្រាប់រកដំណោះស្រាយ Leetcode ខុសគ្នា

ប្រសិនបើយើងផ្លាស់ប្តូរទស្សនៈរបស់យើងដើម្បីមើលបញ្ហាបន្ទាប់មកពេលខ្លះវាងាយស្រួលក្នុងការដោះស្រាយបញ្ហា។ ដូចនៅត្រង់នេះបញ្ហានិយាយថាខ្សែអក្សរ t ត្រូវបានបង្កើតឡើងដោយសាប់ខ្សែអក្សរនិងបន្ថែមធាតុមួយនៅទីតាំងចៃដន្យ។ ដូច្នេះយើងអាចមើលឃើញថានេះជាខ្សែអក្សរ t ត្រូវបានបង្កើតដោយបន្ថែមតួអក្សរនៅទីតាំងចៃដន្យនៅក្នុងខ្សែអក្សរ s ។ ឥឡូវយើងគ្រាន់តែត្រូវការរកទីតាំងដែលតួអក្សរនៃខ្សែអក្សរមិនត្រូវគ្នានឹងតួអក្សរនៃខ្សែអក្សរ t ហើយបន្ទាប់មកយើងអាចត្រឡប់តួអក្សរដែលមាននៅទីតាំងនោះ។ ដូច្នេះយើងនឹងអនុវត្តតាមជំហានទាំងនេះ៖

  1. តម្រៀបខ្សែអក្សរទាំងពីរ។
  2. ពិនិត្យតួអក្សរតាមតួអក្សរទាំងខ្សែអក្សរនិងចំណុចដែលពួកគេមិនត្រូវគ្នាគឺត្រូវបន្ថែមតួអក្សរហើយនោះជាចម្លើយ។
  3. ប្រសិនបើតួអក្សរទាំងអស់ត្រូវគ្នានោះតួអក្សរនៅទីតាំងចុងក្រោយនៃខ្សែអក្សរ t គឺជាចម្លើយរបស់យើង។

ការអនុវត្តន៍

កូដ C ++ សម្រាប់ស្វែងរកភាពខុសគ្នា

#include <bits/stdc++.h> 
using namespace std; 
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
    
    sort(t.begin(),t.end());
    
    
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
      {
        return t[i];
      }
    }
    
    return t[t.length()-1];
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

កូដចាវ៉ាសម្រាប់ស្វែងរកភាពខុសគ្នា

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
    char[] sortedS = s.toCharArray();
    char[] sortedT = t.toCharArray();
    Arrays.sort(sortedS);
    Arrays.sort(sortedT);
    for(int i=0;i<s.length();i++){
      if (sortedS[i] != sortedT[i]) {
        return sortedT[i];
      }
    }

    return sortedT[s.length()];
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

ការវិភាគភាពស្មុគស្មាញនៃការស្វែងរកដំណោះស្រាយឡេឡេកូដកូដខុសគ្នា

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ O (nlogn) ពីព្រោះយើងកំពុងតម្រៀបខ្សែទាំងពីរ។ នៅទីនេះ n គឺជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ s ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ អូរ (n) សំរាប់ដំណោះស្រាយជ្វាពីព្រោះយើងកំពុងបំលែងខ្សែរទៅជាអារេប៉ុន្តែសំរាប់ C ++ វាគឺអូ (១) ព្រោះវាអនុញ្ញាតិអោយតម្រៀបនៅនឹងកន្លែង។

វិធីសាស្រ្តធ្វើកូដកម្មដើម្បីរកដំណោះស្រាយភាពខុសគ្នា Leetcode

យើងនឹងអនុវត្តតាមជំហានទាំងនេះ៖

  1. បង្កើតអារេប្រេកង់នៃទំហំ ២៦ ដើម្បីទុកប្រេកង់របស់តួអក្សរ។ យើងនឹងចាប់ផ្តើមវាជាមួយលេខ ០ ។
  2. ឆ្លងកាត់ខ្សែអក្សរ s ហើយទុកប្រេកង់នៃតួអក្សរនៅក្នុងអារេប្រេកង់។
  3. ឥឡូវឆ្លងកាត់ខ្សែអក្សរ t និងបន្ថយប្រេកង់នៃតួអក្សរនីមួយៗដែលអ្នកជួបប្រទះក្នុងកំឡុងពេលឆ្លងកាត់ខ្សែអក្សរ t ពីអារេប្រេកង់។
  4. នៅចុងបញ្ចប់បំលែងអារេប្រេកង់និងតួអក្សរដែលត្រូវនឹងទីតាំងដែលមានតម្លៃគឺតួអក្សរបន្ថែមហើយនោះគឺជាចម្លើយដែលត្រូវការ។

ការអនុវត្តន៍

កូដ C ++ សម្រាប់ស្វែងរកភាពខុសគ្នា

#include <bits/stdc++.h> 
using namespace std; 
      char findTheDifference(string s, string t) {
        int count[26] = {0};
        for(int i=0;i<s.length();i++) count[s[i]-'a']++;
        for(int i=0;i<t.length();i++) count[t[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return 'a';
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

កូដចាវ៉ាសម្រាប់ស្វែងរកភាពខុសគ្នា

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
        int[] count = new int[26];
        char[] S = s.toCharArray(), T = t.toCharArray();
        for(int i=0;i<S.length;i++) count[S[i]-'a']++;
        for(int i=0;i<T.length;i++) count[T[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return '\0';
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

ការវិភាគភាពស្មុគស្មាញនៃការស្វែងរកដំណោះស្រាយឡេឡេកូដកូដខុសគ្នា

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ អូរ (n) ដោយសារតែយើងកំពុងឆ្លងកាត់ខ្សែតែមួយប៉ុណ្ណោះ។ នៅទីនេះ n គឺជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ ឱ (១) ពីព្រោះយើងកំពុងប្រើចន្លោះថេរសម្រាប់អារេប្រេកង់។

ឯកសារយោង