目录
49. 字母异位词分组 Group Anagrams 🌟🌟
50. 幂函数 Pow(x, n) 🌟🌟
51. N 皇后 N-Queens 🌟🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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 转换成 i32if 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 mainimport ("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+colif cols[col] || diag1[id1] || diag2[id2] {continue}board[row][col] = 'Q'cols[col], diag1[id1], diag2[id2] = true, true, truebacktrack(row + 1)cols[col], diag1[id1], diag2[id2] = false, false, falseboard[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）暂停更 |
