LeetCode OJ--Unique Paths *

https://oj.leetcode.com/problems/unique-paths/

首先，转换成一个排列组合问题，计算组合数C(m+n-2) (m-1),请自动想象成上下标。

class Solution {

public:

    int uniquePaths(int m, int n) {

        if(m ==  && n == )

            return ;

        int sum1 = ;

        int sum2 = ;

        for(int i = ; i <= m-; i++)

            sum1 *= i;

        for(int j = m+n-; j >= n; j--)

            sum2 = sum2*j;

        return sum2/sum1;

    }

};

runtime error,当测试数据是36,7的时候，也就是说，这个数太大了，已经算不了了。

于是参考了discuss

class Solution {

public:

    int uniquePaths(int m, int n) {

        if(m ==  && n == )

            return ;

        int sum1 = ;

        int sum2 = ;

        //exchange;

        int temp;

        if(m<n)

        {

            temp = n; n = m; m = temp;

        }

        int p,q;

        int commonFactor;

        for(int i = ; i<= n-; i++)

        {

            p = i;

            q = i+m-;

            commonFactor = gcd(p,q);

            sum1 = sum1 * (p/commonFactor);

            sum2 = sum2 * (q/commonFactor);

            commonFactor = gcd(sum1,sum2);

            sum1 = sum1/commonFactor;

            sum2 = sum2/commonFactor;

        }

        return sum2/sum1;

    }

    int gcd(int a, int b)

    {

        while(b)

        {

            int c = a%b;

            a = b;

            b = c;

        }

        return a;

    }

};

输入58,61的时候wa，因为结果得了个负数，明显又溢出了。

于是：

#include <iostream>

using namespace std;

class Solution {

public:

    int uniquePaths(int m, int n) {

        if(m ==  && n == )

            return ;

        long long sum1 = ;

        long long sum2 = ;

        //exchange;

        int temp;

        if(m<n)

        {

            temp = n; n = m; m = temp;

        }

        int p,q;

        int commonFactor;

        for(int i = ; i<= n-; i++)

        {

            p = i;

            q = i+m-;

            commonFactor = gcd(p,q);

            sum1 = sum1 * (p/commonFactor);

            sum2 = sum2 * (q/commonFactor);

            commonFactor = gcd(sum1,sum2);

            sum1 = sum1/commonFactor;

            sum2 = sum2/commonFactor;

        }

        return sum2/sum1;

    }

    int gcd(long long a, long long b)

    {

        while(b)

        {

            int c = a%b;

            a = b;

            b = c;

        }

        return a;

    }

};

int main()

{

    Solution myS;

    cout<<myS.uniquePaths(,);

    return ;

}

中间过程中使用了long long 类型。

记住求公约数的算法。

巴特西

LeetCode OJ--Unique Paths *

最新文章

热门文章