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

一  

从一个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编辑过]

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

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

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

其实后面两题就是说同一样东西,只是第三题还要在第二题的基础上变通一下[如果长和宽分别为N和M的话,期待时间复杂度为o(N*N*M)]~

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

第二题是是用数组储存状态快速获取的对应值(类似利用散列表快速查找数据那样),这题是要确定两个数据综合起来判断,所以要设计一个快速同时获取两个数据状态的方法~

其实好像和我那个算法遍历次数差不多,那个时间复杂度是个趋势,而不真的要完全遍历~
其实开一个1000*1000的二维数组(题目K数据范围是0<=K<=999)记录两个顶点的状态这样可以优化,但你那个算法可以减少运算量真的很厉害~

PS:我算过一下理论上我那个要遍历40次,首先遍历第一二行,(从左到右扫描就可以了,然后二三行,三四行,遍历的时候看看buf[a[i][j]][a[i][j+x]]的状态值是多少就可以了,所代表这样用了两个循环,然后外循环加一个一三行,二四行这样)~理论上算出是(16+12+8+4)=40次(比36要大一点,算是这样了)~

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

今晚晚点睡了,发现就算把楼主算法复杂度最多还是o(n^4),只是数据量比较少的时候看不出来,实际最多执行次数大约是(n^4)/4次~
输入12*12的时候完全遍历记得是5304次~

附上12楼记录次数的测试代码,输入14楼数据就是和所提供的36完全吻合~

#include <stdio.h>
static unsigned count;
int fun(int a[][100],int x,int y,int s)
{
    int i,j;

    for(i=0;i<x;i++)
    {
        for(j=0;j<y&&(x+1-i)*(y+1-j)>s;j++)
        {
            ++count;
            if(a[i][j]==a[x][y]&&a[x][j]==a[i][y])
                return (x+1-i)*(y+1-j);
        }
    }
    return s;
}
void main()
{
    int n,m,i,j,s,a[100][100];
    scanf("%d%d",&m,&n);
    for(i=s=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
            s=fun(a,i,j,s);
        }
    }
    printf("%d\n",s);
    
    printf("%u\n",count);
}

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

编辑掉~

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