LEETCODE-算法刷题-简单(1)

1216-皇甫同学

发表文章数:34

热门标签

首页 » LeetCode » 正文

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, LCD 和 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

 

 

标签:

拜师教育学员文章:作者:1216-皇甫同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《LEETCODE-算法刷题-简单(1)》 发布于2020-08-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录