讨论/技术交流/面试题目|笔试题求解 - 相邻元素之间替换最大公约数最优解/
面试题目|笔试题求解 - 相邻元素之间替换最大公约数最优解

给一组序列,求其中相邻两个元素之间的最大公约数。一直不停求下去直到所有元素被替换为1. 如果实在不能全部替换,则返回-1

输入的第一行为元素个数 n ,第二行为序列arr


Example1

Input:

4
4 1 3 5

Output

3

Example2:

Input:

5
10 20 30 40 50

Output:

-1

思路:

很明显如果序列里出现1,这个序列就一定能全部转为1,因为1和任何数的公约数都为1。

  1. 那么最先设立的一个初始筛选条件就是检测输入序列里是否有1,如果有就设一个变量num记录序列里面1的个数,返回 n-num就是答案。

  2. 如果初始序列里没有1,那么我们就需要求相邻数的公约数,一旦成功把其中一个元素替换为1,把这之前的替换步骤数(count)记录下来,我们就能够成功利用刚刚所说的就能立即出答案来计算出最终答案。也即是n-count+1. (1 是1的个数,因为这个时候只有1个1)

  3. 如果知道最后都没有1,则返回 -1


因为本人比较菜,限时半小时想了几个在第二步用最快的步骤遍历求1,但是都不太成功。递归容易造成超时,希望有大佬指点迷津。

因为这题属于最优解题目,应该能用DP求解,但是不太清楚这里怎么确定状态和拆分子问题。

菜鸡初始代码如下:

def hcf(x, y): #返回最大公约数
    if x>y: #判断大小
        small =y
    else:
        small = x
    for i in range(1, small+1):
        if (x%i==0)and (y%i==0): #这个i值能被两数相除没有余数,代表为公约数
            hcf = i           
    return hcf

# 获取输入数据
n = int(input()) #长度
list = list(map(int, input().split()))

count = 0
for i in range(n):
    if (list[i] == 1):
        count+=1
if count != 0:    #如果序列有1,输出n-(1的个数)
    print(n-count)
    
'''
上面的是第一步

'''





共 0 个回复
暂无回复