问一道题(6) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道题(6)

问一道题(6)# JobHunting - 待字闺中

f*d2013-08-07 07:08

1 楼

Given an input array A of integers of size n, and a query array B of
integers of size m, find the smallest window of input array that contains
all the elements of query array and also in the same order.
e.g.
input
A = [1, 9, 3, 4, 12, 13, 9, 12, 21]
B = [9, 12, 21]
output
A[6..8] = [9, 12, 21]

e*82013-08-07 07:08

2 楼

leetcode上的原题minimum window substring

f*d2013-08-07 07:08

3 楼

"also in the same order."
还是多谢指教！

【在 e*******8 的大作中提到】

: leetcode上的原题minimum window substring

c*12013-08-07 07:08

4 楼

use your example. keep an array of size 3, arr[0] is the last occurrence
of 9, arr[1] is the last occurrence of 9, 12. arr[2] is the last
occurrence of 9, 12, 21. scan A and update array accordingly. the minimum
size of all values of arr[2] is what you want.

f*d2013-08-07 07:08

5 楼

first, arra[0] is the last occurrence of 9, then you will get last 9, which
maybe not even valid result for the final solution
second, how to update array, any suggestion or hint? Thanks!
Overall, thanks for your help and idea!

minimum

【在 c**1 的大作中提到】

: use your example. keep an array of size 3, arr[0] is the last occurrence
: of 9, arr[1] is the last occurrence of 9, 12. arr[2] is the last
: occurrence of 9, 12, 21. scan A and update array accordingly. the minimum
: size of all values of arr[2] is what you want.

c*12013-08-07 07:08

6 楼

of course I mean last occurrence so far.

f*d2013-08-07 07:08

7 楼

Ok, got it. Then, how to update?

【在 c**1 的大作中提到】

: of course I mean last occurrence so far.

c*12013-08-07 07:08

8 楼

why not think it by yourself? I've given enough hint.

f*d2013-08-07 07:08

9 楼

need a hashmap, right? Then O(n) assuming O(1) of hash read and write.

【在 c**1 的大作中提到】

: why not think it by yourself? I've given enough hint.

r*n2013-08-07 07:08

10 楼

think it this way, it'd be easier to understand:
let arr[0,1,2] store the the latest indices of 9, 12, 21
whenever you update arr[2], check if arr is strictly increasing, if yes,
then arr[2]-arr[0]+1 if the new window size.
However, I think this method only works when the pattern array does not have
duplicates.
For example, if given 9, 12, 9, 21, it won't work
Another approach is to simply do a subsequence search on the source array.
You may be able to use memonization to get O(N) running time.

which

【在 f*********d 的大作中提到】

: first, arra[0] is the last occurrence of 9, then you will get last 9, which
: maybe not even valid result for the final solution
: second, how to update array, any suggestion or hint? Thanks!
: Overall, thanks for your help and idea!
:
: minimum

d*k2013-08-07 07:08

11 楼

Assume len(B) = n, len(A) = m. Maintain 'list[1..n]', where list[i] will
hold the indexes of all B[i]'s occurrence in A. Initially all the n lists
should be empty.
1. Scan A once, for each number A[i] in A, if A[i] is in B[j], append i
to list[j]. Do nothing otherwise.
After this step, for the list[1..n], list[i] holds the indexes of
all B[i]'s occurrence in A.
2. for each value list[1], remove the heads of list[2..n] until
list[j].head >list[1].head for 1 < j <= n. At this point, one
solution is found and the indexes are heads of list[1..n]. The length
of this solution is (list[n].head - list[1].head)
The minimum of length found in step is the answer. Using hash map for the
mappings, the run time should be O(m+n).
It doesn't matter if B contains duplicate values.
Please confirm me or correct me.

【在 f*********d 的大作中提到】

: Given an input array A of integers of size n, and a query array B of
: integers of size m, find the smallest window of input array that contains
: all the elements of query array and also in the same order.
: e.g.
: input
: A = [1, 9, 3, 4, 12, 13, 9, 12, 21]
: B = [9, 12, 21]
: output
: A[6..8] = [9, 12, 21]

m*h2013-08-07 07:08

12 楼

https://gist.github.com/anonymous/6175134

l*l2013-08-07 07:08

13 楼

similar to minimum window
Exception: you don't update appear and appeared[] if any preceding numbers
in B undetected

f*d2013-08-07 07:08

14 楼

好方法！链表奇用啊！
个人觉得是work的，除了一点小的修改，我错了请指出
1 “if A[i] is in B[j]” 这里需要用个hashtable吧？
2 for each value list[1], remove the heads of list[2..n] until
list[j].head >list[1].head for 1 < j <= n.
觉得应该是
for each value list[i] do
remove the heads of list_arr[2..n] until
list_arr[j].head >list_arr[j - 1].head for 1 < j <= n.
get a validate solution
remove head of list[i]
我临时用list_arr是为了避免歧义
===============================================
Assume len(B) = n, len(A) = m. Maintain 'list[1..n]', where list[i] will
hold the indexes of all B[i]'s occurrence in A. Initially all the n lists
should be empty.
1. Scan A once, for each number A[i] in A, if A[i] is in B[j], append i
to list[j]. Do nothing otherwise.
After this step, for the list[1..n], list[i] holds the indexes of
all B[i]'s occurrence in A.
2. for each value list[1], remove the heads of list[2..n] until
list[j].head >list[1].head for 1 < j <= n. At this point, one
solution is found and the indexes are heads of list[1..n]. The length
of this solution is (list[n].head - list[1].head)
please confirm or correct me!

【在 d*k 的大作中提到】

: Assume len(B) = n, len(A) = m. Maintain 'list[1..n]', where list[i] will
: hold the indexes of all B[i]'s occurrence in A. Initially all the n lists
: should be empty.
: 1. Scan A once, for each number A[i] in A, if A[i] is in B[j], append i
: to list[j]. Do nothing otherwise.
: After this step, for the list[1..n], list[i] holds the indexes of
: all B[i]'s occurrence in A.
: 2. for each value list[1], remove the heads of list[2..n] until
: list[j].head >list[1].head for 1 < j <= n. At this point, one
: solution is found and the indexes are heads of list[1..n]. The length

f*d2013-08-07 07:08

15 楼

Think it for a while, still have some trouble if B has duplicates, hash does
not work now (i.e., I don't know how to make records for duplicate values
in B).

【在 f*********d 的大作中提到】

: need a hashmap, right? Then O(n) assuming O(1) of hash read and write.

f*d2013-08-07 07:08

16 楼

子序列查找？
连续的还好
不连续的是在没有什么想法，还请指点迷津~

have

【在 r*********n 的大作中提到】

: think it this way, it'd be easier to understand:
: let arr[0,1,2] store the the latest indices of 9, 12, 21
: whenever you update arr[2], check if arr is strictly increasing, if yes,
: then arr[2]-arr[0]+1 if the new window size.
: However, I think this method only works when the pattern array does not have
: duplicates.
: For example, if given 9, 12, 9, 21, it won't work
: Another approach is to simply do a subsequence search on the source array.
: You may be able to use memonization to get O(N) running time.
:

f*d2013-08-07 07:08

17 楼

先谢再看~

【在 m*******h 的大作中提到】

: https://gist.github.com/anonymous/6175134

f*d2013-08-07 07:08

18 楼

嗯貌似就是dek给的方法！
代码精简漂亮，学习了~

【在 m*******h 的大作中提到】

: https://gist.github.com/anonymous/6175134

a*e2013-08-07 07:08

19 楼

楼主问的题都很好啊，请问楼主都是哪里找的题目？多谢~

【在 f*********d 的大作中提到】

b*e2013-08-07 07:08

20 楼

This works, but mind mentioning the time complexity is O(m*n), which might
not be the best?
BTW, you might be a smartass, but you don't have not be an ass.

minimum

【在 c**1 的大作中提到】

c*12013-08-07 07:08

21 楼

Blame yourself if you don't understand. My algorithm is O(m+n) if there is
no dupe in b.
vector v(b.size(), -1);
int len = MAX_INT;
for (i = 0 to a.size()-1) {
int j = find_index_in_b_using_hash(a[i]); //return -1 if not found;
if (j < 0 ) continue;
if (j == 0) v[0] = i;
else v[j] = v[j-1];
if ( j == b.size()-1 && v[j] >= 0 )
len = min(len, v[j] - i + 1;
}
return len;

r*c2013-08-07 07:08

22 楼

贴个pattern字符串有重复字符的解法，是dek,cpp1等大牛的解法的扩展。
#include
#include
#include
#include
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN -2147483648
class MinWindowSolution
{
public:
struct TreeNode
{
TreeNode *parent;
int val;
vector children;
TreeNode(int i, TreeNode *p) : val(i), parent(p){}
};
void FindMinWindow_Tree(const vector& input , const vector&
query , int& nStart, int& nEnd){
nStart = nEnd = -1;
if (sizeof(query) > sizeof(input) || query.size() <= 0) return;
int nMin = INT_MAX;
unordered_map* > pos;
for (int i = 0; i < query.size(); ++i)
pos[query[i]] = new deque();
bool bFilled = true;
for (int j = 0; j < input.size(); ++j){
if (pos.find(input[j]) != pos.end()){
auto q = pos[input[j]];
q->push_front(j);
pos[input[j]] = q;
if (q->size() <= 0)
bFilled = false;
}
}
if (!bFilled) return;
TreeNode *root = new TreeNode(INT_MIN, 0);
deque *pRoot = reinterpret_cast *>(pos.at(query[0]));
for (int s=0; s< pRoot->size(); ++s){
int v = pRoot->at(s);
root->children.push_back(new TreeNode(v, root));
}
vector lst = root->children;
nMin = INT_MAX;
for (int k = 1; k < query.size(); ++k){
vector tmpList;
for(int r = 0; r < lst.size(); ++r){
TreeNode *pNode = lst[r];
deque *pDeque = reinterpret_cast *>(pos.at(
query[k]));
for (int t = 0; t < pDeque->size(); ++t){
if (pDeque->at(t) <= pNode->val) continue;
TreeNode *pNewNode = new TreeNode(pDeque->at(t), pNode);
pNode->children.push_back(pNewNode);
int nfindex, nlindex;
if (k == query.size()-1 ){
if(nMin > pathLength(pNewNode, nfindex, nlindex)){
nMin = pathLength(pNewNode, nfindex, nlindex);
nStart = nfindex;
nEnd = nlindex;
}
}
}
tmpList.insert(tmpList.end(), pNode->children.begin(), pNode
->children.end());
}
lst = tmpList;
}
}
int pathLength(TreeNode *tnSource, int& nFirstIndex, int& nLastIndex)
{
nLastIndex = nFirstIndex = -1;
nLastIndex = tnSource->val;
TreeNode *temp = tnSource;
TreeNode *trailing = 0;
while (temp->parent != 0){
trailing = temp;
temp = temp->parent;
}
nFirstIndex = trailing->val;
if (nLastIndex > nFirstIndex) //all matched and in good order
return nLastIndex - nFirstIndex + 1;
return INT_MAX;
}
static void TestMinWindowSolution()
{
int inputArray[] = { 1, 7, 8, 19, 3, 2, 2, 38, 25, 39, 14, 0,
2, 2, 87, 39, 14 };
int queryArray[] = { 2, 2, 39, 14 };
std::vector input(std::begin(inputArray), std::end(inputArray));
vector query(std::begin(queryArray), std::end(queryArray));
int nStart, nEnd;
MinWindowSolution *sol = new MinWindowSolution();
sol->FindMinWindow_Tree(input, query, nStart, nEnd);
assert(nStart == 12 && nEnd == 16);
}
};

r*c2013-08-07 07:08

23 楼

之前写了个C#的。思路都一样， use tree matching algorithm to determine the
candidate window.
//using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class MinWindowSolution
{
class TreeNode
{
public TreeNode parent;
public int val;
public List children;
public TreeNode(int i, TreeNode p) { val = i; parent = p; children =
new List(); }
};
public void FindMinWindow_Tree(int[] input, int[] query, out int nStart,
out int nEnd)
{
nStart = nEnd = -1;
if (query.Length > input.Length || query.Length <= 0) return;
int nMin = int.MaxValue;
Hashtable ht = new Hashtable();
for (int i = 0; i < query.Length; ++i)
ht[query[i]] = new Queue();
bool bFilled = true;
for (int j = 0; j < input.Length; ++j)
{
if (ht.ContainsKey(input[j]))
{
var q = (Queue)ht[input[j]];
q.Enqueue(j);
ht[input[j]] = q;
if (q.Count() <= 0)
bFilled = false;
}
}
if (!bFilled) return;
//use tree matching algo to determine the window
TreeNode root = new TreeNode(int.MinValue, null);
foreach (int v in ((Queue)ht[query[0]]).ToArray())
root.children.Add(new TreeNode(v, root));
List lst = root.children;
nMin = int.MaxValue;
for (int k = 1; k < query.Length; ++k)
{
List tmpList = new List();
foreach (var n in lst)
{
foreach (int u in ((Queue)ht[query[k]]).ToArray())
{
if (u <= n.val) continue;
TreeNode tmpNode = new TreeNode(u, n);
n.children.Add(tmpNode);
int nfindex, nlindex;
if (k == query.Length - 1 && nMin > pathLength(tmpNode,
out nfindex, out nlindex))
{
nMin = pathLength(tmpNode, out nfindex, out nlindex);
nStart = nfindex;
nEnd = nlindex;
}
}
tmpList.AddRange(n.children);
}
lst = tmpList;
}
}
int pathLength(TreeNode tnSource, out int nFirstIndex, out int
nLastIndex)
{
nLastIndex = nFirstIndex = -1;
nLastIndex = tnSource.val;
TreeNode temp = tnSource;
TreeNode trailing = null;
while (temp.parent != null)
{
trailing = temp;
temp = temp.parent;
}
nFirstIndex = trailing.val;
if (nLastIndex > nFirstIndex) //all matched and in good order
return nLastIndex - nFirstIndex + 1;
return int.MaxValue;
}
static void Main(string[] args)
{
int[] input = { 1, 7, 8, 19, 3, 2, 2, 38, 25, 39, 14, 0, 2, 2, 87,
39, 14 };
int[] query = { 2, 2, 39, 14 };
int nStart, nEnd;
MinWindowSolution sol = new MinWindowSolution();
sol.FindMinWindow_Tree(input, query, out nStart, out nEnd);
}
}

v*n2013-08-07 07:08

24 楼

mark

b*e2013-08-07 07:08

25 楼

You assumed O(1) hash index on b, which is not strict. Without that
assumption, you algorithm is O(m*n).

is

【在 c**1 的大作中提到】

: Blame yourself if you don't understand. My algorithm is O(m+n) if there is
: no dupe in b.
: vector v(b.size(), -1);
: int len = MAX_INT;
: for (i = 0 to a.size()-1) {
: int j = find_index_in_b_using_hash(a[i]); //return -1 if not found;
: if (j < 0 ) continue;
: if (j == 0) v[0] = i;
: else v[j] = v[j-1];
: if ( j == b.size()-1 && v[j] >= 0 )

d*n2013-08-07 07:08

26 楼

void MinimumWindowCoverInOrder(int[] A, int[] B, out int start, out int min)
{
Dictionary> bPosInAMap = new Dictionary>(
);
Queue[] bPosInA = new Queue[B.Length];
start = -1;
min = Int32.MaxValue;
for (int i = 0; i < B.Length; ++i) {
if (!bPosInAMap.ContainsKey(B[i]))
bPosInAMap.Add(B[i], new Queue());
}
for (int i = 0; i < A.Length; ++i) {
if (bPosInAMap.ContainsKey(A[i]))
bPosInAMap[A[i]].Enqueue(i);
}
// Clone the queues to make it easier to understand
for (int i = 0; i < B.Length; ++i)
if (bPosInAMap.ContainsKey(B[i]))
bPosInA[i] = new Queue(bPosInAMap[B[i]]);
else return;
int prev = -1;
while(true) {
for(int i = 0; i < B.Length; ++i) {
while (bPosInA[i].Count > 0 && bPosInA[i].Peek() <= prev)
bPosInA[i].Dequeue();
if (bPosInA[i].Count < 1) return;
prev = bPosInA[i].Peek();
}
int curLen = bPosInA[B.Length - 1].Peek() - bPosInA[0].Peek() + 1;
if (curLen < min)
{
min = curLen;
start = bPosInA[0].Peek();
}
prev = bPosInA[0].Peek();
}
}

【在 b***e 的大作中提到】

: You assumed O(1) hash index on b, which is not strict. Without that
: assumption, you algorithm is O(m*n).
:
: is

l*92013-08-07 07:08

27 楼

my own o(m*n) solution
* it only can handle unique number in b[]
public static int f(int[] a, int[] b)
{
int n = a.length;
int m = b.length;
int min = Integer.MAX_VALUE;
int minEnd = -1;
int[] pos = new int[m]; // the last occurrence of b[i] in a[]
int[] len = new int[m]; // the length of the last sequence ending at b[i
]
Arrays.fill(pos, -1);
Arrays.fill(len, 0);
for (int j = 0; j < n; ++j) {
// search a[j] in b[]
int i;
for (i = 0; i < m; ++i) {
if (b[i] == a[j])
break;
}
if (i == m) // not found
continue;
if (i == 0) {
// first element
pos[i] = j;
len[i] = 1;
} else {
if (pos[i - 1] >= 0) {
// previous element already found
pos[i] = j;
len[i] = len[i - 1] + pos[i] - pos[i - 1];
if (i == m - 1 && len[i] < min) {
// the complete and shortest sequence found
min = len[i];
minEnd = j;
}
}
}
}
if (minEnd > 0) {
System.out.println(Arrays.toString(Arrays.copyOfRange(a, minEnd - min
+ 1, minEnd + 1)));
}
return min;
}
http://ideone.com/XNxUeR

is

【在 c**1 的大作中提到】

c*n2013-08-07 07:08

28 楼

One-pass solution:
maintain a queue Q with element , initially, it has
an element
scan A one-pass, for each element A[CurInd], update Q with
1. if A[CurInd] == B[NextElementInB]; if (NextElementInB == 0){ BeginInd =
CurInd}; update NextElementInB += 1;
2. Delete q[b1,n1] if existing q[b2,n2] in Q, s.t. b1 <= b2 and n1 <= n2;