Solved 0215

guangsheng.li01 · guangsheng.li01 · commit 2754721e8e7f · 2020-08-05T19:37:21.000+08:00
diff --git a/Cargo.toml b/Cargo.toml
@@ -17,5 +17,11 @@ doctest = false
 url = "2.1.1"
 handlebars = "~3.0.0"
 serde_json = "1.0"
+# criterion = "0.3"
+# bencher = "0.1.5"
+
+# [[bench]]
+# name = "my_benchmark"
+# harness = false
 
 
diff --git a/src/a0215_kth_largest_element_in_an_array.rs b/src/a0215_kth_largest_element_in_an_array.rs
@@ -0,0 +1,64 @@
+/*
+ * [0215] kth-largest-element-in-an-array
+ */
+
+struct Solution;
+
+impl Solution {
+    pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
+        let mut nums = nums;
+        let end = nums.len() - 1;
+        Self::quick_select(&mut nums, 0usize, end, k as usize)
+    }
+
+    fn quick_select(nums: &mut Vec<i32>, start: usize, end: usize, k: usize) -> i32 {
+        let p = nums[start];
+        let mut left = start + 1;
+        let mut right = end;
+
+        while left <= right {
+            while left <= right && nums[left] >= p {
+                left += 1;
+            }
+            while left <= right && nums[right] <= p {
+                right -= 1;
+            }
+            if left <= right && nums[left] < p && nums[right] > p {
+                nums.swap(left, right);
+            }
+        }
+        nums.swap(start, right);
+        if right - start == k - 1 {
+            let mut min = nums[0];
+            for i in start..start + k as usize {
+                if nums[i] < min {
+                    min = nums[i];
+                }
+            }
+            return min;
+        } else if right - start < k - 1 {
+            return Self::quick_select(nums, right + 1, end, k + start - right - 1);
+        } else if right - start > k - 1 {
+            return Self::quick_select(nums, start, right - 1, k);
+        }
+        0
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_case0() {
+        assert_eq!(
+            Solution::find_kth_largest(
+                vec![7, 3, 82, 9, 2, 17, 4, 29, 1, 8, 36, 33, 18, 22, 19],
+                2
+            ),
+            36
+        );
+        assert_eq!(Solution::find_kth_largest(vec![7, 6, 5, 4, 3, 2, 1], 5), 3);
+        assert_eq!(Solution::find_kth_largest(vec![5, 2, 4, 1, 3, 6, 0], 4), 3)
+    }
+}
diff --git a/src/a0226_invert_binary_tree.rs b/src/a0226_invert_binary_tree.rs
@@ -28,6 +28,7 @@ pub struct Solution {}
 use std::cell::RefCell;
 use std::rc::Rc;
 impl Solution {
+    // 使用clone
     pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
         if let Some(root) = root {
             let mut root_mut = root.borrow_mut();
@@ -44,6 +45,41 @@ impl Solution {
         }
         Option::None
     }
+
+    // 使用unsafe
+    pub fn invert_tree_2(mut root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
+        if root.is_none() {
+            return None;
+        }
+
+        let ref_mut = root.as_mut().unwrap().as_ptr();
+        unsafe {
+            let l = &mut (*ref_mut).left;
+            let r = &mut (*ref_mut).right;
+            std::mem::swap(l, r);
+            if l.is_some() {
+                Self::invert_tree(Some(l.as_mut().unwrap().clone()));
+            }
+            if r.is_some() {
+                Self::invert_tree(Some(r.as_mut().unwrap().clone()));
+            }
+        }
+
+        root
+    }
+
+    // 使用take
+    pub fn invert_tree_3(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
+        if root.is_none() {
+            return None;
+        }
+        let root = root.unwrap();
+        let l = Self::invert_tree(root.borrow_mut().left.take());
+        let r = Self::invert_tree(root.borrow_mut().right.take());
+        root.borrow_mut().left = r;
+        root.borrow_mut().right = l;
+        Some(root)
+    }
 }
 
 // solution impl ends here
@@ -53,6 +89,7 @@ impl Solution {
 #[cfg(test)]
 mod tests {
     use super::*;
+    use test::Bencher;
 
     #[test]
     fn test_case0() {
@@ -61,6 +98,42 @@ mod tests {
             tree![4, 7, 2, 9, 6, 3, 1]
         );
     }
+
+    #[bench]
+    fn bench_invert_tree(b: &mut Bencher) {
+        let t = tree![
+            4, 1, 4, 6, 8, 9, 5, 3, 1, 3, 5, 6, 7, 8, 9, 7, 65, 3, 2, 2, 3, 4, 45, 6, 6, 78, 9, 0,
+            8, 7, 6, 67, 8, 9, 9, 7, 5654, 43, 3, 2, 1, 1, 2, 3, 4, 4, 45, 5, 6, 6, 7, 78, 8, 76,
+            5, 4, 67, 8, 9, 90, 009, 7, 65, 87, 654, 356, 789, 87, 6543, 4, 567, 89, 765, 4, 567,
+            89, 87, 654, 35, 6789, 0, 876, 543, 4, 5678, 90, 876, 5432, 1, 345, 67890, 9876, 54321,
+            2, 345, 6789, 87, 65432, 1, 234, 5678, 2, 7, 1, 3, 6, 9
+        ];
+        b.iter(|| Solution::invert_tree(t.clone()));
+    }
+
+    #[bench]
+    fn bench_invert_tree_2(b: &mut Bencher) {
+        let t = tree![
+            4, 1, 4, 6, 8, 9, 5, 3, 1, 3, 5, 6, 7, 8, 9, 7, 65, 3, 2, 2, 3, 4, 45, 6, 6, 78, 9, 0,
+            8, 7, 6, 67, 8, 9, 9, 7, 5654, 43, 3, 2, 1, 1, 2, 3, 4, 4, 45, 5, 6, 6, 7, 78, 8, 76,
+            5, 4, 67, 8, 9, 90, 009, 7, 65, 87, 654, 356, 789, 87, 6543, 4, 567, 89, 765, 4, 567,
+            89, 87, 654, 35, 6789, 0, 876, 543, 4, 5678, 90, 876, 5432, 1, 345, 67890, 9876, 54321,
+            2, 345, 6789, 87, 65432, 1, 234, 5678, 2, 7, 1, 3, 6, 9
+        ];
+        b.iter(|| Solution::invert_tree_2(t.clone()));
+    }
+
+    #[bench]
+    fn bench_invert_tree_3(b: &mut Bencher) {
+        let t = tree![
+            4, 1, 4, 6, 8, 9, 5, 3, 1, 3, 5, 6, 7, 8, 9, 7, 65, 3, 2, 2, 3, 4, 45, 6, 6, 78, 9, 0,
+            8, 7, 6, 67, 8, 9, 9, 7, 5654, 43, 3, 2, 1, 1, 2, 3, 4, 4, 45, 5, 6, 6, 7, 78, 8, 76,
+            5, 4, 67, 8, 9, 90, 009, 7, 65, 87, 654, 356, 789, 87, 6543, 4, 567, 89, 765, 4, 567,
+            89, 87, 654, 35, 6789, 0, 876, 543, 4, 5678, 90, 876, 5432, 1, 345, 67890, 9876, 54321,
+            2, 345, 6789, 87, 65432, 1, 234, 5678, 2, 7, 1, 3, 6, 9
+        ];
+        b.iter(|| Solution::invert_tree_3(t.clone()));
+    }
 }
 
 // solution tests ends here
diff --git a/src/lib.rs b/src/lib.rs
@@ -1,61 +1,65 @@
 #![allow(dead_code)]
+#![feature(test)]
+
+extern crate test;
 
 #[macro_use]
 pub mod utils;
 
-mod a0000_sample;
-mod a0001_two_sum;
-mod a0004_median_of_two_sorted_arrays;
-mod a0007_reverse_integer;
-mod a0009_palindrome_number;
-mod a0019_binary_tree_inorder_traversal;
-mod a0026_remove_duplicates_from_sorted_array;
-mod a0027_remove_element;
-mod a0035_search_insert_position;
-mod a0042_trapping_rain_water;
-mod a0053_maximum_subarray;
-mod a0066_plus_one;
-mod a0088_merge_sorted_array;
-mod a0103_binary_tree_zigzag_level_order_traversal;
-mod a0118_pascals_triangle;
-mod a0119_pascals_triangle_ii;
-mod a0145_binary_tree_postorder_traversal;
-mod a0169_majority_element;
-mod a0172_factorial_trailing_zeroes;
-mod a0226_invert_binary_tree;
-mod a0322_coin_change;
-mod a0343_integer_break;
-mod a0392_is_subsequence;
-mod a0400_nth_digit;
-mod a0404_sum_of_left_leaves;
-mod a0405_convert_a_number_to_hexadecimal;
-mod a0617_merge_two_binary_trees;
-mod a0643_maximum_average_subarray_i;
-mod a0646_maximum_length_of_pair_chain;
-mod a0654_maximum_binary_tree;
-mod a0701_insert_into_a_binary_search_tree;
-mod a0726_number_of_atoms;
-mod a0761_special_binary_string;
-mod a0779_k_th_symbol_in_grammar;
-mod a0783_minimum_distance_between_bst_nodes;
-mod a0867_transpose_matrix;
-mod a0883_projection_area_of_3d_shapes;
-mod a0894_all_possible_full_binary_trees;
-mod a0929_unique_email_addresses;
-mod a0931_minimum_falling_path_sum;
-mod a0937_reorder_data_in_log_files;
-mod a0938_range_sum_of_bst;
-mod a0949_largest_time_for_given_digits;
-mod a0973_k_closest_points_to_origin;
-mod a0980_unique_paths_iii;
-mod a1012_numbers_with_repeated_digits;
-mod a1018_binary_prefix_divisible_by_5;
-mod a1021_remove_outermost_parentheses;
-mod a1047_remove_all_adjacent_duplicates_in_string;
-mod a1137_n_th_tribonacci_number;
-mod a1200_minimum_absolute_difference;
-mod a1287_element_appearing_more_than_25_in_sorted_array;
-mod a1302_deepest_leaves_sum;
-mod a1315_sum_of_nodes_with_even_valued_grandparent;
-mod a1317_convert_integer_to_the_sum_of_two_no_zero_integers;
-mod casting_between_types;
+pub mod a0000_sample;
+pub mod a0001_two_sum;
+pub mod a0004_median_of_two_sorted_arrays;
+pub mod a0007_reverse_integer;
+pub mod a0009_palindrome_number;
+pub mod a0019_binary_tree_inorder_traversal;
+pub mod a0026_remove_duplicates_from_sorted_array;
+pub mod a0027_remove_element;
+pub mod a0035_search_insert_position;
+pub mod a0042_trapping_rain_water;
+pub mod a0053_maximum_subarray;
+pub mod a0066_plus_one;
+pub mod a0088_merge_sorted_array;
+pub mod a0103_binary_tree_zigzag_level_order_traversal;
+pub mod a0118_pascals_triangle;
+pub mod a0119_pascals_triangle_ii;
+pub mod a0145_binary_tree_postorder_traversal;
+pub mod a0169_majority_element;
+pub mod a0172_factorial_trailing_zeroes;
+pub mod a0215_kth_largest_element_in_an_array;
+pub mod a0226_invert_binary_tree;
+pub mod a0322_coin_change;
+pub mod a0343_integer_break;
+pub mod a0392_is_subsequence;
+pub mod a0400_nth_digit;
+pub mod a0404_sum_of_left_leaves;
+pub mod a0405_convert_a_number_to_hexadecimal;
+pub mod a0617_merge_two_binary_trees;
+pub mod a0643_maximum_average_subarray_i;
+pub mod a0646_maximum_length_of_pair_chain;
+pub mod a0654_maximum_binary_tree;
+pub mod a0701_insert_into_a_binary_search_tree;
+pub mod a0726_number_of_atoms;
+pub mod a0761_special_binary_string;
+pub mod a0779_k_th_symbol_in_grammar;
+pub mod a0783_minimum_distance_between_bst_nodes;
+pub mod a0867_transpose_matrix;
+pub mod a0883_projection_area_of_3d_shapes;
+pub mod a0894_all_possible_full_binary_trees;
+pub mod a0929_unique_email_addresses;
+pub mod a0931_minimum_falling_path_sum;
+pub mod a0937_reorder_data_in_log_files;
+pub mod a0938_range_sum_of_bst;
+pub mod a0949_largest_time_for_given_digits;
+pub mod a0973_k_closest_points_to_origin;
+pub mod a0980_unique_paths_iii;
+pub mod a1012_numbers_with_repeated_digits;
+pub mod a1018_binary_prefix_divisible_by_5;
+pub mod a1021_remove_outermost_parentheses;
+pub mod a1047_remove_all_adjacent_duplicates_in_string;
+pub mod a1137_n_th_tribonacci_number;
+pub mod a1200_minimum_absolute_difference;
+pub mod a1287_element_appearing_more_than_25_in_sorted_array;
+pub mod a1302_deepest_leaves_sum;
+pub mod a1315_sum_of_nodes_with_even_valued_grandparent;
+pub mod a1317_convert_integer_to_the_sum_of_two_no_zero_integers;
+pub mod casting_between_types;
