区块链技术博客
www.b2bchain.cn

用Python刷力扣:数组(上)求职学习资料

本文介绍了用Python刷力扣:数组(上)求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

前往力扣初级算法

数组

Python3 数组

实例化

list = [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

或 list = []

或 list = [‘Hi!’] * 4

切片

  • list[0] —— ‘red’
  • list[-1] ——- ‘black’
  • list[1:4] —— [‘green’, ‘blue’, ‘yellow’] 前闭后开
  • list[1:-2] —— [‘green’, ‘blue’, ‘yellow’]
  • list[1:] —— [‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]
  • list[:-1] ——- [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

列表生成式

  • 要生成list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]可以用list(range(1, 11))
  • 或者 [x for x in range(1, 11)]
  • for循环后面还可以加上if判断 [x * x for x in range(1, 11) if x % 2 == 0]

python针对于list的内置函数

  1. len(list) 列表元素个数

  2. max(list) 返回列表元素最大值

  3. min(list) 返回列表元素最小值

  4. list(seq) 将元组转换为列表

list的对象方法

  1. list.append(obj) 在列表末尾添加新的对象
  2. list.count(obj) 统计某个元素在列表中出现的次数
  3. list.extend(seq) 在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)
  4. list.index(obj) 从列表中找出某个值第一个匹配项的索引位置
  5. list.insert(index, obj) 将对象插入列表
  6. list.pop([index=-1]) 移除列表中的一个元素(默认最后一个元素),并且返回该元素的值
  7. list.remove(obj) 移除列表中某个值的第一个匹配项
  8. list.reverse() 反向列表中元素
  9. list.sort( key=None, reverse=False) 对原列表进行排序
  10. list.clear() 清空列表
  11. list.copy() 复制列表

Leetcode 数组

26. 删除排序数组中的重复项

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

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

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

解题一:

关键信息:排序数组、原地删除

思路:快慢指针,慢指保护已处理好的数组,快指针不断寻找

慢指针i

快指针j

快指针 j >= i

当 num[i] != num[j] 时,说明,num[j]就是下一个不重复元素,应当保护起来

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

解题二:

如果本题不用快慢指针,且不需要空间复杂度时,有两个办法:

  • 1. 可以采用一个额外的数组,不断添加新的不重复元素
  • 2. 集合是不重复的,数组转集合,判断集合有多少个值 len(set(nums))

如果本题的数组是无序的,举例两种办法:

  • 1. collections.Counter ,collections.Counter 用于计数可哈希对象,它是一个集合,元素像字典键(key)一样存储,它们的计数存储为值
  • 2. 一个额外用于记录的字典,统计每个值出现的次数

122. 买卖股票的最佳时机 II

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解题一:

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:如何买卖,才能让自己收益最大?最后肯定手里是没有股票的。

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:第i天的收益,受到第i-1天的操作影响。

假如第i天,持有股票的收益最大为 dp[i][0]

假如第i天,不持有股票的收益最大为 dp[i][1]

那么:

dp[i][0] = max(dp[i-1][0],dp[i-1]+prices[i])

dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])

我们求最大利润,那么此时应该是不持有股票的,也就是第n天不持有股票,即求的是dp[n-1][0]的值。

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp[0][0] = 0         dp[0][1] = -prices[0]         for i in range(1,n):             dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])             dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])         return dp[n-1][0]

解题二:

解题一是可以优化的,用了2n的额外空间,来记录每天的最大利润。

观察 for循环,发现只和上一天的最大利润有关:

当天不持有股票时的最大利润为:dp0

当天持有股票时的最大利润为:dp1

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp0 = 0         dp1 = -prices[0]         for i in range(1,n):             dp0 = max(dp0,dp1+prices[i])             dp1 = max(dp0-prices[i],dp1)         return dp0

此时的空间复杂度为 O(1)。

解题三:

贪心算法,这个我还无法组织语言

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

189. 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

解题一:

关键信息:k是0 或者 正数

思路:如果不考虑空间复杂度,新数组只需一遍for循环 new = (i+k)%len(nums),即

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         news = [0 for _ in range(len(nums))]         for i in range(len(nums)):             index = (i+k)%len(nums)             news[index] = nums[i]         for i in range(len(nums)):             nums[i] = news[i]

切片的方式:

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         k = k%len(nums)         new1 = nums[-k:]         new2 = nums[0:len(nums)-k]         new3 = new1 + new2          for i in range(len(nums)):             nums[i] = new3[i]

解题二:

前往力扣初级算法

数组

Python3 数组

实例化

list = [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

或 list = []

或 list = [‘Hi!’] * 4

切片

  • list[0] —— ‘red’
  • list[-1] ——- ‘black’
  • list[1:4] —— [‘green’, ‘blue’, ‘yellow’] 前闭后开
  • list[1:-2] —— [‘green’, ‘blue’, ‘yellow’]
  • list[1:] —— [‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]
  • list[:-1] ——- [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

列表生成式

  • 要生成list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]可以用list(range(1, 11))
  • 或者 [x for x in range(1, 11)]
  • for循环后面还可以加上if判断 [x * x for x in range(1, 11) if x % 2 == 0]

python针对于list的内置函数

  1. len(list) 列表元素个数

  2. max(list) 返回列表元素最大值

  3. min(list) 返回列表元素最小值

  4. list(seq) 将元组转换为列表

list的对象方法

  1. list.append(obj) 在列表末尾添加新的对象
  2. list.count(obj) 统计某个元素在列表中出现的次数
  3. list.extend(seq) 在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)
  4. list.index(obj) 从列表中找出某个值第一个匹配项的索引位置
  5. list.insert(index, obj) 将对象插入列表
  6. list.pop([index=-1]) 移除列表中的一个元素(默认最后一个元素),并且返回该元素的值
  7. list.remove(obj) 移除列表中某个值的第一个匹配项
  8. list.reverse() 反向列表中元素
  9. list.sort( key=None, reverse=False) 对原列表进行排序
  10. list.clear() 清空列表
  11. list.copy() 复制列表

Leetcode 数组

26. 删除排序数组中的重复项

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

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

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

解题一:

关键信息:排序数组、原地删除

思路:快慢指针,慢指保护已处理好的数组,快指针不断寻找

慢指针i

快指针j

快指针 j >= i

当 num[i] != num[j] 时,说明,num[j]就是下一个不重复元素,应当保护起来

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

解题二:

如果本题不用快慢指针,且不需要空间复杂度时,有两个办法:

  • 1. 可以采用一个额外的数组,不断添加新的不重复元素
  • 2. 集合是不重复的,数组转集合,判断集合有多少个值 len(set(nums))

如果本题的数组是无序的,举例两种办法:

  • 1. collections.Counter ,collections.Counter 用于计数可哈希对象,它是一个集合,元素像字典键(key)一样存储,它们的计数存储为值
  • 2. 一个额外用于记录的字典,统计每个值出现的次数

122. 买卖股票的最佳时机 II

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解题一:

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:如何买卖,才能让自己收益最大?最后肯定手里是没有股票的。

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:第i天的收益,受到第i-1天的操作影响。

假如第i天,持有股票的收益最大为 dp[i][0]

假如第i天,不持有股票的收益最大为 dp[i][1]

那么:

dp[i][0] = max(dp[i-1][0],dp[i-1]+prices[i])

dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])

我们求最大利润,那么此时应该是不持有股票的,也就是第n天不持有股票,即求的是dp[n-1][0]的值。

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp[0][0] = 0         dp[0][1] = -prices[0]         for i in range(1,n):             dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])             dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])         return dp[n-1][0]

解题二:

解题一是可以优化的,用了2n的额外空间,来记录每天的最大利润。

观察 for循环,发现只和上一天的最大利润有关:

当天不持有股票时的最大利润为:dp0

当天持有股票时的最大利润为:dp1

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp0 = 0         dp1 = -prices[0]         for i in range(1,n):             dp0 = max(dp0,dp1+prices[i])             dp1 = max(dp0-prices[i],dp1)         return dp0

此时的空间复杂度为 O(1)。

解题三:

贪心算法,这个我还无法组织语言

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

189. 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

解题一:

关键信息:k是0 或者 正数

思路:如果不考虑空间复杂度,新数组只需一遍for循环 new = (i+k)%len(nums),即

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         news = [0 for _ in range(len(nums))]         for i in range(len(nums)):             index = (i+k)%len(nums)             news[index] = nums[i]         for i in range(len(nums)):             nums[i] = news[i]

切片的方式:

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         k = k%len(nums)         new1 = nums[-k:]         new2 = nums[0:len(nums)-k]         new3 = new1 + new2          for i in range(len(nums)):             nums[i] = new3[i]

解题二:

前往力扣初级算法

数组

Python3 数组

实例化

list = [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

或 list = []

或 list = [‘Hi!’] * 4

切片

  • list[0] —— ‘red’
  • list[-1] ——- ‘black’
  • list[1:4] —— [‘green’, ‘blue’, ‘yellow’] 前闭后开
  • list[1:-2] —— [‘green’, ‘blue’, ‘yellow’]
  • list[1:] —— [‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]
  • list[:-1] ——- [‘red’, ‘green’, ‘blue’, ‘yellow’, ‘white’, ‘black’]

列表生成式

  • 要生成list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]可以用list(range(1, 11))
  • 或者 [x for x in range(1, 11)]
  • for循环后面还可以加上if判断 [x * x for x in range(1, 11) if x % 2 == 0]

python针对于list的内置函数

  1. len(list) 列表元素个数

  2. max(list) 返回列表元素最大值

  3. min(list) 返回列表元素最小值

  4. list(seq) 将元组转换为列表

list的对象方法

  1. list.append(obj) 在列表末尾添加新的对象
  2. list.count(obj) 统计某个元素在列表中出现的次数
  3. list.extend(seq) 在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)
  4. list.index(obj) 从列表中找出某个值第一个匹配项的索引位置
  5. list.insert(index, obj) 将对象插入列表
  6. list.pop([index=-1]) 移除列表中的一个元素(默认最后一个元素),并且返回该元素的值
  7. list.remove(obj) 移除列表中某个值的第一个匹配项
  8. list.reverse() 反向列表中元素
  9. list.sort( key=None, reverse=False) 对原列表进行排序
  10. list.clear() 清空列表
  11. list.copy() 复制列表

Leetcode 数组

26. 删除排序数组中的重复项

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

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

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

解题一:

关键信息:排序数组、原地删除

思路:快慢指针,慢指保护已处理好的数组,快指针不断寻找

慢指针i

快指针j

快指针 j >= i

当 num[i] != num[j] 时,说明,num[j]就是下一个不重复元素,应当保护起来

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

解题二:

如果本题不用快慢指针,且不需要空间复杂度时,有两个办法:

  • 1. 可以采用一个额外的数组,不断添加新的不重复元素
  • 2. 集合是不重复的,数组转集合,判断集合有多少个值 len(set(nums))

如果本题的数组是无序的,举例两种办法:

  • 1. collections.Counter ,collections.Counter 用于计数可哈希对象,它是一个集合,元素像字典键(key)一样存储,它们的计数存储为值
  • 2. 一个额外用于记录的字典,统计每个值出现的次数

122. 买卖股票的最佳时机 II

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解题一:

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:如何买卖,才能让自己收益最大?最后肯定手里是没有股票的。

关键信息:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

思路:第i天的收益,受到第i-1天的操作影响。

假如第i天,持有股票的收益最大为 dp[i][0]

假如第i天,不持有股票的收益最大为 dp[i][1]

那么:

dp[i][0] = max(dp[i-1][0],dp[i-1]+prices[i])

dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])

我们求最大利润,那么此时应该是不持有股票的,也就是第n天不持有股票,即求的是dp[n-1][0]的值。

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp[0][0] = 0         dp[0][1] = -prices[0]         for i in range(1,n):             dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])             dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])         return dp[n-1][0]

解题二:

解题一是可以优化的,用了2n的额外空间,来记录每天的最大利润。

观察 for循环,发现只和上一天的最大利润有关:

当天不持有股票时的最大利润为:dp0

当天持有股票时的最大利润为:dp1

class Solution :     def maxProfit(self,prices:List[int]) -> int:         n = len(prices)         dp = [[0 for _ in range(0,2)] for _ in range(0,n)]         dp0 = 0         dp1 = -prices[0]         for i in range(1,n):             dp0 = max(dp0,dp1+prices[i])             dp1 = max(dp0-prices[i],dp1)         return dp0

此时的空间复杂度为 O(1)。

解题三:

贪心算法,这个我还无法组织语言

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

189. 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

解题一:

关键信息:k是0 或者 正数

思路:如果不考虑空间复杂度,新数组只需一遍for循环 new = (i+k)%len(nums),即

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         news = [0 for _ in range(len(nums))]         for i in range(len(nums)):             index = (i+k)%len(nums)             news[index] = nums[i]         for i in range(len(nums)):             nums[i] = news[i]

切片的方式:

class Solution:     def rotate(self, nums: List[int], k: int) -> None:         """         Do not return anything, modify nums in-place instead.         """         k = k%len(nums)         new1 = nums[-k:]         new2 = nums[0:len(nums)-k]         new3 = new1 + new2          for i in range(len(nums)):             nums[i] = new3[i]

解题二:

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 用Python刷力扣:数组(上)求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们