目录
37. 解数独 Sudoku Solver 🌟🌟🌟
38. 外观数列 Count and Say 🌟🌟
39. 组合总和 Combination Sum 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
37. 解数独 Sudoku Solver
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.'
表示。
示例 1:
输入:board = [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]]输出: [["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"], ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]]解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字或者'.'
- 题目数据 保证 输入数独仅有一个解
代码:
fn solve_sudoku(board: &mut Vec<Vec<char>>) {let mut pos: Vec<[usize; 2]> = Vec::new();let mut find = false;for i in 0..board.len() {for j in 0..board[0].len() {if board[i][j] == '.' {pos.push([i, j]);}}}put_sudoku(board, &pos, 0, &mut find);
}fn put_sudoku(board: &mut Vec<Vec<char>>,pos: &Vec<[usize; 2]>,index: usize,succ: &mut bool,
) {if *succ {return;}if index == pos.len() {*succ = true;return;}for i in 1..=9 {if check_sudoku(board, pos[index], i) && !*succ {board[pos[index][0]][pos[index][1]] = (i as u8 + b'0') as char;put_sudoku(board, pos, index + 1, succ);if *succ {return;}board[pos[index][0]][pos[index][1]] = '.';}}
}fn check_sudoku(board: &Vec<Vec<char>>, pos: [usize; 2], val: usize) -> bool {// 判断行是否有重复数字for i in 0..board[0].len() {if board[pos[0]][i] != '.' && (board[pos[0]][i] as u8 - b'0') as usize == val {return false;}}// 判断列是否有重复数字for i in 0..board.len() {if board[i][pos[1]] != '.' && (board[i][pos[1]] as u8 - b'0') as usize == val {return false;}}// 判断九宫格是否有重复数字let posx = pos[0] - pos[0] % 3;let posy = pos[1] - pos[1] % 3;for i in posx..posx + 3 {for j in posy..posy + 3 {if board[i][j] != '.' && (board[i][j] as u8 - b'0') as usize == val {return false;}}}true
}fn main() {let mut board: Vec<Vec<char>> = vec![vec!['5', '3', '.', '.', '7', '.', '.', '.', '.'],vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'],vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'],vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'],vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'],vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'],vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'],vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'],vec!['.', '.', '.', '.', '8', '.', '.', '7', '9'],];solve_sudoku(&mut board);for row in &board {for col in row {print!("{} ", (*col as u8 - b'0') as usize);}println!();}let answer: Vec<Vec<char>> = vec![vec!['5', '3', '4', '6', '7', '8', '9', '1', '2'],vec!['6', '7', '2', '1', '9', '5', '3', '4', '8'],vec!['1', '9', '8', '3', '4', '2', '5', '6', '7'],vec!['8', '5', '9', '7', '6', '1', '4', '2', '3'],vec!['4', '2', '6', '8', '5', '3', '7', '9', '1'],vec!['7', '1', '3', '9', '2', '4', '8', '5', '6'],vec!['9', '6', '1', '5', '3', '7', '2', '8', '4'],vec!['2', '8', '7', '4', '1', '9', '6', '3', '5'],vec!['3', '4', '5', '2', '8', '6', '1', '7', '9'],];// 判断与答案是否一致let mut equal = true;for i in 0..board.len() {for j in 0..board[0].len() {if board[i][j] != answer[i][j] {equal = false;break;}}if !equal {break;}}println!("{}", equal);
}
输出:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
true
38. 外观数列 Count and Say
给定一个正整数 n
,输出外观数列的第 n
项。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列:
countAndSay(1) = "1"
countAndSay(n)
是对countAndSay(n-1)
的描述,然后转换成另一个数字字符串。
前五项如下:
1. 1 2. 11 3. 21 4. 1211 5. 111221 第一项是数字 1 描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11" 描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21" 描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211" 描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。
例如,数字字符串 "3322251"
的描述如下图:
示例 1:
输入:n = 1 输出:"1" 解释:这是一个基本样例。
示例 2:
输入:n = 4 输出:"1211" 解释: countAndSay(1) = "1" countAndSay(2) = 读 "1" = 一 个 1 = "11" countAndSay(3) = 读 "11" = 二 个 1 = "21" countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示:
1 <= n <= 30
代码:
fn count_and_say(n: i32) -> String {if n == 1 {return String::from("1");}let prev = count_and_say(n - 1);let mut res = String::new();let mut i = 0;let mut j = 0;while j <= prev.len() {if j == prev.len() || prev.chars().nth(j) != prev.chars().nth(i) {res += &(j - i).to_string();res += &prev.chars().nth(i).unwrap().to_string();i = j;}j += 1;}res
}fn main() {for i in 1..=5 {println!("{}", count_and_say(i));}
}
输出:
1
11
21
1211
111221
39. 组合总和 Combination Sum
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
示例 1:
输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1 输出: []
提示:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate
中的每个元素都 互不相同1 <= target <= 500
代码1: 回溯法
package mainimport "fmt"func combinationSum(candidates []int, target int) [][]int {var res [][]intvar backtrack func([]int, int, int)backtrack = func(path []int, sum int, start int) {if sum >= target {if sum == target {res = append(res, append([]int{}, path...))return}return}for i := start; i < len(candidates); i++ {path = append(path, candidates[i])backtrack(path, sum+candidates[i], i)path = path[:len(path)-1]}}backtrack([]int{}, 0, 0)return res
}func main() {candidates := []int{2, 3, 6, 7}fmt.Println(combinationSum(candidates, 7))candidates = []int{2, 3, 5}fmt.Println(combinationSum(candidates, 8))candidates = []int{2}fmt.Println(combinationSum(candidates, 1))}
输出:
[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]
代码2: 回溯法
fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {if candidates.is_empty() {return Vec::new();}let mut res = Vec::new();let mut c = Vec::new();let mut nums = candidates.clone();nums.sort();backtrack(&nums, target, 0, &mut c, &mut res);res
}fn backtrack(nums: &Vec<i32>, target: i32, index: usize, c: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {if target <= 0 {if target == 0 {res.push(c.clone());}return;}for i in index..nums.len() {if nums[i] > target {break;}c.push(nums[i]);backtrack(nums, target - nums[i], i, c, res);c.pop();}
}fn main() {let candidates = vec![2, 3, 6, 7];println!("{:?}", combination_sum(candidates, 7));let candidates = vec![2, 3, 5];println!("{:?}", combination_sum(candidates, 8));let candidates = vec![2];println!("{:?}", combination_sum(candidates, 1));
}
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页: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)暂停更 |