x*****0
发帖数: 452 | 1 (1)
The game of Mingo involves a 100x100 board with unique positive whole
numbers in the range from 1 to 1,000,000 randomly distributed in the cells.
Unique numbers are "called" one at a time and the goal is to have a "Mingo",
which is an entire row or column of cells with numbers that have been
called. One might also form a diagonal from corner to corner with numbers
that have been called. Given a square array of 100x100 positive whole
numbers and a list of "called" numbers, write an algorithm to check there is
a "Mingo".
(2)
Assonance is the reiteration of the same vowel sound at the beginning of
several consecutive words. Assume that each vowel(A, E, I, O, and U) has
only one sound. Prompt the user for an alpha-only string with spaces as
delimiters between words. Your program will arrange the words to maximize
assonance, and print the new string. After the fast word in the string that
begins with a given vowel, and all other words in the string that begin with
the same vowel must immediately follow that vowel, in the order
they appear in the original string. All non-assonized words should remain in
the same order in which they occurred in the original string. |
p*****p
发帖数: 379 | 2 是不是只有202种情况？100横100竖加两个对角线？
.
",
is
【在 x*****0 的大作中提到】
: (1)
: The game of Mingo involves a 100x100 board with unique positive whole
: numbers in the range from 1 to 1,000,000 randomly distributed in the cells.
: Unique numbers are "called" one at a time and the goal is to have a "Mingo",
: which is an entire row or column of cells with numbers that have been
: called. One might also form a diagonal from corner to corner with numbers
: that have been called. Given a square array of 100x100 positive whole
: numbers and a list of "called" numbers, write an algorithm to check there is
: a "Mingo".
: (2)
|
x*****0
发帖数: 452 | 3 我感觉是
【在 p*****p 的大作中提到】
: 是不是只有202种情况？100横100竖加两个对角线？
:
: .
: ",
: is
|
p*****p
发帖数: 379 | 4 第一题你怎么答的？最简单的解法O(n^2)吧
或者类似bit，用个mask，需要4个int
第二题用个二维数组就行了吧
【在 x*****0 的大作中提到】
: 我感觉是
|
x*****0
发帖数: 452 | 5 第二题用个二维数组，可以说详细一点吗？
【在 p*****p 的大作中提到】
: 第一题你怎么答的？最简单的解法O(n^2)吧
: 或者类似bit，用个mask，需要4个int
: 第二题用个二维数组就行了吧
|
m*****P
发帖数: 1331 | 6 土了 题目都看不懂
能否解释下第二题的意思
给个例子吧
【在 x*****0 的大作中提到】
: (1)
: The game of Mingo involves a 100x100 board with unique positive whole
: numbers in the range from 1 to 1,000,000 randomly distributed in the cells.
: Unique numbers are "called" one at a time and the goal is to have a "Mingo",
: which is an entire row or column of cells with numbers that have been
: called. One might also form a diagonal from corner to corner with numbers
: that have been called. Given a square array of 100x100 positive whole
: numbers and a list of "called" numbers, write an algorithm to check there is
: a "Mingo".
: (2)
|
x*****0
发帖数: 452 | 7 我说说我的理解哈。当时我也没怎么看懂题目。这个online test。字典也不准用。
下面是一个string
“Assonance reiteration is the of the same vowel sound at the beginning
of several consecutive words”
最后的结果应该是：
"Assonance at reiteration is the of of the same vowel sound the beginning
several consecutive words"
【在 m*****P 的大作中提到】
: 土了 题目都看不懂
: 能否解释下第二题的意思
: 给个例子吧
|
p*****p
发帖数: 379 | 8 开个size为6的list代表aeiou和其他
每个是一个list，装了以那个字母为开头的单词
用java的arraylist就是
ArrayList> container
每碰到一个单词就看开头字母，装到相应的list里
我没理解错题意的话就是这样了吧
【在 x*****0 的大作中提到】
: 第二题用个二维数组，可以说详细一点吗？
|
x*****0
发帖数: 452 | 9 嗯嗯，明白了。是这样的
因为对java不熟，所以都是用c做的。我的想法是这样：
(1) 遍历word one by one.
(2) 每遇到一个word，有三种情况
a. 这个word不是以 A E I O U 开头的, do nothing
b. 这个word如果是，例如以A开头。那么又分两种情况。
b1 如果这是第一个以A开头的word，用变量x记录其位置。
b2 如果这不是第一个以A开头的word，将其移到上个以A开头的word之后，并更新x。
算法时间复杂度O(N^2) N是string的长度。空间复杂度O（1）
移动一个word的算法：
http://stackoverflow.com/questions/15212749/move-a-word-in-a-st
还有另一个方法，时间复杂度要低一些。
(1) 对string中的每个word进行以比较首字母的方式排序。
(2) 然后遍历原始的string。当遇到word以A E I O U开头时，比如A。从排好序的
string中输出所有以A开头的word。
这个方法应该和你的java实现本质上差不多。
【在 p*****p 的大作中提到】
: 开个size为6的list代表aeiou和其他
: 每个是一个list，装了以那个字母为开头的单词
: 用java的arraylist就是
: ArrayList> container
: 每碰到一个单词就看开头字母，装到相应的list里
: 我没理解错题意的话就是这样了吧
|
x*****0
发帖数: 452 | 10 (2) C++ code:
void split_by_whitespace(string& s, vector& result)
{
stringstream ss(s);
string cur;
while(ss >> cur)
result.push_back(cur);
}
void maxi_assonance(vector& x)
{
vector::iterator it = x.begin();
vector > r;
map key_ind;
for(; it!=x.end(); ++it)
{
string cur = *it;
if(cur[0]=='a' || cur[0]=='e' ||
cur[0]=='i' || cur[0]=='o' ||
cur[0]=='u')
{
map::iterator it_map = key_ind.find(cur[0]);
vector tmp;
if(it_map==key_ind.end())
{
key_ind.insert(pair(cur[0], r.size()));
tmp.push_back(cur);
r.push_back(tmp);
}
else
{
r[key_ind[cur[0]]].push_back(cur);
}
}
else
{
vector tmp;
tmp.push_back(cur);
r.push_back(tmp);
}
}
vector >::iterator it1 = r.begin();
for(; it1!=r.end(); ++it1)
{
vector cur = *it1;
vector::iterator it2 = cur.begin();
for(; it2!=cur.end(); ++it2)
{
cout << *it2 << " ";
}
}
}
.
",
is
【在 x*****0 的大作中提到】
: (1)
: The game of Mingo involves a 100x100 board with unique positive whole
: numbers in the range from 1 to 1,000,000 randomly distributed in the cells.
: Unique numbers are "called" one at a time and the goal is to have a "Mingo",
: which is an entire row or column of cells with numbers that have been
: called. One might also form a diagonal from corner to corner with numbers
: that have been called. Given a square array of 100x100 positive whole
: numbers and a list of "called" numbers, write an algorithm to check there is
: a "Mingo".
: (2)
|
