1549 lines
72 KiB
HTML
1549 lines
72 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="coal" dir="ltr">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>rust leetcode - Andrew's Blog</title>
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
<meta name="description" content="Andrew Ryan's Blog">
|
|
<meta name="viewport" content="width=device-width, initial-scale=1">
|
|
<meta name="theme-color" content="#ffffff">
|
|
|
|
<link rel="icon" href="../../favicon.svg">
|
|
<link rel="shortcut icon" href="../../favicon.png">
|
|
<link rel="stylesheet" href="../../css/variables.css">
|
|
<link rel="stylesheet" href="../../css/general.css">
|
|
<link rel="stylesheet" href="../../css/chrome.css">
|
|
|
|
<!-- Fonts -->
|
|
<link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
|
|
<link rel="stylesheet" href="../../fonts/fonts.css">
|
|
|
|
<!-- Highlight.js Stylesheets -->
|
|
<link rel="stylesheet" href="../../highlight.css">
|
|
<link rel="stylesheet" href="../../tomorrow-night.css">
|
|
<link rel="stylesheet" href="../../ayu-highlight.css">
|
|
|
|
<!-- Custom theme stylesheets -->
|
|
<link rel="stylesheet" href="../../src/style/custom.css">
|
|
|
|
<!-- MathJax -->
|
|
<script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
|
|
</head>
|
|
<body class="sidebar-visible no-js">
|
|
<div id="body-container">
|
|
<!-- Provide site root to javascript -->
|
|
<script>
|
|
var path_to_root = "../../";
|
|
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "coal" : "coal";
|
|
</script>
|
|
|
|
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
|
<script>
|
|
try {
|
|
var theme = localStorage.getItem('mdbook-theme');
|
|
var sidebar = localStorage.getItem('mdbook-sidebar');
|
|
|
|
if (theme.startsWith('"') && theme.endsWith('"')) {
|
|
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
|
}
|
|
|
|
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
|
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
|
}
|
|
} catch (e) { }
|
|
</script>
|
|
|
|
<!-- Set the theme before any content is loaded, prevents flash -->
|
|
<script>
|
|
var theme;
|
|
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
|
if (theme === null || theme === undefined) { theme = default_theme; }
|
|
var html = document.querySelector('html');
|
|
html.classList.remove('coal')
|
|
html.classList.add(theme);
|
|
var body = document.querySelector('body');
|
|
body.classList.remove('no-js')
|
|
body.classList.add('js');
|
|
</script>
|
|
|
|
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
|
|
|
|
<!-- Hide / unhide sidebar before it is displayed -->
|
|
<script>
|
|
var body = document.querySelector('body');
|
|
var sidebar = null;
|
|
var sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
|
|
if (document.body.clientWidth >= 1080) {
|
|
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
|
sidebar = sidebar || 'visible';
|
|
} else {
|
|
sidebar = 'hidden';
|
|
}
|
|
sidebar_toggle.checked = sidebar === 'visible';
|
|
body.classList.remove('sidebar-visible');
|
|
body.classList.add("sidebar-" + sidebar);
|
|
</script>
|
|
|
|
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
|
<div class="sidebar-scrollbox">
|
|
<ol class="chapter"><li class="chapter-item affix "><a href="../../index.html">Andrew's Blog</a></li><li class="chapter-item "><a href="../../posts/linux/linux.html"><strong aria-hidden="true">1.</strong> linux</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/linux/install_linux.html"><strong aria-hidden="true">1.1.</strong> install linux</a></li><li class="chapter-item "><a href="../../posts/linux/bash_profile.html"><strong aria-hidden="true">1.2.</strong> bash profile</a></li><li class="chapter-item "><a href="../../posts/linux/command_list.html"><strong aria-hidden="true">1.3.</strong> command list</a></li><li class="chapter-item "><a href="../../posts/linux/git_guide.html"><strong aria-hidden="true">1.4.</strong> git guide</a></li><li class="chapter-item "><a href="../../posts/linux/tar.html"><strong aria-hidden="true">1.5.</strong> tar</a></li><li class="chapter-item "><a href="../../posts/linux/run_x86_elf_in_x64_setup.html"><strong aria-hidden="true">1.6.</strong> run x86 elf in x64 setup</a></li></ol></li><li class="chapter-item "><a href="../../posts/mac/mac.html"><strong aria-hidden="true">2.</strong> mac</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/mac/macos_profiles.html"><strong aria-hidden="true">2.1.</strong> macos profiles</a></li></ol></li><li class="chapter-item "><a href="../../posts/swift/swift.html"><strong aria-hidden="true">3.</strong> swift</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/swift/learn_swift.html"><strong aria-hidden="true">3.1.</strong> learn swift basics</a></li><li class="chapter-item "><a href="../../posts/swift/swift_extensions.html"><strong aria-hidden="true">3.2.</strong> Swift extensions</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_extension.html"><strong aria-hidden="true">3.3.</strong> SwiftUI extensions</a></li><li class="chapter-item "><a href="../../posts/swift/install_swift.html"><strong aria-hidden="true">3.4.</strong> install swift</a></li><li class="chapter-item "><a href="../../posts/swift/task_planner.html"><strong aria-hidden="true">3.5.</strong> implment task panner app with SwiftUI</a></li><li class="chapter-item "><a href="../../posts/swift/swift_cheat_sheet.html"><strong aria-hidden="true">3.6.</strong> Swift Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/swift/yinci_url.html"><strong aria-hidden="true">3.7.</strong> Personal privacy protocol</a></li><li class="chapter-item "><a href="../../posts/swift/swift_regular_exressions.html"><strong aria-hidden="true">3.8.</strong> Swift regular exressions</a></li><li class="chapter-item "><a href="../../posts/ios/how_to_create_beautiful_ios_charts_in_swift.html"><strong aria-hidden="true">3.9.</strong> How to Create Beautiful iOS Charts in鑱絊wift</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_source_code.html"><strong aria-hidden="true">3.10.</strong> SwiftUI source code</a></li><li class="chapter-item "><a href="../../posts/swift/use_swift_fetch_iciba_api.html"><strong aria-hidden="true">3.11.</strong> use swift fetch iciba API</a></li></ol></li><li class="chapter-item "><a href="../../posts/ios/ios.html"><strong aria-hidden="true">4.</strong> ios</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ios/cocaposd_setup_and_install_for_ios_project.html"><strong aria-hidden="true">4.1.</strong> cocaposd setup and install for ios project</a></li><li class="chapter-item "><a href="../../posts/ios/swiftui_show_gif_image.html"><strong aria-hidden="true">4.2.</strong> SwiftUI show gif image</a></li><li class="chapter-item "><a href="../../posts/ios/implement_task_planner_app.html"><strong aria-hidden="true">4.3.</strong> implement Task planner App</a></li></ol></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c.html"><strong aria-hidden="true">5.</strong> objective_c</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/objective_c/objective_c_cheat_sheet.html"><strong aria-hidden="true">5.1.</strong> Objective-C Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c_for_absolute_beginners_read_note.html"><strong aria-hidden="true">5.2.</strong> Objective-C Note</a></li></ol></li><li class="chapter-item "><a href="../../posts/dart/dart.html"><strong aria-hidden="true">6.</strong> dart</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/dart/flutter.html"><strong aria-hidden="true">6.1.</strong> Flutter Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/dart/dart_cheat_sheet.html"><strong aria-hidden="true">6.2.</strong> Dart Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/flutter/flutter_dev_test.html"><strong aria-hidden="true">6.3.</strong> Flutter dev test</a></li></ol></li><li class="chapter-item "><a href="../../posts/rust/rust.html"><strong aria-hidden="true">7.</strong> rust</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/rust/offline_use_rust.html"><strong aria-hidden="true">7.1.</strong> Offline use rust</a></li><li class="chapter-item "><a href="../../posts/rust/rust_grammer.html"><strong aria-hidden="true">7.2.</strong> rust grammar</a></li><li class="chapter-item "><a href="../../posts/rust/pase_string_and_decimal_conversion.html"><strong aria-hidden="true">7.3.</strong> pase string and decimal conversion</a></li><li class="chapter-item "><a href="../../posts/rust/parse_types.html"><strong aria-hidden="true">7.4.</strong> rust types</a></li><li class="chapter-item "><a href="../../posts/rust/rust_life_cycle.html"><strong aria-hidden="true">7.5.</strong> Rust life cycle</a></li><li class="chapter-item "><a href="../../posts/rust/rust_generic.html"><strong aria-hidden="true">7.6.</strong> rust generics</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implment_matrix.html"><strong aria-hidden="true">7.7.</strong> Rust implement matrix</a></li><li class="chapter-item "><a href="../../posts/rust/rust_sort.html"><strong aria-hidden="true">7.8.</strong> Rust implement sort algorithms</a></li><li class="chapter-item "><a href="../../posts/rust/implement_aes_encryption.html"><strong aria-hidden="true">7.9.</strong> Rust implement AEC encryption and decryption</a></li><li class="chapter-item "><a href="../../posts/rust/implement_trie_data_structure.html"><strong aria-hidden="true">7.10.</strong> implement trie data structure</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_tree.html"><strong aria-hidden="true">7.11.</strong> implement tree data_structure</a></li><li class="chapter-item "><a href="../../posts/rust/list_dir.html"><strong aria-hidden="true">7.12.</strong> list dir</a></li><li class="chapter-item "><a href="../../posts/rust/fast_way_to_implment_object_trait.html"><strong aria-hidden="true">7.13.</strong> fast way to implment object trait</a></li><li class="chapter-item "><a href="../../posts/rust/compress_rust_binary_size.html"><strong aria-hidden="true">7.14.</strong> compress rust binary size</a></li><li class="chapter-item "><a href="../../posts/rust/implment_file_upload_backend.html"><strong aria-hidden="true">7.15.</strong> impliment file upload</a></li><li class="chapter-item "><a href="../../posts/rust/this_is_add_post_cli_implementation_in_rust.html"><strong aria-hidden="true">7.16.</strong> this is add_post cli implementation in rust</a></li><li class="chapter-item "><a href="../../posts/rust/use_rust_implment_a_copyclipbord_cli.html"><strong aria-hidden="true">7.17.</strong> Use rust implment a copyclipbord CLI</a></li><li class="chapter-item "><a href="../../posts/rust/sqlite_database_add_delete_update_show_in_rust.html"><strong aria-hidden="true">7.18.</strong> sqlite database add delete update show in rust</a></li><li class="chapter-item "><a href="../../posts/rust/implementing_tokio_joinhandle_for_wasm.html"><strong aria-hidden="true">7.19.</strong> Implementing tokio JoinHandle for wasm</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_a_crate_for_encode_and_decode_brainfuck_and_ook.html"><strong aria-hidden="true">7.20.</strong> rust implement a crate for encode and decode brainfuck and ook</a></li><li class="chapter-item "><a href="../../posts/rust/slint_builtin_elements.html"><strong aria-hidden="true">7.21.</strong> Slint Builtin Elements</a></li><li class="chapter-item "><a href="../../posts/rust/corporate_network_install_rust_on_windows.html"><strong aria-hidden="true">7.22.</strong> Corporate network install Rust on windows</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_file_how_to_judge_static_link_or_dynamic_link_in_macos.html"><strong aria-hidden="true">7.23.</strong> rust binary file how to judge static link or dynamic link in Macos</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_include_dir_and_get_contents.html"><strong aria-hidden="true">7.24.</strong> rust binary include dir and get contents</a></li><li class="chapter-item "><a href="../../posts/rust/rust_logger_non-block.html"><strong aria-hidden="true">7.25.</strong> rust logger non-block</a></li><li class="chapter-item "><a href="../../posts/rust/rust_connect_sql_server_database.html"><strong aria-hidden="true">7.26.</strong> rust connect sql server database</a></li><li class="chapter-item "><a href="../../posts/rust/rust_websocket_implment.html"><strong aria-hidden="true">7.27.</strong> rust websocket implment</a></li></ol></li><li class="chapter-item "><a href="../../posts/java/java.html"><strong aria-hidden="true">8.</strong> java</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/java/java_grammar.html"><strong aria-hidden="true">8.1.</strong> java grammar and codewar</a></li><li class="chapter-item "><a href="../../posts/java/run_jar.html"><strong aria-hidden="true">8.2.</strong> java run .jar</a></li><li class="chapter-item "><a href="../../posts/java/java_pomxml_add_defaultgoal_to_build.html"><strong aria-hidden="true">8.3.</strong> Java pomxml add defaultGoal to build</a></li><li class="chapter-item "><a href="../../posts/java/java_set_mvn_mirror.html"><strong aria-hidden="true">8.4.</strong> Java set mvn mirror</a></li></ol></li><li class="chapter-item "><a href="../../posts/python/python.html"><strong aria-hidden="true">9.</strong> python</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/python/convert_pesn.html"><strong aria-hidden="true">9.1.</strong> convert pesn</a></li><li class="chapter-item "><a href="../../posts/python/find_remove_dir.html"><strong aria-hidden="true">9.2.</strong> find and remove dir</a></li><li class="chapter-item "><a href="../../posts/python/timing_message.html"><strong aria-hidden="true">9.3.</strong> wechat send message</a></li><li class="chapter-item "><a href="../../posts/python/use_python_openpyxl_package_read_and_edit_excel_files.html"><strong aria-hidden="true">9.4.</strong> Use python openpyxl package read and edit excel files</a></li></ol></li><li class="chapter-item "><a href="../../posts/go/go.html"><strong aria-hidden="true">10.</strong> go</a></li><li class="chapter-item "><a href="../../posts/js/js.html"><strong aria-hidden="true">11.</strong> js</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/js/js_tutorial.html"><strong aria-hidden="true">11.1.</strong> js tutorial</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_map.html"><strong aria-hidden="true">11.2.</strong> ja map</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_math.html"><strong aria-hidden="true">11.3.</strong> js math</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_object.html"><strong aria-hidden="true">11.4.</strong> js object</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_set.html"><strong aria-hidden="true">11.5.</strong> js set</a></li><li class="chapter-item "><a href="../../posts/js/single_thread_and_asynchronous.html"><strong aria-hidden="true">11.6.</strong> single thread and asynchronous</a></li><li class="chapter-item "><a href="../../posts/js/this.html"><strong aria-hidden="true">11.7.</strong> js this</a></li><li class="chapter-item "><a href="../../posts/js/js_implment_aes.html"><strong aria-hidden="true">11.8.</strong> js implment aes</a></li><li class="chapter-item "><a href="../../posts/js/getting_started_with_ajax.html"><strong aria-hidden="true">11.9.</strong> getting started with ajax</a></li><li class="chapter-item "><a href="../../posts/js/BinarySearchTree.html"><strong aria-hidden="true">11.10.</strong> binary search tree</a></li><li class="chapter-item "><a href="../../posts/js/goole_zx.html"><strong aria-hidden="true">11.11.</strong> goole zx</a></li><li class="chapter-item "><a href="../../posts/js/es6.html"><strong aria-hidden="true">11.12.</strong> es6</a></li></ol></li><li class="chapter-item "><a href="../../posts/ruby/ruby.html"><strong aria-hidden="true">12.</strong> ruby</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ruby/rails_setup_env.html"><strong aria-hidden="true">12.1.</strong> ruby on rails setup environment</a></li><li class="chapter-item "><a href="../../posts/ruby/learn_ruby.html"><strong aria-hidden="true">12.2.</strong> learn ruby</a></li><li class="chapter-item "><a href="../../posts/ruby/ruby_note.html"><strong aria-hidden="true">12.3.</strong> Ruby Note</a></li><li class="chapter-item "><a href="../../posts/ruby/setup_ruby_for_ctf.html"><strong aria-hidden="true">12.4.</strong> Setup ruby for CTF</a></li></ol></li><li class="chapter-item "><a href="../../posts/react/react.html"><strong aria-hidden="true">13.</strong> react</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/react/react_life_cycle.html"><strong aria-hidden="true">13.1.</strong> react life cycle</a></li><li class="chapter-item "><a href="../../posts/react/react_router.html"><strong aria-hidden="true">13.2.</strong> react router</a></li><li class="chapter-item "><a href="../../posts/react/react_this.html"><strong aria-hidden="true">13.3.</strong> react this</a></li><li class="chapter-item "><a href="../../posts/react/react_interviw.html"><strong aria-hidden="true">13.4.</strong> react interview</a></li><li class="chapter-item "><a href="../../posts/react/important_react_interview.html"><strong aria-hidden="true">13.5.</strong> important react interview</a></li><li class="chapter-item "><a href="../../posts/react/react_quick_reference.html"><strong aria-hidden="true">13.6.</strong> react quick reference</a></li><li class="chapter-item "><a href="../../posts/react/redux_quick_reference.html"><strong aria-hidden="true">13.7.</strong> redux quick reference</a></li></ol></li><li class="chapter-item "><a href="../../posts/vue/vue.html"><strong aria-hidden="true">14.</strong> vue</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/vue/vue_ajax.html"><strong aria-hidden="true">14.1.</strong> vue ajax</a></li></ol></li><li class="chapter-item "><a href="../../posts/angular/angular.html"><strong aria-hidden="true">15.</strong> angular</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/angular/controller_communication.html"><strong aria-hidden="true">15.1.</strong> controller communication</a></li><li class="chapter-item "><a href="../../posts/angular/creating_custom_directives.html"><strong aria-hidden="true">15.2.</strong> creating custom directives</a></li><li class="chapter-item "><a href="../../posts/angular/directive_notes.html"><strong aria-hidden="true">15.3.</strong> directive notes</a></li><li class="chapter-item "><a href="../../posts/angular/directive_communication.html"><strong aria-hidden="true">15.4.</strong> directive communication</a></li><li class="chapter-item "><a href="../../posts/angular/post_params.html"><strong aria-hidden="true">15.5.</strong> post params</a></li><li class="chapter-item "><a href="../../posts/angular/read_json_angular.html"><strong aria-hidden="true">15.6.</strong> read json angular</a></li><li class="chapter-item "><a href="../../posts/angular/same_route_reload.html"><strong aria-hidden="true">15.7.</strong> same route reload</a></li></ol></li><li class="chapter-item "><a href="../../posts/css/css.html"><strong aria-hidden="true">16.</strong> css</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/css/use_css_media.html"><strong aria-hidden="true">16.1.</strong> use css media</a></li></ol></li><li class="chapter-item "><a href="../../posts/php/php.html"><strong aria-hidden="true">17.</strong> php</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/php/for_php_string_implment_some_extemtion_functions.html"><strong aria-hidden="true">17.1.</strong> for php string implment some extemtion functions</a></li><li class="chapter-item "><a href="../../posts/php/php_cheatsheet.html"><strong aria-hidden="true">17.2.</strong> PHP cheatsheet</a></li></ol></li><li class="chapter-item expanded "><a href="../../posts/leetcode/leetcode.html"><strong aria-hidden="true">18.</strong> leetcode</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../posts/leetcode/rust_leetcode.html" class="active"><strong aria-hidden="true">18.1.</strong> rust leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_codewar.html"><strong aria-hidden="true">18.2.</strong> rust codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/swift_codewar.html"><strong aria-hidden="true">18.3.</strong> swift codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/js_leetcode.html"><strong aria-hidden="true">18.4.</strong> js leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/java_leetcode.html"><strong aria-hidden="true">18.5.</strong> java leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_huawei.html"><strong aria-hidden="true">18.6.</strong> huawei test</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_utils.html"><strong aria-hidden="true">18.7.</strong> rust common functions</a></li><li class="chapter-item "><a href="../../posts/leetcode/olympiad_training.html"><strong aria-hidden="true">18.8.</strong> Computer olympiad training</a></li></ol></li><li class="chapter-item "><a href="../../posts/ctf/CTF.html"><strong aria-hidden="true">19.</strong> ctf</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ctf/CTF_Note.html"><strong aria-hidden="true">19.1.</strong> CTF Note</a></li><li class="chapter-item "><a href="../../posts/ctf/0.1_Web.html"><strong aria-hidden="true">19.2.</strong> Web</a></li><li class="chapter-item "><a href="../../posts/ctf/4.1_Misc.html"><strong aria-hidden="true">19.3.</strong> Misc</a></li><li class="chapter-item "><a href="../../posts/ctf/3.2_PWN_note.html"><strong aria-hidden="true">19.4.</strong> PWN</a></li><li class="chapter-item "><a href="../../posts/ctf/3.1_Crypto.html"><strong aria-hidden="true">19.5.</strong> Crypto</a></li><li class="chapter-item "><a href="../../posts/ctf/3.4_RSA_note.html"><strong aria-hidden="true">19.6.</strong> Rsa attack</a></li><li class="chapter-item "><a href="../../posts/ctf/3.5_Base64.html"><strong aria-hidden="true">19.7.</strong> Base64</a></li><li class="chapter-item "><a href="../../posts/ctf/0.0_SQL Injection Cheatsheet.html"><strong aria-hidden="true">19.8.</strong> SQL Injection Cheatsheet</a></li><li class="chapter-item "><a href="../../posts/ctf/1.1_SQL_injection.html"><strong aria-hidden="true">19.9.</strong> SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.2_SQL_injection_UNION_attacks.html"><strong aria-hidden="true">19.10.</strong> SQL Injection UNION attacks</a></li><li class="chapter-item "><a href="../../posts/ctf/1.3_Blind SQL injection.html"><strong aria-hidden="true">19.11.</strong> Blind SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.4_Code Injection.html"><strong aria-hidden="true">19.12.</strong> Code Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.5_SSRF.html"><strong aria-hidden="true">19.13.</strong> SSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.6_OS command injection.html"><strong aria-hidden="true">19.14.</strong> OS command injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.7_Local file inclusion.html"><strong aria-hidden="true">19.15.</strong> Local file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.8_Remote file inclusion.html"><strong aria-hidden="true">19.16.</strong> Remote file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.9_CSRFm.html"><strong aria-hidden="true">19.17.</strong> CSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.10_NoSQL injection.html"><strong aria-hidden="true">19.18.</strong> NoSQL injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.11_JSON injection.html"><strong aria-hidden="true">19.19.</strong> JSON injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.12_CTF_Web_SQL_Note.html"><strong aria-hidden="true">19.20.</strong> CTF Web SQL Note</a></li><li class="chapter-item "><a href="../../posts/ctf/2.1_XXE.html"><strong aria-hidden="true">19.21.</strong> XXE</a></li><li class="chapter-item "><a href="../../posts/ctf/2.2_XSS.html"><strong aria-hidden="true">19.22.</strong> XSS</a></li><li class="chapter-item "><a href="../../posts/ctf/2.3_Upload File.html"><strong aria-hidden="true">19.23.</strong> Upload File</a></li><li class="chapter-item "><a href="../../posts/ctf/2.4_serialize_unserialize.html"><strong aria-hidden="true">19.24.</strong> serialize unserialize</a></li><li class="chapter-item "><a href="../../posts/ctf/2.5_Race condition.html"><strong aria-hidden="true">19.25.</strong> Race condition</a></li><li class="chapter-item "><a href="../../posts/ctf/3.2_PWN_note.html"><strong aria-hidden="true">19.26.</strong> PWN_note</a></li><li class="chapter-item "><a href="../../posts/ctf/3.3_pwn HCTF2016 brop.html"><strong aria-hidden="true">19.27.</strong> pwn HCTF2016 brop</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_patch_defense_skill.html"><strong aria-hidden="true">19.28.</strong> PWN Patch defense skill</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_stack_overflow.html"><strong aria-hidden="true">19.29.</strong> PWN stack overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_heap_overflow.html"><strong aria-hidden="true">19.30.</strong> PWN heap overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_format_string_vulnerability.html"><strong aria-hidden="true">19.31.</strong> PWN Format String Vulnerability</a></li><li class="chapter-item "><a href="../../posts/ctf/kali_linux_tutorials.html"><strong aria-hidden="true">19.32.</strong> Kali linux tutorials</a></li><li class="chapter-item "><a href="../../posts/ctf/google_dorks_2023_lists.html"><strong aria-hidden="true">19.33.</strong> Google Dorks 2023 Lists</a></li><li class="chapter-item "><a href="../../posts/ctf/dvwa_writeup.html"><strong aria-hidden="true">19.34.</strong> DVWA WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/bwapp_writeup.html"><strong aria-hidden="true">19.35.</strong> bWAPP WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/sqlilabs_writeup.html"><strong aria-hidden="true">19.36.</strong> sqlilabs WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/ctf_train_at_hangzhou.html"><strong aria-hidden="true">19.37.</strong> ctf train at hangzhou</a></li><li class="chapter-item "><a href="../../posts/ctf/ctf_common_mindmap_list.html"><strong aria-hidden="true">19.38.</strong> ctf common mindmap list</a></li><li class="chapter-item "><a href="../../posts/ctf/error_based_sql_injection.html"><strong aria-hidden="true">19.39.</strong> Error Based SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/urlfinder_tutorial.html"><strong aria-hidden="true">19.40.</strong> URLFinder Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/observer_ward_tutorial.html"><strong aria-hidden="true">19.41.</strong> observer_ward Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/mysql_udf_.html"><strong aria-hidden="true">19.42.</strong> MySQL UDF 提权</a></li><li class="chapter-item "><a href="../../posts/ctf/nuclei__tutorial.html"><strong aria-hidden="true">19.43.</strong> Nuclei Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/2024_ctf_solution_thinking.html"><strong aria-hidden="true">19.44.</strong> 2024 ctf solution thinking</a></li><li class="chapter-item "><a href="../../posts/ctf/man_che_si_te_bian_ma.html"><strong aria-hidden="true">19.45.</strong> 曼彻斯特编码</a></li></ol></li></ol>
|
|
</div>
|
|
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
|
|
<div class="sidebar-resize-indicator"></div>
|
|
</div>
|
|
</nav>
|
|
|
|
<!-- Track and set sidebar scroll position -->
|
|
<script>
|
|
var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
|
|
sidebarScrollbox.addEventListener('click', function(e) {
|
|
if (e.target.tagName === 'A') {
|
|
sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
|
|
}
|
|
}, { passive: true });
|
|
var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
|
|
sessionStorage.removeItem('sidebar-scroll');
|
|
if (sidebarScrollTop) {
|
|
// preserve sidebar scroll position when navigating via links within sidebar
|
|
sidebarScrollbox.scrollTop = sidebarScrollTop;
|
|
} else {
|
|
// scroll sidebar to current active section when navigating via "next/previous chapter" buttons
|
|
var activeSection = document.querySelector('#sidebar .active');
|
|
if (activeSection) {
|
|
activeSection.scrollIntoView({ block: 'center' });
|
|
}
|
|
}
|
|
</script>
|
|
|
|
<div id="page-wrapper" class="page-wrapper">
|
|
|
|
<div class="page">
|
|
<div id="menu-bar-hover-placeholder"></div>
|
|
<div id="menu-bar" class="menu-bar sticky">
|
|
<div class="left-buttons">
|
|
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
|
<i class="fa fa-bars"></i>
|
|
</label>
|
|
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
|
<i class="fa fa-paint-brush"></i>
|
|
</button>
|
|
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
|
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
|
</ul>
|
|
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
|
<i class="fa fa-search"></i>
|
|
</button>
|
|
</div>
|
|
|
|
<h1 class="menu-title">Andrew's Blog</h1>
|
|
|
|
<div class="right-buttons">
|
|
<a href="https://gitlink.org.cn/dnrops/dnrops.gitlink.net.git" title="Git repository" aria-label="Git repository">
|
|
<i id="git-repository-button" class="fa fa-github"></i>
|
|
</a>
|
|
|
|
</div>
|
|
</div>
|
|
|
|
<div id="search-wrapper" class="hidden">
|
|
<form id="searchbar-outer" class="searchbar-outer">
|
|
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
|
</form>
|
|
<div id="searchresults-outer" class="searchresults-outer hidden">
|
|
<div id="searchresults-header" class="searchresults-header"></div>
|
|
<ul id="searchresults">
|
|
</ul>
|
|
</div>
|
|
</div>
|
|
|
|
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
|
<script>
|
|
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
|
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
|
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
|
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
|
});
|
|
</script>
|
|
|
|
<div id="content" class="content">
|
|
<main>
|
|
<h1 id="leetcode-rust-implementation"><a class="header" href="#leetcode-rust-implementation">Leetcode rust implementation</a></h1>
|
|
<h2 id="add-two-numbers"><a class="header" href="#add-two-numbers">add-two-numbers</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>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);
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="container-with-most-water"><a class="header" href="#container-with-most-water">container-with-most-water</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="di-string-match"><a class="header" href="#di-string-match">di-string-match</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="flipping-an-image"><a class="header" href="#flipping-an-image">flipping an image</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]
|
|
]
|
|
)
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="hamming-distance"><a class="header" href="#hamming-distance">hamming distance</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="integer-to-roman"><a class="header" href="#integer-to-roman">integer to roman</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="jewels-and-stones"><a class="header" href="#jewels-and-stones">jewels and stones</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="maximum-depth-of-binary-tree"><a class="header" href="#maximum-depth-of-binary-tree">maximum-depth-of-binary-tree</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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))
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="merge-two-binary-trees"><a class="header" href="#merge-two-binary-trees">merge two binary trees</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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()),
|
|
})))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="nim-game"><a class="header" href="#nim-game">nim game</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="palindrome-number"><a class="header" href="#palindrome-number">palindrome number</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="permutations"><a class="header" href="#permutations">permutations</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="reverse-integer"><a class="header" href="#reverse-integer">reverse integer</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="robot-return-to-origin"><a class="header" href="#robot-return-to-origin">robot return to origin</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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")));
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="same-tree"><a class="header" href="#same-tree">same-tree</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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))),
|
|
));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="self-dividing-numbers"><a class="header" href="#self-dividing-numbers">self-dividing-numbers</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]
|
|
);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="string-to-integer"><a class="header" href="#string-to-integer">string-to-integer</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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()));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="sudoku-solver"><a class="header" href="#sudoku-solver">sudoku-solver</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="to-lower-case"><a class="header" href="#to-lower-case">to-lower-case</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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"));
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="two-sum"><a class="header" href="#two-sum">two sum</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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]);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="unique-email-addresses"><a class="header" href="#unique-email-addresses">unique-email-addresses</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="unique-morse-code-words"><a class="header" href="#unique-morse-code-words">unique morse code words</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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
|
|
);
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="unique-vec"><a class="header" href="#unique-vec">Unique Vec</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>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
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="zigzag-conversion"><a class="header" href="#zigzag-conversion">zigzag conversion</a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/// @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));
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="丑数-ii"><a class="header" href="#丑数-ii"><a href="https://leetcode.cn/problems/ugly-number-ii/">丑数 II</a></a></h2>
|
|
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>/*
|
|
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()
|
|
}
|
|
}
|
|
<span class="boring">}</span></code></pre></pre>
|
|
<h2 id="不用临时变量替换number"><a class="header" href="#不用临时变量替换number">不用临时变量替换Number</a></h2>
|
|
<pre><code>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;
|
|
}
|
|
</code></pre>
|
|
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="../../posts/leetcode/leetcode.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next prefetch" href="../../posts/leetcode/rust_codewar.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
|
|
<div style="clear: both"></div>
|
|
</nav>
|
|
</div>
|
|
</div>
|
|
|
|
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
|
<a rel="prev" href="../../posts/leetcode/leetcode.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next prefetch" href="../../posts/leetcode/rust_codewar.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
</nav>
|
|
|
|
</div>
|
|
|
|
|
|
|
|
<script>
|
|
window.playground_line_numbers = true;
|
|
</script>
|
|
|
|
<script>
|
|
window.playground_copyable = true;
|
|
</script>
|
|
|
|
<script src="../../ace.js"></script>
|
|
<script src="../../editor.js"></script>
|
|
<script src="../../mode-rust.js"></script>
|
|
<script src="../../theme-dawn.js"></script>
|
|
<script src="../../theme-tomorrow_night.js"></script>
|
|
|
|
<script src="../../elasticlunr.min.js"></script>
|
|
<script src="../../mark.min.js"></script>
|
|
<script src="../../searcher.js"></script>
|
|
|
|
<script src="../../clipboard.min.js"></script>
|
|
<script src="../../highlight.js"></script>
|
|
<script src="../../book.js"></script>
|
|
|
|
<!-- Custom JS scripts -->
|
|
<script src="../../src/js/custom.js"></script>
|
|
|
|
|
|
</div>
|
|
</body>
|
|
</html>
|