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

- 日理万妓 2023-06-06 12:25 2阅读 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中

## 代码 ##

class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            list,nums_n = [],nums[:]
            for i in range(len(nums)):
                nums_n.remove(nums[i])
                if (target-nums[i]) in nums_n:
                    m = nums_n.index(target-nums[i])+i+1
                    list.append(i)
                    list.append(m)
                    return list

# 7 整数反转 #

## 描述 ##

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

## 思路 ##

转化为字符串反转

## 代码 ##

class Solution(object):
        def reverse(self, x):
            """
            :type x: int
            :rtype: int
            """
            # 处理溢出情况
            x_min,x_max = -2**31,2**31-1
            if x < x_min or x > x_max or not x:
                return 0
            # 处理尾数是0情况
            while not x % 10:
                x = x / 10
            # 处理负数情况
            neg_flag = 0    
            x_str = str(x)
            if '-' in x_str:    
                x_str = x_str[1:]
                neg_flag = 1
            # 整数反转
            x_reverse_str = ''
            for i in x_str:
                x_reverse_str = i + x_reverse_str
            
            if neg_flag:
                x_reverse = -int(x_reverse_str)
            else:
                x_reverse = int(x_reverse_str)
            if x_reverse < x_min or x_reverse > x_max:
                    return 0
            return x_reverse

# 9 回文数 #

## 描述 ##

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

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

## 思路 ##

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

## 代码 ##

class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            """
            if x < 0:
                return bool(0)
            x_str = str(x)
            return x_str[::-1] == x_str

## 进阶版 ##

class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            """
            if x < 0:
                return bool(0)
            x_re_list = []
            while x:
                x_re_list.append(x%10)
                x = x // 10
            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.

## 代码 ##

class Solution(object):
        def romanToInt(self, s):
            """
            :type s: str
            :rtype: int
            """
            number= 0
            luoma_dic = {
        'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
            special_dic = {
        'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}
            for i,j in special_dic.items():
                if i in s:
                    number += j
                    s = s.replace(i,'')
            for i in s:
                number += luoma_dic[i]
            return number

class Solution(object):
        def romanToInt(self, s):
            """
            :type s: str
            :rtype: int
            """
            number,s_len = 0,len(s)
            luoma_dic = {
        'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
            for i in range(s_len-1):
                if luoma_dic[s[i]] >= luoma_dic[s[i+1]]:
                    number += luoma_dic[s[i]]
                else:
                    number -= luoma_dic[s[i]]
            number += luoma_dic[s[s_len-1]]
            return number

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

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))

注意’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 。

## 代码 ##

class Solution(object):
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            if len(strs) == 1:
                return ''
            com_str = ''
            for i in range(len(strs)-1):
                if not strs[i] or not strs[i+1]:
                    return ''
                j = 0
                temp_str = ''
                while strs[i][j] == strs[i+1][j]:
                    temp_str += strs[i][j]
                    j += 1
                    if j == len(strs[i]) or j == len(strs[i+1]):
                        break
                if len(temp_str) < len(com_str):
                    com_str = temp_str
                if not com_str:
                    com_str = temp_str
                if not temp_str:
                    return temp_str
            return com_str

## 大神解法 ##

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

def longestCommonPrefix(self, strs):
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1

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

def longestCommonPrefix(self, strs):
        if not strs: return ""
        ss = list(map(set, zip(*strs)))
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res

# 20 有效的括号 #

## 描述 ##

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

## 代码 ##

class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            pair_str_list = []
            pair_dic = {
        '(':')','[':']','{':'}'}
            pair_re_dic = {
        ')':'(',']':'[','}':'{'}
            for i in s:
                if not pair_str_list:
                    pair_str_list.append(i)
                elif i in pair_re_dic and pair_re_dic[i] in pair_str_list:
                    temp = pair_str_list.pop()
                    if temp != pair_re_dic[i]:
                        return False
                else:
                    pair_str_list.append(i)
            if pair_str_list:
        	    return False
            return True

## 大神解法 ##

class Solution:
        def isValid(self, s):
            while '{}' in s or '()' in s or '[]' in s:
                s = s.replace('{}', '')
                s = s.replace('[]', '')
                s = s.replace('()', '')
            return s == ''

# 21 合并两个有序链表 #

## 描述 ##

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

## 代码 ##

# Definition for singly-linked list.
    # class ListNode(object):
    #    def __init__(self, x):
    #       self.val = x
    #        self.next = None
    
    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            L = l3 = ListNode(0)
            while l1 and l2:
                if l1.val < l2.val:
                    l3.next = l1
                    l1 = l1.next
                else:
                    l3.next = l2
                    l2 = l2.next
                l3 = l3.next
            if l1:
                l3.next = l1
            else:
                l3.next = l2
            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。

## 代码 ##

class Solution(object):
        def removeDuplicates(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            i = 0
            while i < len(nums):
                if not i:
                    i += 1
                    continue
                if nums[i] == nums[i-1]:
                    nums.remove(nums[i])
                    i -= 1
                i += 1
            return len(nums)

## 大神解法 ##

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

[leetcode]: https://leetcode-cn.com/problemset/all/