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 }
