HJ41 称砝码

HJ41 称砝码

提示：文章

文章目录

• 前言
• 一、背景
• 二、
  • 2.1
  • 2.2
• 总结

前言

前期疑问：
本文目标：

---

一、背景

这个题目之前是没有做出来的，我把之前没做出来的代码也记录一下

二、

2.1 之前的代码

#include <stdio.h>int main() {int a, b;int num = 0;int array[20000] = {0};while (scanf("%d", &num) != EOF) { // 注意 while 处理多个 case// 64 位输出请用 printf("%lld") to int key[num];int value[num];int count = 0;for(int i = 0; i < num; i++){scanf("%d", &key[i]);}for(int i = 0; i < num; i++){scanf("%d", &value[i]);}for(int i = 0; i < num; i++){while(value[i]){int heigh = key[i] * value[i];array[heigh] = 1;value[i]--;}}for(int i = 0; i < 20000; i++){if(array[i] > 0){count++;}}printf("%d\n", count + 1);printf("%d ", 0);for(int i = 0; i < 20000; i++){if(array[i] > 0){printf("%d ", i);}}}return 0;
}

示例是没有通过的

自测输入	2 1 2 2 1
预期输出	5
实际输出	3 0 1 2

2.2 今天编的代码

2024年6月20日12:28:44

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int compare(const void* a, const void* b)
{return (int*)a - (int*)b;
}int main() {int count = 0;char countStr[3] = {'\0'};while (fgets(countStr, 3, 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[21];char numStr[21];int weightIndex = 0;int numIndex = 0;fgets(weightStr, 21, stdin);fgets(numStr, 21, 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, " ");}for(int i = 0; i < count; i++){//printf("weight:%d, num:%d\n", weight[i], num[i]);}int length = pow(count, 2);int resultArray[length + 3];memset(resultArray, 0, sizeof(int) * (length + 3));//int resultArrayIndex = 1;           //把0算作一个重量,把单独的重量也算上int resultArrayIndex = 0;           //把0算作一个重量,把单独的重量也算上for(int i = 0; i < count; i++){for(int j = 0; j < num[i]; j++){resultArray[resultArrayIndex++] = weight[i] * j; }}for(int i = 0; i < count; i++){for(int j = 0; j < count; j++){resultArray[resultArrayIndex++] = weight[i] + num[j];}}int tempArray[20001] = {0};for(int i = 0; i < resultArrayIndex; i++){tempArray[resultArray[i]]++;}int resultArrayCopy[length + 3];int resultArrayCopyIndex = 0;for(int i = 0; i < 20001; i++){if(tempArray[i] != 0){// printf("index:%d, %d\n", i, tempArray[i]);resultArrayCopy[resultArrayCopyIndex++] = i;}}printf("%d", resultArrayCopyIndex);}return 0;
}

示例有误

用例输入	2 74 185 3 1
预期输出	8
实际输出	7

2.3 2024年7月5日10:55:33编写代码

2024年7月5日10:55:33

现在的问题就是卡在测试用例18/20，问题是：

请检查是否存在数组、列表等越界非法访问，内存非法访问等情况。

这个问题待解决。

这次我调试代码的时候将测试用例用googleTest创建了单元测试，下面是CLion上的测试用例代码：

Clion调试代码如下

#include "HJ41.h"//#define TEST_DEBUG
#define TEST_DEBUG_ARRAY_PRINTint 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++;}}}}#ifdef TEST_DEBUG_ARRAY_PRINTfor(int i = 0; i < arrayIndex; i++){printf("array[%d]:%d ", i, array[i]);}#endifreturn arrayIndex;
}int calculateWeight2(int *weight, int weightLen, int *num, int numLen)
{int array[2000] = {0};int hash[2000] = {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 < 2000 && hash[tempWeight] == 0){hash[tempWeight]++;array[arrayIndex] = tempWeight;arrayIndex++;}
#ifdef TEST_DEBUGstd::cout << "j:    " << j << std::endl;std::cout << "tempWeight:    " << tempWeight << std::endl;
#endif}}}
#ifdef TEST_DEBUG_ARRAY_PRINTfor(int i = 0; i < arrayIndex; i++){std::cout << "array[" << i << "]" << array[i] << " ";}
#endifreturn arrayIndex;
}

写的测试用例如下

#include <gtest/gtest.h>  // googletest header file
#include <iostream>
#include "HJ41.h"class googleMyTest : public testing::Test
{
public:static void SetUpTestCase(){std::cout << "SetUpTestCase" << std::endl;}static void TearDownTestCase(){std::cout << "TearDownTestCase" << std::endl;}virtual void SetUp(){std::cout << "SetUp" << std::endl;}virtual void TearDown(){std::cout << "TearDown" << std::endl;}
};TEST_F(googleMyTest, my_test_f_1)
{int x = 1;EXPECT_EQ(x, 1);
}TEST_F(googleMyTest, HJ41_1)
{int count = 2;int weight[2] = {1, 2};int num[2] = {2, 1};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 5);
}TEST_F(googleMyTest, HJ41_2)
{int count = 2;int weight[2] = {74, 185};int num[2] = {3, 1};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 8);
}TEST_F(googleMyTest, HJ41_3)
{int count = 3;int weight[] = {108, 29, 185};int num[] = {5, 2, 1};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 36);
}/** 这一版之前一直过不了是因为少了这个语句* hash[tempWeight]++;*/
TEST_F(googleMyTest, HJ41_4)
{int count = 3;int weight[] = {10, 191, 103};int num[] = {6, 6, 5};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 254);
}/** 报错段错误*/
//7
//172 162 18 153 199 41 28
//1 1 3 5 1 4 1
TEST_F(googleMyTest, HJ41_5)
{int count = 7;int weight[] = {172, 162, 18, 153, 199, 41, 28};int num[] = {1, 1, 3, 5, 1, 4, 1};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 969);
}
/** 原因有两个，段错误是因为hash数组没有做保护，被识别出来了* 另一个是输入字符串长度不够        应该将21改成100，保证fgets(weightStr, 100, stdin);能够获取足够长度的字符串*//** 这个是因为weight值会大于2000，使用2000判断肯定出问题啊*/
//7
//58 18 139 163 57 167 178
//1 1 3 2 6 3 4
//1711
TEST_F(googleMyTest, HJ41_6)
{int count = 7;int weight[] = {58, 18, 139, 163, 57, 167, 178};int num[] = {1, 1, 3, 2, 6, 3, 4};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 1171);
}/** 这个问题更明显了，数量都达到2000+了，那肯定是array数组长度不够了*/
//10
//68 136 51 137 57 23 166 45 141 58
//3 4 6 6 4 6 2 2 1 3
TEST_F(googleMyTest, HJ41_7)
{int count = 10;int weight[] = {68, 136, 51, 137, 57, 23, 166, 45, 141, 58};int num[] = {3, 4, 6, 6, 4, 6, 2, 2, 1, 3};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 2738);
}
//但是数组array长度改成10000，还是报错：请检查是否存在数组、列表等越界非法访问，内存非法访问等情况
//cao,这个示例在clion上执行不会失败，网页又是失败，我还以为是数组越界，最后突然想到是不是因为fgets获取长度不够，一看果然是这样
//但是在牛客商还是有问题，定位出来是count获取也有问题，应该是10，获取到的是1, 把语句改成fgets(countStr, 4, stdin)//10
//2000 1999 1998 1997 1996 1995 1994 1993 1992 1991
//10 10 10 10 10 10 10 10 10 10
TEST_F(googleMyTest, HJ41_8)
{int count = 10;int weight[] = {2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991};int num[] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10};int totalCount = calculateWeight(weight, count, num, count);EXPECT_EQ(totalCount, 16601);
}
//最大值为array[16600]:199550。开启的数组长度不够
//改成int array[20001] = {0};
//    int hash[300001] = {0};//aced 通过全部用例
//运行时间
//2ms
//占用内存
//1708KB

工程cmakelist

cmake_minimum_required(VERSION 3.16.5)message("this is cmakelist log")
message(${CMAKE_CURRENT_SOURCE_DIR})get_filename_component(ProjectId ${CMAKE_CURRENT_SOURCE_DIR} NAME)
message(${ProjectId})
#set(ProjectId "Hello World!")
message(${ProjectId})
message(NAME)
string(REPLACE " " "_" ProjectId ${ProjectId})
message(${ProjectId})
project(${ProjectId} CXX)add_definitions(-DCHENGFAMA)
add_definitions(-DSTART_GOOGLETEST_MODULE)# 判断宏是否存在
if(DEFINED HELLOWORLD)message(STATUS "HELLOWORLD已定义")
else()message(STATUS "HELLOWORLD未定义")
endif()#添加宏定义Debug为CMAKE_BUILD_TYPE
SET(CMAKE_BUILD_TYPE "Debug")set(CMAKE_CXX_STANDARD 17)if (CMAKE_BUILD_TYPE STREQUAL Debug)set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g -D_DEBUG")
else ()set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -g -D_DEBUG")
endif ()# 添加googletest库
add_subdirectory(googletest)#添加头文件
#例如：include_directories(/usr/include/abc /usr/include/xxx)
#是将“/usr/include/abc”和“/usr/include/xxx”这两个目录添加至编译器的头文件搜索目录(两个目录用空格分隔)。
include_directories(./include/)
include_directories(./HJ41)aux_source_directory(./src Src)
aux_source_directory(./gtest gtestSrc)
aux_source_directory(./HJ41 HJ41Src)#通过编译源文件来创建一个可执行文件，其中，name是生成的可执行文件的名称，source是创建可执行文件所需要的源文件。
#源文件可以使用aux_source_directory指令返回的变量（将源文件保存在这个变量中）,也可以是指定的.cpp文件（注意路径）。
add_executable(${ProjectId}${Src}${gtestSrc}${HJ41Src}arraySort.cppmain.cpp)# 链接googletest库
target_link_libraries(${ProjectId} gtest_main)

我现在在想的是吗，如果使用STL就不会出现这个问题吗？

如果将array数组改成vector好像可以解决溢出的问题。

将hash改成，hash改不了吧？除非C++有封装好的hash。

这里突然意识到应该将araay数组改成set才对。

---

总结

未完待续