【题解】牛牛和网格三角形

题意

有一个的网格三角形，从左下角走到右上角，只能沿着网格边向上或向右走，问总的方案数的奇偶性。

题解

实际上所对应的总的方案数是就是第个数。但是由于这题的太大了，那么应该可以知道这题是个找规律的题面，我们若不知道什么是卡特兰数，可以通过dp来打表看看规律。

n++;
dp[1][1]=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
{
 if(i==1&&j==1)
     continue;
 dp[i][j]=dp[i-1][j]+dp[i][j-1];
}

通过这个打表有

1  true
2  false
3  true
4  false
5  false
6  false
7  true
8  false
9  false
10 false
11 false
12 false
13 false
14 false
15 true
16 false

可以发现当的二进制下都为1时，该方案数就是奇数，否则就是偶数。
那么我们只有判断的二进制是不是都是1就可以知道答案了。若数较小可以直接只用位操作的话，可以用来判断其是否都为1，所以python和java都可以使用位操作进行判断。而c++需要模拟除法来进行对十进制的二进制转换再判断是否二进制下都为1。该复杂度为

复杂度

c++/c模拟除法进行二进制转换时间复杂度为
空间复杂度为

代码

c++

class Solution {
public:
    /**
     * 
     * @param n string字符串 三角形的长和高
     * @return bool布尔型
     */
    string Divide(string str, int x)
    {
        int reminder = 0;
        for(int i = 0; i < str.size(); i++)
        {
            int current = reminder * 10 + str[i] - '0';
            str[i] = current / x + '0';
            reminder = current % x;
        }
        int pos = 0;
        while(str[pos] == '0')
            pos++;
        return str.substr(pos);
    }
    bool judge(string n) {
        // write code here
        int flag=0;
        while(n.size() != 0)
        {
            if((n[n.size() - 1]-'0')%2==0)
            {
                flag=1;
                return false;
            }
            n = Divide(n, 2);
        }
        if(!flag)
            return true;
    }
};

python

#
# 
# @param n string字符串 三角形的长和高
# @return bool布尔型
#
class Solution:
    def judge(self , n ):
        # write code here
        n=int(n)
        if (n&(n+1))==0:
            return True;
        else:
            return False;

java

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param n string字符串 三角形的长和高
     * @return bool布尔型
     */
    public boolean judge (String n) {
        // write code here
        BigInteger N=new BigInteger(n);
        if(N.and(N.add(BigInteger.ONE)).equals(BigInteger.ZERO))
            return true;
        else
            return false;
    }
}