Jewels and Stones Leetcode Həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Facebook google microsoft Yahoo
alqoritmlər kodlaşdırma HashMap müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 44

Problem Jewels and Stones Leetcode Solution sizə iki sim verildiyini bildirir. Onlardan biri daşları, biri daşları təmsil edir. Cəvahirat olan sətir, zinət əşyaları olan simvolları təmsil edir. Daşlardakı zinət əşyaları olan simvol sayını tapmaq lazımdır. Beləliklə, bir neçə nümunəyə nəzər salaq.

Jewels and Stones Leetcode HəllPin

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

İzahat: Daş iplərindən də göründüyü kimi iki 'A' və bir 'a' nümunəsi var. Beləliklə, daşların ipində cəmi 3 daş var. Buna görə cavab.

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

İzahat: Zərgərlik ipində tək bir kiçik 'z' olduğu üçün. Daşların ipində iki böyük 'Z' var. Yoxlama hərflərə həssas olduğundan. Daşların ipində heç bir cəvahirat yoxdur.

Jewels and Stones Leetcode Solution üçün Kobud Güc Yanaşması

Problem Jewels and Stones Leetcode Solution, bizdən daş simli daşların sayını tapmağımızı xahiş edir. Daşların sayını tapmaq üçün xətti bir axtarış edə bilərik. Daş simlərinin hazırkı xarakterinin bir ləl-cəvahir olub olmadığını yoxlayan döngələr üçün iki yuva istifadə edəcəyik. Sonra mövcud xarakterin bir cəvahirat olduğu aşkar edilərsə, cavabımızı artırırıq. İki yanaşmış döngə istifadə etdiyindən yanaşma yavaş olur.

Jewels and Stones Leetcode Solution üçün Brute Force kodu

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * M), burada N - ləl-cəvahirat ipinin uzunluğu, M - daş ipin uzunluğu. Beləliklə zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (1), çünki heç bir sıra və ya vektor istifadə etmirik. Yalnız daimi yerdən istifadə edirik. Beləliklə, kobud yanaşma daimi kosmik mürəkkəbliyə malikdir.

Jewels and Stones Leetcode Solution üçün optimal yanaşma

Kobud güc yanaşması yavaş olduğundan. HashSet istifadə edərək yuxarıdakı yanaşmanı optimallaşdırmağa çalışırıq. Jewels simlindəki simvolları saxlamaq üçün bir HashSet istifadə edirik. Daşlar simlindəki cari xarakterin ləl-cəvahirat olub olmadığını yoxladığımız for forması artıq O (1) vaxtında yoxlanıla bilər. Bu optimallaşdırma HashSet-in istifadəsi ilə bağlıdır. İndi sadəcə cari xarakterin HashSet-də olub olmadığını yoxlaya bilərik. Əgər varsa HashSet, cavabımızı artırırıq.

Kodu

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N + M), burada N və M daş və daş simli ölçüsüdür. Optimizasiya HashSets-dən istifadə etdiyimiz üçün əldə edilir. İndi zaman mürəkkəbliyi xətti olaraq azaldıldı.

Kosmik Mürəkkəblik

O (N), simvolları zinət simlərindən saxladığımız üçün. Məkan mürəkkəbliyi daşların simli ölçüsündən asılıdır.

Şərh yaz

Translate »
1