一個算法,朋友的一個面試題

tigerZH 發布于2019-06-27 10:44 / 534人閱讀

摘要：語言實現我的實現的實現未經優化語言的實現是的其實思路都是一樣的不過語言的版本注意了兩個優化的點第一次輸出都是輸出如下都是斜著輸出的然后我初步想的辦法是把后面的補上所以又做了一個循環其實不需要后來發現了一些規律可以優化的方向第二

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.c語言的算法有一個更巧妙的地方,是我沒注意到的,第一行的7和和最后一行的10是成對角線關系的,所以

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

此判斷是非常巧妙地,沒有浪費多余的變量解決了這個問題,是優化1更進一步的方案

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

再解釋下這個算法的核心,就是這個臨界判斷,當到了輸出邊界,也就是豎排在最左邊的位置的時候,要進行i,j的重置

云服務器 GPU云服務器字符串算法面試題面試c語言算法編程題面試一個php linux的面試題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/20769.html

從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。本文是無精瘋同學投稿的面試經歷關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份在此感謝無精瘋同學的分享目錄：印象中的頭條面試背景準備面試 ...

tracymac7 2019-08-15 17:57 評論0 收藏0
從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。本文是無精瘋同學投稿的面試經歷關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份在此感謝無精瘋同學的分享目錄：印象中的頭條面試背景準備面試頭條一面（Java+項目）頭條...

wdzgege 2019-08-19 11:43 評論0 收藏0
求職準備 - 收藏集 - 掘金

摘要：一基礎接口的意義百度規范擴展回調抽象類的意義想不想通過一線互聯網公司面試文檔整理為電子書掘金簡介谷歌求職記我花了八個月準備谷歌面試掘金原文鏈接翻譯者【面試寶典】從對象深入分析 Java 中實例變量和類變量的區別 - 掘金原創文章，轉載請務必保留原出處為：http://www.54tianzhisheng.cn/... , 歡迎訪問我的站點，閱讀更多有深度的文章。實例變量和類變量...

cuieney 2019-08-16 10:36 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

aaron 2019-08-01 17:38 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

摘要：與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在，至少在被標準化的那一刻起，就支持異步編程了。然而異步編程真正發展壯大，的流行功不可沒。在握手過程中，端點交換認證和密鑰以建立或恢復安全會話。 1、前端排序算法總結排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較...

ARGUS 2019-08-21 16:43 評論0 收藏0