1、两数之和

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/two-sum

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

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

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

解题思路，这道题能用双指针和哈希表两种方法完成，这里只写了一次哈希表的方法。

简单来说，一次哈希表就是依次遍历整个数组，每遍历一个数，就把他保存到哈希表（字典里），然后用目标值减去这个数，看是否已经有数值保存进哈希表里。

在构造哈希表时，要将数值做为哈希表的键，将数值在数组的位置作为哈希表的值，这样方便后续返回数组下标。
 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        a=0
        for i in nums:
            if target-i in hashmap :
                return[a,hashmap[target-i]]
            hashmap[i]=a
            a+=1
#执行用时：68 ms，超过70%
#内存消耗：15 MB，超过41%

7、整数反转

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-integer

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

（1）输入: 123         （2）输入: -123       （3）输入: 120
     输出: 321             输出: -321            输出: 21

解题思路，首先因为有存储限制，所以在输入和输出的时候都要进行一次判断是否超出数值范围。其他的操作就很简单，把数字当字符串进行处理，依次进行反转，然后int一下就行。后来看题解，才发现直接用切片来做也可以，相当于把切片重写了一遍。

class Solution:
    def reverse(self, x: int) -> int:
        y=[]
        a=str(x)
        if x>2**31-1 or x<-2**31:
            return 0
        elif x==0:
            return 0
        else:
            if x>0:
                for i in range(len(a)-1,-1,-1):
                    y.append(a[i])
                z=int(''.join(y))
            else:
                for i in range(len(a)-1,0,-1):
                    y.append(a[i])
                z=int(''.join(y))*-1
        if z>2**31-1 or z<-2**31:
            return 0
        else:
            return z
#执行用时：44 ms, 在所有 Python3 提交中击败了68.57%的用户
#内存消耗：13.6 MB, 在所有 Python3 提交中击败了76.15%的用户

11、盛最多水的容器

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/container-with-most-water

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

输入：[1,8,6,2,5,4,8,3,7]
输出：49

解题思路，误打误撞算是用上了双指针的方法，简单来说就是对于两个确定范围内，如边界的1,7，现在能盛的水是二者较小值1的盛水的最大值，所以将左边的边界往右推一格，【8,7】，这个时候8>7，现在是边界7能盛水的最大值，将右边的边界往左推一格，这样依次进行，将所有的高度遍历一遍得到每个高度盛水的最大值，然后取他们的最大值，就是最大盛水量。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        s_max=0
        j=len(height)-1
        i=0
        while i!=j:
            s=(j-i)*min(height[i],height[j])
            if s>=s_max:
                s_max=s
            if height[i]>height[j]:
                j-=1
            else:
                i+=1
        return s_max
#执行用时：72 ms, 在所有 Python3 提交中击败了60.00%的用户
#内存消耗：15.1 MB, 在所有 Python3 提交中击败了48.05%的用户

13、罗马数字转整数

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/roman-to-integer

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

例如， 罗马数字 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 的范围内。

解题思路，这些组4和9并不会重复出现，可以将这些特殊罗马数字替换成别的字母来表示（要注意，罗马数字里有C，D，不要重复赋值），替换后直接遍历得到值相加就行了。

还有一种解法，是直接进行遍历，在遍历的时候，对当前字母和后面的字母进行一次对比，如果是当前字母代表数值小于后面的数值，则为负数，如果是大于后面的数值则为正数。

class Solution:
    def romanToInt(self, s: str) -> int:
        nums={'A':4,'B':9,'G':40,'H':90,'E':400,'F':900,'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        ss=s.replace('IV','A').replace('IX','B').replace('XL','G').replace('XC','H').replace('CD','E').replace('CM','F')
        number=0
        for i in ss:
            number += nums[i]
        return number
#执行用时：56 ms，超过85%
#内存消耗：13.6 MB，超过86%

14、最长公共前缀

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

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

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

解题思路，开始的时候是想用暴力破解，依次遍历每个字符串的找到相同的字符。

后面看了题解，发现还有用zip()特性来进行解题的方法，zip()对两个字符串压缩的时候，会把每个字符串相同位置的字符并列存储，如123和456压缩后是14,25,36，所以根据这个特性能够很方便的找到字符串的相同字符，在字符不同的地方停止遍历，就得到了最长公共前缀。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ''
        for i in zip(*strs):
            if len(set(i)) == 1:
                ans += i[0]
            else:
                break
        return ans

分享到：

赞(0) 打赏