呆萌的可达鸭

用户名：Harrison

访问量：2296

签　名：

等　　级
排　　名	45155
经　　验	294
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	湖北大学
专　　业

　　自我简介：

TA的其他文章

【金明的预算方案】-题解(C语言代码)
浏览：384

你可能喜欢

【能量项链】-题解(C语言代码)

　　作者: 呆萌的可达鸭　　　　发表时间：2019-12-03 20:52:15 浏览：1291　|　评论：0　

原题链接：能量项链

第一次写题解思路，写的可能会很粗糙，请谅解。
看到这道题时，我第一反应的就是用链表来实现。因为解起来时间复杂度和空间复杂度会相对较小。我也想过有没有可能用动态规划或者贪心算法来解，一想到动态规划的空间复杂度就有点...，并且本人对动态规划和贪心的理解还没到位，状态转移方程相对好理解的我才会考虑这样来解，话不多说，回到链表。（我的代码里使用的是不带头节点的链表）
```c
typedef struct
{
	int data1;
	int data2;
	struct Node_t *next;
//	struct Node_t *prev;
}Node_t;
```
我将能量珠的头尾标记数存节点中，并将这些节点链接起来，返回链表的开始节点指针。
```c

Node_t* CreatNode(int num1, int num2)
{
	Node_t *pNode = (Node_t*)malloc(sizeof(Node_t));
	if(!pNode)
	{
		printf("create node failed\n");
		return NULL;
	}
	pNode->data1 = num1;
	pNode->data2 = num2;
	pNode->next = NULL;
	return pNode;
}

Node_t* CreateEnergyNecklace(int *array, int n)
{
	Node_t *pHead, *pRear, *pTmp;
	int idx;
	for(idx = 0; idx < n; idx ++)
	{
		if(idx + 1 >= n)
			pTmp = CreatNode(array[idx], array[0]);
		else
			pTmp = CreatNode(array[idx], array[idx + 1]);
		if(idx == 0)
		{
			pHead = pTmp;
			pRear = pTmp;
		}
		else
		{
			pRear->next = pTmp;
			pRear = pTmp;
		}
	}
//	pRear->next = pHead;
	return pHead;
}
```
然后开始遍历链表，找到第二个数据最小的节点A，然后根据节点A找到某个节点，其第一个数据与节点A的第二个数据相等，该节点位节点B。然后将节点A与节点B聚合，将节点B的第二个数据赋给机欸但A的第二个数据。循环往复，直至只剩下一个一个节点。
```c

while(pHead->next != NULL)
	{
		pMinValNode = FindMin(pHead);
		pDeleteNode = FindNextNode(pMinValNode, pHead);
		eneryLiberate += pMinValNode->data1 * pDeleteNode->data1 * pDeleteNode->data2;
		pMinValNode->data2 = pDeleteNode->data2;
		if(pDeleteNode == pHead)
			pHead = pDeleteNode->next;
		else
			pMinValNode->next = pDeleteNode->next;
		free(pDeleteNode);
	}
```
以下为代码
```c
typedef struct
{
	int data1;
	int data2;
	struct Node_t *next;
//	struct Node_t *prev;
}Node_t;

Node_t* FindMin(Node_t *pHead)
{
	Node_t *pTmp1;
	int min = 0xffffffff>>1;
	for(pTmp1 = pHead; pTmp1 != NULL; pTmp1 = pTmp1->next)
	{
		if(pTmp1->data2 < min)
			min = pTmp1->data2;
	}
	for(pTmp1 = pHead; pTmp1 != NULL; pTmp1 = pTmp1->next)
	{
		if(pTmp1->data2 == min)
			break;
	}
	return pTmp1;
}

Node_t* FindNextNode(Node_t *pNode, Node_t *pHead)
{
	Node_t *pTmp;
	for(pTmp = pHead; pTmp != NULL; pTmp = pTmp->next)
	{
		if(pTmp->data1 == pNode->data2)
			break;
	}
	return pTmp;
}

int main()
{
	int n;
	scanf("%d", &n);
	int idx, eneryLiberate = 0, array[n];
	Node_t *pHead, *pMinValNode, *pDeleteNode;
	for(idx = 0; idx < n; idx ++)
	{
		scanf("%d ", &array[idx]);
	}
	pHead = CreateEnergyNecklace(array, n);
	while(pHead->next != NULL)
	{
		pMinValNode = FindMin(pHead);
		pDeleteNode = FindNextNode(pMinValNode, pHead);
		eneryLiberate += pMinValNode->data1 * pDeleteNode->data1 * pDeleteNode->data2;
		pMinValNode->data2 = pDeleteNode->data2;
		if(pDeleteNode == pHead)
			pHead = pDeleteNode->next;
		else
			pMinValNode->next = pDeleteNode->next;
		free(pDeleteNode);
	}
	printf("%d", eneryLiberate);
}
```
需要说明的是，此代码提交时遇到了网站编译报错，说是段错误，可能和我的编译环境有关，我习惯于linux下gcc编译，测试过没有问题，不知为何编译报错。我也是个C萌新，第一次写自己的思路，有问题的地方欢迎指出

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

呆萌的可达鸭

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩形面积交（Java代码）

C语言训练-立方和不等式（C语言代码）

【能量项链】-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

一元一次方程（C语言代码）

printf基础练习（C语言代码）

JAM计数法（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

老王赛马（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

呆萌的可达鸭

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩形面积交 （Java代码）

C语言训练-立方和不等式 （C语言代码）

【能量项链】-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

一元一次方程 （C语言代码）

printf基础练习 （C语言代码）

JAM计数法 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

老王赛马 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C二级辅导-进制转换（C语言代码）

矩形面积交（Java代码）

C语言训练-立方和不等式（C语言代码）

　　评论区

一元一次方程（C语言代码）

printf基础练习（C语言代码）

JAM计数法（C语言代码）

老王赛马（C++代码）