Rust每日一练(Leetday0013) 解数独、外观数列、组合总和

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);
}

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));
    }
}

package main
import "fmt"
func combinationSum(candidates []int, target int) [][]int {
  var res [][]int
  var 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))
}

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));
}