Day8

  1. Add Binary
    **思路:开始是想着跟昨天一样,一个数字加一,那就满位进一,但是今天这个不一样,用昨天的方法不合适。
        res = ''
        i, j, plus = len(a)-1, len(b)-1, 0
        while i>=0 or j>=0 or plus==1:
            plus += int(a[i]) if i>= 0 else 0
            plus += int(b[j]) if j>= 0 else 0
            res = str(plus % 2) + res
            i, j, plus = i-1, j-1, plus/2
        return res

  1. Sqrt(x)
    **思路:开始是想着逐渐累加的数i,进行平方,然后判断x在哪个区间里,结果报错说溢出了。后来看到有人做题思路是二分法来找这区间,没觉得高明多少呀,后来干脆直接用math.sqrt()函数,万事大吉
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        return int(math.sqrt(x))  

  1. Climbing Stairs
    **思路:开始想着分奇数和偶数来求1,2的组合,然后穷举出所有的可能的1的个数和2的个数的组合,再进行排列组合,这个时候就缺一个直接调用comb()函数,可是LeetCode里面不能调用,而且我估计复杂度太高,又不会被AC,就像上道题一样
        su = 0
        if n%2 == 0:
            for i in range(0,n/2+1,1):
                num1 = 2*i
                num2 = (n-num1)/2
                su += math.comb(num1+num2,num1)
        else:
            for i in range(0,n/2+1,1):
                num1 = 2*i+1
                num2 = (n-num1)/2
                su += math.comb(num1+num2,num1)     
        return su

还是应该去找规律,发现这是个斐波拉契咧

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        pre = cur = 1
        for i in xrange(1, n):
            pre, cur = cur, pre+cur
        return cur

今天多做了一道题 超时7分钟

你可能感兴趣的