פתרון Leetcode תכשיטים ואבנים


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ פייסבוק Google מיקרוסופט יאהו
מפת גיבוב

הפתרון הבעייתי של תכשיטים ואבנים Leetcode קובע כי נותנים לך שתי מחרוזות. אחת מהן מייצגת תכשיטים ואחת מהן מייצגת אבנים. המחרוזת המכילה תכשיטים מייצגת את הדמויות שהן תכשיטים. עלינו למצוא את מספר התווים במחרוזת האבנים שהם תכשיטים. אז בואו נסתכל על כמה דוגמאות.

פתרון Leetcode תכשיטים ואבנים

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

הסבר: כפי שאנו רואים ממחרוזת האבנים, ישנם שני מקרים של 'A' ומופע אחד של 'a'. לפיכך יש בסך הכל 3 תכשיטים בחוט האבנים. מכאן התשובה.

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

הסבר: מכיוון שיש 'z' קטן במחרוזת התכשיטים. ויש שני 'אותיות' גדולות במחרוזת האבנים. מכיוון שהבדיקה רגישה לאותיות רישיות. אין תכשיטים בחוט האבנים.

גישת כוח הברוט לפתרון תכשיטים ואבנים

הפתרון הבעייתי תכשיטים ואבנים Leetcode מבקש מאיתנו למצוא את מספר התכשיטים בחוט האבנים. אנחנו יכולים לעשות חיפוש לינארי כדי למצוא את מספר התכשיטים. נשתמש בשניים מקוננים לולאות הבודקות אם האופי הנוכחי של מיתר האבנים הוא תכשיט. ואז אם נמצא שהדמות הנוכחית היא תכשיט, אנו מגדילים את תשובתנו. אך הגישה איטית מכיוון שהיא משתמשת בשתי לולאות מקוננות.

קוד Brute Force לפתרונות Leetcode של תכשיטים ואבנים

קוד 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 הוא אורך מחרוזת האבנים. לפיכך מורכבות הזמן היא פולינומית.

מורכבות בחלל

O (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

קוד Java

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) מכיוון שאנו מאחסנים את הדמויות ממחרוזת התכשיטים. מורכבות החלל תלויה בגודל מחרוזת התכשיטים.