String of unique characters - tanakakenji/Rinko GitHub Wiki

C++ใงใฎใƒฆใƒ‹ใƒผใ‚ฏๆ–‡ๅญ—ใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏ

ใƒฆใƒ‹ใƒผใ‚ฏใชๅฐๆ–‡ๅญ—ใƒฉใƒ†ใƒณๆ–‡ๅญ—ใ‹ใ‚‰ใชใ‚‹ๆ–‡ๅญ—ๅˆ—ใ‚’ๅŠน็އ็š„ใซๅ‡ฆ็†ใ™ใ‚‹ใŸใ‚ใซใ€26ใƒ“ใƒƒใƒˆใฎใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใ‚’ไฝฟ็”จใ™ใ‚‹ใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏใ‚’็ดนไป‹ใ—ใพใ™ใ€‚ใ“ใฎใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏใฏใ€ๆ–‡ๅญ—ใฎๅญ˜ๅœจใ‚’็ขบ่ชใ—ใŸใ‚Šใ€2ใคใฎๆ–‡ๅญ—ๅˆ—้–“ใฎๅ…ฑ้€šๆ–‡ๅญ—ใ‚’่ฆ‹ใคใ‘ใŸใ‚Šใ™ใ‚‹้š›ใซ้žๅธธใซๅŠนๆžœ็š„ใงใ™ใ€‚

1. ใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใฎไฝœๆˆ

ใพใšใ€ๆ–‡ๅญ—ๅˆ—ๅ†…ใฎๅ„ๆ–‡ๅญ—ใฎๅญ˜ๅœจใ‚’็คบใ™ใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใ‚’ไฝœๆˆใ—ใพใ™ใ€‚

ไพ‹้กŒ๏ผšๆ–‡ๅญ—ๅˆ—ใ‹ใ‚‰ใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใ‚’็”Ÿๆˆใ™ใ‚‹

#include <iostream>
#include <string>

unsigned int createBitmask(const std::string& word) {
    unsigned int mask = 0;
    for (char c : word) {
        if (c >= 'a' && c <= 'z') {
            mask |= (1 << (c - 'a'));
        }
    }
    return mask;
}

void printBitmask(unsigned int mask) {
    for (int i = 25; i >= 0; i--) {
        std::cout << ((mask & (1 << i)) ? '1' : '0');
    }
    std::cout << std::endl;
}

int main() {
    std::string word = "abcdefz";
    unsigned int mask = createBitmask(word);
    
    std::cout << "Bitmask for \"" << word << "\": ";
    printBitmask(mask);
    
    return 0;
}

ใ“ใฎใ‚ณใƒผใƒ‰ใฏใ€ๆ–‡ๅญ—ๅˆ—ๅ†…ใฎๅ„ๅฐๆ–‡ๅญ—ใƒฉใƒ†ใƒณๆ–‡ๅญ—ใซๅฏพๅฟœใ™ใ‚‹ใƒ“ใƒƒใƒˆใ‚’1ใซ่จญๅฎšใ—ใพใ™ใ€‚

ๅ‡บๅŠ›๏ผš

Bitmask for "abcdefz": 11111100000000000000000001

่งฃ่ชฌ๏ผš

  • 1 << (c - 'a') ใฏใ€ใ‚ขใƒซใƒ•ใ‚กใƒ™ใƒƒใƒˆใฎไฝ็ฝฎใซๅฏพๅฟœใ™ใ‚‹ใƒ“ใƒƒใƒˆใ‚’1ใซใ‚ทใƒ•ใƒˆใ—ใพใ™ใ€‚
  • |= ๆผ”็ฎ—ๅญใ‚’ไฝฟ็”จใ—ใฆใ€ใใฎใƒ“ใƒƒใƒˆใ‚’ใƒžใ‚นใ‚ฏใซ่ฟฝๅŠ ใ—ใพใ™ใ€‚
  • ็ตๆžœใฎใƒžใ‚นใ‚ฏใฏใ€ๆ–‡ๅญ—ๅˆ—ๅ†…ใซๅญ˜ๅœจใ™ใ‚‹ๆ–‡ๅญ—ใซๅฏพๅฟœใ™ใ‚‹ใƒ“ใƒƒใƒˆใŒ1ใซใชใฃใฆใ„ใพใ™ใ€‚

2. 2ใคใฎๆ–‡ๅญ—ๅˆ—ใฎๅ…ฑ้€šๆ–‡ๅญ—ใฎ็ขบ่ช

2ใคใฎๆ–‡ๅญ—ๅˆ—้–“ใงๅ…ฑ้€šใฎๆ–‡ๅญ—ใŒใ‚ใ‚‹ใ‹ใฉใ†ใ‹ใ‚’็ขบ่ชใ™ใ‚‹ใซใฏใ€ใใ‚Œใžใ‚Œใฎใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใซๅฏพใ—ใฆ AND ๆผ”็ฎ—๏ผˆ&๏ผ‰ใ‚’่กŒใ„ใพใ™ใ€‚

ไพ‹้กŒ๏ผš2ใคใฎๆ–‡ๅญ—ๅˆ—้–“ใฎๅ…ฑ้€šๆ–‡ๅญ—ใ‚’็ขบ่ชใ™ใ‚‹

#include <iostream>
#include <string>

bool haveCommonCharacters(const std::string& word1, const std::string& word2) {
    unsigned int mask1 = createBitmask(word1);
    unsigned int mask2 = createBitmask(word2);
    
    return (mask1 & mask2) > 0;
}

int main() {
    std::string word1 = "hello";
    std::string word2 = "world";
    std::string word3 = "xyz";
    
    std::cout << "Bitmask for \"" << word1 << "\": ";
    printBitmask(createBitmask(word1));
    std::cout << "Bitmask for \"" << word2 << "\": ";
    printBitmask(createBitmask(word2));
    std::cout << "Bitmask for \"" << word3 << "\": ";
    printBitmask(createBitmask(word3));
    
    std::cout << "\"" << word1 << "\" and \"" << word2 << "\" have common characters: " 
              << (haveCommonCharacters(word1, word2) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << word1 << "\" and \"" << word3 << "\" have common characters: " 
              << (haveCommonCharacters(word1, word3) ? "Yes" : "No") << std::endl;
    
    return 0;
}

ๅ‡บๅŠ›๏ผš

Bitmask for "hello": 00000000000000100000011000
Bitmask for "world": 00000100000000100000010010
Bitmask for "xyz": 00000000000000000000000111
"hello" and "world" have common characters: Yes
"hello" and "xyz" have common characters: No

่งฃ่ชฌ๏ผš

  • haveCommonCharacters ้–ขๆ•ฐใฏใ€2ใคใฎๆ–‡ๅญ—ๅˆ—ใฎใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใ‚’็”Ÿๆˆใ—ใ€ANDๆผ”็ฎ—ใ‚’่กŒใ„ใพใ™ใ€‚
  • ็ตๆžœใŒ0ใ‚ˆใ‚Šๅคงใใ„ๅ ดๅˆใ€ๅ…ฑ้€šใฎๆ–‡ๅญ—ใŒๅญ˜ๅœจใ™ใ‚‹ใ“ใจใ‚’ๆ„ๅ‘ณใ—ใพใ™ใ€‚
  • "hello" ใจ "world" ใฏ 'o' ใจ 'l' ใ‚’ๅ…ฑๆœ‰ใ—ใฆใ„ใ‚‹ใŸใ‚ใ€ANDๆผ”็ฎ—ใฎ็ตๆžœใฏ้žใ‚ผใƒญใซใชใ‚Šใพใ™ใ€‚
  • "hello" ใจ "xyz" ใฏๅ…ฑ้€šใฎๆ–‡ๅญ—ใ‚’ๆŒใŸใชใ„ใŸใ‚ใ€ANDๆผ”็ฎ—ใฎ็ตๆžœใฏ0ใซใชใ‚Šใพใ™ใ€‚

ใ“ใฎๆŠ€ๆณ•ใฎๅˆฉ็‚น

  1. ๅŠน็އๆ€ง๏ผšใƒ“ใƒƒใƒˆๆผ”็ฎ—ใฏ้žๅธธใซ้ซ˜้€Ÿใงใ€ใƒกใƒขใƒชไฝฟ็”จ้‡ใ‚‚ๅฐ‘ใชใ„ใงใ™ใ€‚
  2. ็ฐกๆฝ”ๆ€ง๏ผš่ค‡้›‘ใชใƒ‡ใƒผใ‚ฟๆง‹้€ ใ‚’ๅฟ…่ฆใจใ›ใšใ€ๅ˜ไธ€ใฎๆ•ดๆ•ฐใงๆ–‡ๅญ—ใฎๅญ˜ๅœจใ‚’่กจ็พใงใใพใ™ใ€‚
  3. ๆŸ”่ปŸๆ€ง๏ผšใƒ“ใƒƒใƒˆๆผ”็ฎ—ใ‚’ไฝฟ็”จใ™ใ‚‹ใ“ใจใงใ€ๆง˜ใ€…ใช้›†ๅˆๆผ”็ฎ—๏ผˆๅ’Œ้›†ๅˆใ€็ฉ้›†ๅˆใชใฉ๏ผ‰ใ‚’็ฐกๅ˜ใซ่กŒใˆใพใ™ใ€‚

ๆณจๆ„็‚น

  • ใ“ใฎใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏใฏๅฐๆ–‡ๅญ—ใฎใƒฉใƒ†ใƒณๆ–‡ๅญ—๏ผˆa-z๏ผ‰ใซใฎใฟ้ฉ็”จๅฏ่ƒฝใงใ™ใ€‚
  • 32ใƒ“ใƒƒใƒˆใฎๆ•ดๆ•ฐๅž‹ใ‚’ไฝฟ็”จใ—ใฆใ„ใ‚‹ใŸใ‚ใ€26ๆ–‡ๅญ—ไปฅไธŠใฎๆ–‡ๅญ—ใ‚ปใƒƒใƒˆใซใฏ้ฉ็”จใงใใพใ›ใ‚“ใ€‚

ใพใจใ‚

ใƒ“ใƒƒใƒˆใƒžใ‚นใ‚ฏใ‚’ไฝฟ็”จใ—ใŸใ“ใฎใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏใฏใ€ใƒฆใƒ‹ใƒผใ‚ฏใชๅฐๆ–‡ๅญ—ใƒฉใƒ†ใƒณๆ–‡ๅญ—ใ‹ใ‚‰ใชใ‚‹ๆ–‡ๅญ—ๅˆ—ใ‚’ๅŠน็އ็š„ใซๅ‡ฆ็†ใ™ใ‚‹ใŸใ‚ใฎๅผทๅŠ›ใชใƒ„ใƒผใƒซใงใ™ใ€‚ๆ–‡ๅญ—ใฎๅญ˜ๅœจ็ขบ่ชใ‚„ๆ–‡ๅญ—ๅˆ—้–“ใฎๅ…ฑ้€šๆ–‡ๅญ—ใฎๆคœๅ‡บใชใฉใ€ๆง˜ใ€…ใชๆ–‡ๅญ—ๅˆ—ๆ“ไฝœใ‚ฟใ‚นใ‚ฏใงๆดป็”จใงใใพใ™ใ€‚ใŸใ ใ—ใ€้ฉ็”จใงใใ‚‹ๆ–‡ๅญ—ใ‚ปใƒƒใƒˆใŒ้™ใ‚‰ใ‚Œใฆใ„ใ‚‹ใŸใ‚ใ€ไฝฟ็”จใ™ใ‚‹้š›ใฏใใฎๅˆถ้™ใ‚’ๅฟต้ ญใซ็ฝฎใๅฟ…่ฆใŒใ‚ใ‚Šใพใ™ใ€‚

โš ๏ธ **GitHub.com Fallback** โš ๏ธ