給定一個描述超矩陣的字串，例如
"[[[1,2],[4,5],[6,7]]" which is a 3,2 matrix
或者
"[[1,2,3],[4,5,6]]" which is a 2,3 matrix
或者
"[ [[1,2],[3,4],[4,6]], [[7,8],[9,10],[11,12]] ]" which is a 2,3,2 matrix
等等
有沒有一種很好的方法來找到矩陣的維度？例如，我正在使用一種演算法，該演算法將為第三個矩陣報告 2,3,2。我可以保證每個維度都有不變的元素，即沒有丟失的數字。可以假設字串可以被標記為整數、逗號和左右方括號。我對人們可能使用的方法更感興趣，我認為它很可能是遞回的。我玩過建造一棵樹的想法，但我不確定這最終會有所幫助。顯然，我可以使用 numpy 和查看形狀很容易地用 python 做到這一點，但我正在尋找可能的演算法的建議。
uj5u.com熱心網友回復：
這是一個 C 版本：
void printMatrixDimensions(const char *inString) {
int depth = 0;
int dimensions = 0;
int *counts = NULL;
for (const char *inString_ptr = inString; inString_ptr[0] != '\0'; inString_ptr ) {
char c = inString_ptr[0];
char upOrDown = 0;
if (c==' ' || c=='\t' || c=='\r' || c=='\n') continue; // skip whitespace
if (c == '[') { upOrDown = 1; } // determine if we're going down in depth
else if (c == ']') { upOrDown = -1; } // or coming up
depth = upOrDown;
if (upOrDown == 1) { // if we're going deeper,
if (depth > dimensions) { // expand our depths stack if needed
dimensions = depth;
counts = realloc(counts, sizeof(int) * dimensions);
}
counts[depth - 1] = 0; // initialize the new depth with a count of 0
}
if (!(c=='[' || c==']')) { // if a character other than []
if (c==',') { // if a comma, then we have at least 2 members
if (counts[depth - 1] == 0) counts[depth - 1] = 2;
else counts[depth - 1] = 1;
} else { // if a non-comma char is there, that counts for a member
if (counts[depth - 1] == 0) counts[depth - 1] = 1;
}
}
}
printf("Matrix dimensions:\n");
for (int i = 0; i < dimensions; i ) {
printf("%i ", counts[i]);
}
printf("\n");
if (counts != NULL) free(counts);
}
uj5u.com熱心網友回復：
- 遍歷字串并維護一個名為 depth 的變數，初始化為 0，在每個 '[' 處增加 1，在每個 ']' 處減少 1。
- 在遍歷字串時，計算每個深度的逗號數。保留一個計數器串列或字典，以便每個深度都有一個計數器。
- 每當變數深度首次再次小于該深度時，停止計算給定深度處的逗號。
def get_dims(mat):
depth = 0
capped_depth = len(mat)
dims = {}
for c in mat:
if c == '[':
depth = 1
elif c == ']':
if depth <= capped_depth:
dims[depth] = dims.get(depth, 0) 1
depth -= 1
capped_depth = min(depth, capped_depth)
elif c == ',' and depth <= capped_depth:
dims[depth] = dims.get(depth, 0) 1
return [v for k,v in sorted(dims.items())]
get_dims("[ [[1,2],[3,4],[4,6]], [[7,8],[9,10],[11,12]] ]")
# [2, 3, 2]
get_dims("[[1,2,3],[4,5,6]]")
# [2, 3]
get_dims("[[1,2],[4,5],[6,7]]")
# [3, 2]
get_dims('[[[]]]')
# [1, 1, 1]
get_dims('[[[,]]]')
# [1, 1, 2]
請注意，此代碼假定該字串描述了一個格式良好的矩陣。但是您可以輕松修改代碼以驗證字串格式是否正確。
- 括號正確嵌套當且僅當
depth在 for 回圈期間始終為正，并且在 for 回圈之后恰好為 0。 - 我寫的代碼使用每個深度的第一個串列的長度來計算相應的維度。如果每個給定深度的所有串列都具有相同的長度，則矩陣將是良構的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313545.html
上一篇：我在解決這個動態規劃問題的方法中缺少什么？（Leetcode740.洗掉并賺取）
下一篇：如何在3D圖形上找到連接點？