49. 字母异位词分组 Group Anagrams
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
代码1： 排序+哈希表
package main import ( "fmt" "sort" ) func groupAnagrams(strs []string) [][]string { res := [][]string{} hash := map[string][]string{} for _, str := range strs { key := sortString(str) hash[key] = append(hash[key], str) } for _, v := range hash { res = append(res, v) } return res } func sortString(str string) string { s := []byte(str) sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) return string(s) } func main() { strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"} fmt.Println(groupAnagrams(strs)) }
输出：
[[eat tea ate] [tan nat] [bat]]
代码2： 计数哈希表
package main import ( "fmt" "strconv" ) func groupAnagrams(strs []string) [][]string { res := [][]string{} hash := map[string][]string{} for _, str := range strs { key := countString(str) hash[key] = append(hash[key], str) } for _, v := range hash { res = append(res, v) } return res } func countString(str string) string { cnt := [26]int{} for i := range str { cnt[str[i]-'a']++ } res := "" for i := 0; i < 26; i++ { res += strconv.Itoa(cnt[i]) + "#" } return res } func main() { strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"} fmt.Println(groupAnagrams(strs)) }
代码3： 质数哈希表
package main import ( "fmt" ) func groupAnagrams(strs []string) [][]string { res := [][]string{} hash := map[int][]string{} primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103} for _, str := range strs { key := 1 for i := range str { key *= primes[int(str[i]-'a')] } hash[key] = append(hash[key], str) } for _, v := range hash { res = append(res, v) } return res } func main() { strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"} fmt.Println(groupAnagrams(strs)) }
50. 幂函数 Pow(x, n)
实现 pow(x,n)，即计算 x 的 n 次幂函数（即，x^n ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4
代码1：
package main import ( "fmt" ) func myPow(x float64, n int) float64 { if n == 0 { return 1 } if n < 0 { x = 1 / x n = -n } res := 1.0 for n > 0 { if n&1 == 1 { res *= x } x *= x n >>= 1 } return res } func main() { fmt.Println(myPow(2.0, 10)) fmt.Println(myPow(2.1, 3)) fmt.Println(myPow(2.0, -2)) }
输出：
1024
9.261000000000001
0.25
代码2：
package main import ( "fmt" ) func myPow(x float64, n int) float64 { if n == 0 { return 1 } if n < 0 { x = 1 / x n = -n } res := 1.0 for n > 0 { if n&1 == 1 { res *= x } x *= x n >>= 1 } return res } func main() { fmt.Println(myPow(2.0, 10)) fmt.Println(myPow(2.1, 3)) fmt.Println(myPow(2.0, -2)) }
输出：
1024
9.261000000000001
0.25
递归法：
package main import ( "fmt" ) func myPow(x float64, n int) float64 { if n == 0 { return 1 } if x == 1 || n == 1 { return x } if n < 0 { x = 1 / x n = -n } res := myPow(x, n/2) if n%2 == 0 { x = 1 } return res * res * x } func main() { fmt.Println(myPow(2.0, 10)) fmt.Println(myPow(2.1, 3)) fmt.Println(myPow(2.0, -2)) }
51. N 皇后 N-Queens
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
代码：
package main import ( "fmt" ) func solveNQueens(n int) [][]string { res := [][]string{} board := make([][]byte, n) for i := range board { board[i] = make([]byte, n) for j := range board[i] { board[i][j] = '.' } } cols, diag1, diag2 := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1) var backtrack func(int) backtrack = func(row int) { if row == n { tmp := make([]string, n) for i := range board { tmp[i] = string(board[i]) } res = append(res, tmp) return } for col := 0; col < n; col++ { id1, id2 := row-col+n-1, row+col if cols[col] || diag1[id1] || diag2[id2] { continue } board[row][col] = 'Q' cols[col], diag1[id1], diag2[id2] = true, true, true backtrack(row + 1) cols[col], diag1[id1], diag2[id2] = false, false, false board[row][col] = '.' } } backtrack(0) return res } func main() { for i := 4; i > 0; i-- { fmt.Println(solveNQueens(i)) } }
输出：
[[.Q.. ...Q Q... ..Q.] [..Q. Q... ...Q .Q..]]
[]
[]
[[Q]]
代码2：
package main import ( "fmt" ) func solveNQueens(n int) [][]string { res := [][]string{} board := make([][]byte, n) for i := range board { board[i] = make([]byte, n) for j := range board[i] { board[i][j] = '.' } } var backtrack func(row int) backtrack = func(row int) { if row == n { tmp := make([]string, n) for i := range board { tmp[i] = string(board[i]) } res = append(res, tmp) return } for col := 0; col < n; col++ { if isValid(board, row, col) { board[row][col] = 'Q' backtrack(row + 1) board[row][col] = '.' } } } backtrack(0) return res } func isValid(board [][]byte, row, col int) bool { n := len(board) for i := 0; i < row; i++ { if board[i][col] == 'Q' { return false } } for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 { if board[i][j] == 'Q' { return false } } for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 { if board[i][j] == 'Q' { return false } } return true } func main() { for i := 4; i > 0; i-- { fmt.Println(solveNQueens(i)) } }
代码3：
package main import ( "fmt" "math/bits" ) func solveNQueens(n int) [][]string { res := [][]string{} board := make([][]byte, n) for i := range board { board[i] = make([]byte, n) for j := range board[i] { board[i][j] = '.' } } var backtrack func(row int, cols, diagonals1, diagonals2 int) backtrack = func(row, cols, diagonals1, diagonals2 int) { if row == n { tmp := make([]string, n) for i := range board { tmp[i] = string(board[i]) } res = append(res, tmp) return } availablePositions := ((1 << n) - 1) & (^(cols | diagonals1 | diagonals2)) for availablePositions != 0 { position := availablePositions & -availablePositions col := bits.OnesCount(uint(position - 1)) board[row][col] = 'Q' backtrack(row+1, cols|position, (diagonals1|position)<<1, (diagonals2|position)>>1) board[row][col] = '.' availablePositions &= availablePositions - 1 } } backtrack(0, 0, 0, 0) return res } func main() { for i := 4; i > 0; i-- { fmt.Println(solveNQueens(i)) } }
代码4：
package main import ( "fmt" "strings" ) func solveNQueens(n int) [][]string { res := [][]string{} cols, diag1, diag2 := make(map[int]bool), make(map[int]bool), make(map[int]bool) queens := make([]string, n) for i := 0; i < n; i++ { queens[i] = strings.Repeat(".", n) } backtrack(n, 0, queens, cols, diag1, diag2, &res) return res } func backtrack(n, row int, queens []string, cols, diag1, diag2 map[int]bool, res *[][]string) { if row == n { tmp := make([]string, n) copy(tmp, queens) *res = append(*res, tmp) return } for col := 0; col < n; col++ { if cols[col] || diag1[row-col] || diag2[row+col] { continue } queens[row] = queens[row][:col] + "Q" + queens[row][col+1:] cols[col], diag1[row-col], diag2[row+col] = true, true, true backtrack(n, row+1, queens, cols, diag1, diag2, res) queens[row] = queens[row][:col] + "." + queens[row][col+1:] cols[col], diag1[row-col], diag2[row+col] = false, false, false } } func main() { for i := 4; i > 0; i-- { fmt.Println(solveNQueens(i)) } }
