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^40 <= strs[i].length <= 100strs[i]仅包含小写字母
代码1： 排序+哈希表
use std::collections::HashMap; fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { let mut res = vec![]; let mut hash: HashMap<String, Vec<String>> = HashMap::new(); for str in strs { let key = sort_string(&str); hash.entry(key).or_default().push(str); } for v in hash.values() { res.push(v.clone()); } res } fn sort_string(s: &str) -> String { let mut s = s.chars().collect::<Vec<char>>(); s.sort(); s.into_iter().collect() } fn main() { let strs = vec![ "eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string(), ]; println!("{:?}", group_anagrams(strs)); }
输出：
[["bat"], ["eat", "tea", "ate"], ["tan", "nat"]]
代码2： 计数哈希表
use std::collections::HashMap; fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { let mut res = vec![]; let mut hash: HashMap<String, Vec<String>> = HashMap::new(); for str in strs { let key = count_string(&str); hash.entry(key).or_default().push(str); } for v in hash.values() { res.push(v.clone()); } res } fn count_string(s: &str) -> String { let mut cnt = [0; 26]; for c in s.chars() { cnt[c as usize - 'a' as usize] += 1; } let mut res = String::new(); for i in 0..26 { res.push_str(&cnt[i].to_string()); res.push('#'); } res } fn main() { let strs = vec![ "eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string(), ]; println!("{:?}", group_anagrams(strs)); }
输出：
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
代码3： 质数哈希表
use std::collections::HashMap; fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { let mut res = vec![]; let mut hash: HashMap<i32, Vec<String>> = HashMap::new(); let primes = vec![ 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 in strs { let key = count_prime(&str, &primes); hash.entry(key).or_default().push(str); } for v in hash.values() { res.push(v.clone()); } res } fn count_prime(s: &str, primes: &[i32]) -> i32 { let mut res = 1; for c in s.chars() { let index = (c as u32 - 'a' as u32) as usize; res *= primes[index]; } res } fn main() { let strs = vec![ "eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string(), ]; println!("{:?}", group_anagrams(strs)); } [["bat"], ["tan", "nat"], ["eat", "tea", "ate"]]
输出：
[["bat"], ["tan", "nat"], ["eat", "tea", "ate"]]
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：
fn my_pow(x: f64, n: i32) -> f64 { let mut n = n as i64; let mut res = 1.0; let mut x = x; if n < 0 { x = 1.0 / x; n = -n; } while n > 0 { if n & 1 == 1 { res *= x; } x *= x; n >>= 1; } res } fn main() { println!("{}", my_pow(2.0, 10)); println!("{}", my_pow(2.1, 3)); println!("{}", my_pow(2.0, -2)); }
输出：
1024
9.261000000000001
0.25
代码2：
use std::convert::TryInto; fn my_pow(x: f64, n: i32) -> f64 { if n == 0 { return 1.0; } if x == 1.0 || n == 1 { return x; } let mut n: i64 = n.try_into().unwrap(); let mut x = x; if n < 0 { x = 1.0 / x; n = -n; } let mut res = my_pow(x, (n/2).try_into().unwrap()); // 将 i64 转换成 i32 if n%2 == 0 { x = 1.0; } res *= res * x; res } fn main() { println!("{}", my_pow(2.0, 10)); println!("{}", my_pow(2.1, 3)); println!("{}", my_pow(2.0, -2)); }
输出：
1024
9.261000000000001
0.25
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：
fn solve_n_queens(n: i32) -> Vec<Vec<String>> { let mut res: Vec<Vec<String>> = Vec::new(); let mut board: Vec<Vec<char>> = vec![vec!['.'; n as usize]; n as usize]; fn is_valid(board: &[Vec<char>], row: usize, col: usize) -> bool { let n = board.len(); for i in 0..row { if board[i][col] == 'Q' { return false; } } let mut i = row as i32 - 1; let mut j = col as i32 - 1; while i >= 0 && j >= 0 { if board[i as usize][j as usize] == 'Q' { return false; } i -= 1; j -= 1; } let mut i = row as i32 - 1; let mut j = col as i32 + 1; while i >= 0 && j < n as i32 { if board[i as usize][j as usize] == 'Q' { return false; } i -= 1; j += 1; } true } fn backtrack( row: usize, n: i32, board: &mut Vec<Vec<char>>, res: &mut Vec<Vec<String>>, ) { if row == n as usize { let mut tmp: Vec<String> = Vec::new(); for i in 0..n { tmp.push(board[i as usize].iter().collect()); } res.push(tmp); return; } for col in 0..n { if is_valid(&board, row, col as usize) { board[row][col as usize] = 'Q'; backtrack(row + 1, n, board, res); board[row][col as usize] = '.'; } } } backtrack(0, n, &mut board, &mut res); res } fn main() { for i in (1..=4).rev() { println!("{:?}", solve_n_queens(i)); } }
代码3：
fn solve_n_queens(n: i32) -> Vec<Vec<String>> { let mut res: Vec<Vec<String>> = Vec::new(); let mut board: Vec<Vec<char>> = vec![vec!['.'; n as usize]; n as usize]; fn backtrack( row: usize, cols: i32, diagonals1: i32, diagonals2: i32, n: i32, board: &mut Vec<Vec<char>>, res: &mut Vec<Vec<String>>, ) { if row == n as usize { let mut tmp: Vec<String> = Vec::new(); for i in 0..n { tmp.push(board[i as usize].iter().collect()); } res.push(tmp); return; } let available_positions = ((1 << n) - 1) & !(cols | diagonals1 | diagonals2); let mut ap = available_positions; while ap != 0 { let position = ap & -ap; let col = (position - 1).count_ones(); board[row][col as usize] = 'Q'; backtrack(row + 1, cols | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1, n, board, res); board[row][col as usize] = '.'; ap &= ap - 1; } } backtrack(0, 0, 0, 0, n, &mut board, &mut res); res } fn main() { for i in (1..=4).rev() { println!("{:?}", solve_n_queens(i)); } }
代码4：
fn solve_n_queens(n: i32) -> Vec<Vec<String>> { let mut res: Vec<Vec<String>> = Vec::new(); let mut queens: Vec<String> = vec![vec!['.'; n as usize].iter().collect(); n as usize]; let mut cols: std::collections::HashSet<i32> = std::collections::HashSet::new(); let mut diag1: std::collections::HashSet<i32> = std::collections::HashSet::new(); let mut diag2: std::collections::HashSet<i32> = std::collections::HashSet::new(); fn backtrack( n: i32, row: usize, queens: &mut Vec<String>, cols: &mut std::collections::HashSet<i32>, diag1: &mut std::collections::HashSet<i32>, diag2: &mut std::collections::HashSet<i32>, res: &mut Vec<Vec<String>>, ) { if row == n as usize { res.push(queens.clone()); return; } for col in 0..n { if cols.contains(&(col as i32)) || diag1.contains(&(row as i32 - col as i32)) || diag2.contains(&(row as i32 + col as i32)) { continue; } queens[row] = queens[row][..col as usize].to_string() + "Q" + &queens[row][(col + 1) as usize..]; cols.insert(col as i32); diag1.insert(row as i32 - col as i32); diag2.insert(row as i32 + col as i32); backtrack(n, row + 1, queens, cols, diag1, diag2, res); queens[row] = queens[row][..col as usize].to_string() + "." + &queens[row][(col + 1) as usize..]; cols.remove(&(col as i32)); diag1.remove(&(row as i32 - col as i32)); diag2.remove(&(row as i32 + col as i32)); } } backtrack(n, 0, &mut queens, &mut cols, &mut diag1, &mut diag2, &mut res); res } fn main() { for i in (1..=4).rev() { println!("{:?}", solve_n_queens(i)); } }
🌟每日一练刷题专栏🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
