计算机保研夏令营1
一、题目一
题目描述
为创建一个能够从指定链表中删除特定节点（非末尾位置）的功能而编写该函数。该函数将接受一个单一参数作为操作对象。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
cpp说明：给定链表中值为5的第二个节点，在执行了你的函数后，该链表应变为4 -> 1 -> 9。
解题思路
说明：长度只能设置为全局变量时，默认情况下不会被显式转换为指针。当函数参数传递时（尤其是传递数组），该隐式转换会发生。因此，在使用sizeof(list)获取对象大小时会存在问题——它将返回指针所占内存空间而非实际数组长度，在函数内部计算实际数组长度会导致错误的结果。
函数外：sizeof(list) = 16,sizeof(int)=4
函数内：sizeof(list) = 8,sizeof(int)=4
其中，在32位 系统中，指针大小为4个字节 ；在64位系统 中，指针的大小为8个字节 。
代码实现
#include<stdio.h>
#include<stdlib.h>
#define N 20
#define Create(p) (Node *)malloc(sizeof(Node))
#define Delete(p) free(p)
typedef struct Node {
int number;
struct Node* next;
}Node;
int length;
void DeleteNode(int list[],int node)
{
int i;
Node* p, *q, *head;
head = Create(head);
head->number = list[0];
head->next = NULL;
p = Create(p);
p = head;
for (i = 1; i < length; i++)
{
if (list[i] == node)
{
continue;
}
q = Create(q);
q->number = list[i];
q->next = NULL;
p->next = q;
p = q;
}
p = head;
printf("[");
while (p != NULL)
{
if (p->next == NULL)
{
printf("%d", p->number);
p = p->next;
}
else {
printf("%d,", p->number);
p = p->next;
}
}
printf("]");
}
int main(void)
{
int list[] = { 4, 5, 1, 9 };
length = sizeof(list) / sizeof(int);
DeleteNode(list,5);
return 0;
}
cpp
二、题目二
题目描述
对于任意正整数n，在1²、2²、3²、4²等完全平方数组中挑选若干项使其总和为n，并使该组中包含的完全平方数量达到最小值
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数是一个整数n²的形式；其中n属于整数集合\mathbb{Z}也可以理解为这是一个整數自乘的结果。举个例子来说当n=1时得到的是1；当n=2时结果就是4依此类推这些都是典型的完全平方數；但与此相比出现在列表中的數像3或11則不符合完備平方數的定義。
示例 1：
输入：n = 12
输出：3
cpp解释：12 = 4 + 4 + 4
提示：
1 <= n <= 104
解题思路
注 ：求解最大/最小问题采用动态规划 （一维）
（1）状态定义：在动态规划问题中，DP[i]被定义为能够组成数字i所需的最小数量平方项（便于后续计算分析）。
（2）初始化操作：边界条件满足dp[0]=0时，在寻求目标函数的最小化问题中，则需将变量dp[1]至dp[n]全部赋初最大数值（与此相反，在寻求目标函数的最大化问题时，则需将这些变量赋初最小数值）。
（3）状态计算 ：可以组成数字i的完全平方数一定满足j*j <=i，因此内层循环j从1开始，遍历到jj>i为止。当**jj=i** 时，i的完全平方数的最少个数就是1 。其余j <i的情况下，采用倒推 的方法，将i减去j*j之后剩余值的完全平方数加一得到一种i的完全平方数组成 ，再和此时i的完全平方数的个数进行比较，取较小值 。状态计算公式如下所示：
由于采用了dp[i-j*j]这一表达式，在算法设计中我们选择按照从低到高的顺序进行递推。具体而言，外层循环的作用是计算从0到n-1的所有数字所需的最小完全平方组合数量；而内层循环则负责确定每个特定数字i所需的最小完全平方数。
#include <stdio.h>
#include <limits.h>
#include <math.h>
#define N 110
int numSquares(int n) {
int dp[N];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = INT_MAX; //如果求最大值则初始化为最小值
for (int j = 1; j * j <= i; j++) {
dp[i] = fmin(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
int main() {
int n;
scanf_s("%d", &n);
int result = numSquares(n);
printf("%d", result);
return 0;
}
cpp
三、题目三
题目描述
该段描述了n个气球的情况：共有n只气球（记作n个），它们依次从索引0开始一直到索引n-1；每个气球都标注了一个数字；这些标有的数字被存储于数组nums中。
现在要求你需要戳破所有位于区间[0, n-1]内的气球。击破第i号气球时可以获得数值为nums[i-1]、nums[i]和nums[i+1]三个数的乘积的数量的硬币（其中当索引越界时，默认对应的虚拟位置数值为1）。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
cpp解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3 1 5 + 3 5 8 + 1 3 8 + 1 8 1 = 167
解题思路
注：求解最大/最小值使用动态规划（二维）
在此处获得的硬币数量与戳破该区间的气球具有直接关联性，在动态规划算法中采用二维dp数组来进行状态描述：其中dp(i,j)代表整个区间[i, j]内所有气球被戳破后所积累的最大硬币数量（衡量标准）。
在该步骤需要用添加了边界条件的新数组来代替原来的数组
①数组边缘情况（超出数组边界，即视为是一个数字为1的气球）
newNums[0] = 1;
newNums[n + 1] = 1;
cpp②其余数字赋值
for (int i = 0; i < n; i++)
{
newNums[i + 1] = nums[i];
}
cpp（3）状态计算：若区间的长度等于1，则将此区间击破可获得的数量等于nums[i]个气球；由于左右两端均被视为超出范围，则无需单独处理此情形。因此，在本算法中将最外层循环决定区间的最小可行起始点，并从区间的最小可行长度设定于2开始逐步扩展至n+1；其中次内层循环固定区间的左端点位置，并根据当前遍历步长与起始点计算出右端点的位置即可完成整个状态计算过程
j = i + length;
cpp在得到一个区间之后，区间内部还可以进行划分，可以划分为[i,k]以及[k,j]，通过k值的不同，戳破对应区间得到的气球数也不相同，因此最内层循环控制区间内部的区间划分，最后得到的状态计算式如下所示：
为了获取数组长度，在C语言中必须将其计算过程置于函数外部。这是因为当数组作为函数参数传递时会隐式地被转换为指向器类型（pointer），从而导致计算过程中出现问题。
#include <stdio.h>
#define N 110
int max(int a, int b) {
return a > b ? a : b;
}
int maxCoins(int* nums, int numsSize) {
int n = numsSize;
int newNums[N];
newNums[0] = 1;
newNums[n + 1] = 1;//处理nums数组边缘情况
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
int dp[N][N];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
dp[i][j] = 0;//可以初始化为0，也可以初始化为最小值
}
}
for (int length = 2; length < n + 2; length++) {
for (int i = 0; i < n + 2 - length; i++) {
int j = i + length;
for (int k = i + 1; k < j; k++) {
//以K作为分割点，分别表示戳破区间[i,k]的最大硬币数和戳破区间[k,j]的最大硬币数，以及戳破第k个气球得到的硬币数。
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + newNums[i] * newNums[k] * newNums[j]);
}
}
}
return dp[0][n + 1];
}
int main() {
int nums[] = { 3, 1, 5, 8 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = maxCoins(nums, numsSize);
printf("%d", result);
return 0;
}
cpp
