每日Leetcode—算法（1）

1.两数之和

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

算法一：

for i in range(len(nums)):
    for j in range(i+1,len(nums)):
        if nums[i]+nums[j] == target
            return i,j

分析：暴力检索，使用两个for循环进行目标查找，但是该方法的时间复杂度为O(n2)。

算法二：

dict = {}
for i in range(len(nums)):
    a = target - nums[i]
    if a in dict:
        return dict[a],i
    else:
        dict[nums[i]] = i

分析：该算法使用hash table方法，在Python中就是dict字典，该方法的时间复杂度为O(n)，然而加入了一个dict字典，空间复杂度升高。是一个时间与空间的trade-off。
其中dict字典里包含的数据为{'数据':数组下标}，只要找到目标数据，就返回下标，未找到目标时，将该数据加入到字典中。

7.整数反转

示例 :
输入: -123，输出: -321； 输入: -123，输出: -321； 输入: 120，输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

算法一：

def reverse(self, x: int) -> int:
    num=0
    if x == 0
        return 0
    if x<0:
        x = -x
        while x!=0:
            num = num*10 + x%10
            x = x//10
    else:
        while x!=0:
            num = num*10 + x%10
            x = x//10
    if num>(2**31)-1 or num<(-2)**31:
        return 0
    return num

分析：该算法使用了数学计算，涉及到取模与取整。

算法二：

plus_minus = ''
reverse_x = ''
if x<0:
    plus_minus = '-'
for i in str(x):
        reverse_x = i + reverse_x
reverse_x = plus_minus + reverse_x
if int(reverse_x)>(2**31-1) or int(reverse_x)<(-2)**31:
    return 0
return int(reverse_x)

分析：该算法将整数转换为字符。另外还可以将转换后的字符串list化，然后利用reverse()函数进行数列反转。

9.回文数

示例：
输入: 121，输出: true；
输入: -121，输出: false，解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入: 10，输出: false，解释: 从右向左读, 为 01 。因此它不是一个回文数。

算法一：

        if x<0:
            return False
        if x == 0:
            return True
        reverse_x = ''
        for i in str(x):
            reverse_x = i + reverse_x
        if int(reverse_x) == x:
            return True
        return False

分析：首先排除0或负数，然后将整数字符化，进行反转后对比。

算法二：

    def isPalindrome(self, x: int) -> bool:
        nums = 0
        origin = x
        if x<0:
            return False
        if x == 0:
            return True
        while x!=0:
            nums = nums*10 + x%10
            x = x//10
        if nums == origin:
            return True
        else:
            return False

分析：思路与整数反转相似，首先排除0或负数，然后将整数进行取模取整变换。

13.罗马数字转整数

示例 :
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
题目参见：https://leetcode-cn.com/problems/roman-to-integer/

dic = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
ans = 0
i = 0
while i<len(s)-1:
    if dic[s[i]]<dic[s[i+1]]:
        ans += dic[s[i+1]] - dic[s[i]]
        i += 2
    else:
        ans += dic[s[i]]
        i += 1
if i<len(s):
    ans += dic[s[len(s)-1]]
return ans

分析：首先使用字典将罗马字符与数字对应，然后while循环进行转换，第一个if-else判断是否有特殊情况，因为while循环需要查看最后一个字符，故while循环只能在倒数第二个字符停止。所以需要用最后的if条件句对最后一个字符进行相加。