算法题记录

2021拼多多

1、数位之和

定义为：每个数字的十进制表示中(0~9)，每个数位各不相同且各个数位之和等于N。
满足条件的数字可能很多，找到其中的最小值即可。

输入描述：

共一行，一个正整数N，如题意所示，表示组合中数字不同数位之和。
（1 <= N <= 1,000）

输出描述：

共一行，一个整数，表示该组合中的最小值。
如果组合中没有任何符合条件的数字，那么输出-1即可。

题目分析：

数：123456789 是最小的数位之和，因为题目中限定了每个数位各不相同，

则只需求1-45之间的就行

解法：

def myCompute(num):
    if num > 45:
        return -1
    if num < 10:
        return num

    nums = 0
    digits = 0 # 记录第几位数，用于进位

    for i in range(9,0,-1):
        if num != 0 and i <= num:
            print(nums,i,"-")
            num -= i
            nums += i * (10**digits)
            
            digits += 1
    return nums

解法二：

def compute(x,num):
    '''
    num代表每一位上的数字
    x 代表总和
    '''
    # 如果发现，剩余的总和比安排的数字还小就不需要递归了
    if x<= num:
        return x
    else:
        # 在剩余的总和中，安排剩余的数字
        return num + 10 * compute(x-num,num-1)

2、字符串变换

多多君最近在研究字符串之间的变换，可以对字符串进行若干次变换操作:

1. 交换任意两个相邻的字符，代价为0。
2. 将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。

输入描述：

共三行，第一行，一个整数N，表示字符串的长度。
（1 <= N <= 2,000）
接下来两行，每行分别是一个字符串，表示字符串X和Y。
（字符串中仅包含小写字母）

输出描述：

共一行，一个整数，表示将X和Y变换成一样的字符串需要的最小的总代价。

示例：

输入：

4
abca
abcd

输出：

3

解法：

def myCompute2(str1,str2):
    str1 = ''.join(sorted(str1))
    str2 = ''.join(sorted(str2))

    n = len(str1)
    res = 0
    for i in range(n):
        ch1 = str1[i]
        ch2 = str2[i]
        res += abs(ord(ch1)-ord(ch2))
    return res

3、和谐值的计算

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。

现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述：

第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100 ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）

输出描述：

共1行，每行1个整数，表示满足整体是和谐的区间的数量。

解法：

来自牛客评论区

def myCompute3(M,A):
    n = len(A)
    count = 0
    note = dict()
    note[0] =1
    # # # # 先从区间数量开始遍历
    # for idx in range(1,n+1):
    #     # print(idx,end=", ")
    #     # 从起点开始遍历
    #     for start in range(0,n):
    #         end_idx = start+idx
    #         if end_idx>n : continue

    #         if sum(A[start:end_idx]) % M == 0:
              
    #             # print(A[start:end_idx])
    #             # print(start,end_idx,end="; ")
    #             count+=1
        # print(n)
    # map的作用  map 里面是sum 跟m取余之后的余数相同值的次数 ，  
    # 如果sum在累加过程中两次取余相等，那么第一次取余的sum
    # 和第二次取余的sum中间加的数列  一定是m的倍数
    sum = 0
    for i in range(n):
        sum += A[i]
        index = sum % M
        if index not in note:
            note[index] = 0
        # print(index)
        count += note[index]
        note[index] += 1
    print(count)

4、骰子分类

多多君拼团购买了N个骰子，为了方便后面进行活动，多多君需要将这些骰子进行分类。

两个骰子为同类的定义是：

将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等。

现在多多君想知道不同种类的骰子的数量分别有多少。

放弃了