gainloというサービスを紹介しているブログを発見。
このモックインタビューのサービスは有料らしいが、ブログも中々読み応えがある。毎日一問ずつ解いてみたのでその記録を。
blog.gainlo.co まずは愚直に解く。この"Sub"というのがポイント。つまり複数のウィンドウに切って処理するので 「どこまで切るか」「どこから切るか」で何回もforループを書く必要があるが、そこをウィンドウをスライドするイメージで計算量を減らす工夫をするテクニックを解説している。
vector<vector<int>> getSubArray(vector<int> num, int sum){ vector<vector<int>> ret; int i = 0; int j = 0; int s = num[0]; while( i < num.size() && j < num.size()) { if( i!=j ){ s+=num[j]; } if ( s > sum ){ s -= num[i]; i++; } if( s == sum ){ ret.push_back(getRange(num,i,j)); s -= num[i]; i++; } j++; } return ret; }
もしくは動的計画法でメモ化を使ったやり方。
void getSubArrayDP( vector<vector<int>>& result, vector<int> sub, vector<int> num, int sum, int remaining, int i ){ if( remaining == 0 ) { auto it = find(result.begin(),result.end(),sub); if(it == result.end()) result.push_back(sub); return; } if( i == num.size() || remaining < 0 ) return; sub.push_back(num[i]); getSubArrayDP(result, sub, num, sum, remaining - num[i], i+1); getSubArrayDP(result, vector<int>(), num, sum, sum, i+1); return; }
なんだ、一旦並べ替えて数えるだけか。
vector<vector<string>> getAnagramGroup( vector<string> input ){
vector<vector<string>> ret;
unordered_map<string,vector<string>> anagramMap;
for( string s : input ){
string key = s;
sort(key.begin(),key.end());
auto it = anagramMap.find(key);
if( it != anagramMap.end()){
it->second.push_back(s);
} else {
anagramMap.insert(make_pair(key,vector<string>{s}));
}
}
for( auto it = anagramMap.begin(); it != anagramMap.end(); ++it) {
if(it->second.size() > 1)
ret.push_back(it->second);
}
return ret;
}
いわゆる最小の編集距離を求める問題。と聞くと難しそうだが前回紹介した動的計画法がそのまま使える。 積み上げていく感じをイメージするとわかりやすい。
int Solution::minDistance(string word1, string word2) { vector<vector<int>> distance(word1.length() + 1, vector<int>(word2.length() + 1, 0)); for (int i = 0; i < distance.size(); i++) { for (int j = 0; j < distance[0].size(); j++) { if (i == 0) distance[i][j] = j; else if (j == 0) distance[i][j] = i; } } for (int i = 1; i < distance.size(); i++) { for (int j = 1; j < distance[0].size(); j++) { if (word1[i - 1] == word2[j - 1]) distance[i][j] = distance[i - 1][j - 1]; else distance[i][j] = 1 + min(distance[i - 1][j - 1], min(distance[i - 1][j], distance[i][j - 1])); } } return distance[word1.length()][word2.length()]; }
blog.gainlo.co 続いて木の問題。ブログでも書かれているStackを使ったDFSの走査を試しに書いてみる。
struct TreeNode2 { TreeNode2* left; TreeNode2* right; string value; bool visited; TreeNode2() : left(NULL),right(NULL),value(""),visited(false){} }; void printDFS(TreeNode2 *root){ if(root == NULL) return; stack<pair<TreeNode2*,string>> s; s.push(make_pair(root,"")); while(!s.empty()){ TreeNode2 *n = s.top().first; string p = s.top().second; p += n->value; s.pop(); n->visited = true; if(n->right && !n->right->visited){ s.push(make_pair(n->right,p+"->")); } if(n->left && !n->left->visited){ s.push(make_pair(n->left,p+"->")); } if(n->left == NULL && n->right ==NULL ){ cout << p << endl; } } }
blog.gainlo.co 今度はリストの並び替え。
struct LinkedList { LinkedList *next; LinkedList *down; int value; LinkedList(int v) : next(NULL),down(NULL),value(v){} }; void flattenList(vector<vector<LinkedList*>>& result, LinkedList *root, int level){ if(root==NULL) return; queue<pair<LinkedList*,int>> q; q.push(make_pair(root,0)); while(!q.empty()){ LinkedList* n = q.front().first; int level = q.front().second; q.pop(); result[level].push_back(n); if(n->next) q.push(make_pair(n->next,level)); if(n->down) q.push(make_pair(n->down,level+1)); } }
blog.gainlo.co これも最初に紹介したスライドウィンドウに似てる。
string findLongestK2( int K, string input ){ string maxStr = ""; int maxLen = 0; int left = 0; int right = 0; unordered_set<char> h; while(left < input.size() && right < input.size()){ h.insert(input[right]); if( h.size() == K ) { int len = right-left+1; if( len > maxLen ){ maxLen = len; maxStr = input.substr(left, len); } } else if( h.size() > K ){ char c = input[left]; while(input[left]==c){ left++; } h.erase(c); } right++; } return maxStr; }
blog.gainlo.co グラフの二つのノードから共通の親を返すものを見つけるもの。
bool findNode(TreeNode *root, TreeNode *target){ if( root == NULL) return false; if( root->val == target->val) return true; return findNode(root->left, target) || findNode(root->right, target); } TreeNode* getCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){ if( root == NULL || root == p || root == q ){ return root; }; bool pIsLeft = findNode(root->left, p); bool qIsLeft = findNode(root->left, q); if(pIsLeft != qIsLeft){ return root; } TreeNode *child = pIsLeft ? root->left : root->right; return getCommonAncestor(child, p, q); } int getLCA(TreeNode *root, TreeNode *p, TreeNode *q){ if( !findNode(root,p) || !findNode(root,q) ){ return -1; } TreeNode* node = getCommonAncestor(root, p, q); return (node) ? node->val : -1; }
blog.gainlo.co これも有名な問題のようだ。
int countMaximumMeetingRoom(vector<pair<int,int>> interval){ struct Event{ int time; bool in; Event(): time(-1),in(false){} bool operator< ( const Event& right) const { return time < right.time; } }; vector<Event> ev(interval.size()*2); for( int i = 0; i < interval.size(); i++ ){ ev[2*i].time = interval[i].first; ev[2*i].in = true; ev[2*i+1].time = interval[i].second; ev[2*i+1].in = false; } sort(ev.begin(),ev.end()); int count = 0; int maxCount = 0; for( int i = 0; i < ev.size(); i++ ){ count += ev[i].in ? 1 : -1; maxCount = max(count, maxCount); } return maxCount; }
string getLongestSubStr2(string s){
string maxStr = "";
unordered_set<char> dup;
int start = 0;
int end = 0;
while(start < s.size() && end < s.size()){
if(dup.find(s[end])==dup.end()){
dup.insert(s[end]);
string sub = s.substr(start,(end-start)+1);
if(sub.size()>maxStr.size()){
maxStr = sub;
}
end++;
} else {
while(start<end){
dup.erase(dup.find(s[start]));
if(s[start]==s[end]){
start++;
break;
}
start++;
}
}
}
return maxStr;
}