分享一个有趣的算法题

今天,在QQ群看到一个有趣的算法题,简单写了一下,本文做一个记录。

题目

做如下一个数据结构,给定N为行列数量(比如5)

1 2 6 7 15
3 5 8 14 16
4 9 13 17 22
10 12 18 21 23
11 19 20 24 25

然后给定索引X和Y,用以查询第X行,第Y列,然后将两个结果的元素相加(交叉的元素只需要加一次)即为结果

分析

乍一看好像没有什么规律,但仔细看看便会发现,将表格中的元素位置依次相连起来,便得出了规律,从(0,0)下标开始算,每次相连起来的斜线上,每个点的下标之和都是一样的,只不过如果是横向增加则是右上斜向左下,然后到了纵向增加,然后方向又是左下斜向右上了。所以,我们只需要确定当前点位下标之和即可得到所有点位,然后反向做同样的操作即可得到下一条线

规律图

解题

根据上面分析出的规律,那就很容易写出代码如下

int n = 5;
int x = 1;
int y = 2;
int current=1;
bool rev=true;

int[,] nums = new int[n,n];

for(int l = 0; l < n + n - 1; l++){
    for(int a = 0; a <= l && a < n; a++){
        for(int b = 0; b <= l && b < n; b++){
            if(a + b == l){
                if(!rev){      
                    nums[a,b] = current;             
                }
                else{
                    nums[b,a] = current;
                }
                current++;
            }
        }
    }
    rev=!rev;
}

int[] xx = new int[n];
int[] yy = new int[n];

for(int a = 0; a < n; a++){
    xx[a] = nums[x-1,a];
}

for(int a = 0; a < n; a++){
    yy[a] = nums[a,y-1];
}

var result = xx.Concat(yy).Distinct().ToArray();

int sum=0;

foreach(var item in result){
   sum += item;
}

Console.WriteLine("数组为:");
Console.WriteLine(nums);
Console.WriteLine($"第{x}行,第{y}列结果为:");
Console.WriteLine(result);
Console.WriteLine($"结果为:{sum}");
发布时间:2021-05-17
其他阅读

HTTP状态码

HTTP状态码为客户端提供了一种理解事务处理结果的边界方式。本文列出一些原因短语,所使用的是HTTP/1.1规范所定义的。

查看原文

C#完成一个应用内的消息中心

本文会讲解如何使用 C# 完成一个应用内部的消息中心(事件总线),事件驱动最大的好处就是可以很大程度的解耦合,松散结构。

查看原文

解决sqlite依赖无法打包单文件的问题

在一次WPF开发中,选用了sqlite作为内嵌数据库,使用 ystem.Data.SQLite 库来调用,在使用 Fody 进行单文件打包时,发现打包文成后会出现 x86 和 x64 两个特定的文件夹,分别对应着32位和64位的 SQLite.Interop.dll,本文介绍修改项目文件来实现将 sqlite 通信库一起打包成单文件的方法。

查看原文

使用正则表达式来判断邮箱

在开发中,很多地方都需要用户输入邮箱,用户注册,登录需要邮箱,订阅消息需要邮箱,为了防止被恶意使用,一般都会使用正则表达式来判断输入是否符合邮箱规范

查看原文

Angular 中跨分模块后路由复用问题

当我们的 Angular 应用越来越大后,就需要考虑使用模块或者直接使用库来将解体应用,使用时进来懒加载,加快访问速度。当跨分模块后,普通的路由复用策略就是失效,需要额外的解决方法。

查看原文