单链表

1. 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]

#include<iostream>

using namespace std;

const int N = 100010;

int e[N], ne[N], idx, head;
// e[idx]数组存储值
// ne[idx]数组存储链表下一个结点的地址
// head是头指针(指向第一个节点地址的指针)
// idx是计数指针,存储结点地址

void init()
{
        head = -1; // 开始时指向空
        idx = 1; // 计数指针，第一个地址
}

void add_to_head( int x )
{
        e[idx] = x;  
        ne[idx] = head;
        head = idx++;  // 当前头指针指向新插入的结点
}

void remove( int k )
{
        ne[k] = ne[ ne[k] ];
}

int main()
{
        int m;
        cin>>m;
        init();

        while( m-- )
        {
            int x;
            cin>>x;
            add_to_head(x);
        }

        int val;
        cin>>val;

        for( int i=head; i!=-1; i=ne[i] )
        {
            if( e[ne[i]] == val ) remove(i);
        }

        for( int i=head; i!=-1; i=ne[i] ) cout<<e[i]<<' ';
        return 0;
}

动态规划

1.给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
提示：

1 <= n <= 104

#include<iostream>

using namespace std;

// dp[i] 表示组成和为 i 的完全平方数的最小数量。
int main()
{
    int n;
    cin>>n;
    int dp[120];
    for(int i = 1;i<=120;i++) dp[i] = 120;
    dp[0] = 0;
    for( int i = 1;i<=n;i++ )
    {
        for( int j = 1;j<=10;j++ )
        {
            if( j*j <= i ) dp[i] = min( dp[i], dp[i-j*j]+1 );
        }
    }
    cout<<dp[n];
    return 0;
}

爆搜（超时）

#include<iostream>

using namespace std;
int a[15];
int ans = 0;
int sum  = 0;
int last = 120;
int x;

void dfs() 
{
    if( sum > x )
    {
        return;
    }
    if( sum == x )
    {
        last = min(ans,last);
        return;
    }

    for( int i = 10;i>=1;i-- )
    {
        sum+=a[i];
        ans++;
        dfs();
        sum-=a[i];
        ans--;
    }
}

int main()
{
        cin>>x;
        for( int i=1;i<11;i++) a[i] = i*i;

        dfs();

        cout<<last;
        return 0;
}