letcode刷题(2019.12.20--2019.12.31)

朱雀 2023-06-23 15:24 16阅读 0赞

1.[数组的相对排序][Link 1]（2019.12.20）

题目描述：

给你两个数组，arr1 和 arr2，

arr2 中的元素各不相同  
arr2 中的每个元素都出现在 arr1 中  
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/relative-sort-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

定义空列表res，遍历arr2所有元素，如果该元素也在arr1中，将arr1中的该元素移除，将该元素添加到res，最后返回res+sorted(arr1)

代码实现：

class Solution:
        def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
            res=[]
            #遍历arr2
            for i in arr2:
                #如果i在arr1中，将i添加到res中，同时移出arr1中的i
                while i in arr1:
                    res.append(i)
                    arr1.remove(i)
            #返回得到的res+剩余arr1的升序排列部分
            return res + sorted(arr1)

2.[两数之和][Link 2](2019.12.23)

题目描述：

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/two-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  首先获取列表的长度，并定义num2的下标j为-1
2.  使用for循环获取遍历nums，并对nums进行切片，获取当前元素之前的元素为一个新的列表temps
3.  如果taget-nums\[i\]在列表temps中，获取num2的下标，并跳出循环
4.  如果j>=0时，说明taget = num1+num2成立，返回num1和num2的下标

代码实现：

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            lens = len(nums)
            j = -1
    
            for i in range(1,lens):
                #对nums切片获取i之前的元素，作为新的列表
                temps = nums[:i]
                #如果target-nums[i]在temps中，获取j的下标，跳出循环
                if (target - nums[i]) in temps:
                    j = temps.index(target - nums[i])
                    break
    
            if j >= 0:
                return j,i

3.[整数反转][Link 3]（2019.12.24）

题目描述：

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

示例 1:

输入: 123  
输出: 321  
 示例 2:

输入: -123  
输出: -321  
示例 3:

输入: 120  
输出: 21  
注意:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reverse-integer  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  将传入的整型转换为字符串num\_strs，并定义一个空的列表reverse\_strs
2.  将num\_strs反转并赋值给reverse\_strs，如果reverse\_strs最后一位为‘-’，将其插入到列表的第一位
3.  定义空的字符串nums，将reverse\_strs各元素累计后赋值给nums，将nums转换为整型
4.  如果nums<-2\*\*31或nums>2\*\*31-1，将0赋值给nums

代码实现：

class Solution:
        def reverse(self, x: int) -> int:
            num_strs = str(x)
            reverse_strs = []
            #将num_strs进行反转赋值给reverse_strs
            for i in num_strs:
                reverse_strs.insert(0,i)
            if reverse_strs[-1] == '-':
                reverse_strs.insert(0,reverse_strs[-1])
                reverse_strs.pop(-1)
            nums = ''
            #将reverse_strs各元素累加后赋值给nums
            for num in reverse_strs:
                nums += num
            nums = int(nums)
            if nums < -2**31 or nums > (2**31-1):
                nums = 0
            return nums

4.[回文数][Link 4]

题目描述：

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

示例 1:

输入: 121  
输出: true  
示例 2:

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/palindrome-number  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  将整数X转换为字符串strs，定义空列表news
2.  遍历字符串strs，将字符串元素反转存入news
3.  将news各元素累加后，赋值给new\_str
4.  new\_str等于strs时，返回true，否则，返回false

代码实现：

class Solution:
        def isPalindrome(self, x: int) -> bool:
            strs = str(x)
            news = []
            for i in strs:
                news.insert(0,i)
            new_str = ''
            for new in news:
                new_str += new
            if new_str == strs:
                return True
            else:
                return False

5.[二叉树的层次遍历][Link 5]（2019.12.26）

题目描述：

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:  
给定二叉树: \[3,9,20,null,null,15,7\],

3  
   / \\  
  9  20  
    /  \\  
   15   7  
返回其层次遍历结果：

\[  
  \[3\],  
  \[9,20\],  
  \[15,7\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  定义空列表levels，判断传入的节点root是否为空，如果为空，返回空列表levels
2.  定义递归方法helper，入参当前节点node、当前深度level
3.  如果levels的长度等于level，在levels最后添加空列表
4.  将当前node的值添加到levels\[level\]中
5.  判断当前节点是否有左子节点，如果有，用左子节点、level+1调用helper方法
6.  判断当前节点是否有右子节点，如果有，用右子节点、level+1调用helper方法
7.  调用helper方法，传入参数为root、0
8.  返回levels

代码实现：

class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            #定义一个空列表levels
            levels = []
            #如果传入的二叉树为空，返回空列表
            if not root:
                return levels
            
            def helper(node,level):
                """
                递归遍历二叉树
                """
                #如果列表的长度等于当前节点的深度，给列表levels中添加一个空的列表
                if len(levels) == level:
                    levels.append([])
                #将当前节点的值，添加到列表levels中子列表level下
                levels[level].append(node.val)
                #判断当前节点是否有左子节点，如果有，左子节点和level+1调用helper
                if node.left:
                    helper(node.left,level+1)
                if node.right:
                    helper(node.right,level+1)
            helper(root,0)
            return levels

6.[罗马数字转整数][Link 6]

题目描述：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/roman-to-integer  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  将各种罗马数字对应的值放到字典RomanToNum中，初始化n为传入字符串的长度，i、res都为0
2.  使用while，当i小于n时继续循环
3.  如果i等于n-1说明其为字符串中最后一位，不可能为IV等情况，对res加RomanToNum\[s\[i\]\]，i加1
4.  如果字符串s当前元素及下一个元素存在与RomanToNum中，说明s\[i:i+2\]为特例，那么对res加RomanToNum\[s\[i:i+2\]\],i加2
5.  如果不满足条件3、4，则说明该元素既不是特列，也不是字符串的最后一位，只需要对res加加RomanToNum\[s\[i\]\]，i加1即可
6.  返回res

代码实现：

class Solution:
        def romanToInt(self, s: str) -> int:
            RomanToNum = {
                "I":1,
                "IV":4,
                "V":5,
                "IX":9,
                "X":10,
                "XL":40,
                "L":50,
                "XC":90,
                "C":100,
                "CD":400,
                "D":500,
                "CM":900,
                "M":1000
            }
            n = len(s)
            i = 0
            res = 0
            while i<n:
                if i == n-1:
                    res += RomanToNum[s[i]]
                    i += 1
                else:
                    if s[i:i+2] in RomanToNum:
                        res += RomanToNum[s[i:i+2]]
                        i += 2
                    else:
                        res += RomanToNum[s[i]]
                        i += 1
            return res

7.[最长公共前缀][Link 7](2019.12.28)

题目描述：

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

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

示例 1:

输入: \["flower","flow","flight"\]  
输出: "fl"  
示例 2:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-common-prefix  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  判断传入的字符串数组是否为空，如果为空直接返回空字符串，如果不为空定义res等于传入的字符串数组第一个元素
2.  遍历整个数组，如果res为空，则直接返回res，如果不为空，和当前元素前len(res)进行比较，如果相等跳出本次循环。
3.  如果不等，将res最后一位删除，重新进行比较，直到相等或res为空

代码实现：

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            #如果strs不为空
            if strs:
                #定义res等于strs[0]
                res = strs[0]
                #遍历列表strs
                for string in strs:
                    #如果res为空，则说明没有相同的前缀，直接返回res
                    if not res:
                        return res
                    #如果res等于当前字符串相同位数的前缀，跳出本次循环
                    if res == string[0:len(res)]:
                        continue
                    #res不等于字符串相同位数的前缀，去除res的最后一位继续比较，直到等于或res为空为止
                    else:
                        while res != string[0:len(res)]:
                            res = res[0:len(res) -1]
                return res
            else:
                res = ''
                #如果为空直接返回空字符串
                return res

8.[有效的括号][Link 8]（2019.12.29）

题目描述：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"  
输出: true  
示例 2:

输入: "()\[\]\{\}"  
输出: true  
示例 3:

输入: "(\]"  
输出: false  
示例 4:

输入: "(\[)\]"  
输出: false  
示例 5:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  判断是否为空字符串，如果是返回true
2.  定义n为字符串长度的一般，i为0
3.  使用while循环，如果"()"或"\{\}"或"\[\]"在字符串s中，使用空字符串替换空格，否则直接返回false
4.  如果s为空，返回true

代码实现：

class Solution:
        def isValid(self, s: str) -> bool:
            if not s:
                return True
            n = len(s)//2
            i = 0
            while i < n:
                i += 1
                if "()" or "[]" or "{}" in s:
                    s = s.replace("()","")
                    s = s.replace("[]", "")
                    s = s.replace("{}", "")
                else:
                    return False
                if not s:
                    return True

9.[删除排序数组中的重复项][Link 9]（2019.12.30）

题目描述：

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。

你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.  判断数组是否为空，如果为空直接返回0
2.  定义k为1，使用for循环遍历数组nums
3.  如果当前元素不等于当前元素所在位置的前一个元素，则说明当前元素不重复，使用nums\[k\]等于当前元素，并且对k加1
4.  返回k

代码实现：

class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            if not nums: return 0
            k = 1
            for i in range(1,len(nums)):
                if nums[i] != nums[i-1]:
                    nums[k] = nums[i]
                    k += 1
            return k

10.[从二叉搜索树到更大和树][Link 10]（2019.12.31）

题目描述：

给出二叉**搜索**树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 `node` 的新值等于原树中大于或等于 `node.val` 的值之和。（题目描述不理解的话可以参考链接：[https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/solution/dui-ti-yi-de-li-jie-by-hardy-5/][https_leetcode-cn.com_problems_binary-search-tree-to-greater-sum-tree_solution_dui-ti-yi-de-li-jie-by-hardy-5]）

解题思路：

1.  定义空列表sort，将节点根据值从小到大存入sort中
2.  令sort\[i\].val等于sort\[i\].val+sort\[i+1\].val+...+sort\[-1\].val

代码实现：

class Solution:
        def bstToGst(self, root: TreeNode) -> TreeNode:
            sort = []
            def inorder(node):
                #在sort中将node从小到大排列
                if node:
                    inorder(node.left)
                    sort.append(node)
                    inorder(node.right)
            inorder(root)
            #令当前node的值等于 当前node和大于当前node值的和
            for i in range(len(sort)):
                for j in range(i+1,len(sort)):
                    sort[i].val += sort[j].val
            return root

[Link 1]: https://leetcode-cn.com/problems/relative-sort-array/
[Link 2]: https://leetcode-cn.com/problems/two-sum/
[Link 3]: https://leetcode-cn.com/problems/reverse-integer/
[Link 4]: https://leetcode-cn.com/problems/palindrome-number/
[Link 5]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[Link 6]: https://leetcode-cn.com/problems/roman-to-integer/
[Link 7]: https://leetcode-cn.com/problems/longest-common-prefix/
[Link 8]: https://leetcode-cn.com/problems/valid-parentheses/
[Link 9]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[Link 10]: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
[https_leetcode-cn.com_problems_binary-search-tree-to-greater-sum-tree_solution_dui-ti-yi-de-li-jie-by-hardy-5]: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/solution/dui-ti-yi-de-li-jie-by-hardy-5/