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

Commit 7409b53

Browse files
committed
add linklist macron and q876
1 parent 6a8cdad commit 7409b53

File tree

7 files changed

+141
-21
lines changed

7 files changed

+141
-21
lines changed

‎aaa_macro/Cargo.toml

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
[package]
2+
name = "aaa_macro"
3+
version = "0.1.0"
4+
edition = "2018"
5+
6+
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
7+
8+
[dependencies]

‎aaa_macro/src/lib.rs

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2+
#[derive(PartialEq, Eq, Clone, Debug)]
3+
pub struct ListNode {
4+
pub val: i32,
5+
pub next: Option<Box<ListNode>>
6+
}
7+
8+
impl ListNode {
9+
pub fn new(val: i32) -> ListNode {
10+
ListNode {
11+
val,
12+
next: None
13+
}
14+
}
15+
}
16+
17+
#[macro_export]
18+
macro_rules! linklist {
19+
() => {
20+
None
21+
};
22+
($($e:expr), *) => {
23+
{
24+
let mut head = Box::new(ListNode::new(0));
25+
let mut ref_head = &mut head;
26+
27+
$(
28+
ref_head.next = Some(Box::new(ListNode::new($e)));
29+
ref_head = ref_head.next.as_mut().unwrap();
30+
)*
31+
32+
let _ = ref_head; // 避免 `unused_assignments`
33+
head.next
34+
}
35+
};
36+
}

‎double-pointer/Cargo.toml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,3 +6,4 @@ edition = "2018"
66
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
77

88
[dependencies]
9+
aaa_macro = {path="../aaa_macro"}

‎double-pointer/src/lib.rs

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
1+
use aaa_macro::*;
2+
13
mod q977;
24
mod q283;
35
mod q167;
46
mod q344;
5-
mod q557;
7+
mod q557;
8+
mod q876;

‎double-pointer/src/q557.rs

Lines changed: 17 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,30 @@
1-
struct Solution ();
1+
struct Solution();
2+
23
impl Solution {
34
pub fn reverse_words(s: String) -> String {
4-
55
let mut v = s.into_bytes();
6-
let (mut left, mut right) = (0, 0);
6+
let (mut l, mut r) = (0, 0);
7+
78

8-
while right < v.len() {
9-
while right < v.len() && v[right] != ' ' as u8 {
10-
right += 1
9+
while r < v.len() {
10+
while r < v.len() && v[r] != ' ' as u8 {
11+
r += 1;
1112
}
1213

13-
let next = right + 1;
14+
let new_pos = r + 1;
1415

15-
while left < right {
16+
while l < r {
1617
unsafe {
17-
std::ptr::swap(&mut v[right -1], &mut v[left]);
18+
std::ptr::swap(&mut v[l], &mut v[r-1]);
19+
l += 1;
20+
r -= 1;
1821
}
19-
left += 1;
20-
right -= 1;
2122
}
2223

23-
left = next;
24-
right = next;
25-
}
2624

25+
l = new_pos;
26+
r = new_pos;
27+
}
2728
String::from_utf8(v).unwrap()
2829
}
2930
}
@@ -32,14 +33,10 @@ impl Solution {
3233
mod tests {
3334
use super::*;
3435

35-
#[test] fn test_1() {
36-
37-
38-
36+
#[test]
37+
fn test_1() {
3938
assert_eq!(
4039
Solution::reverse_words(String::from("Let's take LeetCode contest")),
4140
String::from("s'teL ekat edoCteeL tsetnoc"))
4241
}
43-
44-
4542
}

‎double-pointer/src/q876.py

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
# Definition for singly-linked list.
2+
import pytest
3+
4+
class ListNode:
5+
def __init__(self, val=0, next=None):
6+
self.val = val
7+
self.next = next
8+
9+
class Solution:
10+
def middleNode(self, head: ListNode) -> ListNode:
11+
if head.next is None:
12+
return head
13+
14+
fp = head
15+
np = head
16+
17+
while True:
18+
np = np.next
19+
if np is None:
20+
return fp
21+
np = np.next
22+
if np is None:
23+
return fp.next
24+
25+
fp = fp.next
26+
27+
28+
29+
def test_mid():
30+
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, None)))))
31+
32+
assert Solution().middleNode(head).val == 3
33+
34+
head = ListNode(0, head)
35+
assert Solution().middleNode(head).val == 3
36+
37+
38+
if __name__ == '__main__':
39+
pytest.main(["./q876.py", "-s", "-v"])

‎double-pointer/src/q876.rs

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
use super::*;
2+
3+
struct Solution ();
4+
impl Solution {
5+
pub fn middle_node(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
6+
let mut fast = head.as_ref().unwrap();
7+
let mut slow = head.as_ref();
8+
9+
if fast.next.is_none() { return head; }
10+
11+
while !fast.next.is_none() && !fast.next.as_ref().unwrap().next.is_none() {
12+
fast = fast.next.as_ref().unwrap().next.as_ref().unwrap();
13+
if fast.next.is_none() {
14+
return slow.unwrap().next.clone();
15+
}
16+
slow = slow.unwrap().next.as_ref();
17+
18+
}
19+
slow.unwrap().next.clone()
20+
21+
22+
}
23+
}
24+
25+
26+
#[cfg(test)]
27+
mod tests {
28+
use super::*;
29+
30+
#[test] fn test_1() {
31+
assert_eq!(Solution::middle_node(linklist!(1,2,3,4,5)).unwrap().val, 3);
32+
assert_eq!(Solution::middle_node(linklist!(1,2,3,4,5, 6)).unwrap().val, 4);
33+
34+
35+
}
36+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /