Skip to content

Instantly share code, notes, and snippets.

@fairjm
Last active December 22, 2019 10:10
Show Gist options
  • Save fairjm/4409e6c34e6f94e6fc2ed01cb5f39e39 to your computer and use it in GitHub Desktop.
Save fairjm/4409e6c34e6f94e6fc2ed01cb5f39e39 to your computer and use it in GitHub Desktop.
my_bad_solutions
/// https://leetcode.com/problems/two-sum/
impl Solution {
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut nums2 = nums.clone();
nums2.sort();
let mut begin = 0;
let mut end = nums.len() - 1;
while begin < end {
let r = nums2[begin] + nums2[end];
if r == target {
break;
}
if r < target {
begin = begin + 1;
} else {
end = end - 1;
}
}
vec![nums.iter().position(|&e| e == nums2[begin]).unwrap() as i32, nums.iter().rposition(|&e| e == nums2[end]).unwrap() as i32]
}
}
impl Solution {
pub fn roman_to_int(s: String) -> i32 {
fn map(c:char) -> i32 {
match c {
'I' => 1,
'V' => 5,
'X' => 10,
'L' => 50,
'C' => 100,
'D' => 500,
'M' => 1000,
_ => 0
}
}
let l :Vec<char> = s.chars().collect();
let mut i = 0;
let mut last_v = 0;
let mut r = 0;
while i < l.len() {
let c = l[i];
let v = map(c);
if (v == 5 || v == 10) && last_v == 1 {
r = r - 2 + v;
last_v = 0;
} else if (v == 50 || v == 100) && last_v == 10 {
r = r - 20 + v;
last_v = 0;
} else if (v == 500 || v == 1000) && last_v == 100 {
r = r - 200 + v;
last_v = 0;
} else {
r = r + v;
last_v = v;
}
i = i + 1;
}
r
}
}
// https://leetcode.com/problems/add-two-numbers/
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if l1 == None {
return l2;
}
if l2 == None {
return l1;
}
let r = &l1.as_ref().unwrap().val + &l2.as_ref().unwrap().val;
let mut up = r >= 10;
let mut newHeadBox = Box::new(ListNode::new(r % 10));
let mut newNode = &mut newHeadBox;
let mut l1NodeOp = &l1.as_ref().unwrap().next;
let mut l2NodeOp = &l2.as_ref().unwrap().next;
while *l1NodeOp != None || *l2NodeOp != None {
let mut l1Val = 0;
let mut l2Val = 0;
if let Some(v) = l1NodeOp {
l1Val = v.val;
l1NodeOp = &v.next;
}
if let Some(v) = l2NodeOp {
l2Val = v.val;
l2NodeOp = &v.next;
}
let r = l1Val + l2Val + (if up {1} else {0});
up = r >= 10;
newNode.next = Some(Box::new(ListNode::new(r % 10)));
newNode = newNode.next.as_mut().unwrap();
}
if up {
newNode.next = Some(Box::new(ListNode::new(1)));
}
Some(newHeadBox)
}
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
// code by fairjm bad solution
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if l1 == None { return l2;};
if l2 == None {return l1;};
let mut l1node = l1;
let mut l2node = l2;
let mut new_node = if &l1node.as_ref().unwrap().val < &l2node.as_ref().unwrap().val {
let mut tmp = l1node.unwrap();
l1node = tmp.next.take();
tmp
} else {
let mut tmp = l2node.unwrap();
l2node = tmp.next.take();
tmp
};
let mut new_head = &mut new_node;
loop {
if l1node == None {
new_head.next = l2node;
break;
}
if l2node == None {
new_head.next = l1node;
break;
}
let mut next = if &l1node.as_ref().unwrap().val < &l2node.as_ref().unwrap().val {
let mut tmp = l1node.unwrap();
l1node = tmp.next.take();
tmp
} else {
let mut tmp = l2node.unwrap();
l2node = tmp.next.take();
tmp
};
new_head.next = Some(next);
new_head = new_head.next.as_mut().unwrap();
}
Some(new_node)
}
}
// code by fairjm
// https://leetcode.com/problems/longest-substring-without-repeating-characters/
pub fn length_of_longest_substring(s: String) -> i32 {
if s.is_empty() {return 0 }
if s.len() == 1 {return 1}
use std::collections::HashMap;
let mut max = 0;
let cs :Vec<char> = s.chars().collect();
let len = cs.len();
let mut i = 0;
let mut j = 0;
let mut map:HashMap<char,usize> = std::collections::HashMap::new();
let mut count = 1;
while i < len {
if len - i <= max { break }
map.insert(*cs.get(i).unwrap(), i);
if j >= len {break}
loop {
j = j + 1;
if j >= len {
// println!("fin - i:{},j:{},count:{}", i, j, count);
if count > max { max = count }
i = len;
break;
}
let cuc = cs.get(j).unwrap();
if let Some(idx) = map.get(cuc) {
if *idx >= i {
// println!("re - i:{},j:{},count:{}", i, j, count);
if count > max { max = count }
i = idx + 1;
count = j - i + 1;
map.insert(*cuc, j);
break;
}
}
map.insert(*cuc, j);
count = count + 1;
}
}
max as i32
}
///https://leetcode.com/problems/reverse-integer/
impl Solution {
pub fn reverse(x: i32) -> i32 {
if x == 0 {
return 0;
}
let a = x.abs();
let is_ne = x < 0;
let r:String = format!("{}", a).chars().collect::<Vec<char>>().iter().rev().skip_while(|e| **e == '0').collect();
let rr = r.parse().unwrap_or(0);
if is_ne {
-1 * rr
} else {
rr
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment