力扣----经典题（python实现）

快来打我* 2022-10-23 08:03 111阅读 0赞

### 经典题 ###

*   *   *  一：两数之和：
         *  二：三数之和：
         *  三：两数相加：
         *  四： 买股票的最佳时机：
         *  五：二叉树的中序遍历：
         *  六：爬楼梯（不能使用递归）
         *  七：零钱兑换（动态规划）：
         *  八： 二叉树的直径：
         *  九： 盛水最多的容器：

### 一：两数之和： ###

### 二：三数之和： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]  
1：首先我们要对数组进行排序， 排序的原因是因为不允许出现重复的。  
2：第一层循环，我们可以循环遍历数组，枚举a，而且我们要判断当前枚举的和上次枚举的是否值是相同的，如果相同的，则直接跳过。  
3：第二层中，我们可以计算出，剩余两个相加需要的和。我们可以让第三个指针，指向末尾，然后循环遍历第二个指针，  
4：第三层中，每次第二个指针到达一个位置，我们计算这两个指针的相加和是多少，如果大于需要的和，说明加多了，则第三个指针向前移动。结束第三个循环有三种情况：第一种： 两个指针相碰了，说明从这个位置 到最后的相加和一直大于目标值，则此时可以退出循环了，因为后面不可能存在了。第二种情况，我们找到两个相加和是目标值的了，则此时将三个元素加入到列表中即可。另外一种就是两个的和突然小于目标值了，此时需要让第二个指针向前移动，重新循环。

class Solution:
    
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            n = len(nums)
            nums.sort()
            ans = list()
            # 枚举 a
            for first in range(n):
                # 需要和上一次枚举的数不相同
                if first > 0 and nums[first] == nums[first - 1]:
                    continue
                # c 对应的指针初始指向数组的最右端
                third = n - 1
                target = -nums[first]
                # 枚举 b
                for second in range(first + 1, n):
                    # 需要和上一次枚举的数不相同
                    if second > first + 1 and nums[second] == nums[second - 1]:
                        continue
                    # 需要保证 b 的指针在 c 的指针的左侧
                    while second < third and nums[second] + nums[third] > target:
                        third -= 1
                    # 如果指针重合，随着 b 后续的增加
                    # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                    if second == third:
                        break
                    if nums[second] + nums[third] == target:
                        ans.append([nums[first], nums[second], nums[third]])
                        
            return ans

### 三：两数相加： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]

class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    
            add_filg = 0
            head = ListNode(0)
            Head = head
            while(l1 or l2):
                sum_num = l1.val + l2.val + add_filg
                node = ListNode(sum_num % 10)
                head.next = node
                head = head.next
                add_filg = (sum_num // 10)
                if l1.next == None and l2.next != None:
                    node = ListNode(0)
                    l1.next = node
                if l2.next == None and l1.next != None:
                    node = ListNode(0)
                    l2.next = node
                l1 = l1.next
                l2 = l2.next
            if add_filg == 1:
                node = ListNode(1)
                head.next = node
    
            return Head.next

### 四： 买股票的最佳时机： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]  
分析： **我们可以遍历这个数组，当遍历到一个数值的时候，我们可以与之前的最小值相减，得到当前出售的最大收益，与之前的进行比较，如果大于最大收益则进行更新最大收益。遍历的过程中我们也要更新最小值，因为可能这个值变成最小的了。**

import sys
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            min_price = sys.maxsize
            max_pro = 0
            for i in prices:
                max_pro = max(i - min_price, max_pro)
                min_price = min (i, min_price)
            return max_pro

### 五：二叉树的中序遍历： ###

class Solution:
    
        def __init__(self):
            self.my_list = []
            
        def middle_research(self, root):
            if root == None:
                return 
            self.middle_research(root.left)
            self.my_list.append(root.val)
            self.middle_research(root.right)
    
        def inorderTraversal(self, root: TreeNode) -> List[int]:
            if root == None:
                return []
            else:
                self.middle_research(root)
                return self.my_list

### 六：爬楼梯（不能使用递归） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]

class Solution:
        def climbStairs(self, n: int) -> int:
            p, q, r = 0, 0, 1
            for i in range(n):
                p = q
                q = r
                r = p + q
            return r

### 七：零钱兑换（动态规划）： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]

class Solution:
    
        def coinChange(self, coins: List[int], amount: int) -> int:
            # 初始化状态数组:均设置成最大值
            dp = [float('inf')] * (amount + 1)
            # 当总钱数是0的时候，根本不需要硬币，所以设置成0
            dp[0] = 0
            # 外层开始遍历这个硬币
            for coin in coins:
                # 从硬币的位置向后遍历
                for x in range(coin, amount + 1):
                    # 如果当前的硬币，与上一个能到达的+1进行比较，选择最小的那个
                    dp[x] = min(dp[x], dp[x - coin] + 1)
            # 最终返回状态数组的最后那个
            return dp[amount] if dp[amount] != float('inf') else -1

### 八： 二叉树的直径： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 5]  
二叉树的直径 = **叶子节点到叶子节点的最大路径**。= **某个节点到左叶子节点的最大路径 + 右叶子节点的最大路径。**

class Solution:
        def __init__(self):
            # 因为最小的直径也是1
            self.max_flag = 1
    
        def dfs(self, root):
            # 递归到边界返回0
            if root == None:
                return 0
            left_depth = self.dfs(root.left)
            right_depth = self.dfs(root.right)
            # 左边的深度 + 右边的深度 + 1 = 经过当前节点的路径
            self.max_flag = max(self.max_flag, left_depth + right_depth)
            # 当前根的深度 = 自己左子树，自己右子树高的值 + 1
            return max(left_depth, right_depth) + 1
    
        def diameterOfBinaryTree(self, root: TreeNode) -> int:
            if root == None:
                return 0
            else:
                self.dfs(root)
                return self.max_flag - 1 # 直径 = 路径 -1

### 九： 盛水最多的容器： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 6]  
思路： 采用双指针，谁是短板谁移动。

class Solution:
        def maxArea(self, height: List[int]) -> int:
            i, j , res = 0, len(height)-1, 0
            while(i < j):
                # 如果左面的小于右面的高度
                if height[i] < height[j]:
                    # 更新最大面积
                    res = max(res, height[i] * (j - i))
                    # 短板移动
                    i += 1
                else:
                    res= max(res, height[j] * (j - i))
                    j -= 1
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]: /images/20221023/0de738a1e1eb4c8cabe46dfaf20acfd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]: /images/20221023/972198d41c5c47ce9578c5f44bed43e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]: /images/20221023/468f5757e5e842269ddc3e8319376850.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]: /images/20221023/6a651f729465438ab8719e162c4e4236.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]: /images/20221023/4522475f3c2748fba499c5733e057b9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 5]: /images/20221023/4da7c740815f47fba40992faab483737.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 6]: /images/20221023/65a9bf10543942a9bca0aac76ff7c3b3.png