【LeetCode】力扣刷题之路 (20240916~20240920)
题目(20240916~20240920)
161. 连续天数的最高销售额
某公司每日销售额记于整数数组sales，请返回所有连续一或多天销售额总和的最大值。
要求实现时间复杂度为O(n)的算法。
示例1：
输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
示例2：
输入：sales = [5,4,-1,7,8]
输出：23
解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。
提示：
- 1 <= arr.length <= 105
- -100 <= arr[i] <= 100
方法1：动态规划
from typing import List
class Solution:
def maxSales(self, sales: List[int]) -> int:
max_rev = sales[0]
for i in range(1, len(sales)):
if sales[i - 1] > 0:
sales[i] += sales[i - 1]
max_rev = max(max_rev, sales[i])
return max_rev
if __name__ == "__main__":
s = Solution()
# 161.连续天数的最高销售额 - 示例1
sales = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
res = s.maxSales(sales)
print(res) # 输出：6
# 示例2
sales = [5, 4, -1, 7, 8]
res = s.maxSales(sales)
print(res) # 输出：23
方法2：分治
from typing import List
class Solution:
def maxSales(self, sales: List[int]) -> int:
# 分治函数(左右下标)
def dc(l, r):
# 只有一个元素时
if l == r:
t = max(sales[l], 0)
# 返回值设计成四元组,分别代表:区间和,前缀最大值,后缀最大值,最大子数组和;用[sum, lm, rm, max]表示
return [sales[l], t, t, t]
# 分成两组分别求解
mid = (l + r) // 2
left, right = dc(l, mid), dc(mid + 1, r)
ans = [0] * 4 # 四元组初始化0
ans[0] = left[0] + right[0] # 当前区间之和:sum = left[0] + right[0]
ans[1] = max(left[1], left[0] + right[1]) # 合并区间前缀最大值:lm = max(left[1], left[0] + right[1])
ans[2] = max(right[2], right[0] + left[2]) # 合并区间后缀最大值:rm = max(right[2], right[0] + left[2])
ans[3] = max(left[3], right[3], left[2] + right[1]) # 合并最大子数组和:max(left[3], right[3], left[2] + right[1])
return ans
# 若最大值小于0则返回最大值
m = max(sales)
if m <= 0:
return m
return dc(0, len(sales) - 1)[3]
if __name__ == "__main__":
s = Solution()
# 161.连续天数的最高销售额 - 示例1
sales = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
res = s.maxSales(sales)
print(res) # 输出：6
# 示例2
sales = [5, 4, -1, 7, 8]
res = s.maxSales(sales)
print(res) # 输出：23
181. 字符串中的单词反转
你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息message转换为正常语序。
注意：输入字符串message中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入: message = “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: message = " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: message = “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
提示:
- 1 <= message.length <= 104
- message 中包含英文大小写字母、空格和数字
- message 中至少有一个单词
方法1.双指针
class Solution:
def reverseMessage(self, message: str) -> str:
mg = message.strip() # 清除首尾空格
i = j = len(mg) - 1
res = []
while i >= 0:
while i >= 0 and mg[i] != ' ':
i -= 1
res.append(mg[i + 1: j + 1]) # 添加单词
while i >= 0 and mg[i] == ' ':
i -= 1 # 跳过空格
j = i # j指向下一个字符
return ' '.join(res)
if __name__ == '__main__':
s = Solution()
# 181.字符串中的单词反转 - 示例1
message = "the sky is blue"
res = s.reverseMessage(message)
print(res) # 输出："blue is sky the"
# 示例2
message = " hello world! "
res = s.reverseMessage(message)
print(res) # 输出："world! hello"
# 示例3
message = "a good example"
res = s.reverseMessage(message)
print(res) # 输出："example good a"
方法2.倒序函数
class Solution:
def reverseMessage(self, message: str) -> str:
mg = message.strip() # 清除首尾空格
strs = mg.split() # 分割
strs.reverse() # 翻转
return ' '.join(strs)
if __name__ == '__main__':
s = Solution()
# 181.字符串中的单词反转 - 示例1
message = "the sky is blue"
res = s.reverseMessage(message)
print(res) # 输出："blue is sky the"
# 示例2
message = " hello world! "
res = s.reverseMessage(message)
print(res) # 输出："world! hello"
# 示例3
message = "a good example"
res = s.reverseMessage(message)
print(res) # 输出："example good a"
原文地址：https://blog.csdn.net/weixin_44940843/article/details/142359598
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！