这个难度应该是呈递增阶级的,有兴趣的看看可以弄几题~

一  

从一个N个元素的递增数组里面判断有没有差值为K的两个数。

输入:
第一行输入数组元素个数N(1<=N<=1e6)和目标差值K(1e-9<=1e9)
第二行递增输入N个元素Ni(1e-9<=Ni<=1e9,注意:数据初始化的时候已是递增输入)

输出:
有就输出Yes没有就输出No

示例:

Input
5 4
1 3 6 8 9

Output
No

Input
6 9
1 5 7 9 11 14

Output
Yes


二

从一个只含有'0'和'1'两种字符的字符串里面选一个子串,使得该子串里面'0'和'1'的个数相等,求符合这个条件的最长子串。

输入:
第一行输入数组元素个数N(1<=N<=1e6)
第二行输入N个元素Ni(每个元素只能是'0'或'1')

输出:
符合条件的最长子串,没有符合条件的则输出0


示例:

Input
10
0001011010

Output
8

Input
5
11011
Output
2

Input
5
11111
Output
0

三

在一个K阶矩阵里面如果某个子矩阵的对角顶点元素分别对应相等,那么这个矩阵就叫"特殊子矩阵",现在就要求这样的特殊子矩阵的最大内含元素个数(包括其顶点边界,实际就是子矩阵的长乘以子矩阵的宽)

输入:
第一行输入矩阵的长N(1<=N<=100)和宽M(1<=M<=100)
接下来M行每行N个元素Nij表示第i行的第j个元素(0<=Nij<=999)

输出:
该特殊子矩阵的最大内含元素个数,如果没有这样的特殊子矩阵就输出0。

示例:
Input

3 4
2 3 2
4 5 1
1 3 4
3 1 2

Output
6

4 4
1 2 3 1
2 2 1 3
4 5 4 2
1 3 2 1

Output
16

Input
2 2
1 2
1 2

Output
0

PS:第三问感觉把1<=Nij<=100改成0<=Nij<=999比较好(这算是一个小提示了,毕竟数据范围本来就是对解题方向的一个要好的提示,当然数个题外话也有给出小数据取值范围但解题方法适用于大数据的"人为"特殊情况)

其实拿出来就是感觉这些解题方法好好玩而已~

[此贴子已经被作者于2018-3-26 23:19编辑过]

期待楼下。。这累的。。

/*/
从一个N个元素的递增数组里面判断有没有差值为K的两个数。

输入:
第一行输入数组元素个数N(1<=N<=1e6)和目标差值K(1e-9<=1e9)
第二行递增输入N个元素Ni(1e-9<=Ni<=1e9,注意:数据初始化的时候已是递增输入)

输出:
有就输出Yes没有就输出No
/*/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    int iN, iK;
    int *aN;    //动态数组，存放元素Ni

    int i, j;

    printf("Input\n");
    scanf("%d %d", &iN, &iK);    //输入N和K
    aN = (int *)calloc(iN, sizeof(int));    //给数组分配空间
    for (i = 0; i < iN; i++)    //输入N个元素Ni
        scanf("%d", &aN[i]);

    printf("\nOutput\n");
    for (i = 0; i < iN - 1; i++)
        for (j = 1; j < iN; j++)
            if (abs(aN[i] - aN[j]) == iK)
            {
                printf("YES\n\n");    //有符合条件，输出YES
                goto END;    //转终止处理
            }
    printf("NO\n\n");    //无符合条件，输出NO

END:
    free(aN);    //释放数组空间
    system("PAUSE");
    return 0;
}

[此贴子已经被作者于2018-3-27 16:53编辑过]

代码的价值在于其算法，程序员不应该只是个打字员，暴力遍历不常常是有效的。
以第一题为例，时间复杂度O(n)要1秒的话，那么O(n*n)就需要十多天。

抛砖引玉：
用两个指针指向数字开头
如果 *p1 + k 小于 *p2，则 ++p1
如果 *p1 + k 大于 *p2，则 ++p2
如果 *p1 + k 等于 *p2，则输出YES
循环以上步骤

谢谢指点。

/*/
从一个N个元素的递增数组里面判断有没有差值为K的两个数。

输入:
第一行输入数组元素个数N(1<=N<=1e6)和目标差值K(1e-9<=1e9)
第二行递增输入N个元素Ni(1e-9<=Ni<=1e9,注意:数据初始化的时候已是递增输入)

输出:
有就输出Yes没有就输出No
/*/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    int iN, iK;
    int *aN;    //动态数组，存放元素Ni

    int i, j;

    printf("Input\n");
    scanf("%d %d", &iN, &iK);    //输入N和K
    aN = (int *)calloc(iN, sizeof(int));    //给数组分配空间
    for (i = 0; i < iN; i++)    //输入N个元素Ni
        scanf("%d", &aN[i]);

    printf("\nOutput\n");
    i = 0;    //指向前一个元素
    j = 1;    //指向后一个元素
    while(1)
    {
        if ((aN[j] - aN[i]) == iK)    //后一个元素值与前一个元素值的差为K则输出Yes
        {
            printf("Yes\n\n");
            break;
        }
        else if ((aN[j] - aN[i]) > iK)    //后一个元素值与前一个元素值的差大于K则将前一个元素推进一格
        {
            i++;
        }
        else if ((aN[j] - aN[i]) < iK)    //后一个元素值与前一个元素值的差小于K则将后一个元素推进一格
        {
            j++;
            if (j > iN)    //后一个元素无法推进时代表无符合条件情况，输出No
            {
                printf("No\n\n");
                break;
            }
        }
    }

    free(aN);    //释放数组空间
    system("PAUSE");
    return 0;
}

[此贴子已经被作者于2018-3-27 21:19编辑过]

第一题过了,5楼那个代码可以作为样板参考一下……
当然5楼的严谨一点还是要判断N=1的情况,不然数组下标会越界的(当然这只是小问题,不必太过在意),其实说白了这些题目和其它算法设计题相比就是不需要太过高端的算法知识,就在于其算法本身的"精妙"二字,而且后面两题在构建代码过程(如果有兴趣去弄代码的话)也会用到一些小别致的处理技巧~

[此贴子已经被作者于2018-3-27 22:14编辑过]

第二题

#include<stdio.h>
int main(void)
{
    char arr[1000];
    int a[1000];
    int i,j,n,answer=0;
    printf("Input\n");
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%c",&arr[i]);
    if(arr[0]=='1')
        a[0]=1;
    else
        a[0]=-1;
    for(i=1;i<n;++i)
    {
        if(arr[i]=='1')
            a[i]=a[i-1]+1;
        else
            a[i]=a[i-1]-1;
    }
    for(i=0;i<n-1;++i)
        for(j=i+1;j<n;++j)
        {
            if(a[j]==a[i]&&j-i>answer)
                answer=j-i;
        }
    printf("Output\n");
    printf("%d\n",answer);
    return 0;
}

第二题判断方法以及解题方向OK了,但看样子就是判断用了传统的枚举,变通一下判断方法其实可以优化到o(n)~

第二题也可以 空间换时间
既然累加值在[-N,+N]之间，那不如用bitmap来寻找相同值，时间复杂度由 O(n*n/2) 降为 O(n)

代码没验证过，意思到了就行

#include <stdio.h>

enum { MAXN = 1000000 };

int main( void )
{
    static unsigned buf[MAXN+1+MAXN];
    buf[MAXN] = 1;

    unsigned n;
    scanf( "%u ", &n );

    unsigned range = 0;
    int sum = MAXN;
    for( unsigned i=0; i!=n; ++i )
    {
        if( getchar() == '0' )
            --sum;
        else
            ++sum;

        if( buf[sum] == 0 )
            buf[sum] = i+2;
        else
            range = range > i+2-buf[sum] ? range : i+2-buf[sum];
    }

    printf( "%u\n", range );
}

第三题还是用遍例，复杂度O(n2)，我想不到什么好办法：

/*/
在一个K阶矩阵里面如果某个子矩阵的对角顶点元素分别对应相等,那么这个矩阵就叫"特殊子矩阵",现在就要求这样的特殊子矩阵的最大内含元素个数(包括其顶点边界,实际就是子矩阵的长乘以子矩阵的宽)

输入:
第一行输入矩阵的长N(1<=N<=100)和宽M(1<=M<=100)
接下来M行每行N个元素Nij表示第i行的第j个元素(0<=Nij<=999)

输出:
该特殊子矩阵的最大内含元素个数,如果没有这样的特殊子矩阵就输出0。
/*/
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    int iN, iM;    //矩阵的长N和宽M
    int *aN, iaNL;    //矩阵数组及长度
    int iSX, iSY;    //子矩阵左上元素及坐标
    int iEX, iEY;    //子矩阵右下元素及坐标
    int iaNMaxL = 0;    //最大子矩阵内含元素个数，初始为0

    int i, j, x;

    printf("Input\n");
    scanf("%d %d", &iN, &iM);    //矩阵的长N和宽M
    iaNL = iN * iM;    //计算矩阵元素个数
    aN = (int *)calloc(iaNL, sizeof(int));    //给矩阵分配空间
    for (i = 0; i < iaNL; i++)    //输入N*M个元素
        scanf("%d", &aN[i]);

    printf("\nOutput\n");
    for (i = 0; i < iaNL; i++)    //查找特殊子矩阵
        for (j = 0; j < iaNL; j++)
        {
            iSX = i / iN;    //左上元素坐标
            iSY = i % iN;
            iEX = j / iN;    //右下元素坐标
            iEY = j % iN;
            if ((iSX != iEX) && (iSY !=iEY) &&    //左上和右下元素不在同一行/列
                (aN[i] == aN[j]) &&    //并且：左上和右下元素相等
                (aN[iSX * iN + iEY] == aN[iEX * iN + iSY]))    //并且：右上和左下元素相等，则为特殊子矩阵
                {
                    x = (abs(iEX - iSX) + 1) * (abs(iEY - iSY) + 1);    //计算此子矩阵元素个数
                    iaNMaxL = (iaNMaxL > x) ? iaNMaxL : x;    //如大于以前的最大值则保留
                }
        }
    printf("%d\n\n", iaNMaxL);  //输出结果

    free(aN);    //释放数组空间
    system("PAUSE");
    return 0;
}

[此贴子已经被作者于2018-3-28 14:31编辑过]