c********t
发帖数: 5706 | 1 总听大家说面试碰到拓扑排序题。谁能给一两道。一般怎么解？ |
w****x
发帖数: 2483 | 2 const int M = 6;
void printTopoSort(bool a[M][M])
{
int into[M] = {0};
for (int i = 0; i < M; i++)
{
for (int j = 0; j < M; j++)
{
if (a[j][i])
into[i]++;
}
}
int res[M] = {0};
for (int i = 0; i < M; i++)
{
int j = 0;
for (; j < M; j++)
{
if (into[j] == 0)
break;
}
if (j >= M) return;
into[j] = -1;
res[i] = j;
for (int k = 0; k < M; k++)
{
if (a[j][k])
into[k]--;
}
}
for (int i = 0; i < M; i++)
cout<
} |
c**s
发帖数: 159 | 3 例如 给定另外一种语言的字典，信息足够多，还原出那种语言的字母表顺序。
【在 c********t 的大作中提到】
: 总听大家说面试碰到拓扑排序题。谁能给一两道。一般怎么解？
|
c********t
发帖数: 5706 | 4 多谢两位大侠，看着都很难，我先好好消化消化。
【在 c**s 的大作中提到】
: 例如 给定另外一种语言的字典，信息足够多，还原出那种语言的字母表顺序。
|
w****x
发帖数: 2483 | 5
/*
Given an array list of lots of strings, they are arranged by unknown
alphabetical
order, print all possible alphabetical orders (Sort)
*/
void buildMap(const char* str[], int n, int nBeg, bool bMap[26][26])
{
if (str == NULL || n <= 1) // <= 1 not 0
return;
int nPrev = 0;
while (str[nPrev][nBeg] == 0 && nPrev < n) // missing nPrev < n
nPrev++;
int nIter = nPrev + 1;
while (nIter < n)
{
if (str[nPrev][nBeg] != str[nIter][nBeg])
{
assert(str[nPrev][nBeg] >= 'a' && str[nPrev][nBeg] <= 'z');
assert(str[nIter][nBeg] >= 'a' && str[nIter][nBeg] <= 'z');
bMap[str[nPrev][nBeg] - 'a'][str[nIter][nBeg] - 'a'] = true;
buildMap(str + nPrev, nIter - nPrev, nBeg + 1, bMap);
nPrev = nIter;
}
nIter++; //forget ++
}
buildMap(str + nPrev, nIter - nPrev, nBeg + 1, bMap);
}
void printOrder(bool bMap[26][26], int rec[26], bool visit[26], char order[
26], int nIndex)
{
if (nIndex >= 26)
{
for (int i = 0; i < 26; i++)
cout<
cout<
return;
}
for (int i = 0; i < 26; i++)
{
if (visit[i] || rec[i] != 0) continue;
visit[i] = true;
order[nIndex] = 'a' + i;
for (int j = 0; j < 26; j++)
if (bMap[i][j]) rec[j]--;
printOrder(bMap, rec, visit, order, nIndex+1);
for (int j = 0; j < 26; j++)
if (bMap[i][j]) rec[j]++;
visit[i] = false;
}
}
void PrintAllOrder(const char* str[], int n)
{
if (NULL == str || n <= 0)
return;
bool bMap[26][26] = { false };
buildMap(str, n, 0, bMap);
int rec[26] = { 0 };
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
if (bMap[i][j]) rec[j]++;
char order[26];
bool visit[26] = { false };
printOrder(bMap, rec, visit, order, 0);
}
【在 c**s 的大作中提到】
: 例如 给定另外一种语言的字典，信息足够多，还原出那种语言的字母表顺序。
|
c********t
发帖数: 5706 | 6 随手就来，你果然有800题的题库和解法啊
【在 w****x 的大作中提到】
:
: /*
: Given an array list of lots of strings, they are arranged by unknown
: alphabetical
: order, print all possible alphabetical orders (Sort)
: */
: void buildMap(const char* str[], int n, int nBeg, bool bMap[26][26])
: {
: if (str == NULL || n <= 1) // <= 1 not 0
: return;
|
b*****n
发帖数: 143 | 7 试了一下上面的程序，好像不对呀：
int main() {
const char* str[2];
str[0] = "bcdefghijklmnopqrstuvwxyz";
str[1] = "a";
PrintAllOrder(str, 2);
return 0;
}
是不是应该打印出26种顺序？ |
l*****a
发帖数: 14598 | 8 why 26?
【在 w****x 的大作中提到】
:
: /*
: Given an array list of lots of strings, they are arranged by unknown
: alphabetical
: order, print all possible alphabetical orders (Sort)
: */
: void buildMap(const char* str[], int n, int nBeg, bool bMap[26][26])
: {
: if (str == NULL || n <= 1) // <= 1 not 0
: return;
|
b*****n
发帖数: 143 | 9 26个字母只有a的位置不确定，不是26种顺序吗？ |
e********3
发帖数: 229 | |
|
|
w****x
发帖数: 2483 | 11
不是的，你理解的题和我理解的不一样。
我理解的是一个字典，字典里的单词是按某种字母顺序顺序排列的，
然后打出所有可能得字母顺序， 你看看代码
【在 b*****n 的大作中提到】
: 26个字母只有a的位置不确定，不是26种顺序吗？
|
b*****n
发帖数: 143 | |
c********t
发帖数: 5706 | 13 二爷说拓扑排序要用heap,是为什么啊？
【在 w****x 的大作中提到】
: const int M = 6;
: void printTopoSort(bool a[M][M])
: {
: int into[M] = {0};
: for (int i = 0; i < M; i++)
: {
: for (int j = 0; j < M; j++)
: {
: if (a[j][i])
: into[i]++;
|
b*****n
发帖数: 482 | 14 关于while loop里字母不同的情况，为什么recursive call里要nBeg+1呢？譬如
str[0] = "ad"
str[1] = "bc"
nBeg+1后d不就排在c前面了么?
另外str[nIter][nBeg]是不是可能越界，然后assert？
【在 w****x 的大作中提到】
:
: 不是的，你理解的题和我理解的不一样。
: 我理解的是一个字典，字典里的单词是按某种字母顺序顺序排列的，
: 然后打出所有可能得字母顺序， 你看看代码
|
p*****2
发帖数: 21240 | 15
我说错了吧。我去看看。应该是用queue，最短路径用heap。
【在 c********t 的大作中提到】
: 二爷说拓扑排序要用heap,是为什么啊？
|
n****r
发帖数: 120 | 16 大侠能把题目也给出来么？
【在 w****x 的大作中提到】
: const int M = 6;
: void printTopoSort(bool a[M][M])
: {
: int into[M] = {0};
: for (int i = 0; i < M; i++)
: {
: for (int j = 0; j < M; j++)
: {
: if (a[j][i])
: into[i]++;
|
s****0
发帖数: 117 | 17 The canonical application of topological sorting (topological order) is in
scheduling a sequence of jobs or tasks based on their dependencies
http://en.wikipedia.org/wiki/Topological_sorting#Examples
【在 c********t 的大作中提到】
: 总听大家说面试碰到拓扑排序题。谁能给一两道。一般怎么解？
|
