数据结构与算法练习(2)

简介: 代码如下

6.连续数字最大乘积

在下面这个1000位正整数中,连续4个数字的最大乘积是9 × 9 × 8 × 9 = 5832。

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843

8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557

6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749

3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776

6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397

5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474

8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586

1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408

0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606

0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

解题思路:

通过滑动窗口实现,即控制窗口的大小为13,如果窗口所对的字符串中包含0,则直接将窗口的起点跳到0的下一位,否则计算乘积并与之前的最大值比较并更新,同时窗口后移一位,并循环。

通过简单循环实现,每次计算13位的乘积,同时更新最大值、再后移一位,如果某一位为0时不计算、后移一位再计算。

代码如下:

def str_product(num_str):
    res = 1
    for num in num_str:
        res *= int(num)
    return res
def successive_13_product1():
    '''滑动窗口'''
    num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\
    '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\
    '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\
    '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\
    '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\
    '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\
    '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\
    '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\
    '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\
    '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
    start = 0
    end = 12
    max_result = 1
    sub_str = num_str[start:end + 1]
    if '0' not in sub_str:
        res = str_product(sub_str)
        if res > max_result:
            max_result = res
    while end < 999:        
        end += 1
        if num_str[end] == '0':
            start = end + 1
            end = start + 12           
        else:
            start += 1
            sub_str = num_str[start:end + 1]
            res = str_product(sub_str)
            if res > max_result:
                max_result = res
    return max_result
print(successive_13_product1())
def successive_13_product2(size):
    '''循环'''
    num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\
    '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\
    '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\
    '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\
    '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\
    '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\
    '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\
    '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\
    '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\
    '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
    max_result = 1
    str_len = len(num_str)
    for i in range(str_len - size):
        res = 1
        for j in range(i, i + size):
            if num_str[j] == '0':
                break
            res *= int(num_str[j])
        if res > max_result:
            max_result = res
    return max_result
print(successive_13_product2(13))

输出:

23514624000
23514624000

性能分析:

从前面的分析可以看出,第一种方式循环的次数更少、运行时间更短。

7.特殊毕达哥拉斯三元组

毕达哥拉斯三元组是三个自然数a < b < c组成的集合,并满足a2 + b2 = c2

例如,32 + 42 = 9 + 16 = 25 = 52

有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积abc。

解题思路:

可以看到,这样的三元组可以构成直角三角形,a是短直角边、b是长直角边、c是斜边,最简单的实现方式是两层嵌套循环,循环的范围都是1-1000,但是显然这样循环次数会比较大。

经过分析可以知道,a是最短边,所以其长度是小于周长的三分之一的,所以循环范围为1-1000/3,b是大于a的,且b+c=1000-a、b<c,所以b的范围是a+1-(1000-a)/2,c即为1000-a-c,显然,此时循环次数会大大减小。

代码如下:

def get_pythagorean_triple():
    res = 1
    for i in range(1, 1000 // 3 + 1):
        for j in range(i + 1, (1000 - i) // 2 + 1):
            k = 1000 - i - j
            if i ** 2 + j ** 2 == k ** 2:
                res *= (i * j * k)
                break
    return res
print(get_pythagorean_triple())

输出:

31875000

性能分析:

本方法相比于简单循环,大大降低了循环次数,相率有所提升。

8.素数的和

所有小于10的素数的和是2 + 3 + 5 + 7 = 17。

求所有小于两百万的素数的和。

解题思路:

实现函数判断每一个数是否为素数,并相加即可。在判断素数时可以进一步减少循环次数,如果是大于2的偶数则肯定不是素数,则不需要进行循环,为奇数时,不需要再循环偶数。

代码如下:

def is_prime(n):
    is_prime = True
    if n < 2:
        is_prime = False
    elif n == 2:
        pass
    else:
        if n & 1 == 0:
            is_prime = False
        else:
            for i in range(3, int(pow(n, 0.5)) + 1, 2):
                if n % i == 0:
                    is_prime = False
                    break
    return is_prime
def sum_prime(n):
    prime_sum = 0
    for i in range(2, n + 1):
        if is_prime(i):
            prime_sum += i
    return prime_sum
print(sum_prime(2000000))

输出:

142913828922


相关文章
|
算法 Python
数据结构与算法练习(1)
13195的所有质因数为5、7、13和29。 600851475143最大的质因数是多少?
|
算法
数据结构与算法——二分查找练习
前面说到了二分查找问题,看起来非常的简单,的确,前面的两种实现都不难,代码也很容易写,因为那只是最基础的二分查找问题了。今天来看看几种稍微复杂的二分查找问题: • 查找第一个等于给定值的元素 • 查找最后一个等于给定值的元素 • 查找第一个大于等于给定值的元素 • 查找最后一个小于等于给定值的元素
109 0
|
存储 算法
数据结构与算法——单链表练习
前面的文章说到了一种很基础的数据结构——链表:数据结构与算法——链表,今天就来看看关于单链表的几种常见的操作,技术笔试的时候很大概率能够遇到其中的一些。多练习一下,对我们理解链表有很大的帮助,也能够提升我们的编码能力。 废话不多说,这几个练习题是: • 单链表反转 • 合并两个有序链表 • 检测链表中的环 • 删除链表倒数第 k 个节点 • 找到链表的中间节点
134 0
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
91 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
38 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
25 0
数据结构与算法学习十四:常用排序算法总结和对比
|
2月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
38 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
2月前
|
机器学习/深度学习 存储 算法
【数据结构与算法基础】——算法复杂度
【数据结构与算法基础】——算法复杂度
|
6月前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法
|
2月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
30 0