#![allow(unused)]
fn main() {
use crate::list::ListNode;
/// @number 2
/// @title Add Two Numbers
/// @url https://leetcode.com/problems/add-two-numbers
/// @difficulty medium
struct Solution;
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = None;
let mut cursor = &mut head;
let mut one = &l1;
let mut two = &l2;
let mut step_in = false;
while one.is_some() || two.is_some() {
let one_value = if one.is_some() { one.as_ref().unwrap().val } else { 0 };
let two_value = if two.is_some() { two.as_ref().unwrap().val } else { 0 };
let count = (one_value + two_value + if step_in { 1 } else { 0 }) % 10;
step_in = (one_value + two_value + if step_in { 1 } else { 0 }) > 9;
*cursor = Some(Box::new(ListNode { val: count, next: None }));
cursor = &mut cursor.as_mut().unwrap().next;
if one.is_some() { one = &one.as_ref().unwrap().next };
if two.is_some() { two = &two.as_ref().unwrap().next };
}
if step_in {
*cursor = Some(Box::new(ListNode{ val: 1, next: None }))
}
head
}
}
#[cfg(test)]
mod test {
use crate::add_two_number::Solution;
use crate::list::ListNode;
#[test]
fn should_return_708() {
let l1 = ListNode::build_from_vec(vec![2, 4, 3]);
let l2 = ListNode::build_from_vec(vec![5, 6, 4]);
let ret = Solution::add_two_numbers(l1, l2);
assert_eq!(ListNode::build_from_vec(vec![7, 0, 8]), ret);
}
#[test]
fn should_return_01() {
let l1 = ListNode::build_from_vec(vec![5]);
let l2 = ListNode::build_from_vec(vec![5]);
let ret = Solution::add_two_numbers(l1, l2);
assert_eq!(ListNode::build_from_vec(vec![0, 1]), ret);
}
}
}
#![allow(unused)]
fn main() {
/// @number 11
/// @title Container With Most Water
/// @url https://leetcode.com/problems/container-with-most-water/
/// @difficulty medium
struct Solution;
impl Solution {
pub fn max_area(height: Vec<i32>) -> i32 {
use std::cmp::{min, max};
// let len = height.len();
// let mut max_size = 0;
// for start in 0..len {
// for end in start..len {
// let current_max = (end - start) as i32 * min(height[start], height[end]);
// max_size = max(current_max, max_size);
// }
// }
// max_size
/// two pointer solution
let mut start = 0usize;
let mut end = height.len() - 1;
let mut max_size = 0;
while start < end {
let current_max = (end - start) as i32 * min(height[start], height[end]);
max_size = max(current_max, max_size);
if height[start] < height[end] {
start += 1;
} else {
end -= 1;
}
}
max_size
}
}
#[cfg(test)]
mod test {
use crate::container_with_most_water::Solution;
#[test]
fn test() {
assert_eq!(49, Solution::max_area(vec![1, 8, 6, 2, 5, 4, 8, 3, 7]));
}
}
}
#![allow(unused)]
fn main() {
/// @number 942
/// @title DI String Match
/// @url https://leetcode.com/problems/di-string-match
/// @difficulty easy
struct Solution;
impl Solution {
pub fn di_string_match(s: String) -> Vec<i32> {
let mut end = s.len() as i32;
let mut start = 0;
let mut ret: Vec<i32> = vec![];
s.chars().for_each(|element| {
match element {
'I' => {
ret.push(start);
start += 1;
}
'D' => {
ret.push(end);
end -= 1;
}
_ => {}
};
});
ret.push(start);
ret
}
}
#[test]
fn idid() {
assert_eq!(Solution::di_string_match(String::from("IDID")), vec![0, 4, 1, 3, 2]);
}
#[test]
fn iii() {
assert_eq!(Solution::di_string_match(String::from("III")), vec![0, 1, 2, 3]);
}
#[test]
fn ddi() {
assert_eq!(Solution::di_string_match(String::from("DDI")), vec![3, 2, 0, 1]);
}
}
#![allow(unused)]
fn main() {
/// @number 832
/// @title Flipping an Image
/// @url https://leetcode.com/problems/flipping-an-image
/// @difficulty easy
struct Solution;
impl Solution {
pub fn flip_and_invert_image(a: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
a.into_iter()
.map(|mut v| {
v.reverse();
v.into_iter()
.map(|element| element ^ 1)
.collect::<Vec<i32>>()
})
.collect()
}
}
#[test]
fn test1() {
assert_eq!(
Solution::flip_and_invert_image(vec![vec![1, 1, 0], vec![1, 0, 1], vec![0, 0, 0]]),
vec![vec![1, 0, 0], vec![0, 1, 0], vec![1, 1, 1]]
)
}
#[test]
fn test2() {
assert_eq!(
Solution::flip_and_invert_image(vec![
vec![1, 1, 0, 0],
vec![1, 0, 0, 1],
vec![0, 1, 1, 1],
vec![1, 0, 1, 0]
]),
vec![
vec![1, 1, 0, 0],
vec![0, 1, 1, 0],
vec![0, 0, 0, 1],
vec![1, 0, 1, 0]
]
)
}
}
#![allow(unused)]
fn main() {
/// @number 461
/// @title Hamming Distance
/// @url https://leetcode.com/problems/hamming-distance
/// @difficulty easy
struct Solution;
impl Solution {
pub fn hamming_distance(x: i32, y: i32) -> i32 {
let mut ret = x ^ y;
let mut sum = 0;
while ret != 0 {
sum += ret % 2;
ret /= 2;
};
sum
}
}
#[test]
fn test() {
assert_eq!(Solution::hamming_distance(1, 4), 2);
assert_eq!(Solution::hamming_distance(1, 0), 1);
}
}
#![allow(unused)]
fn main() {
/// @number 12
/// @title Integer to Roman
/// @url https://leetcode.com/problems/integer-to-roman
/// @difficulty medium
struct Solution;
impl Solution {
pub fn int_to_roman(num: i32) -> String {
let mut num_clone = num;
let mut ret = String::new();
while num_clone > 0 {
let x = match num_clone {
1000...std::i32::MAX => ("M", 1000),
900...1000 => ("CM", 900),
500...900 => ("D", 500),
400...500 => ("CD", 400),
100...400 => ("C", 100),
90...100 => ("XC", 90),
50...90 => ("L", 50),
40...50 => ("XL", 40),
10...40 => ("X", 10),
9 => ("IX", 9),
5...9 => ("V", 5),
4 => ("IV", 4),
1...4 => ("I", 1),
_ => unreachable!()
};
ret.push_str(x.0);
num_clone -= x.1;
}
ret
}
}
#[cfg(test)]
mod test {
use crate::integer_to_roman::Solution;
#[test]
fn should_return_iii_given_3() {
assert_eq!("III", &Solution::int_to_roman(3));
}
#[test]
fn should_return_iv_given_4() {
assert_eq!("IV", &Solution::int_to_roman(4));
}
#[test]
fn should_return_ix_given_9() {
assert_eq!("IX", &Solution::int_to_roman(9));
}
#[test]
fn should_return_lviii_given_58() {
assert_eq!("LVIII", &Solution::int_to_roman(58));
}
#[test]
fn should_return_mcmxciv_given_1994() {
assert_eq!("MCMXCIV", &Solution::int_to_roman(1994));
}
}
}
#![allow(unused)]
fn main() {
/// @number 771
/// @title Jewels and Stones
/// @url https://leetcode.com/problems/jewels-and-stones
/// @difficulty easy
struct Solution();
impl Solution {
pub fn num_jewels_in_stones(j: String, s: String) -> i32 {
let mut sum: i32 = 0;
j.chars().for_each(|each_char| {
s.chars().for_each(|inner_char|{
if inner_char == each_char {
sum += 1;
}
});
});
sum
}
}
#[test]
fn all_test() {
assert_eq!(Solution::num_jewels_in_stones("z".to_string(), "ZZ".to_string()), 0);
assert_eq!(Solution::num_jewels_in_stones("z".to_string(), "zZ".to_string()), 1);
}
}
#![allow(unused)]
fn main() {
/// @number 104
/// @title Maximum Depth of Binary Tree
/// @url https://leetcode.com/problems/maximum-depth-of-binary-tree
/// @difficulty easy
//Given a binary tree, find its maximum depth.
//
// The maximum depth is the number of nodes along the longest path from the root
// node down to the farthest leaf node.
//
// Note: A leaf is a node with no children.
//
// Example:
//
// Given binary tree [3,9,20,null,null,15,7],
//
//
// 3
// / \
// 9 20
// / \
// 15 7
//
// return its depth = 3.
// Related Topics Tree Depth-first Search
// 👍 2511 👎 73
use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::max;
struct Solution;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None
}
}
}
//leetcode submit region begin(Prohibit modification and deletion)
// Definition for a binary tree node.
impl Solution {
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
// using reference to avoid clone
pub fn _max_depth(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
if let Some(root_node) = root {
let node_borrow = root_node.borrow();
let left_depth = _max_depth(&node_borrow.left);
let right_depth = _max_depth(&node_borrow.right);
std::cmp::max(left_depth, right_depth) + 1
}else {
0
}
}
_max_depth(&root)
}
}
//leetcode submit region end(Prohibit modification and deletion)
#[cfg(test)]
mod test {
use crate::maximum_depth_of_binary_tree::{Solution, TreeNode};
use std::rc::Rc;
use std::cell::RefCell;
#[test]
fn test() {
let node15 = TreeNode::new(15);
let node7 = TreeNode::new(7);
let mut node20 = TreeNode::new(20);
node20.left = Some(Rc::new(RefCell::new(node15)));
node20.right = Some(Rc::new(RefCell::new(node7)));
let node9 = TreeNode::new(9);
let mut node3 = TreeNode::new(3);
node3.left = Some(Rc::new(RefCell::new(node20)));
node3.right = Some(Rc::new(RefCell::new(node9)));
assert_eq!(3, Solution::max_depth(Some(Rc::new(RefCell::new(node3)))));
}
#[test]
fn test2() {
assert_eq!(0, Solution::max_depth(None))
}
}
}
#![allow(unused)]
fn main() {
/// @number 617
/// @title Merge Two Binary Trees
/// @url https://leetcode.com/problems/merge-two-binary-trees
/// @difficulty easy
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
use std::cell::RefCell;
use std::rc::Rc;
struct Solution;
impl Solution {
pub fn merge_trees(
t1: Option<Rc<RefCell<TreeNode>>>,
t2: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
match (t1, t2) {
(t, None) | (None, t) => t,
(Some(t1), Some(t2)) => {
let (t1, t2) = (t1.borrow(), t2.borrow());
Some(Rc::new(RefCell::new(TreeNode {
val: t1.val + t2.val,
left: Solution::merge_trees(t1.left.clone(), t2.left.clone()),
right: Solution::merge_trees(t1.right.clone(), t2.right.clone()),
})))
}
}
}
}
}
#![allow(unused)]
fn main() {
/// @number 292
/// @title Nim Game
/// @url https://leetcode.com/problems/nim-game
/// @difficulty easy
struct Solution();
impl Solution {
pub fn can_win_nim(n: i32) -> bool {
match n {
1...3 => true,
_ if n % 4 == 0 => false,
_ => true
}
}
}
#[test]
fn test() {
assert!(!Solution::can_win_nim(4));
assert!(Solution::can_win_nim(3));
assert!(Solution::can_win_nim(6));
}
}
#![allow(unused)]
fn main() {
/// @number 9
/// @title Palindrome Number
/// @url https://leetcode.com/problems/palindrome-number/
/// @difficulty easy
struct Solution;
impl Solution {
pub fn is_palindrome(x: i32) -> bool {
if x < 0 { return false; }
let string = x.to_string();
let mut chars: Vec<char> = string.chars().collect();
while chars.len() > 1 {
let last = chars.pop().unwrap();
let first = chars.remove(0);
if first != last {
return false;
}
}
true
}
}
#[cfg(test)]
mod test {
use crate::palindrome_number::Solution;
#[test]
fn should_return_true_given_121() {
assert_eq!(true, Solution::is_palindrome(121));
}
#[test]
fn should_return_false_given_negative_number() {
assert_eq!(false, Solution::is_palindrome(-121));
}
#[test]
fn should_return_true_given_zero() {
assert_eq!(true, Solution::is_palindrome(0));
}
#[test]
fn should_return_false_given_10() {
assert_eq!(false, Solution::is_palindrome(10));
}
}
}
#![allow(unused)]
fn main() {
/// @number 46
/// @title Permutations
/// @url https://leetcode.com/problems/permutations
/// @difficulty medium
//Given a collection of distinct integers, return all possible permutations.
//
// Example:
//
//
//Input: [1,2,3]
//Output:
//[
// [1,2,3],
// [1,3,2],
// [2,1,3],
// [2,3,1],
// [3,1,2],
// [3,2,1]
//]
//
// Related Topics Backtracking
// 👍 3843 👎 106
//leetcode submit region begin(Prohibit modification and deletion)
struct Solution;
impl Solution {
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
if nums.len() <= 1 { return vec![nums]; };
let mut ret = vec![];
for i in 0..nums.len() {
let mut iter_ret = vec![];
let mut cloned_nums = nums.clone();
let index_item = cloned_nums.remove(i);
iter_ret.push(index_item);
for x in Solution::permute(cloned_nums) {
let mut cloned_iter_ret = iter_ret.clone();
cloned_iter_ret.extend(x);
ret.push(cloned_iter_ret);
}
}
ret
}
}
//leetcode submit region end(Prohibit modification and deletion)
#[cfg(test)]
mod test {
use crate::permutations::Solution;
#[test]
fn test() {
let ret = vec![
vec![1, 2, 3],
vec![1, 3, 2],
vec![2, 1, 3],
vec![2, 3, 1],
vec![3, 1, 2],
vec![3, 2, 1]
];
assert_eq!(ret, Solution::permute(vec![1, 2, 3]));
}
}
}
#![allow(unused)]
fn main() {
/// @number 7
/// @title Reverse Integer
/// @url https://leetcode.com/problems/reverse-integer/
/// @difficulty easy
struct Solution;
impl Solution {
pub fn reverse(x: i32) -> i32 {
use std::i32;
let mut ret = 0i32;
let mut x_clone = x;
while x_clone != 0 {
let i = x_clone % 10;
let x1 = ret.overflowing_mul(10);
if x1.1 == true {
return 0;
}
let x2 = x1.0.overflowing_add(i);
if x2.1 == true {
return 0;
}
ret = x2.0;
x_clone = x_clone / 10;
}
ret
}
}
#[cfg(test)]
mod test {
use crate::reverse_integer::Solution;
#[test]
fn should_return_321_given_123() {
assert_eq!(321, Solution::reverse(123));
}
#[test]
fn should_return_negative_321_given_negative_123() {
assert_eq!(-321, Solution::reverse(-123));
}
#[test]
fn should_return_21_given_120() {
assert_eq!(21, Solution::reverse(120));
}
#[test]
fn should_return_0_given_1534236469() {
assert_eq!(0, Solution::reverse(1534236469));
}
}
}
#![allow(unused)]
fn main() {
/// @number 657
/// @title Robot Return to Origin
/// @url https://leetcode.com/problems/robot-return-to-origin
/// @difficulty easy
struct Solution;
impl Solution {
pub fn judge_circle(moves: String) -> bool {
let mut vertical = 0;
let mut horizon = 0;
moves.chars().for_each(|element| {
match element {
'U' => { horizon += 1; }
'D' => { horizon -= 1; }
'L' => { vertical += 1; }
'R' => { vertical -= 1; }
_ => {}
};
});
vertical == 0 && horizon == 0
}
}
#[test]
fn test() {
assert!(Solution::judge_circle(String::from("UUDD")));
assert!(!Solution::judge_circle(String::from("UUUUU")));
assert!(Solution::judge_circle(String::from("RLUURDDDLU")));
}
}
#![allow(unused)]
fn main() {
/// @number 100
/// @title Same Tree
/// @url https://leetcode.com/problems/same-tree
/// @difficulty easy
//Given two binary trees, write a function to check if they are the same or not.
//
//
// Two binary trees are considered the same if they are structurally identical a
//nd the nodes have the same value.
//
// Example 1:
//
//
//Input: 1 1
// / \ / \
// 2 3 2 3
//
// [1,2,3], [1,2,3]
//
//Output: true
//
//
// Example 2:
//
//
//Input: 1 1
// / \
// 2 2
//
// [1,2], [1,null,2]
//
//Output: false
//
//
// Example 3:
//
//
//Input: 1 1
// / \ / \
// 2 1 1 2
//
// [1,2,1], [1,1,2]
//
//Output: false
//
// Related Topics Tree Depth-first Search
// 👍 2062 👎 59
struct Solution;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None
}
}
}
//leetcode submit region begin(Prohibit modification and deletion)
// Definition for a binary tree node.
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
match (p, q) {
(Some(p_node), Some(q_node)) => {
let (t1, t2) = (p_node.borrow(), q_node.borrow());
let value_equals = t1.val == t2.val;
let left_equals = Solution::is_same_tree(t1.left.clone(), t2.left.clone());
let right_equals = Solution::is_same_tree(t1.right.clone(), t2.right.clone());
value_equals && left_equals && right_equals
},
(None, None) => true,
_ => false
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
#[cfg(test)]
mod test {
use crate::same_tree::{Solution, TreeNode};
use std::rc::Rc;
use std::cell::RefCell;
#[test]
fn test() {
let mut node = TreeNode::new(1);
node.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
node.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
let mut node2 = TreeNode::new(1);
node2.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
node2.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
assert_eq!(true, Solution::is_same_tree(
Some(Rc::new(RefCell::new(node))),
Some(Rc::new(RefCell::new(node2))),
));
}
#[test]
fn test2() {
let mut node = TreeNode::new(1);
node.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
let mut node2 = TreeNode::new(1);
node2.right = Some(Rc::new(RefCell::new(TreeNode::new(2))));
assert_eq!(false, Solution::is_same_tree(
Some(Rc::new(RefCell::new(node))),
Some(Rc::new(RefCell::new(node2))),
));
}
#[test]
fn test3() {
let mut node = TreeNode::new(1);
node.left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
node.right = Some(Rc::new(RefCell::new(TreeNode::new(1))));
let mut node2 = TreeNode::new(1);
node2.left = Some(Rc::new(RefCell::new(TreeNode::new(1))));
node2.right = Some(Rc::new(RefCell::new(TreeNode::new(2))));
assert_eq!(false, Solution::is_same_tree(
Some(Rc::new(RefCell::new(node))),
Some(Rc::new(RefCell::new(node2))),
));
}
}
}
#![allow(unused)]
fn main() {
/// @number 728
/// @title Self Dividing Numbers
/// @url https://leetcode.com/problems/self-dividing-numbers
/// @difficulty easy
struct Solution;
impl Solution {
pub fn self_dividing_numbers(left: i32, right: i32) -> Vec<i32> {
let mut ret = vec![];
for index in left..=right {
let mut index_copy = index;
while index_copy > 0 {
let bit = index_copy % 10;
if bit == 0 || index % bit != 0 {
break;
}
index_copy /= 10;
};
if index_copy == 0 {
ret.push(index);
}
}
ret
}
}
#[test]
fn test1() {
assert_eq!(
Solution::self_dividing_numbers(1, 22),
vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
);
}
}
#![allow(unused)]
fn main() {
/// @number 8
/// @title String to Integer (atoi)
/// @url https://leetcode.com/problems/string-to-integer-atoi/
/// @difficulty Medium
struct Solution;
impl Solution {
pub fn my_atoi(str_: String) -> i32 {
use std::i32;
let mut is_getting_number = false;
let mut is_negative: Option<bool> = None;
let mut ret = 0i32;
let x = str_.trim().chars();
for x in x {
match x {
ref n if n.is_ascii_digit() => {
let number_in_position = n.to_digit(10).unwrap() as i32;
let optional_ret: Option<i32> = ret.checked_mul(10).and_then(|inner| inner.checked_add(number_in_position));
if let Some(num) = optional_ret {
is_getting_number = true;
ret = num;
} else {
if let Some(true) = is_negative {
return std::i32::MIN;
}else {
return std::i32::MAX;
}
}
}
'+' => {
if is_negative.is_none() && is_getting_number == false {
is_negative = Some(false);
} else {
break;
}
}
'-' => {
if is_negative.is_none() && is_getting_number == false {
is_negative = Some(true);
} else {
break;
}
}
_ => {
break;
}
}
};
if let Some(true) = is_negative { -ret }else { ret }
}
}
#[cfg(test)]
mod test {
use crate::string_to_integer_atoi::Solution;
#[test]
fn should_work_with_normal_number() {
assert_eq!(42i32, Solution::my_atoi("42".into()));
}
#[test]
fn should_work_with_minus_mark() {
assert_eq!(-42i32, Solution::my_atoi("-42".into()));
}
#[test]
fn should_work_with_prefix_space() {
assert_eq!(-42i32, Solution::my_atoi(" -42".into()));
}
#[test]
fn should_work_with_postfix_external_words() {
assert_eq!(4293i32, Solution::my_atoi("4293 with words".into()));
}
#[test]
fn should_get_zero_with_prefix_words() {
assert_eq!(0i32, Solution::my_atoi("with words 4293".into()));
}
#[test]
fn should_check_overflow() {
assert_eq!(std::i32::MIN, Solution::my_atoi("-91283472332".into()));
assert_eq!(std::i32::MAX, Solution::my_atoi("91283472332".into()));
}
#[test]
fn should_work_with_add_mark() {
assert_eq!(42i32, Solution::my_atoi("+42".into()));
}
#[test]
fn should_work_with_both_add_minus_mark() {
assert_eq!(0i32, Solution::my_atoi("+-42".into()));
}
#[test]
fn should_get_zero_with_internal_space() {
assert_eq!(4i32, Solution::my_atoi("+4 2".into()));
}
#[test]
fn test() {
assert_eq!(4i32, Solution::my_atoi("+4 2".into()));
}
}
}
#![allow(unused)]
fn main() {
/// @number 37
/// @title Sudoku Solver
/// @url https://leetcode.com/problems/sudoku-solver/
/// @difficulty Hard
struct Solution;
impl Solution {
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
let mut empty_position = vec![];
for i in 0..9 {
for j in 0..9 {
if board[i][j] == '.' {
empty_position.push((i, j));
board[i][j] = '0';
}
}
}
let position_len = empty_position.len();
let mut loop_index = 0;
while loop_index < position_len {
let (x, y) = empty_position[loop_index];
if board[x][y] < '9' {
board[x][y] = std::char::from_u32((board[x][y] as u32) + 1).unwrap();
} else {
board[x][y] = '0';
loop_index -= 1;
continue;
}
if Solution::invalid(board, x, y) {
continue;
}
loop_index += 1;
}
}
pub fn invalid(board: &Vec<Vec<char>>, x: usize, y: usize) -> bool {
use std::collections::HashSet;
let mut contain_table = HashSet::new();
// validate line
for i in 0..9 {
let x1 = board[x][i];
if x1 != '0' {
if contain_table.contains(&x1) {
return true;
}
contain_table.insert(x1);
}
}
contain_table.clear();
// validate column
for i in 0..9 {
let x2 = board[i][y];
if x2 != '0' {
if contain_table.contains(&x2) {
return true;
}
contain_table.insert(x2);
}
}
contain_table.clear();
// validate box
let i1 = x / 3;
let i2 = y / 3;
for i in 0..3 {
for j in 0..3 {
let x3 = board[i1 * 3 + i][i2 * 3 + j];
if x3 != '0' {
if contain_table.contains(&x3) {
return true;
}
contain_table.insert(x3);
}
}
}
contain_table.clear();
false
}
}
#[cfg(test)]
mod test {
use crate::sudoku_solver::Solution;
#[test]
fn test() {
let mut sudoku = 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'],
];
Solution::solve_sudoku(&mut sudoku);
let mut expected_solution = 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'],
];
assert_eq!(expected_solution, sudoku);
}
#[test]
fn test_invalid_method() {
let mut expected_solution = 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'],
];
for i in 0..9 {
for j in 0..9 {
assert_eq!(false, Solution::invalid(&expected_solution, i, j));
}
}
}
}
}
#![allow(unused)]
fn main() {
/// @number 709
/// @title To Lower Case
/// @url https://leetcode.com/problems/to-lower-case
/// @difficulty easy
struct Solution();
impl Solution {
pub fn to_lower_case(str: String) -> String {
str.as_str().to_lowercase()
}
}
#[test]
fn test() {
assert_eq!(Solution::to_lower_case(String::from("HELLO")), String::from("hello"));
}
}
#![allow(unused)]
fn main() {
/// @number 1
/// @title Two Sum
/// @url https://leetcode.com/problems/two-sum
/// @difficulty easy
struct Solution;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
use std::collections::HashMap;
let mut r: HashMap<i32, i32> = HashMap::new();
for i in 0..nums.len() {
r.insert(nums[i], i as i32);
}
for i in 0..nums.len() {
match r.get(&(target - nums[i])) {
Some(index) if i as i32 != *index => return vec![i as i32, index.clone()],
None => {}
_ => {}
}
}
vec![]
}
}
#[test]
fn test1() {
assert_eq!(Solution::two_sum(vec![2, 7, 11, 15], 9), vec![0, 1]);
}
#[test]
fn test2() {
assert_eq!(Solution::two_sum(vec![2, 7, 11, 15], 9999), vec![]);
}
#[test]
fn test3() {
assert_eq!(Solution::two_sum(vec![3, 2, 4], 6), vec![1, 2]);
}
}
#![allow(unused)]
fn main() {
/// @number 929
/// @title Unique Email Addresses
/// @url https://leetcode.com/problems/unique-email-addresses
/// @difficulty easy
struct Solution();
impl Solution {
pub fn num_unique_emails(emails: Vec<String>) -> i32 {
let mut real_emails = emails.into_iter().map(|email| {
let email_split: Vec<&str> = email.split('@').collect();
let name_slit: Vec<&str> = email_split[0].split('+').collect();
let real_name = name_slit[0].replace(".", "");
format!("{}@{}", real_name, email_split[1])
}).collect::<Vec<String>>();
println!("{:?}", real_emails);
real_emails.sort();
// dedup can only be used for sorted data.
real_emails.dedup_by(|a, b| a == b);
real_emails.len() as i32
}
}
#[test]
fn test() {
assert_eq!(Solution::num_unique_emails(vec!["a@a.com".to_string(), "a+a@a.com".to_string()]), 1);
assert_eq!(Solution::num_unique_emails(vec![
"fg.r.u.uzj+o.pw@kziczvh.com".to_string(),
"r.cyo.g+d.h+b.ja@tgsg.z.com".to_string(),
"fg.r.u.uzj+o.f.d@kziczvh.com".to_string(),
"r.cyo.g+ng.r.iq@tgsg.z.com".to_string(),
"fg.r.u.uzj+lp.k@kziczvh.com".to_string(),
"r.cyo.g+n.h.e+n.g@tgsg.z.com".to_string(),
"fg.r.u.uzj+k+p.j@kziczvh.com".to_string(),
"fg.r.u.uzj+w.y+b@kziczvh.com".to_string(),
"r.cyo.g+x+d.c+f.t@tgsg.z.com".to_string(),
"r.cyo.g+x+t.y.l.i@tgsg.z.com".to_string(),
"r.cyo.g+brxxi@tgsg.z.com".to_string(),
"r.cyo.g+z+dr.k.u@tgsg.z.com".to_string(),
"r.cyo.g+d+l.c.n+g@tgsg.z.com".to_string(),
"fg.r.u.uzj+vq.o@kziczvh.com".to_string(),
"fg.r.u.uzj+uzq@kziczvh.com".to_string(),
"fg.r.u.uzj+mvz@kziczvh.com".to_string(),
"fg.r.u.uzj+taj@kziczvh.com".to_string(),
"fg.r.u.uzj+fek@kziczvh.com".to_string()
]), 2);
}
}
#![allow(unused)]
fn main() {
/// @number 804
/// @title Unique Morse Code Words
/// @url https://leetcode.com/problems/unique-morse-code-words
/// @difficulty easy
struct Solution();
impl Solution {
pub fn unique_morse_representations(words: Vec<String>) -> i32 {
let morse = [
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
"--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--..",
];
let mut words_morse = words
.into_iter()
.map(|word| {
word.chars()
.map(|each_char| {
let index = each_char as usize - 97;
morse[index].to_string()
})
.collect::<Vec<String>>()
.join("")
})
.collect::<Vec<String>>();
words_morse.sort();
words_morse.dedup_by(|a, b| a == b);
words_morse.len() as i32
}
}
#[test]
fn test1() {
assert_eq!(
Solution::unique_morse_representations(vec![
String::from("gin"),
String::from("zen"),
String::from("gig"),
String::from("msg"),
]),
2
);
}
}
#![allow(unused)]
fn main() {
use std::collections::BTreeSet;
fn unique_in_order(vec: Vec<i32>) -> Vec<i32> {
let mut bset = BTreeSet::new();
for i in vec {
bset.insert(i);
}
let mut re_vec = Vec::new();
for item in &bset {
re_vec.push(*item);
}
re_vec
}
fn unique_in_order<T>(sequence: T) -> Vec<T::Item>
where
T: std::iter::IntoIterator,
T::Item: std::cmp::PartialEq + std::fmt::Debug,
{
let mut v: Vec<_> = sequence.into_iter().collect();
v.dedup();
v
}
}
#![allow(unused)]
fn main() {
/// @number 6
/// @title ZigZag Conversion
/// @url https://leetcode.com/problems/zigzag-conversion
/// @difficulty medium
struct Solution;
impl Solution {
pub fn convert(s: String, num_rows: i32) -> String {
if num_rows == 1 {
return s;
}
let chars: Vec<char> = s.chars().collect();
let mut strings: Vec<String> = (0..num_rows).map(|_| String::new()).collect();
let mut go_down = false;
let mut loop_line = 0 as i32;
for x in chars {
strings[loop_line as usize].push(x);
if loop_line == 0 || loop_line == num_rows - 1 {
go_down = !go_down;
}
loop_line += if go_down { 1 } else { -1 };
}
strings.join("")
}
}
#[cfg(test)]
mod test {
use crate::zigzag_conversion::Solution;
#[test]
fn show_return_itself_when_number_is_1() {
assert_eq!(String::from("PAYPALISHIRING"), Solution::convert(String::from("PAYPALISHIRING"), 1));
}
#[test]
fn should_it_works() {
assert_eq!(String::from("PAHNAPLSIIGYIR"), Solution::convert(String::from("PAYPALISHIRING"), 3));
}
#[test]
fn should_it_works_too() {
assert_eq!(String::from("PINALSIGYAHRPI"), Solution::convert(String::from("PAYPALISHIRING"), 4));
}
}
}
#![allow(unused)]
fn main() {
/*
https://leetcode.cn/problems/ugly-number-ii/
*/
impl Solution {
pub fn nth_ugly_number(n: i32) -> i32 {
let mut ugly = vec![1; n as usize];
let mut idx = vec![0; 3 as usize];
for i in 1..n {
let a = ugly[idx[0]] * 2;
let b = ugly[idx[1]] * 3;
let c = ugly[idx[2]] * 5;
let next = std::cmp::min(a, std::cmp::min(b, c));
if next == a {
idx[0] += 1;
}
if next == b {
idx[1] += 1;
}
if next == c {
idx[2] += 1;
}
ugly[i as usize] = next;
}
ugly.pop().unwrap()
}
}
}
use std::ops::{Add, Sub};
use doe::traits::Print;
fn main() {
let mut a = 10;
let mut b = 90;
swap(&mut a, &mut b);
a.println();
b.println();
}
///do't use temp varible to swap two number
fn swap<T>(a: &mut T, b: &mut T)
where
T: Add<Output = T> + Sub<Output = T>+Copy,
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}