由于作業要求純C，故用C刷題
如題http://https://leetcode-cn.com/problems/triangle/
官方題解
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
int f[triangleSize][triangleSize];
memset(f, 0, sizeof(f));
f[0][0] = triangle[0][0];
for (int i = 1; i < triangleSize; ++i) {
f[i][0] = f[i - 1][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
f[i][j] = fmin(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
}
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
int ret = f[triangleSize - 1][0];
for (int i = 1; i < triangleSize; i++)
ret = fmin(ret, f[triangleSize - 1][i]);
return ret;
}
問題如下：
1.題解使用的c語言是標準c嗎？為什么能用變數初始化陣列長度
2.triangle是二維指標，是怎么能夠進行triangle[i][j]操作？vs是不能運行的，原因在于編譯器不知道*triangle的陣列長度有多大，沒辦法找到triangle[i][j]，而如下操作是可以的，創建了一個一維指標陣列，每一個一維指標都指向一塊獨立的記憶體空間
int** cache = (int**)malloc(sizeof(int*) * triangleSize);
for (int i = 0; i < triangleSize; i++)
{
cache[i] = (int*)malloc(sizeof(int) * triangleColSize[i]);
}
3.針對問題2中的問題，類似于本題的情況，如何才能優雅的實作對一個多維陣列使用陣列下標來操作。
附上我的代碼
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize)
{
int** cache = (int**)malloc(sizeof(int*) * triangleSize);
int** triangle_p = (int**)malloc(sizeof(int*) * triangleSize);
int res = 99999999999;
if (1 == triangleSize)
return triangle[0][0];
else if (!triangleSize)
return -1;
for (int i = 0; i < triangleSize; i++)
{
cache[i] = (int*)malloc(sizeof(int) * triangleColSize[i]);
memset(cache[i], 0, sizeof(int) * triangleColSize[i]);
}
cache[0][0] = triangle_p[0][0]; //此處運行崩潰
for (int i = 1; i < triangleSize; i++)
{
for (int j = 0; j < triangleColSize[i]; j++)
{
if (0 == j)
{
cache[i][0] = cache[i - 1][0] + triangle_p[i][0];
}
else
{
cache[i][j] = MIN(cache[i - 1][j], cache[i - 1][j - 1]) + triangle_p[i][j];
}
}
}
for (int i = 0; i < triangleColSize[triangleSize - 1]; i++)
{
res = MIN(res, cache[triangleSize - 1][i]);
}
return res;
}
uj5u.com熱心網友回復：
1、這個是符合C99標準的語法，用變數初始化陣列長度且是區域作用域的陣列稱為變長陣列
2、triangle是二維指標，是怎么能夠進行triangle[i][j]操作？這個是二維陣列的基本操作，triangle[i]是一維指標，triangle[i][j]就是元素了
3、明顯你只對cache的二維分配了空間，沒有對triangle_p的二維分配空間就訪問當然出錯
uj5u.com熱心網友回復：
C99支持動態陣列Vs出錯是因為他對c99標準不完全支持
uj5u.com熱心網友回復：
LS都說了，補充一下2 【triangle是二維指標，是怎么能夠進行triangle[i][j]操作？vs是不能運行的，原因在于編譯器不知道*triangle的陣列長度有多大，沒辦法找到triangle[i][j]】，如果是這樣，你的代碼
if (1 == triangleSize)
return triangle[0][0]; //為什么就可以操作？i=0,j=0
所以問題不在于編譯器知不知道長度有多少，這個長度是你自己保證的，如果長度沒能保證，編譯器只會陣列越界進行非法操作。所以這些引數的指標的有效性以及陣列長度是你自己去保證的，因為編譯器不知道運行時就傳入什么引數，所以只要你語法對，就可以編譯。
3 你的cache[I]都知道malloc分配記憶體，為何就沒有想到triangle_p[i]沒分配記憶體？所以triangle_p[0][0];是非法的。
uj5u.com熱心網友回復：
不好意思貼錯代碼了 上面的是我除錯的代碼，實際沒有triangle_p這個指標
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize)
{
int** cache = (int**)malloc(sizeof(int*) * triangleSize);
int res = 99999999999;
if (1 == triangleSize)
return triangle[0][0];
else if (!triangleSize)
return -1;
for (int i = 0; i < triangleSize; i++)
{
cache[i] = (int*)malloc(sizeof(int) * triangleColSize[i]);
memset(cache[i], 0, sizeof(int) * triangleColSize[i]);
}
cache[0][0] = triangle[0][0]; //此處運行崩潰
for (int i = 1; i < triangleSize; i++)
{
for (int j = 0; j < triangleColSize[i]; j++)
{
if (0 == j)
{
cache[i][0] = cache[i - 1][0] + triangle_p[i][0];
}
else
{
cache[i][j] = MIN(cache[i - 1][j], cache[i - 1][j - 1]) + triangle_p[i][j];
}
}
}
for (int i = 0; i < triangleColSize[triangleSize - 1]; i++)
{
res = MIN(res, cache[triangleSize - 1][i]);
}
return res;
}
uj5u.com熱心網友回復：
不好意思貼錯代碼了
我之所以會說編譯器不知道多少是因為如下例子：
int a[2][2] = { {0,1}, {2,3} };
int **b = a;
printf("%d\n", b[1][0]);
這樣子運行的時候會崩潰，因為編譯器不知道b[0]-b[1]間具體有多大的記憶體空間，所以必須顯式的指定指標的寬度所以得寫成以下這樣才能正確運行
int a[2][2] = { {0,1}, {2,3} };
int (*b)[2] = a;
printf("%d\n", b[1][0]);
那么問題來了 我的這個題目傳入的引數陣列的寬度不是定值，也就是說指定指標寬度得是個變值，而vs里又要求指標寬度不能是變數，這就很矛盾了，例如下面這樣編譯就會報錯
int c = 2;
int (*b)[c] = a;
uj5u.com熱心網友回復：
if (1 == triangleSize)return triangle[0][0]; //為什么就可以操作？i=0,j=0
這句話沒報錯是因為用例沒運行到
uj5u.com熱心網友回復：
這個崩潰和你說的內容毫無關系
假設 int* 和 int 都是 4個位元組 假設 陣列a地址是1000
b[1] 就是 *(b+1)
b是1000
b+1是1004
1004是 a[0][1]的地址
b[1][0] 相當于 *(int*)a[0][1]
把a[0][1]這個int內容當成地址 并解參考
導致崩潰
uj5u.com熱心網友回復：
陣列不是指標你用二級指標指向二維陣列是錯誤的行為
屬于對指標和陣列理解錯誤
uj5u.com熱心網友回復：
所以oj在呼叫我的函式進行傳參的時候傳入的是一個指標陣列，而不是直接將一個二維陣列傳入嘍
這樣看起來就說的過去了
uj5u.com熱心網友回復：
你沒明白我的意思。我上面也說了，編譯器不管長度，你不保證長度它就越界非法訪問記憶體，所以這個引數傳入是你自己保證的。
人家的題目又沒有說main函式會給minimumTotal函式傳入一個等長的二維陣列（為了回答還去看了一下題目，下次直接貼題目不要鏈接），你怎么就自以為人家傳入函式的引數是等長二維陣列呢？
比如
void printDoublePointer(int **p, int row, int *col) { //誰規定這里的p是等長的二維陣列？p本身就是個不等長陣列，1維長度row控制，2維長度col控制，很正常
int i, j;
for(i=0; i<row; i++) {
for (j=0; j<col[i]; j++) {
printf("%d ", p[i][j]); //這里的I，j是靠你保證的，你傳入的引數不對，自然就會造成非法訪問
}
printf("\n");
}
}
int main() {
int n=5, i, j;
int **p = (int**)malloc(sizeof(int*)*n);
int *col = (int*)malloc(sizeof(int)*n);
for (i=0; i<n; i++) {
col[i] = i+1;
p[i] = (int*)malloc(sizeof(int)*col[i]);
for (j=0; j<col[i]; j++) {
p[i][j] = j+1;
}
}
printDoublePointer(p, n, col); //人家main函式這樣傳引數不行嗎？誰規定一定用等長二維陣列
free(col);
for (i=0; i<n; i++) {
free(p[i]);
}
free(p);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162096.html
標籤：C語言
上一篇：status未定義識別符號