LeetCode 配列 / 文字列（基礎）ハッシュテーブル

数値をキーとして目的の計算結果をハッシュテーブルに保存しておく

Contains Duplicates

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::set<int> dic;
        bool is_duplicate = false;
        for (int i = 0; i < nums.size(); i++){
            if(dic.find(nums[i]) != dic.end()){
                is_duplicate = true;
                break;
            } else{
                dic.insert(nums[i]);
            }
        }
        return is_duplicate;
    }
};

Contains Duplicate2

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        std::unordered_map<int, int> dic;
        for (int i = 0; i < nums.size(); i++){
            if (dic.contains(nums[i])){
                if (i - dic[nums[i]] <= k){
                    return true;
                } 
            }
            dic[nums[i]] = i;
        }
        return false;
    }
};

Longest Consective Sequence

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set(nums.begin(), nums.end());
        int longestStreak = 0;
        for (int num : nums) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
};

brute forceで最初実装した後に、それを最適化できないか考える.
時間計算量はfor文のO(n)とwhile文のO(n). (whileは、num-1がない場合にのみ動くので、O(n)).

文字 or 数値の出現回数などを管理する

Group Anagram

class Solution {
public:
    std::string join(const std::vector<int>& strings,
                     const std::string& delimiter) {
        std::ostringstream result;
        for (size_t i = 0; i < strings.size(); ++i) {
            result << strings[i];
            if (i < strings.size() - 1) {
                result << delimiter; // デリミタを追加
            }
        }
        return result.str();
    }

    string createKey(const string& str) {
        vector<int> s(26);
        for (char ch : str) {
            s[static_cast<int>(ch) - static_cast<int>('a')] += 1;
        }
        return join(s, ",");
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::unordered_map<string, vector<string>> map;
        for (string str : strs) {
            string key = createKey(str);
            if (!map.contains(key)){
                map[key] = {};
            } 
            map[key].push_back(str);
        }
        std::vector<vector<string>> ans;
        for (auto pair : map){
            ans.push_back(pair.second);
        }
        return ans;
    }
};

Number of Good Pairs

from collections import Counter
import math
class Solution:
    def comb(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    def numIdenticalPairs(self, nums: List[int]) -> int:
        nums_counter = Counter(nums)
        ans = 0
        for key in nums_counter:
            ans += comb(nums_counter[key],2)
        return ans

Verifying an Alien Dictionary

class Solution:

    def isAlienSorted(self, words: List[str], order: str) -> bool:
        def compareTwoStrings(s, t, ordered_dic):
            min_length = min(len(s), len(t))
            for i in range(min_length):
                if ordered_dic[s[i]] < ordered_dic[t[i]]:
                    return True
                elif ordered_dic[s[i]] > ordered_dic[t[i]]:
                    return False
        
            # deal with corner case
            if (len(s) > len(t)):
                return False
            return True

        ordered_dic = {}
        ## prepare dictionary
        for i in range(len(order)):
            ordered_dic[order[i]] = i
        
        ## detect if words are sorted

        for i in range(1, len(words)):
            # compare words[i] and words[i-1]
            if not compareTwoStrings(words[i-1], words[i], ordered_dic):
                return False
        return True

最初、compareTwoStringsを切り出さなかったせいでややこしくなった、coding interviewでもややこしくなったらまず関数に切り出す.
コーナーケース見落としてる. 復習すべき