毎日アルゴリズム(四)問題例題の検索

タイトルはLeetCodeから
242. Valid Anagram
この問題は前の「簡単な問題探し」で述べたようにmapでマッピングタグを行い、ループします.
遍歴して判断すればいい.

class Solution {
public:
    bool isAnagram(string s, string t) {
       if(s.size() != t.size())
		return false;
	map s1;
	for( int i = 0 ; i < s.size() ; i++ ) {
		s1[s[i]] ++;
	}
	
	bool isA = true;
	for( int i = 0 ; i < t.size() ; i++ ) {
		if( s1[t[i]] > 0 ) {
			s1[t[i]] --;
		}else {
			isA = false;
			break;
		}
	}
	return isA; 
    }
};

202
. 
Happy Number
ここではmapをタグとして使用し、intタイプの整数をstringタイプに変えて保存し、各ビットを取り出すのに便利です.

bool isAnHappyNumber(int n) {
	map list;
	int sum;
	stringstream ss;
	ss<

補足:c++のintタイプとstringタイプの間の変換は気持ち悪いです.私の中でstringstreamを採用して変換しました.ヘッダーファイルを追加するのを忘れないでください.もちろんchar配列を媒介としてstringをc_str()メソッドは文字配列に変換されます.またstringタイプは下付き文字で各文字にアクセスでき、各文字はcharタイプであり、直接演算するとcharタイプを対応するASCIIコードに変換し、ASCIIコードテーブルのいくつかのルールに基づいて一連の変換を行うことができます.ここで文字0のASCIIのコードは48なので、48を減算すると対応する数値が得られます.もちろんここではstringタイプのデータではなくintタイプのデータを格納し、残りを取って各ビットを求めることができます.コードは以下の通りです.

void getSum(int n) {
	int sum;
	while(n) {
		sum += pow(n%10,2);
		n = n/10;
	}
}

205. Isomorphic Strings   290. Word Pattern
この2つの問題のタイプはよく似ていて、解決策もあまり違いません.
290文字列とパターンを与えて、この文字列がこのパターンに合っているかどうかを判断します.
205は、2つの文字列を与えて、彼らが同構造であるかどうかを判断します.つまり、互いにマッピングすることができます.
ここではクエリーテーブルとしてmapを使用し、文字や文字列に対応するタイプをマークします.
vectorの格納場所と対応するタイプ.(以上はc++98で実現されているが、c++11を使用するとunordered_mapを使用できると提案されている場合、vectorを使用する必要はない.ここでmapは無秩序であり、位置ごとに対応する異なるタイプを特定する必要があるため、vectorが1つ多く作成されている)
構想は文字あるいは文字列を取り出してmapの中で照会して、もし存在するならば対応するタイプを取って、保存します
vectorが対応する位置に行き、mapでクエリーされていない場合はmapに格納され、vectorに格納されます.最後に、vectorの異なる位置のタイプが同じかどうかを比較することで、2つの文字列が同性であるか、またはパターンに合致しているかを決定します.
具体的なコードは次のとおりです.
290
コードは少しくどいかもしれませんが、まだ大きな最適化の空間があります.興味のある友达は最適化することができます.

bool wordPattern(string pattern, string str) {
	map m; // require table (itself and type)
	vector v,v1;  //  result table  (local and type)
	vector s_list;
	string tem("");
	//                 
	for(int i = 0 ; i < str.size() ; i++ ) {
		if(str[i] == ' ') {
			s_list.push_back(tem);
			tem = "";
		} 
		else 
			tem += str[i];	
	}
	s_list.push_back(tem);
	if(s_list.size() != pattern.size())
		return false;
	map::iterator it;
	int type = 0;
	for( int i = 0 ; i < pattern.size() ; i++ ) {
		it = m.find(pattern[i] + "");
		if(it != m.end()) {
			v.push_back(it->second);
		}else {
			v.push_back(++type);
			m[pattern[i] +""] = type;
		}
	}

	m.clear();
	type = 0;
	for( int i = 0 ; i < s_list.size() ; i++ ) {
		it = m.find(s_list[i]);
		if(it != m.end()) {
			v1.push_back(it->second);
		}else {
			v1.push_back(++type);
			m[s_list[i]] = type;
		}
	}
	for(int i = 0 ; i < v.size() ; i++ ) {
		if(v[i] != v1[i])
			return false;
	}
	return true;
	
}

205コードは以下の通りである.

bool isIsomorphic(string s, string t) {
	if( s.size() != t.size() )
		return false;
        vector v;
        vector v1;
        map m;
        int type = 0;
        map::iterator it;
        for( int i = 0 ; i < s.size() ; i++ ) {
        	it = m.find(s[i]);
        	if( it != m.end() )
        		v.push_back(it->second);
        	else {
        		v.push_back(++type);
        		m[s[i]] = type;
			}		
		}
		m.clear();
		type = 0;
		for( int i = 0 ; i < t.size() ; i++ ) {
        	it = m.find(t[i]);
        	if( it != m.end() )
        		v1.push_back(it->second);
        	else {
        		v1.push_back(++type);
        		m[t[i]] = type;
			}
			if(v1[i] != v[i])
				return false;		
		}
		return true;
}