leetcode（1）

柔光的暖阳◎ 2022-03-09 01:10 96阅读 0赞

**目录**

2.整数反转

3.回文数

4罗马数字转整型

5.最长公共前缀

6.有效的括号

7.合并两个有序的链表

8.删除有序数组中的重复元素

9.括号生成

10.移除元素

--------------------

### **1.两数之和** ###

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

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

class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            dict = {}
            for i in range(len(nums)):
                if (target - nums[i]) not in dict.keys():
                    dict[nums[i]] = i
                else:
                    return [dict[target - nums[i]], i]

###  ###

### 2.整数反转 ###

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

**示例 1:**

输入: 123
    输出: 321

**示例 2:**

输入: -123
    输出: -321

**示例 3:**

输入: 120
    输出: 21

**注意:**

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

class Solution(object):
        def reverse(self, x):
            """
            :type x: int
            :rtype: int
            """
            a = abs(x)
            num = 0
            while (a != 0):
                temp = a % 10
                num = num * 10 + temp
                a = int(a / 10)
            if x < 0 and num <= 2**31:
                return -num
            elif x > 0 and num < 2**31:
                return num
            else:
                return 0

### 3.回文数 ###

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

**示例 1:**

输入: 121
    输出: true

**示例 2:**

输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

**示例 3:**

输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数。

#回文数
    x = 121
    class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            """
            a = abs(x) # a最后将变成 0
            num = 0
            while(a != 0):
                temp = a % 10
                num = num* 10 + temp # 最终输出的反转的数字
                a = a // 10
            if x >= 0 and num == x:
                return True
            else:
                return False
            
            
    s = Solution()
    print(s.isPalindrome(x))

### 4罗马数字转整型 ###

罗马数字包含以下七种字符: `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:**

输入: "IX"
    输出: 9

**示例 4:**

输入: "LVIII"
    输出: 58
    解释: L = 50, V= 5, III = 3.

**示例 5:**

输入: "MCMXCIV"
    输出: 1994
    解释: M = 1000, CM = 900, XC = 90, IV = 4.

# 罗马数字转换成整型
    s = "MCMXCIV"   #前面的数字比后面的数字要小
    class Solution(object):
        def romanToInt(self, s):
            """
            :type s: str
            :rtype: int
            """
            result = 0
            dict = {"I": 1, "V": 5, "X": 10, "L":50, "C":100, "D":500, "M": 1000}
            for i in range(len(s)):
                if i > 0 and dict[s[i]] > dict[s[i-1]]:
                    result += dict[s[i]] - 2 * dict[s[i-1]]     #当i=1时，满足else的条件， 此时已经加了 c:100， 所以满足此条件时，需要减去2 个C
                else:
                    result += dict[s[i]]
            return result
     
    so = Solution() 
    print(so.romanToInt(s))

### 5.最长公共前缀 ###

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

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

**示例 1:**

输入: ["flower","flow","flight"]
    输出: "fl"

**示例 2:**

输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。

**说明:**

所有输入只包含小写字母 `a-z` 。

strs = ["flower","flow","flight"]
    # mySet = set(string[i] for string in strs)
    # print(mySet)
    # result = ""
    # result += mySet.pop()
    # print(result)
    # print(mySet)    #空集
    
    class Solution(object):
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            if not strs:
                return ""
            for i in range(len(strs[0])):   #默认第一项作为比较
                for str in strs[1:]:
                    if i >= len(str) or strs[0][i] != str[i]:
                        return strs[0][:i]  #对第一个字符串进行切片
                    
            return strs[0] #如果第一个字符串就是最长公共前缀
            
    #         result = ""
    #         i = 0
    #         while True:
    #             try:    #当strs中某一字符串为空集时，会报错
    #                 mySet = set(string[i] for string in strs)
    #                 if len(mySet) == 1:
    #                     result += mySet.pop()
    #                     i += 1
    #                 else:
    #                     break
    #             except Exception as e:
    #                 break
    #         return result
    
                
            
    s = Solution()
    print(s.longestCommonPrefix(strs))

### 6.有效的括号 ###

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串，判断字符串是否有效。

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

**示例 1:**

输入: "()"
    输出: true

**示例 2:**

输入: "()[]{}"
    输出: true

**示例 3:**

输入: "(]"
    输出: false

**示例 4:**

输入: "([)]"
    输出: false

**示例 5:**

输入: "{[]}"
    输出: true

# 有效的括号
    # 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    s = "()[]{}"
    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            dict = {'(': ')', '{': '}', '[': ']'}
            stack = []
            
            for abra in s:
                if abra in dict:
                    stack.append(abra)
                elif dict[stack.pop()] != abra or len(stack) == 0:
                    return False
                
            return len(stack) == 0  
        
    sl = Solution()  
    print(sl.isValid(s))
    
    # a = 12
    # b = 13
    # print(a == 12 or b == 12)
    # print(True or False)
    # print(False or True)
    # 
    # print(False and True)
    # print(True and False)

### 7.合并两个有序的链表 ###

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

特殊情况： 1,2,3----4， 5， 6

# 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
            """
            cur = dummy = ListNode(0)   #起始结点为 0,所以最后要dummy.next 
            
            while l1 and l2:
                if l1.val < l2.val:
                    cur.next = l1
                    l1 = l1.next 
                else:
                    cur.next = l2
                    l2 = l2.next 
                cur = cur.next 
            
            cur.next = l1 or l2 # 特殊情况时，
            return dummy.next

### 8.删除有序数组中的重复元素 ###

给定一个排序数组，你需要在**[原地][Link 1]**删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在**[原地][Link 2]修改输入数组**并在使用 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。
    
    你不需要考虑数组中超出新长度后面的元素。

**说明:**

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以**“引用”**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

# 删除有序数组中的重复项，不开辟新的数组空间
    nums = [0,0,1,1,1,2,2,3,3,4] 
    class Solution(object):
        def removeDuplicates(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            count = 0
            for i in range(len(nums)):
                if nums[count] != nums[i]:
                    count += 1  #只有不同的值才更新count
                    nums[count] = nums[i] #使得不同元素放在数组前面
            return count + 1
        
    s = Solution()
    print(s.removeDuplicates(nums))

### 9.括号生成 ###

给出 *n* 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且**有效的**括号组合。

例如，给出 *n* =3，生成结果为：

[
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

使用递归的方法

#生成括号, 使用递归的方法
    n = 3
    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            if n == 0:
                return []
            result = []
            self.helper(n, n, '', result)
            return result 
        
        def helper(self, l, r, item, result):
            if l > r:   #l,r 代表剩余的括号，当使用的右括号比 使用的左括号还多时，此时是不成立的
                return 
            if l > 0:
                self.helper(l-1, r, item+ '(', result)
            if r > 0:
                self.helper(l, r-1, item+ ')', result)
            if l == 0 and r == 0:
                result.append(item) 
                
    s = Solution()        
    print(s.generateParenthesis(n))

### 10.移除元素 ###

给定一个数组 *nums* 和一个值 *val*，你需要**[原地][Link 2]**移除所有数值等于 *val* 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在**[原地][Link 2]修改输入数组**并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

**示例 1:**

给定 nums = [3,2,2,3], val = 3,
    
    函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
    
    你不需要考虑数组中超出新长度后面的元素。

**示例 2:**

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
    
    函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
    
    注意这五个元素可为任意顺序。
    
    你不需要考虑数组中超出新长度后面的元素。

**说明:**

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以**“引用”**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
    int len = removeElement(nums, val);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

# 在不创建额外空间的情况下，删除指定的元素
    nums = [3,2,2,3]
    val = 3
    class Solution(object):
        def removeElement(self, nums, val):
            """
            :type nums: List[int]
            :type val: int
            :rtype: int
            """
            start, last = 0, len(nums)-1
            while start <= last:
                if nums[start] == val:
                    #swap 将等于val的元素放在最后
                    nums[last], nums[start] = nums[start], nums[last]
                    last -= 1
                else:
                    start += 1
            return last + 1
        
    s = Solution()
    print(s.removeElement(nums, val))

[Link 1]: http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[Link 2]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95