[알고리즘] . 보석과 돌

문제 설명

<:> 두 개의 문자열을 제공합니다.

보석 유형을 나타내고 는 소유 한 돌을 나타냅니다. 각 캐릭터는 당신이 소유 한 어떤 종류의 돌을 나타냅니다. 돌에 보석 수를 계산해야합니다.

문자의 글자, "a"와 "a"는 다른 유형의 돌을 나타냅니다.

문제의 열쇠 jewels 문자열의 문자열에서 문자를 찾아서이 문자의 총 수를 반환하십시오. stones 예제 1 stones

예제 2

제약 조건

1 ≤ , jewels 및 stones는 영어 문자 만 포함합니다.

모든 캐릭터는 독특합니다.

계획 1 : 포함 () 메소드 를 사용하십시오.

단계 :

<code>输入：jewels = "aA", stones = "aAAbbbb"
输出：3</code>

총 보석 수를 저장하는 데 사용되는 카운터 초기화 카운터

. 는 스트링을 가로 지르고 메소드를 사용하여 각 문자가 문자열인지 확인하십시오. 포함하면

가 증가합니다.

<code>输入：jewels = "z", stones = "ZZ"
输出：0</code>

마지막 반품 .

이 방법의 시간 복잡성은 O (m*n)이고, 여기서 m은 스트링의 길이이고, n은

스트링의 길이입니다. 메서드가 문자열에서 각 문자를 가로 지르기 때문입니다. 입력 스케일이 증가하면이 방법은 비효율적입니다. 시간 복잡성을 줄이기위한 계획을 최적화해야합니다.

플랜 2 : set () 메소드 (Hash 테이블) 를 사용하십시오.
• 단계 : jewels.length 총 보석 수를 저장하는 데 사용되는 카운터 초기화 카운터 stones.length.
• 를 사용하여 jewels를 만듭니다. 해시 테이블을 사용하여 더 빠른 검색을 찾으십시오. stones 는 스트링을 가로 지르고 메소드를 사용하여 각 문자가 인지 확인하십시오.
존재하면
• 가 증가합니다. jewels 마지막 반품 .

포함 ()보다 더 빠른 이유는 무엇입니까? <..> 각 체크의 복잡성을 통해

문자열을 통과하여 값을 확인하는 방법은 문자열의 길이입니다. 데이터 구조 내부의 및

hach ​​테이블은 일정한 시간 O (1) 검색에 대한

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewels.includes(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

메소드를 사용할 수 있습니다. 초기 O (N) 시간을 생성해야하지만 팔로우 검색은 메소드보다 훨씬 빠릅니다.

오류가 있거나보기가 다른 경우 언제든지 메시지를 남겨주세요. 나는 항상 다른 관점에서 배우게되어 기쁩니다! 이 기사가 마음에 들면 언제든지 LinkedIn에 연락하십시오.

위 내용은 [알고리즘] . 보석과 돌의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!