10.17-10.21 leetcode基于python刷题

运行速度啥的大家就看看，感觉这不是很能作为参考依据，跟网络状态挺有关系的，即是相同的代码运行出来也不同。

1.Two Sum(Easy)

'''
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

给定一个整数数组nums和一个整数目标，返回两个数字的索引，使它们相加等于目标。
你可以假设每个输入都会有一个确切的解决方案，而且你不能两次使用同一个元素。
你可以按任何顺序返回答案。
'''

思路

解法1.for循环遍历所有可能，找到答案
解法2. 找到（整数目标-元素值）的下标，注意审题“不能两次使用同一个元素”
这样，又衍生出两种解法：
1）用.index()函数直接找到（整数目标-元素值）的下标并判断是否是一个元素。
2）用字典dic保存（整数目标-元素值）的下标，不在dic中就存入，直到另一半出现。

代码实现

class Solution1(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

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

class Solution2(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        dic = {}

        for i in range(len(nums)):
            if target - nums[i] not in dic:
                dic[nums[i]] = i
            else:
                return [dic[target-nums[i]],i]

class Solution3(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        for i in range(len(nums)):
            if target - nums[i] in nums and i != nums.index(target - nums[i]):
                return [i,nums.index(target - nums[i])]


list1 = [2,3,5,6,78,5]
list2 = [2,3,5,6,78,5]
list3 = [2,3,5,6,78,5]

sol1 = Solution1()
sol2 = Solution2()
sol3 = Solution3()
print(sol1.twoSum(list1,5))
print(sol2.twoSum(list2,5))
print(sol3.twoSum(list2,5))

运行速度

9.Palindrome Number(Easy)

'''
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
For example, 121 is a palindrome while 123 is not.

给定一个整数x，如果x是回文整数，返回true。
当一个整数向后读与向前读相同时，它就是一个回文。
例如，121是一个调色板，而123不是。
'''

思路

解法1.将int型通过str()、list()、reversed()函数进行比转换。
解法2.利用循环，以此获得数字的每一位，再形成回文数。

代码实现

class Solution1(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        x1 = str(x)
        s1 = list(reversed(str(x)))
        s1 = ''.join(s1)
        if s1 == x1:
            return True
        else:
            return False

class Solution2(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        num = 0
        a = abs(x)

        while(a!=0):
            temp = a % 10
            num = num * 10 + temp
            a = a // 10

        if x >= 0 and x == num:
            return True
        else:
            return False


sol1 = Solution1()
sol2 = Solution1()
s1 = sol1.isPalindrome(1234321)
s2 = sol2.isPalindrome(123432)
print(s1,s2)

sol3 = Solution2()
sol4 = Solution2()
s3 = sol3.isPalindrome(1234321)
s4 = sol4.isPalindrome(123432)
print(s3,s4)

运行速度

13.Roman to Integer(Easy)

'''
oman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II.
The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII.
Instead, the number four is written as IV. Because the one is before the five we subtract it making IV.
The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].

罗马数字由七个不同的符号表示。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。
因为一在五的前面，我们把它减去就成了四。同样的原则也适用于数字9，它被写成IX。有六种情况用到了减法。
I可以放在V（5）和X（10）之前，组成4和9。
X可以放在L（50）和C（100）之前，组成40和90。
C可以放在D（500）和M（1000）之前，组成400和900。
给出一个罗马数字，把它转换成一个整数。
1 <= s.length <= 15
s只包含字符（'I', 'V', 'X', 'L', 'C', 'D', 'M'）。
保证s是一个有效的罗马数字，范围是[1, 3999]。
'''

思路

解法1.建立两个字典：一个是单字母的，一个是两字母的，每次读入两个字符，先判断是否在两字母字典里，并累加，下标向后移动2；若不在两字母字典里，则使用单字母字典，并累加，下标向后移动1.
解法2.事实上，出现减法的情况仅限于后面的罗马数字＞前面的罗马数字，因此只有做一次判断即可。同时需要注意，如果后面的罗马数字＞前面的罗马数字，累加并不是加dic[s[i]] - dic[s[i-1]]，例如‘MCM’,i=0，M；i=1，M+C；i=2时，发现M>C，那么CM要连起来一起看成是M-C，但同时i=1已经算了一遍C，所以此时要减去，即是M+C+M-2C，即dic[s[i]] - 2 * dic[s[i-1]]。

代码实现

class Solution1(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """

        dic1 = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        dic2 = {'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}

        sum = 0
        i = 0
        while i < len(s):
            temp1 = ''.join(s[i:i+2])
            temp2 = s[i]
            if temp1 in dic2.keys():
                sum += dic2[temp1]
                i += 2
            else:
                sum += dic1[temp2]
                i += 1
        return sum

class Solution2(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """

        dic = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        result = 0

        for i in range(len(s)):
            if i > 0 and dic[s[i]] > dic[s[i-1]]:
                result += dic[s[i]] - 2 * dic[s[i-1]]
            else:
                result += dic[s[i]]
        return result

sol1 = Solution1()
s1 = sol1.romanToInt('MCMXCIV')
print(s1)

sol2 = Solution2()
s2 = sol2.romanToInt('MCMXCIV')
print(s2)

运行速度

14. Longest Common Prefix(Easy)

'''
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string

编写一个函数，在一个字符串数组中找到最长的共同前缀字符串。
如果没有共同的前缀，则返回一个空字符串。
'''

思路

解法1.依次将从第二个元素开始之后的元素的每一位与第一个元素的每一位进行比较，注意位数。
解法2.用set()方法获取每一个元素的每一位的字母集合，若长度为1，则说明为同一个单词。

代码实现

class Solution1(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        if not strs:
            return ''

        for i in range(len(strs[0])):
            for string in strs[1:]:
                if i >= len(string) or string[i] != strs[0][i]:
                    return strs[0][:i]

        return strs[0]

class Solution2(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        i = 0
        result = ''

        while True:
            try:

                sets = set(string[i] for string in strs)
                if len(sets) == 1:
                    result += sets.pop()
                    i += 1
                else:
                    break
            except Exception as e:
                break

        return result


s1 = Solution1()
s1 = s1.longestCommonPrefix(["flower","flow","flight"])
s2 = Solution1()
s2 = s2.longestCommonPrefix(["dog","racecar","car"])
print(s1,s2)

运行速度

12. Integer to Roman(Medium)

'''
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral.

罗马数字由七个不同的符号表示。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。相反，四的数字被写成四。因为一在五的前面，我们把它减去就成了四。同样的原则也适用于数字9，它被写成IX。有六种情况用到了减法。
I可以放在V（5）和X（10）之前，组成4和9。
X可以放在L（50）和C（100）之前，组成40和90。
C可以放在D(500)和M(1000)之前，组成400和900。
给出一个整数，把它转换成罗马数字。
'''

思路

解法1.从数字的每一位出发，对数字进行分类，总共包括4种情况：1）a[i] 不等于4且a[i]小于5，加对应（10的次方）对应的字符；2）a[i] 不等于9且a[i]大于5，先加对应5（10的次方）对应的字符，再加对应（10的次方）对应的字符；3）a[i]等于5，加对应5（10的次方）对应的字符；4）a[i]等于4或9，加对应（10的次方）对应的字符。
解法2.从数字本身出发，所有情况列举出来，每次找到对应情况后，减去这个数字。

代码实现

class Solution1(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """

        dic1 = {1: 'I',5 : 'V',10 : 'X',50 : 'L',100 : 'C',500 : 'D', 1000:'M'}
        dic2 = {4: 'IV',9:'IX',40 :'XL',90 :'XC',400 :'CD',900 :'CM'}

        a = []

        while(num!=0):
            temp = num % 10
            a.append(temp)
            num = num // 10

        a.reverse()
        result = []
        i = 0
        while i < len(a):
            if a[i] != 4 and a[i] < 5:
                for j in range(a[i]):
                    result.append(dic1[10**(len(a)-i-1)])
                i += 1
            elif a[i] != 9 and a[i] > 5:
                result.append(dic1[10 ** (len(a) - i - 1) * 5])
                for j in range(a[i]-5):
                    result.append(dic1[10**(len(a)-i-1)])
                i += 1
            elif a[i] == 5:
                result.append(dic1[10 ** (len(a)-i-1)*5])
                i += 1
            else:
                result.append(dic2[10**(len(a)-i-1)*a[i]])
                i += 1

        return ''.join(result)

class Solution2(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """

        v = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        n = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']

        result = ''
        for i in range(len(v)):
            while num >= v[i]:
                num -= v[i]
                result += n[i]
        return result

s1 = Solution1()
s1 = s1.intToRoman(58)
print(s1)

s2 = Solution2()
s2 = s2.intToRoman(3)
print(s2)

运行速度

11. Container With Most Water(Medium)

'''
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.

给你一个长度为n的整数数组height。有n条垂直线，使第i条线的两个端点为（i，0）和（i，height[i]）。
找出两条线，它们与x轴一起构成一个容器，使该容器中的水最多。
返回一个容器所能储存的最大水量。
'''

思路

解法1.计算所有water，最终取最大值
解法2.从两边开始，每次向内移动一次，尽量保存更高的一根柱子

代码实现

class Solution1(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        t = []
        n = len(height)
        for i in range(n):
            for j in range(i+1,n):
                t.append((j-i)*min(height[i], height[j]))

        return max(t)

class Solution2(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        left = 0
        right = len(height) - 1
        result = 0

        while left < right:
            water = min(height[left],height[right])*(right - left)

            if water > result:
                result = water

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return result

s1 = Solution1()
s1 = s1.maxArea([1,8,6,2,5,4,8,3,7])
print(s1)

s2 = Solution2()
s2 = s2.maxArea([1,8,6,2,5,4,8,3,7])
print(s2)

运行速度

很奇怪，个人觉得思路一是正确是，运行多次也是对的，但在官网上显示超时。

66. Plus One(Easy)

'''
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.

给你一个大的整数，用一个整数数组digits表示，其中每个digits[i]是整数的第i位。这些数字是按照从左到右的顺序从最有意义到最无意义排列的。大整数不包含任何前导0。
将大整数递增1，并返回所得到的数字数组。
'''

思路

转换为整数后+1，再转化为字符串，把每一位输入列表。

代码实现

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """

        s = ""
        for i in digits:
            s = s + str(i)

        a = int(s)
        a = a + 1
        a = str(a)

        list1 = []
        for i in a:
            list1.append(i)

        return list1

s = Solution()
s = s.plusOne([9])
print(s)

运行速度

15. 3Sum(Medium)

'''
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

给出一个整数数组nums，返回所有的三联体[nums[i], nums[j], nums[k]]，使得i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0。
请注意，解集不能包含重复的三联体。
'''

思路

解法1.使用1.Two Sum(Easy)的思路，只不过两数的和变成-nums[i]，得到的结果会有重复，注意去重。
解法2.使用双指针。先对数组排好序，若 nums[i] >0 ，则 i 之后的三元组之和不可能为0 ，结束。如果 nums[i] 与之前的元素重复，即跳过。左指针 设为 i+1 ，右指针设为 n-1。如果nums[i] + nums[left] + nums[right] == 0 加入答案列表，如果nums[lef] 与nums[left+1]重复，则 left 递增，同理，但right 是递减。如果nums[i] + nums[left] + nums[right] >0 , right-=1； 反之left +=1

代码实现

import copy

class Solution1(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        def twosum(li, target, m, l_result):
            dic = {}
            for i in range(0, len(li)):
                if i != m and target - li[i] not in dic:
                    dic[li[i]] = i
                elif i > m and dic[target - li[i]] > m:
                    result = [li[m], target - li[i], li[i]]
                    l_result.append(sorted(result))
            return l_result

        result = []
        for k in range(len(nums)):
            target = - nums[k]
            twosum(nums, target, k, result)
        result2 = copy.copy(result)
        for item in result2:
            count = result.count(item)
            if count > 1:
                for k in range(count-1):
                    result.remove(item)
        return result

class Solution2(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []

        lens = len(nums)
        if lens < 3: return []
        nums.sort()
        for i in range(lens):
            if nums[i] > 0:  # 数组已经排好序，后面大于0的数，和都不为0
                res
            if i > 0 and nums[i] == nums[i - 1]:  # 对于重复元素，跳过，避免出现重复解
                continue
            left = i + 1
            right = lens - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        return res

s1 = Solution1()
s1 = s1.threeSum([-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0])
print(s1)

s2 = Solution2()
s2 = s2.threeSum([-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0])
print(s2)

运行速度

solotion1由于时间复杂度问题，运行超时，但运算了几个以后发现都是对的

记录一下