目录
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/