LeetCode-62劃水記錄04

LeetCode-62 劃水記錄 04
題目一看;
感覺可以用回溯法就是從(0.0)開始 走到下一步 再走下一步 走到盡頭了 向右邊走 到盡頭了回去上一個格子 再從上一個格子換一個方向 走 因?yàn)橹荒茏?個方向 如果一個格子2個方向都走完了 就又回到上一個
通過這樣的辦法 可以列出所有路徑 并且找到所有的路徑數(shù)之和。
回溯法遞歸實(shí)現(xiàn):
代碼如下：

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、網(wǎng)頁空間、營銷軟件、網(wǎng)站建設(shè)、潤州網(wǎng)站維護(hù)、網(wǎng)站推廣。

//遞歸版
void uniquePaths2(int m, int n,int H,int L,int *res) 
{
    if (m == H && n == L)
    {
        (*res)++;
        return 0;
    }
    if(m<=H-1)
    uniquePaths2(m + 1, n,H,L,res);
    if(n<=L-1)
    uniquePaths2(m , n+1,H,L,res);
}
int uniquePaths(int m, int n) {

    int res = 0;
    uniquePaths2(1, 1,m,n,&res);
    return res;
}
int main()
{
    int m = 4, n = 4;
    printf("%d\n", uniquePaths(m, n));
    return 0;
}

程序跑出來沒問題 用題目提供的樣本數(shù)據(jù) 測試都o(jì)k
LeetCode-62 劃水記錄 04
但是再大一點(diǎn)到 m=20 n=15的時候就超時了 隨著m n的增加時間幾乎也以幾何級的速度增長。程序運(yùn)行幾秒cpu就罵人了。。。
然后我想試試迭代版的時間如何
回溯法迭代版:

//迭代版
struct Point
{
    int x, y;
};
int uniquePaths3(int m,int n)
{
    int x = 0, y = 0,lsx=0,lsy=0;
    int zt[100][100] = { 0 };
    int sum = 0;
    struct Point Yl[100][100] = { 0 };

    while (1)
    {
        if (x >= m || y >= n)//該點(diǎn)超出范圍了 返回
        {
            lsx = Yl[x][y].x;
            lsy= Yl[x][y].y;
            x = lsx;    //返回上一點(diǎn)
            y = lsy;
            continue;
        }
        switch (zt[x][y])
        {
        case 0://該點(diǎn)未使用過 默認(rèn)向下
            zt[x][y]++; //表明已經(jīng)向下走了一次
            x += 1;
            Yl[x][y].x = x-1;
            Yl[x][y].y= y;
            break;
        case 1:
            zt[x][y]++; //表明已經(jīng)向下走了一次
            y += 1;
            Yl[x][y].x = x ;
            Yl[x][y].y = y-1;
            break;
        case 2:         //該點(diǎn)下右都走完了 返回上一點(diǎn)
            if (x == 0 && y == 0)
            {
                return sum;
            }
            zt[x][y] = 0;
            lsx = Yl[x][y].x;
            lsy = Yl[x][y].y;
            x = lsx;    //返回上一點(diǎn)
            y = lsy;
            break;
        default:
            break;
        }
        if (x == m - 1 && y == n - 1 && zt[x][y] == 0)
            sum++;
    }
    return sum;
}
int main()
{
    int m = 20, n = 15;
    printf("%d\n", uniquePaths3(m, n));
    //printf("%d\n", uniquePaths(m, n));
    return 0;
}

結(jié)果效果跟遞歸版一樣
。。。然后我就想應(yīng)該是從0，0 到終點(diǎn)的話會出現(xiàn)很多重復(fù)的工作，比如m=10 n=10 從中間5，5到 9，9 點(diǎn)如果有N種走法 那么剛開始 0，0 開始遍歷到 5，5的時候 和 1，1遍歷到5，5的時候都會從5，5遍歷到9，9了。這就重復(fù)工作了。可以考慮把5，5到9，9的走法記錄下來，然后到5，5的時候就讀取這個記錄就行了。
但是不能從0，0開始
應(yīng)該從9，9終點(diǎn)開始向左邊走。
然后走到左邊終點(diǎn)的時候
就返回到上一層的末尾
如此反復(fù)到0，0 這樣的話在遍歷的過程中每個點(diǎn)都可以獲取向下和向右的走法數(shù)量 兩者之和即為該點(diǎn)到終點(diǎn)的走法數(shù)；

代碼如下:

#include <stdio.h>

/*
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
*/
int uniquePaths2(int m, int n,int h,int l,int **HashMap)
{
    int Sum = 0;

    if (m<0||n<0)//坐標(biāo)非法
        return 0;

    if (n >= 0 && n <= l-1)//如果還不用切換到上一行
    {
        if (n >= 0 && n < l-1)//可以向右讀
        {
            Sum += HashMap[m][n + 1];
        }
        if (m >= 0 && m < h-1)  //可以向下讀
        {
            Sum += HashMap[m+1][n];
        }
        if (h-1 == m && l-1 == n) Sum = 1;
        HashMap[m][n] = Sum;
        //切換到上一行
        if (0 == m && n == 0)
        {

            return HashMap[0][0];
        }
        if (n == 0)
        {
            return uniquePaths2(m - 1, l-1,h,l,HashMap);//返回到上一行
        }
        else
            return uniquePaths2(m, n - 1,h,l,HashMap);

    }
    return 0;
}
int uniquePaths(int m, int n) 
{
    int xhbl = 0, xhbl2 = 0;
    //int HashMap[100][100] = { 0 };//記錄 leetcode中不能用全局變量 所以只能這樣
    int **HashMap = malloc(sizeof(int*) * 100);
    for(xhbl=0;xhbl<100;xhbl++)
        HashMap[xhbl]=malloc(sizeof(int) * 100);
    for (xhbl = 0; xhbl < 100; xhbl++)
    {
        for (xhbl2 = 0; xhbl2 < 100; xhbl2++)
        {
            HashMap[xhbl][xhbl2] = 0;
        }
    }
    HashMap[m-1][n-1] = 1;
    return uniquePaths2(m - 1, n - 1, m, n,HashMap);
}
int main()
{

    printf("%d", uniquePaths(7, 3));
    return 0;
}

提交到leetcode:
LeetCode-62 劃水記錄 04
沒毛病，就是時間太慢了。。

網(wǎng)頁名稱：LeetCode-62劃水記錄04
本文來源：http://muchs.cn/article12/pihhgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、手機(jī)網(wǎng)站建設(shè)、面包屑導(dǎo)航、網(wǎng)站設(shè)計(jì)、App設(shè)計(jì)、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都app開發(fā)公司