Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7628e87

Browse files
committed
tries
1 parentdd8ea62 commit7628e87

8 files changed

+291
-2
lines changed

‎src/construct_tree.rs

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
usecrate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pubstructSolution{}
5+
implSolution{
6+
pubfnbuild_tree(preorder:Vec<i32>,inorder:Vec<i32>) ->Option<Rc<RefCell<TreeNode>>>{
7+
if preorder.is_empty() || inorder.is_empty(){
8+
returnNone;
9+
}
10+
11+
let mid = inorder.iter().position(|&x| x == preorder[0]).unwrap();
12+
let root_node =Rc::new(RefCell::new(TreeNode::new(preorder[0])));
13+
let left =Self::build_tree(preorder[1..=mid].to_vec(), inorder[..mid].to_vec());
14+
let right =Self::build_tree(preorder[mid +1..].to_vec(), inorder[mid..].to_vec());
15+
root_node.borrow_mut().left = left;
16+
root_node.borrow_mut().right = right;
17+
Some(root_node)
18+
}
19+
}

‎src/implement_trie.rs

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
use std::collections::HashMap;
2+
pubstructTrie{
3+
children:HashMap<char,Trie>,
4+
end:bool,
5+
}
6+
implTrie{
7+
fnnew() ->Self{
8+
Trie{
9+
end:false,
10+
children:HashMap::new(),
11+
}
12+
}
13+
fninsert(&mutself,word:String){
14+
letmut cur =self;
15+
for cin word.chars(){
16+
cur = cur.children.entry(c).or_insert(Trie::new());
17+
}
18+
cur.end =true;
19+
}
20+
fnstarts_with(&self,prefix:String) ->bool{
21+
letmut cur =self;
22+
for cin prefix.chars(){
23+
if cur.children.contains_key(&c){
24+
cur = cur.children.get(&c).unwrap();
25+
}else{
26+
returnfalse;
27+
}
28+
}
29+
true
30+
}
31+
fnsearch(&self,word:String) ->bool{
32+
letmut cur =self;
33+
for cin word.chars(){
34+
ifletSome(node) = cur.children.get(&c){
35+
cur = node;
36+
}else{
37+
returnfalse;
38+
}
39+
}
40+
cur.end
41+
}
42+
}

‎src/kth_largest_stream.rs

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
use std::cmp::Reverse;
2+
use std::collections::BinaryHeap;
3+
structKthLargest{
4+
nums:Vec<i32>,
5+
k:i32,
6+
heap:BinaryHeap<Reverse<i32>>,
7+
}
8+
implKthLargest{
9+
fnnew(k:i32,nums:Vec<i32>) ->Self{
10+
letmut heap =BinaryHeap::new();
11+
for valin nums{
12+
heap.push(Reverse(val));
13+
if heap.len() > kasusize{
14+
heap.pop();
15+
}
16+
}
17+
println!("{:?}", heap);
18+
KthLargest{ nums, k, heap}
19+
}
20+
fnadd(&mutself,val:i32) ->i32{
21+
self.heap.push(Reverse(val));
22+
self.heap.pop().unwrap();
23+
self.heap.peek().unwrap().0
24+
}
25+
}

‎src/main.rs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
1-
mod kth_smallest_bst;
2-
use kth_smallest_bst::Solution;
1+
mod word_search2;
32
use std::cell::RefCell;
43
use std::rc::Rc;
4+
use words_dictionary;
55
#[derive(Debug,PartialEq,Eq)]
66
pubstructTreeNode{
77
pubval:i32,

‎src/max_path_sum.rs

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
usecrate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pubstructSolution{}
5+
implSolution{
6+
pubfnmax_path_sum(root:Option<Rc<RefCell<TreeNode>>>) ->i32{
7+
fnrec(root:Option<Rc<RefCell<TreeNode>>>,max:&muti32) ->i32{
8+
ifletSome(node) = root{
9+
let node = node.borrow();
10+
let left =rec(node.left.clone(), max).max(0);
11+
let right =rec(node.right.clone(), max).max(0);
12+
let split = left + right + node.val;
13+
*max = std::cmp::max(*max, split);
14+
return node.val + std::cmp::max(left, right);
15+
}
16+
0
17+
}
18+
19+
letmut max = i32::MIN;
20+
std::cmp::max(rec(root,&mut max), max)
21+
}
22+
}

‎src/serialize_deserialize_bt.rs

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
usecrate::TreeNode;
2+
use std::cell::RefCell;
3+
use std::rc::Rc;
4+
pubstructCodec{}
5+
implCodec{
6+
fnnew() ->Self{}
7+
fnserialize(&self,root:Option<Rc<RefCell<TreeNode>>>) ->String{
8+
self.preorder(root)
9+
}
10+
fnpreorder(&self,root:Option<Rc<RefCell<TreeNode>>>) ->String{
11+
letmut res =String::new();
12+
ifletSome(node) = root{
13+
let node = node.borrow();
14+
res.push_str(&node.val.to_string());
15+
res.push(',');
16+
res.push_str(&self.preorder(node.left.clone()));
17+
res.push_str(&self.preorder(node.right.clone()));
18+
return res;
19+
}
20+
"null,".to_string()
21+
}
22+
23+
fndeserialize(&self,data:String) ->Option<Rc<RefCell<TreeNode>>>{
24+
let parts:Vec<&str> = data.split(',').collect();
25+
println!("{:?}", parts);
26+
fnrec(parts:&Vec<&str>,i:&mutusize) ->Option<Rc<RefCell<TreeNode>>>{
27+
let val = parts[*i];
28+
if parts[*i] =="null"{
29+
*i +=1;
30+
returnNone;
31+
}
32+
letmut node =Rc::new(RefCell::new(TreeNode::new(val.parse().unwrap())));
33+
*i +=1;
34+
let left =rec(parts, i);
35+
let right =rec(parts, i);
36+
node.borrow_mut().left = left;
37+
node.borrow_mut().right = right;
38+
Some(node)
39+
}
40+
rec(&parts,&mut0)
41+
}
42+
}

‎src/word_search2.rs

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
pubstructSolution{}
2+
use std::collections::{HashMap,HashSet};
3+
pubstructTrie{
4+
end:bool,
5+
children:HashMap<char,Trie>,
6+
}
7+
implTrie{
8+
fnnew() ->Self{
9+
Trie{
10+
end:false,
11+
children:HashMap::new(),
12+
}
13+
}
14+
fninsert(&mutself,word:String){
15+
letmut cur =self;
16+
for cin word.chars(){
17+
let cur = cur.children.entry(c).or_insert(Trie::new());
18+
}
19+
cur.end =true;
20+
}
21+
}
22+
implSolution{
23+
pubfnfind_words(board:Vec<Vec<char>>,words:Vec<String>) ->Vec<String>{
24+
letmut root =Trie::new();
25+
for win words{
26+
root.insert(w);
27+
}
28+
letmut visted:HashSet<(i32,i32)> =HashSet::new();
29+
letmut res:Vec<String> =Vec::new();
30+
fndfs(
31+
row:i32,
32+
col:i32,
33+
node:&mutTrie,
34+
word:&str,
35+
board:&Vec<Vec<char>>,
36+
res:&mutVec<String>,
37+
visited:&mutHashSet<(i32,i32)>,
38+
){
39+
if row <0
40+
|| col <0
41+
|| rowasusize == board.len()
42+
|| colasusize == board[0].len()
43+
|| visited.contains(&(row, col))
44+
|| !node
45+
.children
46+
.contains_key(&board[rowasusize][colasusize])
47+
{
48+
return;
49+
}
50+
visited.insert((row, col));
51+
52+
letmut cur = node
53+
.children
54+
.get_mut(&board[rowasusize][colasusize])
55+
.unwrap();
56+
letmut new_word = word.to_string();
57+
new_word.push(board[rowasusize][colasusize]);
58+
println!("{:?}", word);
59+
if cur.end{
60+
res.push(new_word.clone());
61+
}
62+
dfs(row +1, col,&mut cur,&new_word, board, res, visited);
63+
dfs(row +1, col,&mut cur,&new_word, board, res, visited);
64+
dfs(row, col +1,&mut cur,&new_word, board, res, visited);
65+
dfs(row, col -1,&mut cur,&new_word, board, res, visited);
66+
visited.remove(&(row, col));
67+
}
68+
letmut word =String::new();
69+
for rin0..board.len(){
70+
for cin0..board[0].len(){
71+
letmut word:Vec<char> =Vec::new();
72+
dfs(
73+
rasi32,
74+
casi32,
75+
&mut root,
76+
&"",
77+
&board,
78+
&mut res,
79+
&mut visted,
80+
);
81+
}
82+
}
83+
res
84+
}
85+
}

‎src/words_dictionary.rs

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
use std::collections::HashMap;
2+
3+
structWordDictionary{
4+
children:HashMap<char,WordDictionary>,
5+
end:bool,
6+
}
7+
8+
/**
9+
* `&self` means the method takes an immutable reference.
10+
* If you need a mutable reference, change it to `&mut self` instead.
11+
*/
12+
implWordDictionary{
13+
fnnew() ->Self{
14+
WordDictionary{
15+
children:HashMap::new(),
16+
end:false,
17+
}
18+
}
19+
20+
fnadd_word(&mutself,word:String){
21+
letmut cur =self;
22+
for cin word.chars(){
23+
cur = cur.children.entry(c).or_insert(WordDictionary::new());
24+
}
25+
cur.end =true;
26+
}
27+
28+
fnsearch(&self,word:String) ->bool{
29+
fndfs(root:&WordDictionary,word:String) ->bool{
30+
letmut cur = root;
31+
letmut i =0;
32+
for cin word.chars(){
33+
if c =='.'{
34+
for nodein cur.children.values(){
35+
let word =&word[i +1..];
36+
ifdfs(node, word.to_string()){
37+
returntrue;
38+
}
39+
}
40+
returnfalse;
41+
}
42+
ifletSome(val) = cur.children.get(&c){
43+
cur = val;
44+
}else{
45+
returnfalse;
46+
}
47+
i +=1;
48+
}
49+
cur.end
50+
}
51+
dfs(self, word)
52+
}
53+
}
54+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp