ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට් යාහූ
ඇල්ගොරිතම කේතීකරණය හැෂ්මැප් සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුමේ ගැටලුව වන්නේ ඔබට නූල් දෙකක් ලබා දී ඇති බවයි. ඔවුන්ගෙන් එක් කෙනෙක් ස්වර්ණාභරණ නියෝජනය කරන අතර ඉන් එකක් ගල් නියෝජනය කරයි. ස්වර්ණාභරණ අඩංගු නූල් නිරූපණය කරන්නේ ස්වර්ණාභරණ ය. ස්වර්ණාභරණ වන ගල් නූලෙහි අක්ෂර ගණන අපට සොයාගත යුතුය. ඉතින්, අපි උදාහරණ කිහිපයක් දෙස බලමු.

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුමපින්

jewels = "aA", stones = "aAAbbbb"
3

පැහැදිලි කිරීම: ගල් නූලෙන් අපට පෙනෙන පරිදි, 'ඒ' හි අවස්ථා දෙකක් ද, 'අ' හි එක් අවස්ථාවක් ද තිබේ. මේ අනුව ගල් නූලෙහි ස්වර්ණාභරණ 3 ක් ඇත. එබැවින් පිළිතුර.

jewels = "z", stones = "ZZ"

පැහැදිලි කිරීම: ස්වර්ණාභරණ නූලෙහි තනි කුඩා 'z' ඇති බැවින්. ගල් නූලෙහි ලොකු ඉසෙඩ් දෙකක් ඇත. පරීක්ෂා කිරීම සිද්ධි සංවේදී බැවින්. ගල් නූලෙහි ආභරණ නොමැත.

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුම සඳහා තිරිසන් බල ප්‍රවේශය  

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුම අපෙන් ඉල්ලා සිටින්නේ ගල් නූල්වල ඇති ස්වර්ණාභරණ ගණන සොයා ගන්නා ලෙසයි. ස්වර්ණාභරණ ගණන සොයා ගැනීමට අපට රේඛීය සෙවුමක් කළ හැකිය. ගල් නූල් වල වර්තමාන ස්වරූපය මැණිකක් දැයි පරීක්ෂා කරන ලූප සඳහා අපි කූඩු දෙකක් භාවිතා කරමු. වර්තමාන චරිතය මැණිකක් බව පෙනේ නම්, අපි අපගේ පිළිතුර වැඩි කරමු. නමුත් එය කූඩු ලූප දෙකක් භාවිතා කරන බැවින් ප්‍රවේශය මන්දගාමී වේ.

මෙයද බලන්න
අරා දෙකක් ලීට්කෝඩ් විසඳුම අතර දුර අගය සොයා ගන්න

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුම සඳහා තිරිසන් බල කේතය

සී ++ කේතය

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

int numJewelsInStones(string jewels, string stones) {
    int answer = 0;
    for(int i=0; i<stones.length();i++){
        for(int j=0;j<jewels.length();j++){
            if(stones[i] == jewels[j])
                answer++;
        }
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}
3

ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        int answer = 0;
        for(int i=0; i<stones.length();i++){
            for(int j=0;j<jewels.length();j++){
                if(stones.charAt(i) == jewels.charAt(j))
                    answer++;
            }
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}
3

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් * එම්), මෙහි N යනු ස්වර්ණාභරණ නූලෙහි දිග වන අතර M යනු ගල් නූලෙහි දිග වේ. මේ අනුව කාල සංකීර්ණතාව බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි කිසිදු අරාවක් හෝ දෛශිකයක් භාවිතා නොකරන බැවින්. අපි භාවිතා කරන්නේ නියත ඉඩක් පමණි. මේ අනුව තිරිසන් ප්රවේශය නිරන්තර අවකාශ සංකීර්ණතාවයක් ඇත.

ස්වර්ණාභරණ සහ ගල් ලීට්කෝඩ් විසඳුම සඳහා ප්‍රශස්ත ප්‍රවේශය  

තිරිසන් බලවේගය මන්දගාමී බැවින්. අපි හැෂ්සෙට් භාවිතයෙන් ඉහත ප්‍රවේශය ප්‍රශස්ත කිරීමට උත්සාහ කරමු. ස්වර්ණාභරණ නූලෙන් අක්ෂර ගබඩා කිරීම සඳහා අපි හැෂ්සෙට් එකක් භාවිතා කරමු. ගල් නූලෙන් වත්මන් අක්ෂරය මැණිකක් දැයි පරීක්ෂා කිරීමට අප භාවිතා කළ for loop දැන් O (1) වේලාවෙන් පරීක්ෂා කළ හැකිය. මෙම ප්‍රශස්තිකරණය හැෂ්සෙට් භාවිතා කිරීම නිසාය. දැන් අපට සරලවම හැෂ්සෙට් හි වර්තමාන අක්‍ෂරය තිබේදැයි පරීක්ෂා කළ හැකිය. එය තිබේ නම් හැෂ්සෙට්, අපි අපගේ පිළිතුර වැඩි කරමු.

කේතය

සී ++ කේතය

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

int numJewelsInStones(string jewels, string stones) {
    unordered_set<char> jewelSet;
    for(int i=0;i<jewels.length();i++)
        jewelSet.insert(jewels[i]);

    int answer = 0;
    for(int i=0;i<stones.length();i++){
        if(jewelSet.count(stones[i]) == true)
            answer++;
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}
3

ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> jewelSet = new HashSet<Character>();
        for(int i=0;i<jewels.length();i++)
            jewelSet.add(jewels.charAt(i));
        
        int answer = 0;
        for(int i=0;i<stones.length();i++){
            if(jewelSet.contains(stones.charAt(i)) == true)
                answer++;
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}
3

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් + එම්), මෙහි N සහ M යනු ස්වර්ණාභරණ සහ ගල් නූල්වල ප්‍රමාණයයි. අපි හැෂ්සෙට් භාවිතා කළ නිසා ප්‍රශස්තිකරණය ළඟා කර ගත හැකිය. දැන්, කාල සංකීර්ණතාව රේඛීය දක්වා අඩු කර ඇත.

මෙයද බලන්න
ශුන්‍ය ලීට්කෝඩ් විසඳුම දක්වා වූ අද්විතීය පූර්ණ සංඛ්‍යා සොයා ගන්න

අභ්‍යවකාශ සංකීර්ණතාව

මත), අපි ස්වර්ණාභරණ නූලෙන් අක්ෂර ගබඩා කරන නිසා. අවකාශයේ සංකීර්ණත්වය ස්වර්ණාභරණ නූල් ප්‍රමාණය මත රඳා පවතී.