leetcode

新计划编程入门数组&字符串 山脉数组的顶峰索引 难度：普通 给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。返回峰值元素的下标。你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。 示例 1： 输入：arr = [0,1,0] 输出：1 示例 2： 输入：arr = [0,2,1,0] 输出：1 示例 3： 输入：arr = [0,10,5,2] 输出：1 方法一 123456789class Solution(object): def peakIndexInMountainArray(self, arr): """ :type arr: List[int] :rtype: int """ for i in range(len(arr)): if arr[i]>arr[i+1]: return i 复杂度分析 时间复杂度： ...

动态规划斐波那契类型 使用最小花费爬楼梯 难度：简单 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费示例 1：输入：cost = [10,15,20]输出：15解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。 示例 2：输入：cost = [1,100,1,1,1,100,1,1,100,1]输出：6解释：你将从下标为 0 的台阶开始。支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6 。 方法一 12345678910111213class Solution(object): ...

动态规划斐波那契类型 删除并获得点数 难度：中等 给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数示例 1：输入：nums = [3,4,2]输出：6解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：输入：nums = [2,2,3,3,3,4]输出：9解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。 方法一 123456789101112131415161718192021class Solution(object): def deleteAndEarn(self, nums): """ :type nums ...

动态规划字符串 不同的子序列 难度：困难 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。 示例 1：输入：s = “rabbbit”, t = “rabbit”输出：3示例 2：输入：s = “babgbag”, t = “bag”输出：5 方法一 1234567891011121314151617class Solution: def numDistinct(self, s: str, t: str) -> int: m = len(s) n = len(t) if m<n: return 0 dp = [[0]*(n+1) for _ in range (m+1)] for i in range(m+1): dp[i][0]=1 for i in range(1,m+1): for j in range(1,n+1): if s[i-1]==t[j-1]: ...

新计划编程入门数组&字符串 字符串分割最大得分 难度：简单 给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。 「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。示例 1：输入：s = “011101”输出：5解释：将字符串 s 划分为两个非空子字符串的可行方案有：左子字符串 = “0” 且 右子字符串 = “11101”，得分 = 1 + 4 = 5左子字符串 = “01” 且 右子字符串 = “1101”，得分 = 1 + 3 = 4左子字符串 = “011” 且 右子字符串 = “101”，得分 = 1 + 2 = 3左子字符串 = “0111” 且 右子字符串 = “01”，得分 = 1 + 1 = 2左子字符串 = “01110” 且 右子字符串 = “1”，得分 = 2 + 1 = 3示例 2：输入：s = “00111”输出：5解释：当 左子字符串 = “00” 且 右子字符串 = “111” 时，我们得到最大得分 = 2 + ...

动态规划斐波那契类型 斐波那契数列 难度：简单 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。示例 1：输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3 方法一1234567891011class Solution(object): def climbStairs(self, n): if n<=2: return n a = 1 b = 2 for i in range (2,n): tem = a ...

新计划编程入门数组&字符串 统计范围内的元音字符串数 难度：简单 给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 ‘a’、’e’、’i’、’o’、’u’ 。 返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。 示例 1：输入：words = [“are”,”amy”,”u”], left = 0, right = 2输出：2解释： “are” 是一个元音字符串，因为它以 ‘a’ 开头并以 ‘e’ 结尾。 “amy” 不是元音字符串，因为它没有以元音字母结尾。 “u” 是一个元音字符串，因为它以 ‘u’ 开头并以 ‘u’ 结尾。在上述范围中的元音字符串数目为 2 。示例 2：输入：words = [“hey”,”aeo”,”mu”,”ooo”,”artro”], left = 1, right = 4输出：3解释： “aeo” 是一个元音字符串，因为它以 ‘a’ 开头并以 ‘o’ 结尾。 “mu” ...

动态规划矩阵 最小路径和 难度：中等 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例 1：输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。示例 2：输入：grid = [[1,2,3],[4,5,6]]输出：12 方法一 12345678910111213141516171819class Solution(object): def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ m=len(grid) n=len(grid[0]) dp = [[0] * n for i in range(m)] dp[0][0]=grid[0][0] for i ...

动态规划斐波那契类型 第 N 个泰波那契数 难度：简单 泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。示例 1：输入：n = 4输出：4解释：T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4 示例 2：输入：n = 25输出：1389537 方法一 1234567891011121314151617181920class Solution(object): def tribonacci(self, n): """ :type n: int :rtype: int """ if n == 0: return 0 elif n<= 2: return 1 a = 0 b = 1 c = 1 ...

动态规划斐波那契类型 打家劫舍 难度：中等 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。示例 1：输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2：输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 方法一 12345678910111213141516171819class Solution(object): def rob(self, nums): """ :type nums: List[int] ...