Драгоценности и камни Leetcode Solution  


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Facebook Google Microsoft Yahoo
алгоритмы кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions

В решении Leetcode «Драгоценности и камни» говорится, что вам даны две строки. Один из них представляет собой драгоценности, а другой - камни. Строка, содержащая драгоценности, представляет символы, которые являются драгоценностями. Нам нужно найти количество символов в цепочке камней, которые являются драгоценностями. Итак, давайте рассмотрим несколько примеров.

Драгоценности и камни Leetcode Solutionшпилька

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

Пояснение: Как видно из цепочки камней, есть два экземпляра буквы «А» и один экземпляр буквы «а». Таким образом, в цепочке камней всего 3 камня. Отсюда и ответ.

jewels = "z", stones = "ZZ"

Объяснение: Поскольку в строке с драгоценными камнями есть одна строчная буква "z". В строке камней есть две заглавные буквы «Z». Поскольку проверка чувствительна к регистру. В цепочке камней нет драгоценных камней.

Подход грубой силы к решению Leetcode для драгоценных камней и камней  

Задача «Драгоценности и камни» Leetcode Solution просит нас найти количество драгоценных камней в цепочке камней. Мы можем выполнить линейный поиск, чтобы найти количество драгоценных камней. Мы будем использовать два вложенных цикла for, которые проверяют, является ли текущий символ строки камней драгоценным камнем. Затем, если обнаруживается, что текущий символ - драгоценный камень, мы увеличиваем наш ответ. Но этот подход медленный, поскольку он использует два вложенных цикла.

Смотрите также
Найдите значение расстояния между двумя массивами Решение Leetcode

Код грубой силы для решения 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

Анализ сложности

Сложность времени

О (Н * М), где 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

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

Анализ сложности

Сложность времени

О (Н + М), где N и M - размер цепочки драгоценных камней и камней. Оптимизация достигается благодаря использованию HashSets. Теперь временная сложность уменьшена до линейной.

Смотрите также
Найдите N уникальных целых чисел, чтобы получить нулевое решение Leetcode

Космическая сложность

НА), так как мы храним символы из строки драгоценных камней. Сложность пространства зависит от размера нити драгоценных камней.