جواهر وأحجار Leetcode Solution


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل Facebook جوجل Microsoft ياهو
خريطة التجزئة

تنص مشكلة Jewels and Stones Leetcode Solution على منحك سلسلتين. إحداها تمثل جواهر وأحدها تمثل حجارة. السلسلة التي تحتوي على الجواهر تمثل الأحرف التي هي جواهر. نحتاج إلى إيجاد عدد الأحرف في سلسلة الأحجار التي هي جواهر. لذا ، دعونا نلقي نظرة على بعض الأمثلة.

جواهر وأحجار Leetcode Solution

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

Explanation: كما يمكننا أن نرى من سلسلة الأحجار ، هناك حالتان من "A" ومثال واحد لـ "a". وبالتالي هناك ما مجموعه 3 جواهر في سلسلة الأحجار. ومن هنا الجواب.

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

Explanation: نظرًا لوجود حرف صغير واحد 'z' في سلسلة المجوهرات. وهناك حرفان كبيران 'Z' في سلسلة الأحجار. نظرًا لأن الفحص حساس لحالة الأحرف. لا توجد جواهر في سلسلة الأحجار.

نهج القوة الغاشمة للمجوهرات والأحجار حل Leetcode

مشكلة Jewels and Stones يطلب منا Leetcode Solution إيجاد عدد الجواهر في سلسلة الأحجار. يمكننا إجراء بحث خطي لإيجاد عدد الجواهر. سنستخدم حلقتين متداخلتين من أجل التحقق مما إذا كان الحرف الحالي لسلسلة الأحجار جوهرة. ثم إذا تم العثور على الشخصية الحالية على أنها جوهرة ، فإننا نزيد إجابتنا. لكن هذا النهج بطيء لأنه يستخدم حلقتين متداخلتين.

رمز القوة الغاشمة لـ Jewels and Stones Leetcode Solution

كود C ++

#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

تحليل التعقيد

تعقيد الوقت

O (N * M)، حيث N هو طول سلسلة المجوهرات و M هو طول سلسلة الأحجار. وبالتالي فإن تعقيد الوقت هو متعدد الحدود.

تعقيد الفضاء

يا (1) ، لأننا لا نستخدم أي مصفوفة أو ناقلات. نحن نستخدم مساحة ثابتة فقط. وبالتالي فإن النهج الغاشم له تعقيد مكاني ثابت.

نهج محسن للمجوهرات والأحجار حل Leetcode

لأن نهج القوة الغاشمة بطيء. نحاول تحسين النهج أعلاه باستخدام HashSet. نستخدم HashSet لتخزين الأحرف من سلسلة المجوهرات. يمكن الآن التحقق من حلقة for التي استخدمناها للتحقق مما إذا كان الحرف الحالي من سلسلة الأحجار جوهرة ، في وقت O (1). هذا التحسين بسبب استخدام HashSet. الآن يمكننا ببساطة التحقق مما إذا كان الحرف الحالي موجودًا في HashSet. إذا كان في HashSet، نزيد إجابتنا.

رمز

كود C ++

#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

تحليل التعقيد

تعقيد الوقت

O (N + M) ، حيث N و M هو حجم سلسلة المجوهرات والأحجار. تم تحقيق التحسين لأننا استخدمنا HashSets. الآن ، تم تقليل التعقيد الزمني إلى الخطي.

تعقيد الفضاء

O (N) لأننا نقوم بتخزين الأحرف من سلسلة المجوهرات. يعتمد تعقيد المساحة على حجم سلسلة المجوهرات.