797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length – 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0—>1
| |
v v
2—>3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

思路

这题直接DFS,递归遍历就好了

• 时间复杂度 O(N)
• 空间复杂度 O(N)

代码

pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let mut paths = Vec::with_capacity(graph.len()); let mut path = Vec::with_capacity(graph.len()); path.push(0); find_N(0,&mut path,&mut paths,&graph); return paths; } pub fn find_N(poient:i32,mut path:&mut Vec<i32>,mut paths:&mut Vec<Vec<i32>>,graph:&Vec<Vec<i32>>){ if poient == (graph.len()-1) as i32 { paths.push(path.clone()); } else { for next in &graph[poient as usize]{ path.push(*next); find_N(*next,&mut path,&mut paths,& graph); path.pop(); } } }

• 执行用时: 12 ms
• 内存消耗: 2.4 MB

题型与相似题

题型

1.DFS
2.graph

相似题

• DFS
• 图
• 543. Diameter of Binary Tree

代码链接

all_paths_from_source_to_target

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

思路

设计一个HashMap的几点：

• 设计一个合适的散列函数；
• 定义装载因子阈值，并且设计动态扩容策略；
• 选择合适的散列冲突解决方法。

工业级的HashMap主要采用链表法，有的库为了优化还采用红黑树。

这里就粗暴的用两个链表来实现。

• 时间复杂度 O(N)
• 空间复杂度 O(N)

代码

use std::cell::RefCell; use std::rc::{Rc, Weak}; #[derive(Clone, Debug)] pub struct MyLinkedList { len: i32, head: Option<Rc<RefCell<Node>>>, tail: Option<Rc<RefCell<Node>>>, } #[derive(Clone, Debug)] struct Node { pub key: i32, pub val: i32, pub prev: Option<Weak<RefCell<Node>>>, pub next: Option<Rc<RefCell<Node>>>, } impl Node { pub fn new(key: i32, val: i32) -> Self { Node { key, val, prev: None, next: None, } } } impl MyLinkedList { pub fn new() -> Self { let ret = MyLinkedList { len: 0, head: Some(Rc::new(RefCell::new(Node::new(0, 0)))), tail: Some(Rc::new(RefCell::new(Node::new(0, 0)))), }; ret.head.as_ref().unwrap().borrow_mut().next = ret.tail.clone(); ret.tail.as_ref().unwrap().borrow_mut().prev = Some(Rc::downgrade(ret.head.as_ref().unwrap())); ret } pub fn push(&mut self, key: i32, val: i32) { if let Some(p) = self.find_by_key(key) { p.borrow_mut().val = val; return; } let p = self.tail.clone().unwrap(); let p = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap(); let next = p.borrow().next.clone().unwrap(); let prev = p; let node = Rc::new(RefCell::new(Node::new(key, val))); node.borrow_mut().prev = Some(Rc::downgrade(&prev)); node.borrow_mut().next = Some(next.clone()); next.borrow_mut().prev = Some(Rc::downgrade(&node)); prev.borrow_mut().next = Some(node); self.len += 1; } #[inline] fn find_by_key(&self, key: i32) -> Option<Rc<RefCell<Node>>> { let mut p = self.head.clone().unwrap(); for _ in 0..self.len { let next = p.borrow().next.clone().unwrap(); p = next; if p.borrow().key == key { return Some(p); } } None } pub fn get(&self, key: i32) -> i32 { self.find_by_key(key).map(|p| p.borrow().val).unwrap_or(-1) } pub fn remove_by_key(&mut self, key: i32) { if let Some(p) = self.find_by_key(key) { let prev = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap(); let next = p.borrow().next.clone().unwrap(); prev.borrow_mut().next = Some(next.clone()); next.borrow_mut().prev = Some(Rc::downgrade(&prev)); self.len -= 1; } } } struct MyHashMap { map: Vec<Option<MyLinkedList>>, } /** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */ impl MyHashMap { /** Initialize your data structure here. */ fn new() -> Self { Self { map: vec![None; 1001], } } /** value will always be non-negative. */ fn put(&mut self, key: i32, value: i32) { let idx = (key % 1001) as usize; if self.map[idx].is_none() { self.map[idx] = Some(MyLinkedList::new()); } self.map[idx].as_mut().unwrap().push(key, value); } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ fn get(&self, key: i32) -> i32 { let idx = (key % 1001) as usize; match self.map[idx].as_ref() { None => -1, Some(sub_map) => sub_map.get(key) } } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ fn remove(&mut self, key: i32) { let idx = (key % 1001) as usize; if let Some(sub_map) = self.map[idx].as_mut() { sub_map.remove_by_key(key); } } }

• 执行用时: 36 ms
• 内存消耗: 4.6 MB

题型与相似题

题型

1.哈希表

相似题

• 705. Design HashSet
• 355. Design Twitter

代码链接

design_hashmap

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2:

Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

思路

题意来讲就是在字符数组中原地前后交换，这里我也采用了异或来做。

但是严格来讲，在这里用异或是错误的。在工程中不允许出现这样的代码。

推荐一篇文章：用异或来交换两个变量是错误的

• 时间复杂度 O(N)
• 空间复杂度 O(1)

代码

impl Solution { pub fn reverse_string(s: &mut Vec<char>) { let n = s.len(); if n == 0 { return; } for i in 0..n/2 { let j = n -1 -i; s[i] = ((s[i] as u8) ^ (s[j] as u8)) as char; s[j] = ((s[i] as u8) ^ (s[j] as u8)) as char; s[i] = ((s[i] as u8) ^ (s[j] as u8)) as char; } } }

• 执行用时: 28 ms
• 内存消耗: 5.3 MB

题型与相似题

题型

1.字符串
2.双指针

相似题

• 541. Reverse String II
• 345. Reverse Vowels of a String

代码链接

reverse_string

0232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

思路

根据题意，使用栈来实现一个队列。先进后出实现先进先出。

这里有提示，如果使用的语言没有实现Stack，就用队列。Python如果使用list来实现队列就非常的简单(算作弊)

这题的基本思路就是使用两个栈，但是具体的操作需要看实现。

可以在入队时变为FIFO，也可以在出队时变为FIFO。

入队如果变FIFO,那么在新进元素的时需要放在栈底，我们只能用另外一个栈暂存元素，放置之后再放回来。

• 时间复杂度 O(N)
• 空间复杂度 O(1)

出队如何变FIFO，那么使用另外一个栈暂存元素，把栈底元素弹出。

• 时间复杂度 O(1) 最坏O(N)
• 空间复杂度 O(1)

代码

struct MyQueue { vec1: Vec<i32>, vec2: Vec<i32>, } /** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */ impl MyQueue { /** Initialize your data structure here. */ fn new() -> Self { MyQueue { vec1: Vec::new(), vec2: Vec::new(), } } /** Push element x to the back of queue. */ fn push(&mut self, x: i32) { while let Some(v) = self.vec1.pop() { self.vec2.push(v); } self.vec2.push(x); while let Some(v) = self.vec2.pop(){ self.vec1.push(v); } } /** Removes the element from in front of queue and returns that element. */ fn pop(&mut self) -> i32 { self.vec1.pop().unwrap() } /** Get the front element. */ fn peek(&self) -> i32 { *self.vec1.last().unwrap() } /** Returns whether the queue is empty. */ fn empty(&self) -> bool { self.vec1.is_empty() } }

• 执行用时: 0 ms
• 内存消耗: 2.1 MB

题型与相似题

题型

1.栈
2.队列

相似题

• 225. Implement Stack using Queues
• 20. Valid Parentheses

代码链接

implement_queue_using_stacks

1037. Valid Boomerang

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Given a list of three points in the plane, return whether these points are a boomerang.

Example 1:

Input: [[1,1],[2,3],[3,2]]
Output: true

Example 2:

Input: [[1,1],[2,2],[3,3]]
Output: false

Note:
1.points.length == 3
2.points[i].length == 2

3.0 <= points[i][j] <= 100

思路

拿到题目先画图

我们来理解题意，首先回旋镖的意思见 回旋镖

根据题意，三个点组成两条直线，两条直线需要有一定的夹角，能组成三角形就满足条件。

那反过来，如果两条直线斜率相同，那就不能组成三角形。

解法：

斜率 k = (y2-y1) / (x2-x1)

伪代码:

return K(AB) != K(BC)

代码：

return (points[1][1]-points[0][1]) / (points[1][0]-points[0][0]) != (points[2][1]-points[1][1]) / (points[2][0]-points[1][0]);

注意算斜率是除法，我们需要考虑除0的情况。两边同时乘以两个除数，把除法转换为乘法。

C++

class Solution { public: bool isBoomerang(vector<vector<int>>& points) { return (points[1][1]-points[0][1]) * (points[2][0]-points[1][0]) != (points[2][1]-points[1][1]) * (points[1][0]-points[0][0]); } };

Rust

impl Solution { pub fn is_boomerang(points: Vec<Vec<i32>>) -> bool { return (points[1][1]-points[0][1]) * (points[2][0]-points[1][0]) != (points[2][1]-points[1][1]) * (points[1][0]-points[0][0]); } }