leetcode解题记录

难度-简单
语言-python3

1.两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            second = target - nums[i]
            if second in nums:
                j = nums.index(second)
                if i!=j:
                    return [i,j]

知识点：

• python3函数写法：def twoSum(self, nums: List[int], target: int) -> List[int]:
• python获取元素下标：nums.index(second)

2.整数反转

class Solution:
   def reverse(self, x: int) -> int:
       if -2**31 <= x < 0:
           x = str(x)[1:]
           x = x[::-1].lstrip('0')
           if int(x) > 2**31:
               return 0
           else:
               return int('-' + x)
       elif x == 0:
           return 0
       elif x < 2**31:
           x = str(x)[::-1].lstrip('0')
           if int(x) >= 2**31:
               return 0
           else:
               return int(x)

知识点：

• 整数转字符串：str(number)
• 字符串转整数：int(string)
• 字符串反转：s = s[::-1]

3.回文数

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        if x == int(str(x)[::-1]):
            return True
        return False

4.*罗马数字转整数

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

5.最长公共前缀
成绩不错：

class Solution:
   def longestCommonPrefix(self, strs: List[str]) -> str:
       if len(strs)==0:
           return ""
       if len(strs)==1:
           return strs[0]
       pre = ""
       strs.sort()
       first = strs[0]
       for i in range(len(first),-1,-1):
           pre = first[:i]
           for j in range(1,len(strs)):
               if pre != strs[j][:i]:
                   pre = ""
           if pre!="":
               return pre
       return ""

5.有效的括号
第10次才通过

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2==1:
            return False
        a = {"(":")","[":"]","{":"}"}
        if s=="":
            return True
        if s[0] not in a:
            return False
        x = [s[0]]
        for i in range(1,len(s)):
            if len(x)==0:
                x.append(s[i])
                continue
            if a[x[len(x)-1]]==s[i]:
                x.pop()
            else:
                if s[i] in a:
                    x.append(s[i])
                else:
                    return False
        if len(x)!=0:
            return False
        return True

知识点：

• python数组弹出最后一个元素：list.pop()
• python数组末尾添加元素：list.append()

6.*合并两个有序链表

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val: l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2

知识点：

• python链表：定义、初始化
• python递归

7.删除排序数组中的重复项
这是一个极端。。。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        a = []
        for i in range(len(nums)):
            if nums[i] not in a:
                a.append(nums[i])
        for j in range(len(a)):
            nums[j]=a[j]
        return(len(a))

8.移除元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if val not in nums:
            return(len(nums))
        count = 0
        for i in range(len(nums)):
            if nums[i]==val:
                for j in range(i+1,len(nums)):
                    if nums[j]!=val:
                        nums[i],nums[j] = nums[j],nums[i]
                        count +=1
                        break;
            else:
                count+=1
        return(count)

9.实现strStr()

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle=="" or needle==haystack:
            return(0)
        if len(needle)>=len(haystack):
            return(-1)
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)]==needle:
                return(i)
        return(-1)

知识点：

• python获取子字符串：a=“abcdefg”,a[2:4]==“cd”

10.搜索插入位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        for i in range(len(nums)):
            if nums[i]>target:
                nums.insert(i,target)
                return(i)
        nums.append(target)
        return(len(nums)-1)

11.报数
拿题想了好一会。。。
12.最大子序和
13.最后一个单词的长度

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        if s=="":
            return(0)
        count = 0
        for i in range(len(s)-1,-1,-1):
            if s[i]!=" ":
                count+=1
            if s[i]==" " and count!=0:
                break
        return(count)

14.加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if digits==[9]:
            return([1,0])
        if digits[-1]!=9:
            digits[-1]+=1
            return(digits)
        else:
            a = self.plusOne(digits[:-1])
            a.append(0)
            return(a)

15.二进制求和

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return(bin(int(a,2)+int(b,2))[2:])

16.*x的平方根
算法超时

class Solution:
    def mySqrt(self, x: int) -> int:
        i = 2
        while (x/i)**2>x:
            i=i+1
        j = i-1
        i = x//i
        j = x//j+1
        def bi(x1,y,z):
            if y-x1==1:
                return(x1)
            middle = (x1+y)//2
            if middle**2 == z:
                return(middle)
            if middle**2 > z:
                return(bi(x1,middle,z))
            else:
                return(bi(middle,y,z))
        return(bi(i,j,x))

17.*爬楼梯
这个方法看着很巧妙，但是不懂。。
超时。。。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n - 1) + self.climbStairs(n - 2)