本文共 12093 字，大约阅读时间需要 40 分钟。

• ：返回[left,right+1]区间内所有自分数的列表（自分数即该数%各位上的数=0，含0的数不是自分数）, Easy

class Solution(object):    def selfDividingNumbers(self, left, right):        """        :type left: int        :type right: int        :rtype: List[int]        """        ret = []        for num in range(left,right+1):            tmp = num            flag = True            while(tmp and flag):                digit = tmp%10                if digit == 0 or num%digit!=0:                    flag = 0                else:                    tmp = tmp/10            if flag:                ret+=[num]        return ret

• ：判断一个数是否满足各个位上平方和之和为1

class Solution(object):    def isHappy(self, n):        if n<1:            return False        elif n==1:            return True        hashtable={}        while n!=1:            if n in hashtable:                return False            else:                hashtable.setdefault(n,None)                array=[]                while n:                    array.append((n%10)**2)                    n=n/10                n=sum(array)        return True

• ：一个数把各个位置数求和，直到得到一个一位数，返回这个数。Easy

  O(1)解法的思想就是，反正高位最后都要加到个位上，那ans>=10就立刻把十位上的数加进去

class Solution(object):    def addDigits(self, num):        """        :type num: int        :rtype: int        """        '''        #循环或递归解法        num = str(num)        while(len(num)>1):            ans = 0            for i in num:                ans +=int(i)            num = str(ans)        return int(num)        '''        # O(1)解答法        num = str(num)        ans = 0        for n in num:            ans+=int(n)            if ans>=10:                ans=(ans%10)+(ans/10)        return ans

• ：将Excel表格的列转化成数字，Easy

class Solution(object):    def titleToNumber(self, s):        Array_=list(s)        Array_.reverse()        s=0        for i in range(len(Array_)):            s+=(ord(Array_[i])-ord('A')+1)*(26**i)        return s

• ：将数字翻译成Excel表中的列，Easy

class Solution(object):    def convertToTitle(self, n):        dict=['Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y']        ans=[]        while n!=0:            ans.append(dict[n%len(dict)])            tmp=n%len(dict)            if tmp==0:                tmp=len(dict)            n=(n-tmp)/len(dict)        ans.reverse()        s=''.join(ans)        return s

• , 每次ops操作会使得[(0,0),(ops[0],ops[1])] 范围的数字增加1， 求最后最大数字的个数。Easy

class Solution(object):    def maxCount(self, m, n, ops):        """        :type m: int        :type n: int        :type ops: List[List[int]]        :rtype: int        """        mincol = m        minrow = n        for op in ops:            mincol = min(mincol,op[0])            minrow = min(minrow,op[1])        return mincol*minrow

• [trick] ：每次n-1个元素增加1，求使数组最后元素相同的最少次数, Easy

  每次n-1个元素增加1，等价于每次有个元素-1，结果为每个元素与最小元素的差值之和

class Solution(object):    def minMoves(self, nums):        """        :type nums: List[int]        :rtype: int        """        minNum = min(nums)        ans = 0        for num in nums:            ans += (num-minNum)        return ans

• ：罗马数->整数，Easy

class Solution(object):    def romanToInt(self,s):        '''        :param s: str        :return: int        '''        if len(s)==0:            return 0        d = {
  'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}        ret = 0        tmp = d[s[0]]        for i in range(1,len(s)):            if d[s[i]]
   
     d[s[i-1]]:                ret -=tmp                tmp = 0            tmp +=d[s[i]]        ret +=tmp        return ret
   

• ：整数->罗马数， Easy

class Solution(object):    def intToRoman(self,num):        '''        :param num:int        :return:str        '''        translation = [['','I','II','III','IV','V','VI','VII','VIII','IX'],                       ['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'],                       ['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'],                       ['','M','MM','MMM']]        s = ''        digit = 1000        i = 3        while(num%digit!=0):            tmp = num/digit            s = s+translation[i][tmp]            num = num%digit            digit /=10            i = i-1        s +=translation[i][num/digit]        return s

• ：求数组中三个数的乘积最大值，Easy

  排序 返回 nums[-1]*nums[-2]*nums[-3], nums[-1]*nums[0]*nums[1]

  需要考虑负数的情况

class Solution(object):    def maximumProduct(self, nums):        """        :type nums: List[int]        :rtype: int        """        nums.sort()        return max(nums[-1]*nums[-2]*nums[-3],nums[-1]*nums[0]*nums[1])

• ：二进制加法，Easy

class Solution(object):    def swap(self,a,b):        a1,b1=list(a),list(b)        a1.reverse()        b1.reverse()        max_num=max(len(a1),len(b1))        if len(a1)

• ：返回字符串加1的结果，Easy

class Solution(object):    def plusOne(self, digits):        digits.reverse()        flag=1        for i in range(len(digits)):            if digits[i]+flag<10:                digits[i]+=flag                flag=0            else:                digits[i]=0                flag=1        if flag==1:            digits.append(1)        digits.reverse()        return digits

• ：大数相加，Easy

class Solution(object):    def addStrings(self, num1, num2):        """        :type num1: str        :type num2: str        :rtype: str        """        len1 = len(num1)        len2 = len(num2)        length = max(len1,len2)        if len1

• [trick] ：大数相乘，Medium

  第x位置的值是满足i+j=x的乘积之和加上x-1位的进位

class Solution(object):    def multiply(self, num1, num2):        """        :type num1: str        :type num2: str        :rtype: str        """        s1,s2 = len(num1),len(num2)        ret = [0] * (s1+s2)        for i in range(s1):            for j in range(s2):                ret[i+j+1]+=int(num1[i])*int(num2[j])        flag = 0        ans = ''        for i in range(s1+s2-1,-1,-1):            ret[i] = ret[i]+flag            flag = ret[i]/10            ret[i] = ret[i]%10            ans = str(ret[i])+ans        if flag:            ans = str(flag)+ans        pos = True        a = ''        for i in range(len(ans)):            if ans[i]=='0' and pos:                pass            else:                pos = False                a += ans[i]        return a if len(a) else '0'

• ：判断一个数是否是3的次方，Easy

  取对数判断

class Solution(object):    def isPowerOfThree(self, n):        if n>0:            a=math.log(n)/math.log(3.0);        else :            a=0.5;        b=round(a,0)        if abs(a-b)<1e-10:            return True;        else:            return False;

• ：找出重复数和缺失数，Easy

class Solution(object):    def findErrorNums(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        tables = dict()        sum_ = sum(nums)        size = len(nums)        for num in nums:            if num in tables:                ans1 = num                break            else:                tables[num] = True        ans2 = ans1 + ((1+size)*size/2-sum_)        return [ans1,ans2]

• ：丑陋数判断（只包含2，3，5因子），Easy

class Solution(object):    def isUgly(self, num):        if num==0:            return False        flag=True        while(flag):            if num%2==0:                num=num/2            elif num%3==0:                num=num/3            elif num%5==0:                num=num/5            else:                flag=False        if num==1:            flag=True        return flag

• ：判断n!中包含多少个0

  主要是看5，25，125

class Solution(object):    def trailingZeroes(self, n):        """        :type n: int        :rtype: int        """        count=0        tmp=5        while(n/tmp):            count=count+n/tmp            tmp=tmp*5        return count

• ：每i层的硬币个数为i+1，给n求第几层缺失硬币，Easy

class Solution(object):    def arrangeCoins(self, n):        """        :type n: int        :rtype: int        """        step = 1        cnt = 0        while(cnt<=n):            cnt+=step            step+=1        return step-2

• ：判断一个数是否是回文数

class Solution(object):    def isPalindrome(self,x):        '''        :param x: int        :return: bool        '''        if x<0:            return False        tmp = x        ret = 0        while(x):            ret = ret*10 + x%10            x = x/10        return ret == tmp

• ：判断一个数是否满足所有因子（除了本身）之和等于这个数，Easy

  注意条件判断的方法

class Solution(object):    def checkPerfectNumber(self, num):        """        :type num: int        :rtype: bool        """        if num == 1: return False        divisors = [1]        start,end = 2,num        while(start*start<=num):            if num%start==0:                end = num/start                divisors.append(end)                divisors.append(start)            start+=1        return sum(divisors)==num

• ：判断一个数是否是两个完全平方数之和，Easy

import mathclass Solution(object):    def judgeSquareSum(self, c):        """        :type c: int        :rtype: bool        """        m = {}        for i in range(int(math.sqrt(c))+1):            m[i*i]=True            if (c-i*i) in m:                return True        return False

• [aaaa] 给定一个无穷整数序列1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 求序列的第n位数字, Easy

class Solution(object):    def findNthDigit(self, n):        """        :type n: int        :rtype: int        """        for i in range(9):            d = 9 * 10 ** i            if n <= d * (i + 1): break            n -= d * (i + 1)        n -= 1        return int(str(10**i + n / (i + 1))[n % (i + 1)])

• ：整数转置，Easy

class Solution(object):    def reverse(self, x):        """        :type x: int        :rtype: int        """        max_=2**31-1        min_=-2**31        if x == 0: return 0        flag = 1 if x>0 else -1        x = x * flag         ans = 0        while(x):            ans = ans*10 + x%10            x = x/10        ans = ans * flag        if ans> max_ or ans< min_:            return 0        return ans

• ：计算1-n中质数的个数

class Solution:# @param {integer} n# @return {integer}    def countPrimes(self, n):        if n < 3:            return 0        primes = [True] * n        primes[0] = primes[1] = False        for i in range(2, int(n ** 0.5) + 1):            if primes[i]:                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])        return sum(primes)

• ：在森林里，每只兔子都有一些颜色。一些兔子的子集（可能是所有的）告诉你其他的兔子有多少和它们一样的颜色。这些答案放在一个数组中。返回可能在森林里的最小数量的兔子。Medium

hash统计

import collectionsclass Solution(object):    def numRabbits(self, answers):        """        :type answers: List[int]        :rtype: int        """        rabbits = collections.Counter(answers)        ans = 0        for rabbit in rabbits:            nums = rabbits[rabbit]            rabbit = rabbit+1            if nums%rabbit:                ans += (nums/rabbit+1)*rabbit            else:                ans += (nums/rabbit)*rabbit        return ans

• ：求字符串分数相加结果，Medium

分数字符串可以拆解成若干个分数相加的形式,”-1/2+1/3”

[-1/2,1/3]

分子为 -1*(6/2)+1*(6/3) = -1 (6是所有分母的乘积）

分母为乘积

计算最大公约数，然后约分即可

class Solution(object):    def fractionAddition(self, expression):        """        :type expression: str        :rtype: str        """        numerators = []        product = 1        products = []        tmp = []        c = ''        for i in expression:            if (i=='+' or i=='-') and len(c):                tmp.append(c)                c=i            else:                c+=i        tmp.append(c)        for exp in tmp:            exp = exp.split('/')            product*=int(exp[1])            products.append(int(exp[1]))            numerators.append(int(exp[0]))        numerator = 0        for pro,num in zip(products,numerators):            numerator+=num*(product/pro)        def gcd(a, b):            if a < b: a, b = b, a            while b:                a, b = b, a % b            return a        x = gcd(abs(numerator),abs(product))        numerator = numerator/x        product = product/x        return str(numerator)+'/'+str(product)

• ：同一时刻，你和鬼魂均可以向东、西、南、北移动一步，判断在鬼魂抓到你之前是否能够到达目的地，Medium

计算鬼魂和目的地的最小距离，如果大于目标点到起始点的距离，则能够被抓住。

import sysclass Solution(object):    def escapeGhosts(self, ghosts, target):        """        :type ghosts: List[List[int]]        :type target: List[int]        :rtype: bool        """        minDist = sys.maxint        for ghost in ghosts:            minDist = min(abs(target[0]-ghost[0])+abs(target[1]-ghost[1]),minDist)        Dist = abs(target[0])+abs(target[1])        return minDist>Dist

转载地址：http://zbqmi.baihongyu.com/