算法题练习——python题解BM20 数组中的逆序对和BM22 比较版本号

妖狐艹你老母 2024-04-07 16:03 76阅读 0赞

**目录**

BM20 数组中的逆序对

BM22 比较版本号

--------------------

### BM20 数组中的逆序对 ###

**描述**

> 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

**数据范围：**

> 对于 50% 的数据, size≤10^4  
> 对于 100% 的数据, size≤10^5

> 数组中所有数字的值满足 0 ≤val≤1000000

**要求：**

> 空间复杂度 O(n)，时间复杂度 O(nlogn)

**输入描述：**

> 题目保证输入的数组中没有的相同的数字

**示例1**

> 输入：\[1,2,3,4,5,6,7,0\]
> 
> 返回值：7

**示例2**

> 输入：\[1,2,3\]
> 
> 返回值：0

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param data int整型一维数组 
    # @return int整型
    #
    class Solution:
        def InversePairs(self , data: List[int]) -> int:
            # write code here
            return self.recur(data)%1000000007
        def recur(self, arr):
            if len(arr)<=1:
                return 0
            b, s = [], []
            res, pre = 0,arr[0]
            for n in arr[1:]:
                if n>pre:
                    b.append(n)
                else:
                    s.append(n)
                    res += len(b)+1
            return res+self.recur(b)+self.recur(s)

--------------------

### BM22 比较版本号 ###

**描述**

> 牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
> 
> 现在给你2个版本号version1和version2，请你比较他们的大小
> 
> 版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
> 
> 每个版本号至少包含1个修订号。
> 
> 修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

**比较规则：**

> 1.  比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
> 2.  如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
> 3.  version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

**数据范围：**

> 1 <= version1.length, version2.length <= 1000，version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围

> 进阶： 时间复杂度 O(n)O(n)

**示例1**

> 输入："1.1","2.1"
> 
> 返回值：-1
> 
> 说明：version1 中下标为 0 的修订号是 "1"，version2 中下标为 0 的修订号是 "2" 。1 < 2，所以 version1 < version2，返回-1

**示例2**

> 输入："1.1","1.01"
> 
> 返回值：0
> 
> 说明：version2忽略前导0，为"1.1"，和version相同，返回0

**示例3**

> 输入："1.1","1.1.1"
> 
> 返回值：-1
> 
> 说明："1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1

**示例4**

> 输入："2.0.1","2"
> 
> 返回值：1
> 
> 说明：version1的下标2>version2的下标2，返回1

**示例5**

> 输入："0.226","0.36"
> 
> 返回值：1
> 
> 说明：226>36，version1的下标2>version2的下标2，返回1

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 比较版本号
    # @param version1 string字符串 
    # @param version2 string字符串 
    # @return int整型
    #
    class Solution:
        def compare(self , version1: str, version2: str) -> int:
            # write code here
            n1 = version1.split('.')
            n2 = version2.split('.')
            l1 = len(n1)
            l2 = len(n2)
            if l1<=l2:
                for i in range(l1):
                    if int(n1[i])>int(n2[i]):
                        return 1
                    elif int(n1[i])<int(n2[i]):
                        return -1
                    else:
                        continue
                return 0
            else:
                for i in range(l2):
                    if int(n1[i])>int(n2[i]):
                        return 1
                    elif int(n1[i])<int(n2[i]):
                        return -1
                    else:
                        continue
                return 1