Python算法题目汇总

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

# 耗时28s 耗内存：14.9M 
# 前一个数循环和后面的数对比，看是否符合条件
class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(len(nums)):
                if nums[i] + nums[j] == target and i != j:
                    return [i,j]
if __name__ == '__main__':
    ts = Solution()
    print(ts.twoSum([3,2,4 ], 6))

2. 整数反转

给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321

# 耗时36s 耗内存：14.9M 
# 将整数转化为字符串，判断是否带负号，有负号提出负号翻转(翻转后添加负号即可)，无负号直接翻转，最后判断是否在范围内，在则返回不在则返回0.
class Solution:
    def reverse(self, x: int) -> int:
        if str(x)[0] == '-':
            new_x = int('-' + str(x)[1:][::-1])
        else:
            new_x = int(str(x)[::-1])
        return new_x if -2**31 <= new_x <= 2**31-1 else 0
if __name__ == '__main__':
    sl = Solution()
    print(sl.reverse(-5612345))

3. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 ture ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true
示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

# 耗时68s 耗内存：14.8M 
# 判断该数字与逆序之后是否相等
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x = str(x)
        return True if x == x[::-1] else False
if __name__ == '__main__':
    ipd = Solution()
    print(ipd.isPalindrome(12321))

4. 罗马数字转换整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

输入: “III”
输出: 3

输入: “IV”
输出: 4

输入: “IX”
输出: 9

输入: “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

输入: “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

"""
通过观察我们发现，只有在遇到特殊情况时，两个字符中左边的字符小于右边的字符，且等于右边的字符代表的数减左边字符代表的数。 比如 CM 等于 1000 - 1001000−100，XC 等于 100 - 10100−10...
因此，我们将 字符：数值 存在 rT 的哈希表中。然后从左到右遍历每个字符，如果 s[i] < s[i+1]，就将结果减去 s[i] 代表的数字；否则，将结果加上 s[i] 代表的数字
"""
class Solution:
    def romanToInt(self, s: str) -> int:
        rT = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        num = 0
        n = len(s)
        for i in range(n-1):
            if rT[s[i]] < rT[s[i+1]]:
                num -= rT[s[i]]
            else:
                num += rT[s[i]]
        return num+rT[s[-1]]
if __name__ == '__main__':
    st = Solution()
    print(st.romanToInt('CMXCIV'))

5. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

class Solution:
    def longestCommonPrefix(self, strs):
        out_str = ''
        for i in zip(*strs):
            if len(set(i)) == 1:
                out_str += i[0]
            else:
                break
        return out_str
if __name__ == '__main__':
    strs = ["flower", "flow", "flight"]
    st = Solution()
    print(st.longestCommonPrefix(strs))  # fl
"""
zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的对象，这样做的好处是节约了不少的内存。
我们可以使用 list() 转换来输出列表。
如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表
"""
strs = ["flower", "flow", "flight"]
print(list(zip(*strs)))   # [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]