目录

52. N皇后 II N Queens II  🌟🌟🌟

53. 最大子数组和  Maximum Subarray  🌟🌟

54. 螺旋矩阵 Spiral Matrix  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

52. N皇后 II N Queens II

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

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

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

相关题目： N皇后  N Queens

 https://hannyang.blog.csdn.net/article/details/129772806#t2

代码1： 回溯法

func totalNQueens(n int) int {
    var res int
    queens := make([]int, n)
    var backtrack func(int)
    backtrack = func(row int) {
        if row == n {
            res++
            return
        }
        for col := 0; col < n; col++ {
            if isNotUnderAttack(queens, row, col) {
                queens[row] = col
                backtrack(row + 1)
                queens[row] = 0
            }
        }
    }
    backtrack(0)
    return res
}
func isNotUnderAttack(queens []int, row, col int) bool {
    for i := 0; i < row; i++ {
        if queens[i] == col || queens[i]+i == row+col || queens[i]-i == col-row {
            return false
        }
    }
    return true
}

代码2： 位运算

bits := (^(col | ld | rd)) & ((1 << n) - 1)

func totalNQueens(n int) int {
    var res int
    var dfs func(int, int, int, int)
    dfs = func(row, col, ld, rd int) {
        if row == n {
            res++
            return
        }
        bits := (^(col | ld | rd)) & ((1 << n) - 1)
        for bits != 0 {
            pick := bits & -bits
            dfs(row+1, col|pick, (ld|pick)<<1, (rd|pick)>>1)
            bits &= bits - 1
        }
    }
    dfs(0, 0, 0, 0)
    return res
}

---

53. 最大子数组和  Maximum Subarray

给你一个整数数组 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 <= 10^5
• -10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

代码1： 动态规划

func maxSubArray(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    dp[0] = nums[0]
    for i := 1; i < n; i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
    }
    res := dp[0]
    for i := 1; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

代码2： 贪心算法

func maxSubArray(nums []int) int {
    n := len(nums)
    curSum, maxSum := 0, nums[0]
    for i := 0; i < n; i++ {
        curSum += nums[i]
        if curSum > maxSum {
            maxSum = curSum
        }
        if curSum < 0 {
            curSum = 0
        }
    }
    return maxSum
}

---

54. 螺旋矩阵 Spiral Matrix

给你一个 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.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

代码1：

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return nil
    }
    m, n := len(matrix), len(matrix[0])
    res := make([]int, m*n)
    top, bottom, left, right := 0, m-1, 0, n-1
    idx := 0
    for top <= bottom && left <= right {
        for i := left; i <= right; i++ {
            res[idx] = matrix[top][i]
            idx++
        }
        for i := top + 1; i <= bottom; i++ {
            res[idx] = matrix[i][right]
            idx++
        }
        if top < bottom && left < right {
            for i := right - 1; i > left; i-- {
                res[idx] = matrix[bottom][i]
                idx++
            }
            for i := bottom; i > top; i-- {
                res[idx] = matrix[i][left]
                idx++
            }
        }
        top++
        bottom--
        left++
        right--
    }
    return res
}

代码2： 递归

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return nil
    }
    m, n := len(matrix), len(matrix[0])
    res := make([]int, 0, m*n)
    var spiral func(int, int, int, int)
    spiral = func(top, bottom, left, right int) {
        if top > bottom || left > right {
            return
        }
        for i := left; i <= right; i++ {
            res = append(res, matrix[top][i])
        }
        for i := top + 1; i <= bottom; i++ {
            res = append(res, matrix[i][right])
        }
        if top < bottom && left < right {
            for i := right - 1; i > left; i-- {
                res = append(res, matrix[bottom][i])
            }
            for i := bottom; i > top; i-- {
                res = append(res, matrix[i][left])
            }
        }
        spiral(top+1, bottom-1, left+1, right-1)
    }
    spiral(0, m-1, 0, n-1)
    return res
}

代码3： 迭代器

type spiralIterator struct {
    m, n  int
    x, y  int
    dx, dy [4]int
}
func newSpiralIterator(m, n int) *spiralIterator {
    return &spiralIterator{
        m:  m,
        n:  n,
        dx: [4]int{0, 1, 0, -1},
        dy: [4]int{1, 0, -1, 0},
    }
}
func (it *spiralIterator) hasNext() bool {
    return 0 <= it.x && it.x < it.m && 0 <= it.y && it.y < it.n
}
func (it *spiralIterator) next() int {
    res := (it.x * it.n) + it.y + 1
    it.x += it.dx[0]
    it.y += it.dy[0]
    if !it.hasNext() {
        return res
    }
    if it.x == it.m && it.y == it.n-1 {
        it.dx[0], it.dy[0] = it.dx[3], it.dy[3]
        it.m--
    } else if it.x == it.m-1 && it.y == 0 {
        it.dx[0], it.dy[0] = it.dx[1], it.dy[1]
        it.n--
    } else if it.x == 0 && it.y == it.n-1 {
        it.dx[0], it.dy[0] = it.dx[2], it.dy[2]
        it.m--
    } else if it.y == 0 && it.x == 1 {
        it.dx[0], it.dy[0] = it.dx[0], it.dy[0]
        it.n--
        it.x = 0
    } else {
        it.x += it.dx[0]
        it.y += it.dy[0]
    }
    return res
}
func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return nil
    }
    m, n := len(matrix), len(matrix[0])
    res := make([]int, 0, m*n)
    it := newSpiralIterator(m, n)
    for it.hasNext() {
        res = append(res, matrix[it.x][it.y])
        it.next()
    }
    return res
}

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏