LeetCode简单题目-2019.10.10-10.11-8道

- 日理万妓 2023-06-06 12:25 69阅读 0赞

leetcode题库中共有350道简单题目。
本文记录已解决的题目和代码。
本文中的序号是leetcode题目中的真实序号。

文章目录

  • 1 两数之和
    • 描述
    • 思路
    • 代码
  • 7 整数反转
    • 描述
    • 思路
    • 代码
  • 9 回文数
    • 描述
    • 思路
    • 代码
    • 进阶版
  • 13 罗马数字转整数
    • 描述
    • 代码
  • 14 最长公共前缀
    • 描述
    • 代码
    • 大神解法
  • 20 有效的括号
    • 描述
    • 代码
    • 大神解法
  • 21 合并两个有序链表
    • 描述
    • 代码
  • 26 删除排序数组中的重复项
    • 描述
    • 代码
    • 大神解法

1 两数之和

描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

利用python的in语句。判断target-nums[i]是否在nums中

代码

  1. class Solution(object):
  2.     def twoSum(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: List[int]
  7.         """
  8.         list,nums_n = [],nums[:]
  9.         for i in range(len(nums)):
  10.             nums_n.remove(nums[i])
  11.             if (target-nums[i]) in nums_n:
  12.                 m = nums_n.index(target-nums[i])+i+1
  13.                 list.append(i)
  14.                 list.append(m)
  15.                 return list

7 整数反转

描述

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

思路

转化为字符串反转

代码

  1. class Solution(object):
  2.     def reverse(self, x):
  3.         """
  4.         :type x: int
  5.         :rtype: int
  6.         """
  7.         # 处理溢出情况
  8.         x_min,x_max = -2**31,2**31-1
  9.         if x < x_min or x > x_max or not x:
  10.             return 0
  11.         # 处理尾数是0情况
  12.         while not x % 10:
  13.             x = x / 10
  14.         # 处理负数情况
  15.         neg_flag = 0    
  16.         x_str = str(x)
  17.         if '-' in x_str:    
  18.             x_str = x_str[1:]
  19.             neg_flag = 1
  20.         # 整数反转
  21.         x_reverse_str = ''
  22.         for i in x_str:
  23.             x_reverse_str = i + x_reverse_str
  25.         if neg_flag:
  26.             x_reverse = -int(x_reverse_str)
  27.         else:
  28.             x_reverse = int(x_reverse_str)
  29.         if x_reverse < x_min or x_reverse > x_max:
  30.                 return 0
  31.         return x_reverse

9 回文数

描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121 输出: true
示例 2:
输入: -121 输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10 输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:
你能不将整数转为字符串来解决这个问题吗？

思路

利用字符串列表函数[::-1]

代码

  1. class Solution(object):
  2.     def isPalindrome(self, x):
  3.         """
  4.         :type x: int
  5.         :rtype: bool
  6.         """
  7.         if x < 0:
  8.             return bool(0)
  9.         x_str = str(x)
  10.         return x_str[::-1] == x_str

进阶版

  1. class Solution(object):
  2.     def isPalindrome(self, x):
  3.         """
  4.         :type x: int
  5.         :rtype: bool
  6.         """
  7.         if x < 0:
  8.             return bool(0)
  9.         x_re_list = []
  10.         while x:
  11.             x_re_list.append(x%10)
  12.             x = x // 10
  13.         return x_re_list[::-1] == x_re_list

13 罗马数字转整数

描述

罗马数字包含以下七种字符: 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。数字 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 的范围内。

示例 1:
输入: “III” 输出: 3
示例 2:
输入: “IV” 输出: 4
示例 3:
输入: “MCMXCIV” 输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

代码

  1. class Solution(object):
  2.     def romanToInt(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         number= 0
  8.         luoma_dic = {
  9.     'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
  10.         special_dic = {
  11.     'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}
  12.         for i,j in special_dic.items():
  13.             if i in s:
  14.                 number += j
  15.                 s = s.replace(i,'')
  16.         for i in s:
  17.             number += luoma_dic[i]
  18.         return number
  20. class Solution(object):
  21.     def romanToInt(self, s):
  22.         """
  23.         :type s: str
  24.         :rtype: int
  25.         """
  26.         number,s_len = 0,len(s)
  27.         luoma_dic = {
  28.     'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
  29.         for i in range(s_len-1):
  30.             if luoma_dic[s[i]] >= luoma_dic[s[i+1]]:
  31.                 number += luoma_dic[s[i]]
  32.             else:
  33.                 number -= luoma_dic[s[i]]
  34.         number += luoma_dic[s[s_len-1]]
  35.         return number

牛人代码
作者：QQqun902025048
链接：https://leetcode-cn.com/problems/roman-to-integer/solution/2-xing-python-on-by-knifezhu/

  1. class Solution:
  2.     def romanToInt(self, s: str) -> int:
  3.         d = {
  4.     '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}
  5.         return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

注意’IV’:3，‘IX’:8。 等。此乃算法巧妙之处。
如IV，算了两次，先算I:1，再算IV:3,1+3即是IV真实值4

14 最长公共前缀

描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1:
输入: [“flower”,“flow”,“flight”]
输出: “fl”
示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

代码

  1. class Solution(object):
  2.     def longestCommonPrefix(self, strs):
  3.         """
  4.         :type strs: List[str]
  5.         :rtype: str
  6.         """
  7.         if len(strs) == 1:
  8.             return ''
  9.         com_str = ''
  10.         for i in range(len(strs)-1):
  11.             if not strs[i] or not strs[i+1]:
  12.                 return ''
  13.             j = 0
  14.             temp_str = ''
  15.             while strs[i][j] == strs[i+1][j]:
  16.                 temp_str += strs[i][j]
  17.                 j += 1
  18.                 if j == len(strs[i]) or j == len(strs[i+1]):
  19.                     break
  20.             if len(temp_str) < len(com_str):
  21.                 com_str = temp_str
  22.             if not com_str:
  23.                 com_str = temp_str
  24.             if not temp_str:
  25.                 return temp_str
  26.         return com_str

大神解法

1、利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，
举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀

  1. def longestCommonPrefix(self, strs):
  2.     if not strs: return ""
  3.     s1 = min(strs)
  4.     s2 = max(strs)
  5.     for i,x in enumerate(s1):
  6.         if x != s2[i]:
  7.             return s2[:i]
  8.     return s1

2、利用python的zip函数，把str看成list然后把输入看成二维数组，
左对齐纵向压缩，然后把每项利用集合去重，之后遍历list中找到元素长度大于1之前的就是公共前缀

  1. def longestCommonPrefix(self, strs):
  2.     if not strs: return ""
  3.     ss = list(map(set, zip(*strs)))
  4.     res = ""
  5.     for i, x in enumerate(ss):
  6.         x = list(x)
  7.         if len(x) > 1:
  8.             break
  9.         res = res + x[0]
  10.     return res

20 有效的括号

描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()[]{}” 输出: true
示例 2:
输入: “(]” 输出: false
示例 3:
输入: “([)]” 输出: false
示例 4:
输入: “{[]}” 输出: true

代码

  1. class Solution(object):
  2.     def isValid(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: bool
  6.         """
  7.         pair_str_list = []
  8.         pair_dic = {
  9.     '(':')','[':']','{':'}'}
  10.         pair_re_dic = {
  11.     ')':'(',']':'[','}':'{'}
  12.         for i in s:
  13.             if not pair_str_list:
  14.                 pair_str_list.append(i)
  15.             elif i in pair_re_dic and pair_re_dic[i] in pair_str_list:
  16.                 temp = pair_str_list.pop()
  17.                 if temp != pair_re_dic[i]:
  18.                     return False
  19.             else:
  20.                 pair_str_list.append(i)
  21.         if pair_str_list:
  22.             return False
  23.         return True

大神解法

  1. class Solution:
  2.     def isValid(self, s):
  3.         while '{}' in s or '()' in s or '[]' in s:
  4.             s = s.replace('{}', '')
  5.             s = s.replace('[]', '')
  6.             s = s.replace('()', '')
  7.         return s == ''

21 合并两个有序链表

描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码

  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. #    def __init__(self, x):
  4. #       self.val = x
  5. #        self.next = None
  7. class Solution(object):
  8.     def mergeTwoLists(self, l1, l2):
  9.         """
  10.         :type l1: ListNode
  11.         :type l2: ListNode
  12.         :rtype: ListNode
  13.         """
  14.         L = l3 = ListNode(0)
  15.         while l1 and l2:
  16.             if l1.val < l2.val:
  17.                 l3.next = l1
  18.                 l1 = l1.next
  19.             else:
  20.                 l3.next = l2
  21.                 l2 = l2.next
  22.             l3 = l3.next
  23.         if l1:
  24.             l3.next = l1
  25.         else:
  26.             l3.next = l2
  27.         return L.next

26 删除排序数组中的重复项

描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

代码

  1. class Solution(object):
  2.     def removeDuplicates(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int
  6.         """
  7.         i = 0
  8.         while i < len(nums):
  9.             if not i:
  10.                 i += 1
  11.                 continue
  12.             if nums[i] == nums[i-1]:
  13.                 nums.remove(nums[i])
  14.                 i -= 1
  15.             i += 1
  16.         return len(nums)

大神解法

  1. def removeDuplicates(self, nums: List[int]) -> int:
  2.     flag = 0                  # 定义一个指针变量
  3.     for num in nums:          # 遍历数组
  4.         if nums[flag] != num: # 若指针指向的元素与当前遍历数组的元素不同
  5.             flag += 1         # 指针后移一位
  6.             nums[flag] = num  # 修改数组，将不同的元素占用重复元素的位置
  7.         # 若相同则指针不动，数组继续往后遍历
  8.     # 注意考虑数组为空的情况（flag初始值为0，由于要求数组长度，故需要加1）
  9.     return flag + 1

发表评论

表情：
评论列表 （有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读