leetcode 53. 最大子数组和 54. 螺旋矩阵
53. 最大子数组和
难度简单4073收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
class status:
def __init__(self, lsum, rsum, msum, isum):
self.lsum = lsum
self.rsum = rsum
self.msum = msum
self.isum = isum
class Solution:
"""
分治
"""
def maxSubArray(self, nums: List[int]) -> int:
def pushUp(lsub, rsub):
isum = lsub.isum + rsub.isum
lsum = max(lsub.lsum, lsub.isum + rsub.lsum)
rsum = max(rsub.rsum, rsub.isum + lsub.rsum)
msum = max(max(lsub.msum, rsub.msum), lsub.rsum + rsub.lsum)
return status(lsum, rsum, msum, isum)
def dfs(a, l, r):
if l == r:
return status(a[l], a[l], a[l], a[l])
m = (l + r) >> 1
lsub = dfs(a, l, m)
rsub = dfs(a, m + 1, r)
return pushUp(lsub, rsub)
return dfs(nums, 0, len(nums) - 1).msum
"""
动态规划
"""
def maxSubArray4(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i - 1] > 0:
nums[i] = nums[i - 1] + nums[i]
return max(nums)
"""
贪心
"""
def maxSubArray3(self, nums: List[int]) -> int:
length = len(nums)
s = ans = nums[0]
if length == 1:
return ans
for i in range(1, length):
s = max(nums[i], s + nums[i])
ans = max(ans, s)
return ans
def maxSubArray2(self, nums: List[int]) -> int:
length = len(nums)
ans = nums[0]
s = 0
if length == 1:
return ans
for i in range(length):
ans = max(ans, nums[i])
s += nums[i]
if s < 0:
s = 0
if nums[i] > 0:
ans = max(ans, s)
return ans
54. 螺旋矩阵
难度中等924收藏分享切换为英文接收动态反馈
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# @Time : 2021/11/18 16:03
# @Author : mtl
# @Desc : ***
# @File : 54.py
# @Software: PyCharm
from typing import List
import math
class Solution:
def spiralOrder3(self, matrix: List[List[int]]) -> List[int]:
cols, rows = len(matrix[0]), len(matrix)
total = cols * rows
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
n = 0
pos = [[False for _ in range(cols)] for _ in range(rows)]
num = 0
row, col = 0,0
out_matrix = []
while n < total:
pos[row][col] = True
out_matrix .append(matrix[row][col])
row, col = row + direction[num][0], col + direction[num][1]
if (row >= rows or row < 0) or \
(col >= cols or col < 0) or pos[row][col]:
row, col = row - direction[num][0], col - direction[num][1]
num += 1
if num >= len(direction):
num = 0
row, col = row + direction[num][0], col + direction[num][1]
n += 1
return out_matrix
def spiralOrder2(self, matrix: List[List[int]]) -> List[int]:
col, row = len(matrix[0]), len(matrix)
n = math.ceil(min(col, row) / 2)
out = []
if row == 1:
return matrix[0]
if col == 1:
return [i[0] for i in matrix]
for i in range(n):
for j in range(col - i * 2 if row - i * 2 - 1 == 0 else col - i * 2 - 1):
out.append(matrix[i][j + i])
for j in range(row - i * 2 if col - i * 2 - 1 == 0 and col != row else row - i * 2 - 1):
out.append(matrix[j + i][col - 1 - i])
if col - i * 2 - 1 > 0 and row - i * 2 - 1 > 0:
for j in range(col - i * 2 - 1):
out.append(matrix[row - i - 1][col - i - j - 1])
for j in range(row - i * 2 - 1):
out.append(matrix[row - i - j - 1][i])
return out
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return list()
rows, columns = len(matrix), len(matrix[0])
order = list()
left, right, top, bottom = 0, columns - 1, 0, rows - 1
while left <= right and top <= bottom:
for column in range(left, right + 1):
order.append(matrix[top][column])
for row in range(top + 1, bottom + 1):
order.append(matrix[row][right])
if left < right and top < bottom:
for column in range(right - 1, left, -1):
order.append(matrix[bottom][column])
for row in range(bottom, top, -1):
order.append(matrix[row][left])
left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
return order
if __name__ == '__main__':
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
matrix = [[6, 9, 7]]
matrix = [[7], [9], [6]]
# matrix = [[1, 2, 3, 4,1], [5, 6, 7, 8,1], [9, 10, 11, 12,1], [13, 14, 15, 16,1],[17, 18, 19, 20,1],[21, 22, 23, 24,1]]
# matrix = [[1, 2, 3], [5, 6, 7], [9, 10, 11]]
matrix = [[2,3,4]
,[5,6,7]
,[8,9,10]
,[11,12,13]
,[14,15,16]]
matrix = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15]]
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# print(0,0 + 0,1)
print(Solution().spiralOrder(matrix))
,[14,15,16]]
matrix = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15]]
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# print(0,0 + 0,1)
print(Solution().spiralOrder(matrix))