网站举报12321_洛阳自助建站_seo关键词如何设置_线上营销工具

---

前言

 记录力扣Hot150的思路，为了加深理解，示例和题目是我自己表达的，而且代码随机贴，每次更新十大题目。

1、合并两个有序数组

1.1.描述

 给定两个有序数组，其中一个nums1=[1,2,2,0,0]，长度为3，后面的0是补的；nums2 = [1,2,3]，n=3，合并后为[1,1,2,2,3]。

思路：先拼接+sort
class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""nums1[m:] = nums2return nums1.sort()

2、移除元素

2.1.描述

 给定一个nums=[3,2,2,3]和一个val=2，移除nums中2，并返回非2的个数。比如该例子返回2，nums=[3,3]

2.2.思路

 快慢指针，慢指针指向将要被替换的位置；快指针则按照顺序遍历数组；如果快指针指向元素==val，则+1；否则交换slow跟fast指向元素。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slow, fast = 0, 0while fast < len(nums):if val == nums[fast]:fast += 1else:nums[slow] = nums[fast]slow += 1fast += 1return slow 

3、删除有序数组中的重复元素

3.1.描述

 给定一个有序数组，[1,1,2,2,2,3]，返回[1,2,3]，使得数组中每个元素只出现一次，返回长度3。

3.2.思路

 快慢指针，慢指针指向第二个元素，若nums[fast] == nums[slow-1]，则fast+=1；否则，交换元素，快慢指针并同时+=1，最终返回slow。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow, fast = 1, 1while fast < len(nums):if nums[fast] == nums[slow-1]:fast += 1else:nums[slow] = nums[fast]slow += 1fast += 1return slow  

4、输出有序数组中的重复项二

4.1.描述

 给定一个有序数组，使得每个元素最多出现两次。nums=[1,1,1,2,2,3,3,3]，返回6，且nums=[1,1,2,2,3,3]。

4.2.思路

 快慢指针，跟上题目类似，只是起始位置指向第三个元素，若nums[fast] == nums[slow-2]，则fast+=1；否则交换并更新slow和fast指针。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow, fast = 2, 2while fast < len(nums):if nums[fast] == nums[slow-2]:fast+=1else:nums[slow] = nums[fast]slow +=1fast += 1return slow 

5、多数元素

5.1.描述

 给定一个数组，返回数组里面哪个元素，出现次数超过len(nums) // 2。比如[2,2,3]，返回2。

5.2.思路

 哈希表，统计nums中每个元素出现的次数。

class Solution:def majorityElement(self, nums: List[int]) -> int:hash_map = {}for num in nums:if num not in hash_map:hash_map[num] = 1else:hash_map[num] += 1for k,v in hash_map.items():if v > len(nums) // 2:return k 

6、轮转数组

6.1.描述

 给定一个nums=[1,2,3,4,5]，和k=2，表示向右滑动的次数。返回[4,5,1,2,3]。

6.2.思路

 代码很简单，只是通过不了，不清楚为啥。

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""left_sub_nums = nums[:-k]right_sub_nums = nums[-k:]nums = right_sub_nums + left_sub_numsreturn nums 

7、买卖股票最佳时机一

 给定一个股价数组，每个元素表示当天的股价，假设你在i天买入，在第j天卖出，卖出的日期需要比买入的日期靠后。返回能获取的最大利润。
 输入：[7,1,5,3,6,4]
 输出：5
 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

7.1.思路

 重点：遍历数组，假设当前遍历日期就是你卖出的价格，则只需减去过去天数 最小价格就能得到最大利润。因此，需要维护一个最小价格和一个最大利润变量。

class Solution:def maxProfit(self, prices: List[int]) -> int:min_prices = prices[0]   # 默认第一天买入股票。max_profit = 0# 从第二天开始遍历卖股票for i in range(1, len(prices)):max_profit = max(max_profit, prices[i] - min_prices)min_prices = min(min_prices, prices[i])return max_profit

8、买卖股票最佳时机二

 给定一串prices，你在任意天数内都可以买进或卖出，求你能获得的最大利润。
示例 1：

 输入：prices = [7,1,5,3,6,4]
 输出：7
 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
 最大总利润为 4 + 3 = 7 。

8.1.思路

 不推荐动态规划，只需画个折线图，只要后一天比前一天股价高，就累加到利润里面。

class Solution:def maxProfit(self, prices: List[int]) -> int:max_profit = 0for i in range(0, len(prices) - 1):if prices[i+1] > prices[i]:max_profit += (prices[i+1] - prices[i])return max_profit

9、跳跃游戏一

 给定一个非负数组，里面每个元素表示能往前跳到的位置，试问能不能跳到最后一个位置，返回True or False；

 示例 1：

 输入：nums = [2,3,1,1,4]
 输出：true
 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

9.1.思路

 遍历数组，维护一个变量记录能够最远到达的位置，如果遍历过程中超过了最远到达的位置，则说明遍历不成功，返回False。

class Solution:def canJump(self, nums: List[int]) -> bool:reach = 0for i in range(0, len(nums)):# 注意是先进行if判断，然后在更新最远位置。别弄反了！！if i > reach:return Falsereach = max(reach , i + nums[i])return True 

10、跳跃游戏二

 给定一个非负数组nums，里面每个元素表示能够往前跳动的位置，计算跳到最后元素所需的最小步数。

10.1.思路

 这里有个解答不错：图解。遍历数组，维护三个变量，主要是end变量，用来记录当前子区间的右边界，若遍历过程中超过右边界，则step+=1，并将end更新为遍历过程中最远的位置。

class Solution:def jump(self, nums: List[int]) -> int:step = 0end = 0   # 当前子区间的最右边界reach = 0 for i in range(0, len(nums)):   # 遍历所有元素# 如果超过右边界，则step+=1，同时赋值最新最远距离。if i > end:end = reach step += 1reach = max(reach, i+nums[i])  # 始终记录能够达到的最远距离。return step