力扣

zyKDM / 2023-08-03 / 原文

2023年8月1日08:56:14

力扣51 N皇后

"""
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
"""

回溯和BFS的区别在于，BFS是一个确定的树，而回溯面对的是隐形的树，暂时可以这么理解

每行每列恰好一个皇后

由题目分析可知解决本题目需要回溯算法

全排列A，组合排列C

class Solutiona:
def solveNQueens(self,n:int):
res = []
def is_valid(board,row,col):
# 检查所有的列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row-1, col-1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
return True

    def backtrack(board,row):
        if row == n:
            temp_res = []
            for temp in board:
                temp_str = ''.join(temp)
                temp_res.append(temp_str)
            res.append(temp_res)
            return
        
        for col in range(n):
            if is_valid(board,row,col):
                board[row][col] = 'Q'
                backtrack(board, row + 1)
                board[row][col] = '.'
        
    # for _ in range(*)这种写法，下划线可以替换为任何符合规定的字符串
    # 假如用到不需要传值的情况，我们就可以用这种写法
    board = [['.'for _ in range(n)] for _ in range(n)]
    backtrack(board,0)
    print(res)
    return res

class Solutionb:
def solveNQueens(self, n:int)->list[list[str]]:
ans = []
col = [0] * n

    def valid(r, c):
        for R in range(r):
            C = col[R]
            if r+c == R+C or r-c == R-C:
                return False
        return True
    
    def dfs(r, s):
        if r == n:
            ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col])
            return 
        for c in s:
            if valid(r, c):
                col[r] = c
                dfs(r+1,s-{c})
    dfs(0,set(range(n)))
    return ans

2023年8月1日14:26:17

力扣52 N皇后2

力扣53 最大子数组和

"""
给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。
"""

动态规划

class Solutionc:
def maxSubArray(self, nums: list[int]) -> int:
tmp = nums[0]
max_ = tmp
n = len(nums)
for i in range(1,n):
# 当当前序列加上此时的元素的值大于tmp的值，说明最大序列和可能出现在后续序列中，记录此时的最大值
if tmp + nums[i]>nums[i]:
max_ = max(max_, tmp+nums[i])
tmp = tmp + nums[i]
else:
#当tmp(当前和)小于下一个元素时，当前最长序列到此为止。以该元素为起点继续找最大子序列,
# 并记录此时的最大值
max_ = max(max_, tmp, tmp+nums[i], nums[i])
tmp = nums[i]
print(max_)
return max_

暴力算法

class Solutiond:
# 表示其接收一个整数数组，返回一个整数参数，一般我们定义函数时不会定义其得到的数值类型
def maxSubArray(self, nums: list[int]) -> int:
all_len = len(nums)
this_biggest = nums[0]
for index,ob in enumerate(nums):
sub_list = nums[index:]
this_biggest1 = nums[0]
for j_index, ob1 in enumerate(sub_list):
this_biggest2 = nums[0]
for i in range(all_len-j_index):
if sum(sub_list[j_index:all_len-i])>this_biggest2:
this_biggest2 = sum(sub_list[j_index:all_len-i])
print(i)
if this_biggest2>this_biggest1:
this_biggest1 = this_biggest2
if this_biggest1>this_biggest:
this_biggest = this_biggest1
print(this_biggest)
return this_biggest

力扣54 螺旋矩阵

"""
给你一个m行n列的矩阵matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
"""
class Solutione:
def spiralorder(self,matrix:list[list[int]])->list[int]:
# 如果传入的数组为空
if not matrix: return []
l = 0 #左
r = len(matrix[0]) - 1 #右
t = 0 #上
b = len(matrix[0]) - 1 #下
res = []
while True:
for i in range(l,r+1):
res.append(matrix[t][i])
t += 1
if t > b:
break
for i in range(t,b+1):
res.append(matrix[i][r])
r -= 1
if l > r:
break
for i in range(r,l-1,-1):
res.append(matrix[b][i])
b -= 1
if t > b:
break
for i in range(b,t-1,-1):
res.append(matrix[i][l])
l += 1
if l > r:
break
print(res)
return res