资讯专栏INFORMATION COLUMN

一个算法,朋友的一个面试题

tigerZH / 383人阅读

摘要:语言实现我的实现的实现未经优化语言的实现是的其实思路都是一样的不过语言的版本注意了两个优化的点第一次输出都是输出如下都是斜着输出的然后我初步想的办法是把后面的补上所以又做了一个循环其实不需要后来发现了一些规律可以优化的方向第二

c语言实现
/**
1 2 4 7 
3 5 8 11 
6 9 12 14 
10 13 15 16 
 */
#include 
#include 

const int N=1010;
int q[N][N];

/*
 * 
 */
int main(int argc, char** argv) {
    int n =4;
    int i = 1,j=1;
    for (int k = 1; k <= n*n; k++) {
        q[i][j] = k;
        if (i == n) {
            i = 1+j;
            j = n;
        } else if (j==1) {
            j = i+1;
            i = 1;
        } else {
            i++;
            j--;
        }
    }

    for (int i=1;i<=n;i++,puts(""))
        for (int j =1;j<=n;j++)
            printf("%d ", q[i][j]);
    return 0;
}

我的php实现

= 0) {
                        if ($i < 3) {
                                if (empty($arr[$i+1][$j-1])) {
                                        $n++;
                                        $arr[$i+1][$j-1] = $n;
                                }
                                $i++;
                                $j--;
                        } else {
                                //$prev = $n;
                                break;;
                        }
                }
        }
}
var_dump($arr);

php的实现未经优化,c语言的实现是O(n)的

其实思路都是一样的,不过c语言的版本注意了两个优化的点

第一次输出,都是输出如下,都是斜着输出的

1 2 4 7 
3 5 8 
6 9  
10

然后我初步想的办法,是把后面的补上,所以又做了一个循环,其实不需要,后来发现了一些规律,可以优化的方向

1.第二行开始,每次缺的都是从最后一个开始的,也就是第二行的第四位,所以,只要从第二行第四位开始输出就可以了,省去了外层的一层遍历

2.c语言的算法有一个更巧妙的地方,是我没注意到的,第一行的7和和最后一行的10是成对角线关系的,所以

   if (i == n) {
            i = 1+j;
            j = n;
        }

此判断是非常巧妙地,没有浪费多余的变量解决了这个问题,是优化1更进一步的方案

else if (j==1) {
            j = i+1;
            i = 1;
        }

再解释下这个算法的核心,就是这个临界判断,当到了输出边界,也就是竖排在最左边的位置的时候,要进行i,j的重置

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/20769.html

相关文章

  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录: 印象中的头条 面试背景 准备面试 ...

    tracymac7 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享目录:印象中的头条面试背景准备面试头条一面(Java+项目)头条...

    wdzgege 评论0 收藏0
  • 求职准备 - 收藏集 - 掘金

    摘要:一基础接口的意义百度规范扩展回调抽象类的意义想不想通过一线互联网公司面试文档整理为电子书掘金简介谷歌求职记我花了八个月准备谷歌面试掘金原文链接翻译者 【面试宝典】从对象深入分析 Java 中实例变量和类变量的区别 - 掘金原创文章,转载请务必保留原出处为:http://www.54tianzhisheng.cn/... , 欢迎访问我的站点,阅读更多有深度的文章。 实例变量 和 类变量...

    cuieney 评论0 收藏0
  • 前端排序算法总结;前端面试2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    aaron 评论0 收藏0
  • 前端排序算法总结;前端面试2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    ARGUS 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<