接上文，HJ41 稱砝碼

---

更新acd代碼，牛客代碼如下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int calculateWeight(int *weight, int weightLen, int *num, int numLen)
{int array[20001] = {0};int hash[300001] = {0};hash[0] = 1;int arrayIndex = 1;for(int i = 1; i <= num[0]; i++){int tempWeight = weight[0]  * i;if(hash[tempWeight] == 0){array[i] = tempWeight;arrayIndex++;}hash[array[i]]++;}for(int i = 1; i < numLen; i++){int tempArrayIndex = arrayIndex;for(int j = 1; j <= num[i]; j++){for(int k = 0; k < tempArrayIndex; k++){int tempWeight = j * weight[i] + array[k];if(tempWeight < 300000 && hash[tempWeight] == 0){hash[tempWeight]++;array[arrayIndex] = tempWeight;arrayIndex++;} }}}return arrayIndex;
}int main() {return 0;int count = 0;char countStr[4] = {'\0'};while (fgets(countStr, 4, stdin) != NULL) { // 注意 while 處理多個 case// 64 位輸出請用 printf("%lld") to // countStr[1] = '\0';count = atoi(&countStr[0]);int weight[count];memset(weight, 0, sizeof(weight));int num[count];memset(num, 0, sizeof(num));char weightStr[200];char numStr[200];int weightIndex = 0;int numIndex = 0;fgets(weightStr, 200, stdin);fgets(numStr, 200, stdin);int len = strlen(weightStr);weightStr[strlen(weightStr) - 1] = '\0';numStr[strlen(numStr) - 1] = '\0';char* p = strtok(weightStr, " ");while(p){weight[weightIndex++] = atoi(p);p = strtok(NULL, " ");}p = strtok(numStr, " ");while(p){num[numIndex++] = atoi(p);p = strtok(NULL, " ");}int resultArrayIndex = calculateWeight(weight, count, num, count);printf("%d", resultArrayIndex);}return 0;
}

三、

3.1 最終aced了

//aced 通過全部用例
//運行時間
//2ms
//占用內存
//1708KB

這次的代碼著實搞了很久，開始是因為不知道怎么樣取端所有的砝碼值，然后看了別人的代碼，自己也嘗試寫出來了。

后面就是因為獲取數據的時候出問題，包括獲取數量值，獲取重量值字符串數組的長度、以及獲取個數值字符串數組的長度。

后面就是因為array數組的長度不夠、以及hash數組長度不夠導致程序一直會有問題。

這次的改進就是開始使用googleTest開始進行單元測試了。其實一開始c語言課程的時候就教過，但是當時沒有意識到用處。后面寫trafficLight測試用例的時候意識到了重要性。這次寫牛客題用了感覺確實有用。

下面是對于空間復雜度的計算

顯示計算了牛客編譯器int型數組的字節數，printf(“%d”, sizeof(int));打印值是4。

// int array[20001] = {0};
// int hash[300001] = {0};total = 20000 * 4 + 300000 * 4 = 1,280,000Byte = 1280KB
// 和1708KB有區別，但是接近可參考

四、后續

還要看下別人是怎么實現的

這個算法是：后面每個重量都是weight[i] * num[i] + 前面已稱出的砝碼。所以保留第一種所有砝碼的重量，然后將后面算出的砝碼都和后面的相加。

看評論好像還有路徑規劃的算法。

另外就是比較和c++解題的差別。c++的會更好處理數組嗎？不會出現數組長度分配不夠大但是有擔心過度分配的問題？

2024年7月8日19:33:48

今天看了下解題思路，然后其實一開始我還糾結于想看下官方解題的，覺得里面應該有關于路徑規劃的視頻。搞了一段時間發現沒有辦法找到會員，除非淘寶買會員。最后只能硬看別人的代碼，發現其實好像也不難。

下面先回答上面的幾個問題。

首先就是如果使用c原因其實也不用那么麻煩。

第一個就是我用fgets獲取每一行字符串然后再解析的，看別人的代碼，使用scanf就可以了。

第二個就是我處理起來很棘手的問題，就是關于hash數組開辟多大的值。我從一開始的1000，最后到10萬都不夠，真尷尬，實際看別人的代碼處理的方法就很簡單。就是將所有砝碼的值加起來得到一個最大值。用這個值作為數組的長度。另外就是關于存在唯一的砝碼重量的array的長度，其實應該也是用砝碼總重量來開辟。但是其實被人根本就沒有處理，只是用了一個計數器來計數，是可以這樣處理的，因為不需要記錄這些唯一的砝碼的重量。

需要用新的方法重新處理一下代碼。

更新代碼如下：

#define HJ41_2024年7月8日20#ifdef HJ41_2024年7月8日20
#include <string.h>int calculateWeight(int *weight, int weightLen, int *num, int numLen)
{int totalNum = 0;for(int i = 0; i < numLen; i++){for(int j = 1; j <= num[i]; j++){totalNum += j * weight[i];}}int array[totalNum];int hash[totalNum];memset(array, 0, sizeof(array));memset(hash, 0, sizeof(hash));hash[0] = 1;int arrayIndex = 1;for(int i = 1; i <= num[0]; i++){int tempWeight = weight[0]  * i;if(hash[tempWeight] == 0){array[i] = tempWeight;arrayIndex++;}hash[array[i]]++;}for(int i = 1; i < numLen; i++){int tempArrayIndex = arrayIndex;for(int j = 1; j <= num[i]; j++){for(int k = 0; k < tempArrayIndex; k++){int tempWeight = j * weight[i] + array[k];if(tempWeight < totalNum && hash[tempWeight] == 0){hash[tempWeight]++;array[arrayIndex] = tempWeight;arrayIndex++;}}}}return arrayIndex;
}#ifdef HJ41_2024年7月2日20_WITH_MAIN
int main() {int count = 0;char countStr[4] = {'\0'};while (scanf("%d",&count) != EOF) { // 注意 while 處理多個 caseint weight[count];memset(weight, 0, sizeof(weight));for(int i = 0; i <count; i++){scanf("%d", &weight[i]);}int num[count];memset(num, 0, sizeof(num));for(int i = 0; i < count; i++){scanf("%d", &num[i]);}int resultArrayIndex = calculateWeight(weight, count, num, count);printf("%d", resultArrayIndex);}return 0;
}#endif#endif

上述代碼很好的解決了輸入數據獲取的問題。同時也很簡單的解決了hash數組和array數組的問題。下面是時間空間復雜度，怎么感覺比之前的還多呢，無語。先不管這個。

通過全部用例

運行時間9ms

占用內存8832KB

2024年7月8日20:45:40

增加對上述代碼的修改

其實上述代碼在Clion上運行的時候是有報錯的，但是我沒有看出來。

[ RUN      ] googleMyTest.HJ41_7
SetUp
TearDown
[       OK ] googleMyTest.HJ41_7 (1 ms)
[ RUN      ] googleMyTest.HJ41_8
SetUp進程已結束，退出代碼為 -1073741571 (0xC00000FD)

其實HJ41_8示例沒有跑完，調試代碼發現在申請array[totalNum]的時候程序進入hardFault。感覺可能棧溢出了。然后使用堆內存申請資源。

改成

int* array = (int*)malloc(sizeof(int) * totalNum);
int* hash = (int*)malloc(sizeof(int) * totalNum);
memset(array, 0, sizeof(int) * totalNum);
memset(hash, 0, sizeof(int) * totalNum);

示例正常跑完。

現在我的疑慮是為什么直接寫成int array[20001] = {0};不會報錯呢？

然后我再看了下值，當第8個示例時，算出來的totalNum值為1097525，遠大于之前寫的2w，所以會溢出。使用堆內存申請避免溢出，這也解釋了為什么第二版代碼的占用內存為8832KB。因為確實占用的資源很多。

然后看了別人的代碼，是這樣得到重量最大值的。然后對于示例八，totalNum的值是199550。確實小了不少。

for(int i = 0; i < numLen; i++)
{totalNum += (weight[i] * num[i]);
}

哎，我覺得還是做的題目太少，才手忙腳亂沒處理好。

五、總結

上述是集合處理方法，還有路徑規范的沒有實現。