Рашэнне Leetcode для каштоўнасцей і камянёў


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык facebook Google Microsoft Yahoo
HashMap

У праблеме Leetcode Solution Jewels and Stones гаворыцца, што вам дадзены два радкі. Адзін з іх уяўляе каштоўнасці, а адзін - камяні. Радок, які змяшчае каштоўныя камяні, прадстаўляе сімвалы, якія з'яўляюцца каштоўнасцямі. Нам трэба знайсці колькасць знакаў у радку камянёў, якія з'яўляюцца каштоўнасцямі. Такім чынам, разбярэм некалькі прыкладаў.

Рашэнне Leetcode для каштоўнасцей і камянёў

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

Тлумачэнне: Як мы бачым па радку камянёў, ёсць два асобнікі "A" і адзін асобнік "a". Такім чынам, у радку камянёў усяго 3 каштоўнасці. Адсюль і адказ.

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

Тлумачэнне: Паколькі ў радку каштоўных камянёў ёсць адзіная малая літара "z". І ў радку камянёў ёсць два вялікія літары "Z". Так як праверка адчувальная да рэгістра. У радках камянёў няма каштоўнасцей.

Падыход грубай сілы да вырашэння штрых-кода каштоўных камянёў і камянёў

Праблема "Каштоўныя вырабы і камяні", рашэнне якой патрабуе знайсці колькасць каштоўных камянёў у радку камянёў. Мы можам правесці лінейны пошук, каб знайсці колькасць каштоўных камянёў. Мы будзем выкарыстоўваць дзве ўкладзеныя цыклы, якія правяраюць, ці з'яўляецца бягучы сімвал радка камянямі каштоўнасцю. Тады, калі бягучы персанаж апынецца каштоўнасцю, мы павялічым наш адказ. Але падыход марудны, бо ён выкарыстоўвае дзве ўкладзеныя цыклы.

Код Brute Force для рашэння Leetcode Jewels and Stones

Код 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

Код Java

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), бо мы не выкарыстоўваем ні масіў, ні вектар. Мы выкарыстоўваем толькі пастаянную прастору. Такім чынам, грубы падыход мае пастаянную касмічную складанасць.

Аптымізаваны падыход да вырашэння ювелірных вырабаў і камянёў

Так як падыход грубай сілы марудны. Мы спрабуем аптымізаваць вышэйзгаданы падыход з дапамогай 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), бо мы захоўваем сімвалы з радка каштоўных камянёў. Складанасць прасторы залежыць ад памеру радкі каштоўных камянёў.