两数之和

题目给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍

题解思路
解法一双层for循环，外层控制循环次数，内层控制两数两两相加
解法二构建key、value值与可迭代对象num反转的字典，且已知target-num1 = num2，获得字典对应value（即可迭代对象对应的key），返回两个目标数字的下标

  1. """示例:
  2. 给定 nums = [2, 7, 11, 15], target = 9
  3. 因为 nums[0] + nums[1] = 2 + 7 = 9
  4. 所以返回 [0, 1]"""
  6. class Solution:
  8.     def twoSum(self, nums, target1):
  9.         getlen = len(nums)
  10.         for i in range(getlen):
  11.             neinum = getlen - i
  12.             for j in range(i+1, getlen):
  13.                 results = nums[i] + nums[j]
  14.                 if results == target1:
  15.                     return [i, j]
  16.                     break
  20. if __name__ == '__main__':
  21.     num = [2, 7, 11, 15]
  22.     target = 9
  23.     a = Solution()
  24.     print(a.twoSum(num, target))
  26. #解法二：哈希查询    
  27. class Solution:
  28.     def twoSum(self, nums, target):
  29.         dic = {}
  30.         for k, v in enumerate(nums):
  31.             if target - v in dic:  # 写之前判断，避免了重复元素的覆盖
  32.                 return [dic[target - v], k]
  33.             dic[v] = k
  36. if __name__ == '__main__':
  37.     num = [2, 7, 11, 72]
  38.     target1 = 9
  39.     a = Solution().twoSum(num, target1)
  40.     print(a)

整数反转

题目给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转
注意：假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2, 2− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0

题解思路
解法一整数转换成字符串，再根据字符串内建函数反转字符串
解法二利用取模运算（%）和取整除运算（//）

  1. class Soultion:
  2.     def reverse(self, x):
  3.         y, res = abs(x), 0
  4.         while y != 0:
  5.             verify = (2**31)-1 if x > 0 else (2**31)
  6.             # 循环取出末尾数并反转相加
  7.             res = res * 10 + y % 10
  8.             # 判断是否溢出
  9.             if res > verify:
  10.                 return 0
  11.             # 取整除
  12.             y //= 10
  13.         return res if x > 0 else -res

回文数

题目判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数
解题思路
解法一整数转换成字符串，再[::-1]反转字符串
解法二双指针，整数转换成列表，定义两个指针 L、R，对比是否list[L] ==list[R]

  1. class Solution1:
  2.     """回文数
  3.       转换成字符串"""
  4.     def isPalindrome1(self, x: int) -> bool:
  5.         if x < 0:
  6.             return False
  7.         elif x > 0:
  8.             res = str(x)
  9.             result = res[::-1]
  10.             # result = ''.join(reversed(res))
  11.             print(result)
  12.             return True if result == str(x) else False
  14. class Solution:
  15.     """双指针"""
  16.     def isPalindrome(self, x):
  17.         list_info = list(str(x))
  18.         L, R = 0, len(list_info) - 1
  19.         while L <= R:
  20.             if list_info[L] != list_info[R]:
  21.                 return False
  22.             L += 1
  23.             R -= 1
  24.         return True
  27. if __name__ == '__main__':
  28.     solution = Solution()
  29.     verify = solution.isPalindrome(0)
  30.     print(verify)

罗马数字转整数

题目罗马数字包含以下七种字符: 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 的范围内。

  1. 示例 1:
  2. 输入: "III"
  3. 输出: 3

解题思路 将罗马数字对应整数存在哈希表中，罗马数字前面的与后面的比较，小于则减，大于则加

class Solution:
    def romanToInt(self, s: str) -> int:

        dit_roman = {"I": 1,
                     "V": 5,
                     "X": 10,
                     "L": 50,
                     "C": 100,
                     "D": 500,
                     "M": 1000}
        int_roman = 0
        n = len(s)
        for i in range(n - 1):
            if dit_roman[s[i]] < dit_roman[s[i + 1]]:
                int_roman -= dit_roman[s[i]]
            else:
                int_roman += dit_roman[s[i]]
        return int_roman + dit_roman[s[-1]]

有效的括号

题目
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

解题思路构建哈希表，每次遇到右边括号则查询对应value，有则左边括号出栈（pop），到最后如果是空栈，则说明是有效括号

class Solution:
    def isValid(self, s: str) -> bool:
        # 构建哈希表
        dict_info = {")": "(", "]": "[", "}": "{"}
        stack = []
        for i in s:
            if i in "({[":
                stack.append(i)
            elif i in "}])":
                # 如果“}])”提前出线则提前结束
                if not stack:
                    return False
                # 如果出线右括号，查询哈希表右边括号是否等于对应的value
                if dict_info[i] == stack[-1]:
                    # 是则出栈
                    stack.pop(-1)
                else:
                    return False
        # 如果执行完毕栈为空，则括号有效
        if not stack:
            return True
        else:
            return False

最长公共前缀

题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
说明:
所有输入只包含小写字母 a-z 

示例 1:
q输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

解题思路
1.横向扫描
依次遍历字符串数组中的每个字符串,对于每个遍历到的字符串,更新最长公共前缀,遍历完所有字符串后,可得到字符串数组中的最长公共前缀
时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量
空间复杂度：O(1)

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs or not strs[0]:
            # 如果strs为空则返回空
            return ''
        count, prefix = len(strs), strs[0]
        for i in range(1, count):
            # 横向比较
            prefix = self.lcp(prefix, strs[i])
            if not prefix:
                break
        return prefix

    def lcp(self, str1, str2):
        # 两数比较
        lenth, index = min(len(str1), len(str2)), 0
        while index < lenth and str1[index] == str2[index]:
            index += 1
        # 返回最长公共前缀
        return str1[:index]

2.纵向扫描
从前完后遍历所有字符串的每一列,比较相同列上的字符串是否相同

class Solution:
    def longestCommonPrefix(self, strs) -> str:
        if not strs:
            return ""
        # 设置第一个字符串，获取元素字符串个数
        lenth, count = len(strs[0]), len(strs)
        for i in range(lenth):
            # 遍历第一个字符串
            c = strs[0][i]
            # 判断遍历超过当前字符串长度或者"列排"字符串不相等，则返回
            if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
                return strs[0][:i]

3.分治法
4.二分查找法

随机分配礼物

题目:有n个人,随机分配礼物,且不能分配到本人的礼物.
思路：
1.存参与的人
2.如果礼物没有被分配出去，则暂时pop出去，随机分配一个礼物
3.将自己未分配的礼物添加到未分配礼物中，参与分配

# 随机分配礼物且不分配到自己的礼物

gift_out = {'Jack': 'apple', 'Peter': 'beer', 'Tom': 'card', 'Duke': 'doll', 'Mary': 'pineapple',
              'James': 'flute',
              'Tina': 'coffee'}
gift_in = {}
persons = [p for p in gift_out.keys()]  # 获取参与人数

for p in persons:
    # 开始随机分配礼物
    flag = 0    # 标记礼物已分配
    if p in gift_out:
        # 如果自己礼物未分配，暂时丢弃
        flag = 1    # 标记礼物未分配
        my_gift = gift_out.pop(p)
    get_gift = gift_out.popitem()
    gift_in[p] = get_gift[1]
    if flag == 1:
        gift_out[p] = my_gift
print(gift_in)