நகைகள் மற்றும் கற்கள் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் பேஸ்புக் கூகிள் மைக்ரோசாப்ட் யாகூ
ஹாஷ்மேப்

ஜுவல்ஸ் அண்ட் ஸ்டோன்ஸ் லீட்கோட் சொல்யூஷன் உங்களுக்கு இரண்டு சரங்களை வழங்கியதாக கூறுகிறது. அவற்றில் ஒன்று நகைகளையும், அவற்றில் ஒன்று கற்களையும் குறிக்கிறது. நகைகளைக் கொண்ட சரம் நகைகள் கொண்ட எழுத்துக்களைக் குறிக்கிறது. நகைகள் என்று கற்கள் சரத்தில் உள்ள எழுத்துக்களின் எண்ணிக்கையை நாம் கண்டுபிடிக்க வேண்டும். எனவே, சில எடுத்துக்காட்டுகளைப் பார்ப்போம்.

நகைகள் மற்றும் கற்கள் லீட்கோட் தீர்வு

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

விளக்கம்: கற்களின் சரத்திலிருந்து நாம் காணக்கூடியபடி, 'A' இன் இரண்டு நிகழ்வுகளும், 'a' இன் ஒரு நிகழ்வும் உள்ளன. இவ்வாறு கற்களின் சரத்தில் மொத்தம் 3 நகைகள் உள்ளன. எனவே பதில்.

jewels = "z", stones = "ZZ"
0

விளக்கம்: நகைகள் சரத்தில் ஒற்றை சிறிய 'z' இருப்பதால். மேலும் கற்களின் சரத்தில் இரண்டு பெரிய '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), நாங்கள் எந்த வரிசை அல்லது திசையனையும் பயன்படுத்தவில்லை என்பதால். நாங்கள் நிலையான இடத்தை மட்டுமே பயன்படுத்துகிறோம். இதனால் முரட்டு அணுகுமுறை நிலையான இட சிக்கலைக் கொண்டுள்ளது.

நகைகள் மற்றும் கற்கள் லீட்கோட் தீர்வுக்கான உகந்த அணுகுமுறை

முரட்டுத்தனமான அணுகுமுறை மெதுவாக இருப்பதால். மேலே உள்ள அணுகுமுறையை ஹாஷ்செட்டைப் பயன்படுத்தி மேம்படுத்த முயற்சிக்கிறோம். நகைகள் சரத்திலிருந்து எழுத்துக்களைச் சேமிக்க ஹாஷ்செட்டைப் பயன்படுத்துகிறோம். கற்களின் சரத்திலிருந்து தற்போதைய எழுத்து ஒரு நகைதானா என்பதை சரிபார்க்க நாங்கள் பயன்படுத்திய லூப், இப்போது 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 என்பது நகைகள் மற்றும் கற்களின் சரத்தின் அளவு. நாங்கள் ஹேஷ்செட்களைப் பயன்படுத்தியதால் தேர்வுமுறை அடையப்படுகிறது. இப்போது, ​​நேர சிக்கலானது நேரியல் ஆக குறைக்கப்பட்டுள்ளது.

விண்வெளி சிக்கலானது

ஓ (என்), நகைகள் சரத்திலிருந்து எழுத்துக்களை சேமிப்பதால். விண்வெளி சிக்கலானது நகைகள் சரம் அளவைப் பொறுத்தது.