| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 920 人关注过本帖, 1 人收藏
标题:分享三个好玩的小问题,有兴趣的可以弄弄看~
只看楼主 加入收藏
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:49
帖 子:4936
专家分:13916
注 册:2016-10-22
结帖率:100%
  已结贴   问题点数:100  回复次数:19   
分享三个好玩的小问题,有兴趣的可以弄弄看~
这个难度应该是呈递增阶级的,有兴趣的看看可以弄几题~

一  

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

2018-03-26 18:43
lanke711
Rank: 9Rank: 9Rank: 9
来 自:流浪在天国之路
等 级:蜘蛛侠
威 望:7
帖 子:317
专家分:1437
注 册:2015-7-16
  得分:3 
期待楼下。。这累的。。

普通人之所以普通,是因为他们普遍有一个通病,那就是认为自己永远普通。
千夫所指,我亦坚持。就算被所有人误解,我也照样守护这一切。
我们总是觉得,这些灵魂的表情,傲慢自大,目中无人,其实,真正目中无人的是我们。它们傲慢的不过是表情,而我们傲慢的却是行为!
记得,是为了忘记!
只要想着有那么一天,我就能忍受现在的每一天!
灾难并不可怕,可怕的是心中没有了希望。
你以为我在天堂,其实我正在路上。
当你觉得自己走不到终点的时候,请不要放弃。或许你的对手也是这种感觉。
2018-03-26 22:36
sunus
Rank: 4
等 级:业余侠客
威 望:3
帖 子:43
专家分:214
注 册:2017-10-10
  得分:5 
程序代码:

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

2018-03-27 16:28
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:254
帖 子:5715
专家分:32361
注 册:2011-1-18
  得分:25 
代码的价值在于其算法,程序员不应该只是个打字员,暴力遍历不常常是有效的。
以第一题为例,时间复杂度O(n)要1秒的话,那么O(n*n)就需要十多天。

抛砖引玉:
用两个指针指向数字开头
如果 *p1 + k 小于 *p2,则 ++p1
如果 *p1 + k 大于 *p2,则 ++p2
如果 *p1 + k 等于 *p2,则输出YES
循环以上步骤
2018-03-27 19:36
sunus
Rank: 4
等 级:业余侠客
威 望:3
帖 子:43
专家分:214
注 册:2017-10-10
  得分:25 
回复 4楼 rjsp
谢谢指点。

程序代码:

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

2018-03-27 21:16
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:49
帖 子:4936
专家分:13916
注 册:2016-10-22
  得分:0 
第一题过了,5楼那个代码可以作为样板参考一下……
当然5楼的严谨一点还是要判断N=1的情况,不然数组下标会越界的(当然这只是小问题,不必太过在意),其实说白了这些题目和其它算法设计题相比就是不需要太过高端的算法知识,就在于其算法本身的"精妙"二字,而且后面两题在构建代码过程(如果有兴趣去弄代码的话)也会用到一些小别致的处理技巧~

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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-03-27 21:36
李晨经纪人
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:6
帖 子:175
专家分:848
注 册:2018-2-14
  得分:5 
第二题
程序代码:
#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;
}
2018-03-27 22:19
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:49
帖 子:4936
专家分:13916
注 册:2016-10-22
  得分:0 
回复 7楼 李晨经纪人
第二题判断方法以及解题方向OK了,但看样子就是判断用了传统的枚举,变通一下判断方法其实可以优化到o(n)~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-03-27 22:26
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:254
帖 子:5715
专家分:32361
注 册:2011-1-18
  得分:25 
第二题也可以 空间换时间
既然累加值在[-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 );
}

2018-03-28 10:14
sunus
Rank: 4
等 级:业余侠客
威 望:3
帖 子:43
专家分:214
注 册:2017-10-10
  得分:5 
第三题还是用遍例,复杂度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编辑过]

2018-03-28 14:23







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040122 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved