letcode刷题(2020.01.11--2020.01.20)

浅浅的花香味﹌ 2023-06-29 10:58 65阅读 0赞

1.[移动零][Link 1](2020.1.11)

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: \[0,1,0,3,12\]  
输出: \[1,3,12,0,0\]  
说明:

必须在原数组上操作，不能拷贝额外的数组。  
尽量减少操作次数。

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

解题思路：

1.  记录0总共在列表中出现的次数count\_0，定义变量n等于列表长度减count\_0。
2.  使用while循环，当i小于n时，如果nums\[i\]等于0，并将num\[i\]，放到列表的最后。
3.  最后返回nums

代码实现：

class Solution:
        def moveZeroes(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            count_0 = nums.count(0)
            if count_0 == 0:
                return nums
            i = 0
            n = len(nums) -count_0
            while i < n:
                if nums[i] == 0:
                    nums.pop(i)
                    nums.append(0)
                else:
                    i += 1
            return nums

2.[反转链表][Link 2](2020.1.12)

题目描述：

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

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

解题思路：

1.  定义变量pro等于None，cur等于cur
2.  使用while循环，当cur不为空时，满足条件
3.  定义变量temp等于cur.next，cur.next等于pro，pro等于cur，通过这一波操作，可以将链表相邻的节点反转
4.  cur等于temp，将cur传递给下一个节点，重复执行第三步，直到cur为None

代码实现：

class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            pro = None
            cur = head
            
            while cur:
                #记录当前节点的下一个节点
                temp = cur.next
                #将当前节点指向pro
                cur.next = pro
                #pro、cur都前进一步
                pro = cur
                cur = temp
            return pro

3.[删除排序链表中的重复元素][Link 3](2020.1.13)

题目描述：

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2  
输出: 1->2  
示例 2:

输入: 1->1->2->3->3  
输出: 1->2->3

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

解题思路：

1.  定义变量pro等于head，cur等于head.next。
2.  当cur不等于空时，如果pro.val等于cur.val，删除cur节点，pro.next指向cur.next，cur等于cur.next。否则，pro和cur各前进一步
3.  返回head

代码实现：

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            if not head:
                return head
            pro = head
            cur = head.next
            while cur:
                if pro.val == cur.val:
                    pro.next = cur.next
                    cur = cur.next
                else:
                    pro = cur
                    cur = cur.next
            return head

4.[相同的树][Link 4](2020.1.14)

题目描述：

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1  
          / \\       / \\  
         2   3     2   3

\[1,2,3\],   \[1,2,3\]

输出: true  
示例 2:

输入:      1          1  
          /           \\  
         2             2

\[1,2\],     \[1,null,2\]

输出: false  
示例 3:

输入:       1         1  
          / \\       / \\  
         2   1     1   2

\[1,2,1\],   \[1,1,2\]

输出: false

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

解题思路：

1.  看到这道题目，第一感觉就是需要用递归的方法。
2.  定义isSame方法，入参p,q，如果p,q都为空，则返回True.如果p或q为空，范围False。
3.  判断p.val是否等于q.val，如果相等，返回isSame(p.left,q.left) and isSame(p.right,q.right)，如果不相等返回False。
4.  最后返回isSame(p,q)

代码实现：

class Solution:
        def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            def isSame(p, q):
                if not p and not q:
                    return True
                if not p or not q:
                    return False
                if p.val == q.val:
                    return isSame(p.left,q.left) and isSame(p.right,q.right)
                else:
                    return False
            return isSame(p,q)

5.[对称二叉树][Link 5](2020.1.15)

题目描述：

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1  
   / \\  
  2   2  
 / \\ / \\  
3  4 4  3  
但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1  
   / \\  
  2   2  
   \\   \\  
   3    3

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

解题思路：

1.  使用递归的思想进行解题，首先定义递归函数is\_equal，传入参数left，right
2.  如果left和right都为空时，返回True，如果left或right为空时，返回False，如果left.val不等于right.val时，返回False
3.  通过观察我们可以发现镜像对称数有如下特征，left.left等于right.right，left.right等于right.left。在is\_equal中返回is\_equal(left.left,right.right) and is\_equal(left.right,right.left)
4.  最后返回is\_equal(root.left,root.right)

代码实现：

class Solution:
        def isSymmetric(self, root: TreeNode) -> bool:
            if not root:
                return True
            def is_equal(left,right):
                if not left and not right:
                    return True
                if not left or not right:
                    return False
                if left.val != right.val:
                    return False
                return is_equal(left.left,right.right) and is_equal(left.right,right.left)
            return is_equal(root.left,root.right)

6.[二叉树的最大深度][Link 6](2020.1.16)

题目描述：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：  
给定二叉树 \[3,9,20,null,null,15,7\]，

3  
   / \\  
  9  20  
    /  \\  
   15   7  
返回它的最大深度 3 。

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

解题思路：

1.  看到此题，第一个想到的就是递归，root节点的最大深度就等于左节点、右节点的最大深度中，较大的值加1

代码实现：

class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            #如果root为空，返回0
            if not root:
                return 0
            #求得root左子节点的最大深度
            left_height = self.maxDepth(root.left)
            #求得root右子节点的最大深度
            right_height = self.maxDepth(root.right)
            #去左子节点、右子节点深度最大的值 加 1
            return max(left_height,right_height) + 1

7.[只出现一次的数字][Link 7](2020.1.17)

题目描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

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

解题思路：

1.  从数学角度解决该问题，2\*(a+b+c) - (a+b+c+a+b) = c

代码实现：

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            return 2 * sum(set(nums)) - sum(nums)

8.[宝石与石头][Link 8](2020.1.18)

题目描述：

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:

输入: J = "aA", S = "aAAbbbb"  
输出: 3  
示例 2:

输入: J = "z", S = "ZZ"  
输出: 0  
注意:

S 和 J 最多含有50个字母。  
 J 中的字符不重复。

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

解题思路：

1.  遍历S中所有字符，如果该字符存在于J，说明该字符为宝石，宝石数加1，返回总的宝石数

代码实现：

class Solution:
        def numJewelsInStones(self, J: str, S: str) -> int:
            i = 0
            for s in S:
                if s in J:
                    i += 1
            return i

9.[买卖股票的最佳时机][Link 9](2020.1.19)

题目描述：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: \[7,1,5,3,6,4\]  
输出: 5  
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。  
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。  
示例 2:

输入: \[7,6,4,3,1\]  
输出: 0  
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

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

解题思路：

1.  本题使用动态规划的思想解决，遍历列表，首先判断当前价格是否比买入价格低，如果比买入价格低，使得当前价格等于买入价格
2.  如果当前价格比买入价格高，当前利润等于当日价格减去买入价格，
3.  判断当前利润是否高于最高利润，如果是，另最高利润等于当前利润
4.  返回最高利润

代码实现：

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if not prices:
                return 0
            buy_price = prices[0]
            max_profit = 0
            for i in range(len(prices)):
                if prices[i] < buy_price:
                    buy_price = prices[i]
                else:
                    profit = prices[i] - buy_price
                    if profit > max_profit:
                        max_profit = profit
            return max_profit

[Link 1]: https://leetcode-cn.com/problems/move-zeroes/
[Link 2]: https://leetcode-cn.com/problems/reverse-linked-list/
[Link 3]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
[Link 4]: https://leetcode-cn.com/problems/same-tree/
[Link 5]: https://leetcode-cn.com/problems/symmetric-tree/
[Link 6]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[Link 7]: https://leetcode-cn.com/problems/single-number/
[Link 8]: https://leetcode-cn.com/problems/jewels-and-stones/
[Link 9]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/