美文网首页
每日Leetcode—算法(16)

每日Leetcode—算法(16)

作者: Chuck_Wu | 来源:发表于2019-05-18 20:52 被阅读0次

172. 阶乘后的零

算法:

def trailingZeroes(self, n):
    s = 0
    while n>=5:
        n = n//5
        s += n
    return s

分析:5的阶乘均会出现一次0,所以直接利用整数n整除5,得到的数就是0出现的次数。

189.旋转数组

说明:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

算法一:

def rotate(self, nums, k):
    def rev(start, end , s):
        while start < end:
            s[end] ,s[start]= s[start], s[end]
            end-=1
            start+=1
    length = len(nums)
    rev(length-k%length,length-1,nums)   #这个%不是很明白
    rev(0,length-k%length-1,nums)
    rev(0,length-1,nums)

算法二:

def rotate(self, nums, k):
    l = len(nums)
    nums[:l-k] = reversed(nums[:l-k])     #直接进行本地运算
    nums[l-k:] = reversed(nums[l-k:])
    nums[:] = reversed(nums)

算法三:

def rotate(self, nums, k):
    l = len(nums)
    nums[:] = nums[l-k:] + nums[:l-k]

190.颠倒二进制位

算法一:

def reverseBits(self, n):
    l = list({'0:32b'}.format(n))   #首先需要格式化为32位无符号数
    l.reverse()
    return int(''.join(l),2)

分析:算法利用了Python的format格式化。

算法二:

def reverseBits(self, n):
    return int(bin(n)[2:].zfill(32)[::-1],2)

分析:zfill(n)用于字符串右对齐补齐前端的0,参数n为字符串的总长度。

191.位1的个数

算法一:

def hammingWeight(self, n):
    r = 0
    l = list(map(int,list('{:b}'.format(n))))     #首先格式化无符号整数,再使用map进行int化
    for i in l:     #计算1的个数
        if i == 1:
            r += 1
    return r

算法二:

def hammingWeight(self, n):
    l = bin(n)       #首先转换为二进制数
    return n.count('1')

198.打家劫舍

算法:

def rob(self, nums: List[int]) -> int:
    last, now = 0,0
    for i in nums: last, now = now, max(last+i, now)
    return now

分析:算法使用了动态规划

相关文章

  • Swap Nodes in Pairs

    标签: C++ 算法 LeetCode 链表 每日算法——leetcode系列 问题 Swap Nodes in ...

  • Combination Sum II

    标签: C++ 算法 LeetCode DFS 每日算法——leetcode系列 问题 Combinatio...

  • Divide Two Integers

    标签: C++ 算法 LeetCode 每日算法——leetcode系列 问题 Divide Two Integ...

  • First Missing Positive

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 First Missing...

  • Valid Sudoku

    Valid Sudoku 标签: C++ 算法 LeetCode 每日算法——leetcode系列 问题 Val...

  • Next Permutation

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 Next Permuta...

  • Trapping Rain Water

    标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 问题 Trapping Rain...

  • Combination Sum

    标签: C++ 算法 LeetCode 数组 DFS 每日算法——leetcode系列 问题 Combinat...

  • Remove Nth Node From End of List

    标签: C++ 算法 LeetCode 链表 每日算法——leetcode系列 问题 Remove Nth Nod...

  • Merge k Sorted Lists

    标签: C++ 算法 LeetCode 链表 每日算法——leetcode系列 问题 Merge Two Sort...

网友评论

      本文标题:每日Leetcode—算法(16)

      本文链接:https://www.haomeiwen.com/subject/ymbtzqtx.html