问题:
生活场景:
分析:
以我们列举的生活场景为例,我们在具体做这件事的时候,肯定不会拿着老板给的类似T中:A物品 B物品 A物品 C物品 这么二的清单,而是对物品做统计,生成这样的需求清单:
物品A:X件
物品B:Y件
物品C:Z件
而在寻找的过程中,我们还需要一份已收集清单,就是目前已经找到的每个物品的信息,其形式与上面列举的一致。那么这些信息怎么来存储呢,我们总是希望对给定的物品,在O(1)的时间内找出对应的数值信息,所以要用hash table。
我们开始在起始楼层(下电梯的楼层)向上查找,遇到一个物品,我们看下是否是我们需要的,若是,则收集,并更改已收集清单相应物品的数量上加1。若不是,则跳过,继续向楼上搜集。看到这里我们就发现了问题,因为我们看到物品是需要的就收集它,并更改已收集表,那么我们怎么判断我们已经完成了收集工作了呢?比较两个表中对于的项,已收集项都大于等于需求的时候?但这样要进行比较,不能在O(1)的时间得到明确的判断,所以我们还需要一个变量,来记录到目前为止,收集到的”有效“的物品数,何为有效的物品,比如需求里A:3,B:2,假设A的数量已经是3,当再次遇到A时,虽然A是需求清单里需要的,但是已经有3个了,满足要求了,现在遇到的A就不能算作有效的物品,你现在需要做的是去收集除A以外其他物品。当有效物品数与需求清单中的总物品数相等的时候,我们就说我们的收集工作完成了。
但是这时你又会想,有没有更好的选择,比如你是从1楼开始收集的,收集到10楼将物品收集完毕,从2楼或者更高的楼层开始收集是不是也能完成任务?这样就可以少爬几层楼梯。这就要判断1楼的物品性质了,假如1楼的物品不是需要的,当然可以直接从2楼开始,亦或者,虽然1楼的物品是需要的,但是2楼也有这个物品,而且从2楼开始,这个物品总是也满足要求。那么就可以从2楼开始,依次2楼,3楼,直到不能精简,这就是当前的一个精简窗口,也就是不包含子窗口的窗口。但这个就是最小的吗?不一定,因为可能从11楼开始,到13楼就收集齐备了。所以这个查找的过程要进行到最后。每次找到新的窗口,跟目前最小的比较,更新最小窗口。
实现:
string minWindow(string S, string T) { int N = S.size(); int M = T.size(); int minWindowLen = INT_MAX; //hash table init all 0s //used to statistic the number of each letter needed. int needToFind[256] = {0}; for (int i = 0; i < M; ++i) needToFind[T[i]]++; //hash table init all 0s //used to record the number of each letter has found. int hasFind[256] = {0}; //use to record the total letters we has found. //if it equal to T.size(), it means we get a window. int count = 0; // end used to find the letters needed in T. // start used to drop the redundant letters to cut short the window. int start, end; //min_start and min_end recored the optimal resolve. int min_start = 0; int min_end = INT_MAX; for (start = 0, end = 0; end < N; ++end) { if( 0 == needToFind[ S[end] ])//not needed continue; hasFind[ S[end] ]++; if(hasFind[ S[end] ] <= needToFind[ S[end] ]) count++; //find a window if(count == M){ //judge whether the window can be cut short, for example, //the letter indicated by start is not needed or redundant. while ( 0 == needToFind[ S[start] ] || hasFind[S[start]] > needToFind[S[start]]) { if(hasFind[S[start]] > needToFind[S[start]])//redundant hasFind[S[start]]--; ++start; } int windowLen = end - start + 1; if (windowLen < minWindowLen) { minWindowLen = windowLen; min_start = start; min_end = end; } } } if(min_end == INT_MAX) return ""; return S.substr(min_start, min_end - min_start + 1); }