Leetcode 刷题记录¶
- date:
2021-03-10
小技巧
用 ./new-problem.sh 来开始一道新题目：
new-problem.sh
#!/usr/bin/bash
title=$(python -c "print('$1'.replace('-', ' ').title())")
title_delim=$(python -c "print('-'*len('$title'))")
cat <<EOF >> index.rst
$title
$title_delim
.. leetcode:: _
:id: $1
:diffculty:
:language:
:key:
:date: $(date +%F)
EOF
mkdir $1
Two Sum¶
- 地址:
- 难度:
- 语言:
题解
// ref: https://github.com/iosmanthus/leetcode-rust/blob/master/two-sum/src/lib.rs
use std::collections::HashMap;
pub struct Solution;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut seen = HashMap::new();
for (i, num) in nums.iter().enumerate() {
if seen.contains_key(num) {
return vec![seen[num], i as i32];
} else {
seen.insert(target - num, i as i32);
}
}
panic!();
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(vec![1, 3], Solution::two_sum(vec![9, 1, 2, 4, 3], 5));
assert_eq!(vec![0, 5], Solution::two_sum(vec![1, 4, 3, 4, 0, 5], 6));
}
}
我居然以为是 a+b 真是太蠢了。
花了一些时间来回忆 rust 的语法，工作后技术直觉好了很多，之前觉得不容易理解的地方 （指 rust）现在觉得非常直观了。
Valid Parentheses¶
- 地址:
- 难度:
- 语言:
- 日期:
题解
pub struct Solution;
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack = Vec::new();
for ch in s.chars() {
match ch {
'(' | '{' | '[' => stack.push(ch),
']' => {
let _ = match stack.last() {
Some('[') => stack.pop(),
_ => return false,
};
},
'}' => {
let _ = match stack.last() {
Some('{') => stack.pop(),
_ => return false,
};
},
')' => {
let _ = match stack.last() {
Some('(') => stack.pop(),
_ => return false,
};
},
_ => panic!("no parenthes!"),
}
}
return stack.len() == 0
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(true, Solution::is_valid(String::from("[][]"), ));
assert_eq!(false, Solution::is_valid(String::from("[[]"), ));
assert_eq!(true, Solution::is_valid(String::from("{[]}"), ));
assert_eq!(false, Solution::is_valid(String::from("{[}]"), ));
}
}
熟悉语法……
LRU Cache¶
- 地址:
- 难度:
- 语言:
- 日期:
题解
package main
import "container/list"
type LRUCache struct {
capacity int
recent *list.List
elems map[int]*list.Element
}
type Pair struct {
Key int
Value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
recent: list.New(),
elems: make(map[int]*list.Element),
}
}
func (this *LRUCache) Get(key int) int {
if elem, ok := this.elems[key]; ok {
this.recent.MoveToFront(elem)
return elem.Value.(Pair).Value
} else {
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
pair := Pair{Key: key, Value: value}
if elem, ok := this.elems[key]; ok {
elem.Value = pair
this.recent.MoveToFront(elem)
} else if len(this.elems) >= this.capacity {
elem = this.recent.Back()
delete(this.elems, elem.Value.(Pair).Key)
elem.Value = pair
this.recent.MoveToFront(elem)
this.elems[key] = elem
} else {
elem = this.recent.PushFront(pair)
this.elems[key] = elem
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
想用 rust 写个 LRU cache 吧发现 std::collection:LinkedList 没有暴露出类似
链表节点的结构体……有的话所有权也是问题，Cursor 看起来像然而 nightly only，
好像还是太菜了 —— 是说我自己。
但如果换成 go 的话…… 这么简单的题也算 medium 吗 ，可能因为太实用了所以写起来不难？
LFU Cache¶
- 地址:
- 难度:
- 语言:
- 日期:
- 参考:
https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/LRU:LFU_interview.md
题解
package main
import "container/list"
type Pair struct {
Key int
Value int
Freq int
}
type LFUCache struct {
capacity int
freq *list.List
elems map[int]*list.Element
}
func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
freq: list.New(),
elems: make(map[int]*list.Element),
}
}
func (this *LFUCache) Get(key int) int {
if elem, ok := this.elems[key]; ok {
this.touch(elem)
return elem.Value.(*Pair).Value
} else {
return -1
}
}
func (this *LFUCache) touch(elem *list.Element) {
elem.Value.(*Pair).Freq += 1
// println("touch", elem.Value.(*Pair).Value, elem.Value.(*Pair).Freq)
for e := elem.Prev(); e != nil; e = e.Prev() {
if e.Value.(*Pair).Freq <= elem.Value.(*Pair).Freq {
// println("move", elem.Value.(*Pair).Value, "before", e.Value.(*Pair).Value)
// println("freq", elem.Value.(*Pair).Freq, e.Value.(*Pair).Freq)
this.freq.MoveBefore(elem, e)
}
}
}
func (this *LFUCache) Put(key int, value int) {
// println("put", key, value)
pair := Pair{Key: key, Value: value, Freq: 0}
if elem, ok := this.elems[key]; ok {
this.touch(elem)
elem.Value.(*Pair).Value = value
} else if len(this.elems) >= this.capacity {
if this.capacity == 0 {
return
}
oldElem := this.freq.Back()
// println("pop", oldElem.Value.(*Pair).Key)
delete(this.elems, oldElem.Value.(*Pair).Key)
this.freq.Remove(oldElem)
elem := this.freq.PushBack(&pair)
this.touch(elem)
this.elems[key] = elem
} else {
elem := this.freq.PushBack(&pair)
this.touch(elem)
this.elems[key] = elem
}
}
// ----------------------------------------------------------------------------
type LFUCache2 struct {
capacity int
elems map[int]*list.Element
freq map[int]*list.List
min int
}
func Constructor2(capacity int) LFUCache2 {
return LFUCache2{
capacity: capacity,
freq: make(map[int]*list.List),
elems: make(map[int]*list.Element),
}
}
func (this *LFUCache2) Get(key int) int {
if elem, ok := this.elems[key]; ok {
this.touch(elem)
return elem.Value.(*Pair).Value
} else {
return -1
}
}
func (this *LFUCache2) touch(elem *list.Element) {
pair := elem.Value.(*Pair)
oldList := this.freq[pair.Freq]
oldList.Remove(elem)
if oldList.Len() == 0 && pair.Freq == this.min {
this.min++
}
// Incr fre
pair.Freq++
newList, ok := this.freq[pair.Freq]
if !ok {
newList = list.New()
this.freq[pair.Freq] = newList
}
newElem := newList.PushFront(pair)
this.elems[pair.Key] = newElem
}
func (this *LFUCache2) Put(key int, value int) {
if this.capacity == 0 {
return
}
// println("put", key, value)
if elem, ok := this.elems[key]; ok {
this.touch(elem)
elem.Value.(*Pair).Value = value
return
}
if len(this.elems) >= this.capacity {
lst := this.freq[this.min]
oldElem := lst.Back()
// println("pop", oldElem.Value.(*Pair).Key)
delete(this.elems, oldElem.Value.(*Pair).Key)
lst.Remove(oldElem)
}
this.min = 1
pair := Pair{Key: key, Value: value, Freq: 1}
lst, ok := this.freq[1]
if !ok {
lst = list.New()
this.freq[1] = lst
}
elem := lst.PushFront(&pair)
this.elems[key] = elem
}
func main() {
/**
* Your LFUCache object will be instantiated and called as such:
*/
//obj := Constructor(10)
//println(obj.Get(1))
//obj.Put(1, 1)
//println(obj.Get(1))
obj2 := Constructor2(2)
obj2.Put(1, 1)
obj2.Put(2, 2)
println(obj2.Get(1)) // touch
println(obj2.Get(2)) // touch
obj2.Put(3, 3)
println(obj2.Get(3))
println(obj2.Get(2))
println(obj2.Get(1))
}
- 解法 1
在 touch 一个元素的的时候从链表尾部往上找，是一个 \(O(n)\) 的操作，然而 Leetcode 给过了…… 要是在 SCAU OJ 是肯定要 TLE。
备注
看一眼输入输出限制，想想边界值，比如
cap == 0的情况就忽略了- 解法 2
更好的做法是按 freq 分成多个桶，每次 touch 一个元素就把它挪到对应的 frequency 的桶里，并且 cache 内维护一个 minFreq 方便立刻找到最应该该淘汰的桶， 桶内部是一个小的 LRU，这样 touch 就是 \(O(1)\) 了。
想过另一个做法是维护一个 freq 为结点值的最小堆，但本质上和方法一没区别，只是把 \(O(n)\) 的查找变成 \(O(\log n)\) 而已，大量重复的 freq 值是很浪费时间和空间的。
Add Two Numbers¶
- 地址:
- 难度:
- 语言:
- 日期:
题解
package main
/**
* Definition for singly-linked list.
*/
type ListNode struct {
Val int
Next *ListNode
}
func (self *ListNode) Equal(n *ListNode) bool {
if self == nil || n == nil {
// println(self, n, self == nil, n == nil, self == nil && n == nil)
return self == nil && n == nil
}
if self.Val != n.Val {
// println(self.Val, "!=", n.Val)
return false
}
return self.Next.Equal(n.Next)
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{}
cur := head
var carry int
for {
val := carry
end := true
if l1 != nil {
val += l1.Val
l1 = l1.Next
end = false
}
if l2 != nil {
val += l2.Val
l2 = l2.Next
end = false
}
if end {
break
}
carry = val / 10
cur.Next = &ListNode{
Val: val % 10,
}
// println("val", cur.Val)
cur = cur.Next
}
if carry != 0 {
cur.Next = &ListNode{
Val: carry,
}
// println("carry val", cur.Val)
}
return head.Next
}
凡是链表的题目都不能用 rust :'(
Partition Equal Subset Sum¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp::max as max;
use std::i32::MAX as i32max;
impl Solution {
pub fn can_partition(nums: Vec<i32>) -> bool {
let sum:i32 = nums.iter().sum();
if sum%2 != 0 {
return false
}
let mut state:Vec<i32> = vec![-i32max; (sum/2 + 1) as usize];
state[0] = 0;
// println!("{:?}", 0..nums.len());
for i in 0..nums.len() {
let base_cost = nums[i] as usize;
if base_cost > state.len()-1 {
// 放不进去，这里可以特判，但没有必要
// println!("cost {} > bag cap {}, skipped", base_cost, state.len()-1);
continue;
}
for j in (base_cost..state.len()).rev() {
state[j] = max(state[j], state[j-base_cost] + 1);
// println!("cap = {}, {} from ({}, {})", j, state[j], j-1, j-base_cost)
}
// println!("{} -> {}", state.len()-1, base_cost);
// println!("state: {:?}", state);
}
// println!("fin state: {:?} {}", state, state[state.len()-1] > 0);
state[state.len()-1] > 0
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::can_partition(vec![1, 2, 3]), true);
assert_eq!(Solution::can_partition(vec![1,5,11,5]), true);
assert_eq!(Solution::can_partition(vec![2,5,11,5]), false);
assert_eq!(Solution::can_partition(vec![2,50,500]), false);
assert_eq!(Solution::can_partition(vec![5, 1, 1, 1, 2]), true);
assert_eq!(Solution::can_partition(vec![2, 2, 3, 5]), false);
}
}
把一个集合分成两个，使其 sum 分别相等。假设原集合 sum 为 Sa ，从集合中选出一个子集，使其 sum 刚好为 Sa/2 ，剩下的元素组成的子集的 sum 自然也为 Sa/2。因此问题可以转化为一个 01 背包问题 问题，背包容量为 Sa/2，要求恰好装满，填充物的 cost 是数字的值，value 统一设置为 1，因为只需要证有解。
- 2024-04-01
用 Go 重写了一次，舍弃了空间优化，定义了完整的状态数组
dp[0..N][0..Sa/2]，当然原理上没有区别。需要手动处理化无物可放的情况，即初始化
dp[0]没有区别，要求恰好装满：容量为 0 的情况下什么都不放，即
dp[i][0] = 0没有东西可放时，容量非 0 的情况无解，即
dp[i][j] = -Infwherej != 0
状态转移方程当然也不变:
1..N → i 0..Sa/2 → j Ci 是第 i 件物品的 cost if j-Ci >= 0: dp[i][j] = max(dp[i-1][j], dp[i-1][j-Ci]+1) else: dp[i][j] = dp[i-1][j]
但注意：需要手动处理
j-Ci<0的情况：此时放不下第 i 件物品，只能不放了dp[i-1][j]TODO: 显示多种语言的解法
Merge Two Sorted Lists¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
/**
* Definition for singly-linked list.
*/
type ListNode struct {
Val int
Next *ListNode
}
func move(from, to *ListNode) (*ListNode, *ListNode) {
if to != nil {
to.Next = from
}
newFrom := from.Next
from.Next = nil
return newFrom, from
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
resHead := ListNode{}
resTail := &resHead
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
l1, resTail = move(l1, resTail)
} else {
l2, resTail = move(l2, resTail)
}
}
if l1 != nil {
resTail.Next = l1
}
if l2 != nil {
resTail.Next = l2
}
return resHead.Next
}
纯逻辑题。
Maximum Subarray¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// import "fmt"
func maxSubArray(nums []int) int {
max := nums[0]
m := make([]int, len(nums))
for i, v := range nums {
if i == 0 || m[i-1] < 0 {
m[i] = v
} else if m[i-1]+v < 0 {
m[i] = v
} else {
m[i] = m[i-1] + v
}
if m[i] > max {
max = m[i]
}
}
return max
}
func maxSubArray_Conquer(nums []int, left bool) (int, int) {
if len(nums) == 1 {
// fmt.Println(nums, nums[0], nums[0], left)
return nums[0], nums[0]
}
lmax, lmid := maxSubArray_Conquer(nums[:len(nums)/2], true)
rmax, rmid := maxSubArray_Conquer(nums[len(nums)/2:], false)
max := lmid + rmid
if lmax > max {
max = lmax
}
if rmax > max {
max = rmax
}
var mid int
if left {
var tmp int
mid = nums[len(nums)-1]
for i := len(nums) - 1; i >= 0; i-- {
tmp += nums[i]
if tmp > mid {
mid = tmp
}
}
} else {
var tmp int
mid = nums[0]
for i := 0; i < len(nums); i++ {
tmp += nums[i]
if tmp > mid {
mid = tmp
}
}
}
// fmt.Println(nums, max, mid, left)
return max, mid
}
func maxSubArray_Divide(nums []int) int {
max, _ := maxSubArray_Conquer(nums, true)
return max
}
func main() {
println(maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
println(maxSubArray([]int{-1, -1, -1, -1}))
println(maxSubArray([]int{1}))
println(maxSubArray([]int{1, 2, 3}))
println(maxSubArray([]int{1, 2, 3, -1}))
println(maxSubArray([]int{-1, 1, 2, 3, -1}))
println(maxSubArray([]int{-2, -3, -1}))
println(maxSubArray([]int{8, -19, 5, -4, 20}))
println("------------")
println(maxSubArray_Divide([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}))
println(maxSubArray_Divide([]int{-1, -1, -1, -1}))
println(maxSubArray_Divide([]int{1}))
println(maxSubArray_Divide([]int{1, 2, 3}))
println(maxSubArray_Divide([]int{1, 2, 3, -1}))
println(maxSubArray_Divide([]int{-1, 1, 2, 3, -1}))
println(maxSubArray_Divide([]int{-2, -3, -1}))
println(maxSubArray_Divide([]int{8, -19, 5, -4, 20}))
}
题目本身比较简单，一维 DP 或者贪心 \(O(n)\) 可做。
题干提示可用分治法做，"which is more subtle"，是一个吃力不讨好的解法。但很有代表性：
设数组最大子序列为 M ，M = max(Mleft, Mright, Mmiddle)，分别为左半边数组的最大子序列，右半边数组的最大子序列，或者是从中间算起，横跨左右的最大子序列。
当问题规模缩减至 1 的时候， Mleft, Mright, Mmiddle 显然为数组里唯一的元素
Mmiddle 的值不可由子问题推导出来，只能在数组 l 和 r 分别逆序和顺序遍历，求各自的从边缘开始的最大子序列，是一个 \(O(n)\) 的操作 -- 这就决定了这个解法比 DP 慢，在每一轮子问题的解决都要遍历一次
二分法，所以问题要 \(O(\log_{2}n)\) 个规模的子问题
复杂度为 \(O(n\log n)\) 。
Climbing Stairs¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
package main
var memo []int
func climbStairs_inner(n int) int {
if n < 0 {
return 0
}
if memo[n] != -1 {
return memo[n]
}
res := climbStairs_inner(n-1) + climbStairs_inner(n-2)
memo[n] = res
return res
}
// 暴搜 + 记忆
func climbStairs(n int) int {
memo = make([]int, n+1)
for i := range memo {
memo[i] = -1
}
if n > 0 {
memo[0] = 1
}
if n > 1 {
memo[1] = 1
}
if n > 2 {
memo[2] = 2
}
return climbStairs_inner(n)
}
// 递推解法
func climbStairs2(n int) int {
res := make([]int, n+1)
if n >= 1 {
res[1] = 1
}
if n >= 2 {
res[2] = 2
}
if n < 3 {
return res[n]
}
for i := 3; i <= n; i++ {
res[i] = res[i-1] + res[i-2]
}
return res[n]
}
func main() {
println(climbStairs(1))
println(climbStairs(2))
println(climbStairs(3))
println(climbStairs(6))
println(climbStairs(45))
println("--------------")
println(climbStairs2(1))
println(climbStairs2(2))
println(climbStairs2(3))
println(climbStairs2(6))
println(climbStairs2(45))
}
- 记忆化搜索
写一个暴力版本，时间复杂度 \(O(2^n)\)。记忆冗余结果后复杂度应为 \(O(n)`(?)。空间复杂度 :math:`O(n)\)
- 递推
有一点动态规划的味道，但逻辑上非常简单，时间空间复杂度都是 \(O(n)\)
- 斐波那契数列
空间上当然可以到 \(O(1)\) ，不写了
Binary Tree Inorder Traversal¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
//* Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
var res = []int{}
if root == nil {
return res
}
if root.Left != nil {
res = append(res, inorderTraversal(root.Left)...)
}
res = append(res, root.Val)
if root.Right != nil {
res = append(res, inorderTraversal(root.Right)...)
}
return res
}
func main() {
}
纯数据结构题，没啥好说。
Symmetric Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
package main
import "container/list"
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isEqual(l, r *TreeNode) bool {
if l == nil && r == nil {
return true
}
if l == nil || r == nil {
return false
}
if l.Val != r.Val {
return false
}
return isEqual(l.Left, r.Right) && isEqual(l.Right, r.Left)
}
// 递归解法
func isSymmetric(root *TreeNode) bool {
return isEqual(root.Left, root.Right)
}
// 迭代解法
func isSymmetric2(root *TreeNode) bool {
stackL := list.New()
stackR := list.New()
// Prevent duplicate compare
L := root.Left
R := root.Right
for L != nil || stackL.Len() != 0 {
for L != nil {
if R == nil {
return false
}
stackL.PushBack(L)
stackR.PushBack(R)
L = L.Left
R = R.Right
}
if R != nil {
return false
}
if stackL.Back() != nil {
if stackR.Back() == nil {
return false
}
L = stackL.Remove(stackL.Back()).(*TreeNode)
R = stackR.Remove(stackR.Back()).(*TreeNode)
if L.Val != R.Val {
return false
}
if L.Right != nil {
if R.Left == nil {
return false
}
stackL.PushBack(L.Right)
stackR.PushBack(R.Left)
}
L = L.Right
R = R.Left
}
}
if R != nil || stackL.Len() != 0 {
return false
}
return true
}
func main() {
}
- 递归解法
按递归做的话是带点变化的数据结构题，左右子树互为镜像，任意对称的节点的左子树等于右子树。
- 非递归解法
引入栈，按
左->中->右和右->中->左应得到完全相同的序列。小技巧
前序遍历写起来应当简单一点
Maximum Depth Of Binary Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxInt(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + maxInt(maxDepth(root.Left), maxDepth(root.Right))
}
func main() {}
数据结构题。
Best Time to Buy and Sell Stock¶
- 地址:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
pub struct Solution;
impl Solution {
// 暴力 O(n!) TLE
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut max = 0;
for i in 0..prices.len()-1 {
for j in i+1..prices.len() {
if prices[j] - prices[i] > max {
max = prices[j] - prices[i];
}
}
}
return max
}
// DP1
pub fn max_profit2(prices: Vec<i32>) -> i32 {
let mut max = 0;
let mut profit = vec![0; prices.len()];
for i in 1..prices.len() {
for j in (0..i).rev() {
if prices[i] >= prices[j] {
profit[i] = profit[j] + (prices[i] - prices[j]);
if profit[i] > max {
max = profit[i];
}
break;
}
}
}
return max
}
// DP2
pub fn max_profit3(prices: Vec<i32>) -> i32 {
let mut max = 0;
let mut profit = vec![0; prices.len()];
for i in 1..prices.len() {
profit[i] = profit[i-1] + (prices[i] - prices[i-1]);
if profit[i] < 0 {
profit[i] = 0;
}
if profit[i] > max {
max = profit[i];
}
}
return max
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::max_profit(vec![1, 2, 3]), 2);
assert_eq!(Solution::max_profit(vec! [7,1,5,3,6,4]), 5);
assert_eq!(Solution::max_profit2(vec![1, 2, 3]), 2);
assert_eq!(Solution::max_profit2(vec! [7,1,5,3,6,4]), 5);
}
}
写了三个版本：
- 暴力
TLE，每次
i+1..prices.len()的回溯有大量荣誉计算，复杂度为 \(O(n!)\)- DP1
其实不太算 DP，参考里给出了非常 DP 的解法。
profit[i]第 i 天卖出股票的最大正收益（亏本不卖）。以为状态转移方程是profit[i] = profit[j] + (prices[i] - prices[j]), wherej < i && prices[j] <= prices[i]。复杂度依然为 \(O(n!)\) ，只是有几率避免冗余计算，勉强 AC 但时间上只超过了 8% 的选手，有问题。备注
实际上
profit[i]可以只从profit[i-1]推断，见下- DP2
更好的状态转移方程是
profit[i] = max(profit[i-1] + (prices[i] - prices[i-1]), 0)。复杂度为 \(O(n)\) ，超过了 85%+ 的选手，够了。从题意上看，方程的意思是：在第 i-1 天我们已经取得了能取得的最大收益，那第 i 天也应该参考第 i-1 天的购入时机，如果亏本了，则不购入。
Invert Binary Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func invertTree(root *TreeNode) *TreeNode {
if root != nil {
l := root.Left
r := root.Right
root.Left = invertTree(r)
root.Right = invertTree(l)
}
return root
}
func main() {
}
我能去 Google 了吗？[1]
Best Time to Buy and Sell Stock II¶
- 地址:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
impl Solution {
// DP2
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut profit = vec![0; prices.len()];
for i in 1..prices.len() {
if prices[i] - prices[i-1] > 0 {
profit[i] = profit[i-1] + (prices[i] - prices[i-1])
} else {
profit[i] = profit[i-1]
}
}
return profit[prices.len()-1]
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::max_profit(vec![7,1,5,3,6,4]), 7);
assert_eq!(Solution::max_profit(vec! [1,2,3,4,5]), 4);
}
}
🧮Best Time to Buy and Sell Stock 的一个简单变体，允许多次买卖，没啥好说。
Best Time to Buy and Sell Stock III¶
- 地址:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
use std::cmp;
pub struct Solution;
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut max = 0;
// First transaction
let mut profit1 = vec![0; prices.len()];
let mut max_profit1 = vec![0; prices.len()];
for i in 1..prices.len() {
profit1[i] = profit1[i - 1] + (prices[i] - prices[i - 1]);
if profit1[i] < 0 {
profit1[i] = 0;
}
max_profit1[i] = cmp::max(profit1[i], max_profit1[i - 1]);
if profit1[i] > max {
max = profit1[i];
}
}
// Possible second transaction
let mut profit2 = vec![0; prices.len()];
for i in 2..prices.len() {
profit2[i] = cmp::max(max_profit1[i - 2], profit2[i - 1]) + (prices[i] - prices[i - 1]);
if profit2[i] < 0 {
profit2[i] = 0;
}
if profit2[i] > max {
max = profit2[i];
}
}
return max;
}
pub fn max_profit2(prices: Vec<i32>) -> i32 {
let mut buy1 = prices[0];
let mut sell1 = 0;
let mut buy2 = prices[0];
let mut sell2 = 0;
for i in 1..prices.len() {
buy1 = cmp::min(buy1, prices[i]);
sell1 = cmp::max(sell1, prices[i] - buy1);
buy2 = cmp::min(buy2, prices[i] - sell1);
sell2 = cmp::max(sell2, prices[i] - buy2);
}
sell2
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::max_profit(vec![3, 3, 5, 0, 0, 3, 1, 4]), 6);
assert_eq!(Solution::max_profit(vec![1, 2, 3, 4, 5]), 4);
assert_eq!(Solution::max_profit(vec![7, 6, 4, 3, 1]), 0);
assert_eq!(Solution::max_profit(vec![1, 8, 1, 8, 7, 10]), 16);
assert_eq!(Solution::max_profit(vec![3, 2, 6, 5, 0, 3]), 7);
assert_eq!(Solution::max_profit(vec![6, 1, 6, 4, 3, 0, 2]), 7); // 5
assert_eq!(Solution::max_profit2(vec![3, 3, 5, 0, 0, 3, 1, 4]), 6);
// assert_eq!(Solution::max_profit2(vec![1, 2, 3, 4, 5]), 4);
// assert_eq!(Solution::max_profit2(vec![7, 6, 4, 3, 1]), 0);
// assert_eq!(Solution::max_profit2(vec![1, 8, 1, 8, 7, 10]), 16);
// assert_eq!(Solution::max_profit2(vec![3, 2, 6, 5, 0, 3]), 7);
// assert_eq!(Solution::max_profit2(vec![6, 1, 6, 4, 3, 0, 2]), 7); // 5
}
}
🧮Best Time to Buy and Sell Stock 的一个更难的变体，允许至多两次不重叠的买卖。
- 解法一
按
🧮Best Time to Buy and Sell Stock的解法，进行一次买卖，在此基础得到一个第 i 天收入的数组max_profit1，该收入不一定是当日卖出所得第二次买卖，需在第一次买卖后一天（当天卖，当天买没有意义，收益和一次买卖没差）:
profit2[i] = max(max_profit1[i-2], profit2[i-1]) + (prices[i] - prices[i-1])profit2数组为第一次买卖 后 ，第 i 天的收入的数组，若收入为负，则放弃该交易，收入为 0。可以看到
profit2[i]肯定会赚 i-1 天的差价prices[i] - prices[i-1]，但可以选择加上 i-2 天时第一次买卖的最大收入max_profit1[i-2]或者沿用 i-1 t天做第二次买卖的最优策略。最终
profit2数组中的最大值为答案。复杂度为 \(2*O(n)\) ，这个常数可以优化掉，测评里只比 6.67% 的选手快，\(O(n)\) 已经是这个问题的极限了，暂时不知道哪里有问题。
- 解法2
看的题解。
对每个状态（两次购买，两次出售）各构造一个互相依赖的状态转移方程。
Single Number¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
pub struct Solution;
impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
let mut res = 0;
for i in nums {
res = res ^ i;
}
return res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::single_number(vec![2, 2, 1]), 1);
assert_eq!(Solution::single_number(vec![2, 3, 4, 2, 3, 4, 1]), 1);
}
}
遥想 👤pcf 师傅还跟我讨论过这题，可惜没记住。反正不看题解打死也做不出来。
Diameter Of Binary Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
package main
import (
"sort"
)
var res int
func maxInts(s ...int) int {
sort.Ints(s)
return s[len(s)-1]
}
// Return (left, right)
func armSpan(root *TreeNode) (int, int) {
var L, R int
ints := []int{res}
if root.Left != nil {
ll, lr := armSpan(root.Left)
L = maxInts(ll, lr) + 1
}
if root.Right != nil {
rl, rr := armSpan(root.Right)
R = maxInts(rl, rr) + 1
}
ints = append(ints, L+R)
res = maxInts(ints...)
// println("node", root.Val, L, R)
return L, R
}
func diameterOfBinaryTree(root *TreeNode) int {
res = 0
armSpan(root)
return res
}
// Return (left, right)
func armSpan2(root *TreeNode) (int, int) {
var L, R int
if root.Left != nil {
ll, lr := armSpan2(root.Left)
L = maxInts(ll, lr) + 1
}
if root.Right != nil {
rl, rr := armSpan2(root.Right)
R = maxInts(rl, rr) + 1
}
ints := []int{res}
ints = append(ints, L+R)
res = maxInts(ints...)
// println("node", root.Val, L, R)
return L, R
}
func diameterOfBinaryTree2(root *TreeNode) int {
res = 0
armSpan2(root)
return res
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
// Return (left, right)
func diameterOfBinaryTree3(root *TreeNode) int {
res = 0
depth(root)
return res
}
func depth(root *TreeNode) int {
if root == nil {
return 0
}
L := depth(root.Left)
R := depth(root.Right)
res = max(res, L+R)
return max(L, R) + 1
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func main() {
t1 := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 4,
},
Right: &TreeNode{
Val: 5,
},
},
Right: &TreeNode{
Val: 3,
},
}
println(diameterOfBinaryTree(t1))
t2 := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 4,
},
},
}
println(diameterOfBinaryTree(t2))
}
这题本不难，答案是所有节点中「左子树深度 + 右子树深度」最大的值。
- 解法1
没能 AC，留下是为了提醒自己。
实现稍复杂，思路上是实现一个对每个节点返回左右臂展（其实就是深度）的函数：需要考虑
root.Left != nil和root.Right != nil的情况，总之是对的，但因为思路的不明确，实现了一个func maxInts(s ...int)的函数，在递归前存了res在数组里，在递归后拿它来做运算…… 非常典型的错误- 解法2
仅修正了比较前的
res被覆盖的问题，AC ，但maxInts很慢。- 解法3
标准解法，参考里的题解有个莫名其妙的
+1再-1，没有用。
Merge Two Binary Trees¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil && root2 == nil {
return nil
}
root3 := &TreeNode{}
var l1, r1, l2, r2 *TreeNode
if root1 != nil {
root3.Val = root1.Val
l1 = root1.Left
r1 = root1.Right
}
if root2 != nil {
root3.Val += root2.Val
l2 = root2.Left
r2 = root2.Right
}
root3.Left = mergeTrees(l1, l2)
root3.Right = mergeTrees(r1, r2)
return root3
}
func main() {
}
数据结构题。
Maximum Product Subarray¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn max_product(nums: Vec<i32>) -> i32 {
let mut products = vec![0; nums.len()];
let mut products_neg = vec![0; nums.len()];
products[0] = if nums[0] > 0 {nums[0]} else {0};
products_neg[0] = if nums[0] < 0 {nums[0]} else {0};
let mut res = nums[0];
for i in 1..nums.len() {
let p = products[i-1]*nums[i];
let p_neg = products_neg[i-1]*nums[i];
products[i] = cmp::max(p, nums[i]);
products[i] = cmp::max(products[i], p_neg);
products_neg[i] = cmp::min(p_neg, nums[i]);
products_neg[i] = cmp::min(products_neg[i], p);
res = cmp::max(res, products[i]);
}
//println!("{:?}", products);
//println!("{:?}", products_neg);
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::max_product(vec![-2, 0, -1]), 0);
assert_eq!(Solution::max_product(vec![-2, 2, 3, -5]), 60);
assert_eq!(Solution::max_product(vec![2, 3, -5]), 6);
assert_eq!(Solution::max_product(vec![2,3,-2,4]), 6);
assert_eq!(Solution::max_product(vec![-2]), -2);
assert_eq!(Solution::max_product(vec![-100,-2]), 200);
assert_eq!(Solution::max_product(vec![-100, 2]), 2);
}
}
🧮Maximum Subarray 的变体，求乘积最大的子序列。偷偷看了一眼题解：得到了「开两个 dp 数组」的提示。
N 为给定数组，用 P[i] 表示以 i 结尾的子序列的最大乘积，假设数组只有非负数，那么 P[i] 的值只和 N[i] 和 P[i-1] 相关： P[i] = P[i-1] * N[i] 。
但数组可能出现负数：
用
P[i]表示以 i 结尾的子序列的最大正乘积用
Pn[i]表示以 i 结尾的子序列的最小负乘积
根据 N[i] 的正负不同：Pn 的值可能转化为 P，P 的值可能也转化为 Pn:
P[i] = max(N[0], P[i-1]*N[0], Pn[i-1]*N[0])Pn[i] = min(N[0], P[i-1]*N[0], Pn[i-1]*N[0])
Shortest Subarray To Be Removed To Make Array Sorted¶
题解
pub struct Solution;
use std::cmp;
pub fn cross_find(arr: &Vec<i32>, l: i32, r: i32) -> i32 {
if l < 0 {
return r;
}
if r >= arr.len() as i32 {
return arr.len() as i32 - l - 1;
}
if arr[l as usize] <= arr[r as usize] {
return r - l - 1;
}
cmp::min(
cross_find(arr, l - 1, r),
cmp::min(cross_find(arr, l, r + 1), cross_find(arr, l - 1, r + 1)),
)
}
impl Solution {
pub fn find_length_of_shortest_subarray(arr: Vec<i32>) -> i32 {
let mut l_ptr = 0;
for i in 1..arr.len() {
if arr[i] < arr[i - 1] {
break;
}
l_ptr = i;
}
if l_ptr == arr.len() - 1 {
return 0;
}
let mut r_ptr = arr.len() - 1;
for i in (l_ptr..arr.len() - 1).rev() {
if arr[i] > arr[i + 1] {
break;
}
r_ptr = i;
}
cross_find(&arr, l_ptr as i32, r_ptr as i32)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::find_length_of_shortest_subarray(vec![1, 2, 3, 10, 4, 2, 3, 5]),
3
);
assert_eq!(
Solution::find_length_of_shortest_subarray(vec![5, 4, 3, 2, 1]),
4
);
assert_eq!(Solution::find_length_of_shortest_subarray(vec![1, 2, 3]), 0);
assert_eq!(
Solution::find_length_of_shortest_subarray(vec![1, 2, 3, 10, 0, 7, 8, 9]),
2
);
}
}
略难，写了很复杂的代码依然 WA，感受是：当你需要判断非常复杂的情况时，思路大概率部队。
移除 一个 最短的子序列使整个数组有序，那该数组必形如：[ 有序..., 无序..., 有序...]，当然两个有序的部分可能是空数组。数组为 N，易从左到右分别求出有序的部分 [0,l] 和 [r, len(N)-1]，那 [l+1, r-1] 是否就为最小的无序子序列呢？
非也，[0,l] 和 [r, len(N)-1] 分别有序，但整体不一定有序，而且可能重叠，如 [1, 2, 100] 和 [0, 2, 5]，从 ll in l->0 和 rr in len(N)-1 -> r 两个方向找恰好 N[ll] < N[rr] 即为答案，递归可做。
备注
注意整个数组有序的边界条件。
House Robber¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
// init state
let mut state = vec![0; nums.len()];
if nums.len() < 2 {
return nums[0];
}
state[0] = nums[0];
state[1] = nums[1];
if nums.len() < 3 {
return cmp::max(state[1], state[0]);
}
state[2] = nums[0] + nums[2];
if nums.len() < 4 {
return cmp::max(state[2], state[1]);
}
let mut res = cmp::max(state[2], state[1]);
for i in 3..nums.len() {
state[i] = cmp::max(state[i - 2], state[i - 3]) + nums[i];
res = cmp::max(res, state[i]);
}
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::rob(vec![1, 2, 3, 1]), 4);
assert_eq!(Solution::rob(vec![2, 7, 9, 3, 1]), 12);
assert_eq!(Solution::rob(vec![100, 1, 2, 200]), 300);
}
}
抢劫第 i 间房子能获得财产 M[i]，最大收入 R[i]。递推方程：R[i] = max(R[i-2], R[i-2]) + M[i]，答案为最大的 R[i]。
手动初始化前三个 R 有点累。
Longest Increasing Subsequence¶
- 地址:
https://leetcode.com/problems/longest-increasing-subsequence
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
pub struct Solution;
use std::cmp;
impl Solution {
// DP
pub fn length_of_lis(nums: Vec<i32>) -> i32 {
let mut res = 1;
let mut state = vec![0; nums.len()];
state[0] = 1;
for i in 1..nums.len() {
state[i] = 1;
for j in (0..i).rev() {
if nums[j] < nums[i] {
state[i] = cmp::max(state[i], state[j] + 1);
res = cmp::max(res, state[i]);
}
}
}
res
}
pub fn length_of_lis2(nums: Vec<i32>) -> i32 {
let mut low = vec![-100000; nums.len() + 1];
low[1] = nums[0];
let mut lidx = 1;
for i in 1..nums.len() {
if nums[i] > low[lidx] {
low[lidx + 1] = nums[i];
lidx += 1;
} else {
let sorted = &low[0..lidx + 1];
match sorted.binary_search(&nums[i]) {
Err(idx) => {
low[idx] = nums[i];
}
_ => (),
}
}
}
return lidx as i32;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::length_of_lis(vec![10, 9, 2, 5, 3, 7, 101, 18]), 4);
assert_eq!(Solution::length_of_lis(vec![0, 1, 0, 3, 2, 3]), 4);
assert_eq!(Solution::length_of_lis(vec![7, 7, 7, 7, 7, 7, 7]), 1);
assert_eq!(
Solution::length_of_lis2(vec![10, 9, 2, 5, 3, 7, 101, 18]),
4
);
assert_eq!(Solution::length_of_lis2(vec![0, 1, 0, 3, 2, 3]), 4);
assert_eq!(Solution::length_of_lis2(vec![7, 7, 7, 7, 7, 7, 7]), 1);
}
}
经典 DP 题。
- 维护以
i结尾的 LIS 的长度 设数组为
N，F[i]为以i结尾的最长上升子序列的长度，有递推式：F[i] = F[j]+1，whereN[i] < N[j]，这个 j 得通过一个0..i的循环获取，因此复杂度 为 \(O(n^2)\)- 维护长度为
i的 LIS 结尾元素的最小值 复杂度 \(O(n\log n)\)，是我想不出来的解法 T_T。
备注
感觉没有说明白，算了。
Edit Distance¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let word1: Vec<char> = word1.chars().collect();
let word2: Vec<char> = word2.chars().collect();
let mut d = vec![vec![0; word2.len() + 1]; word1.len() + 1];
for i in 0..word1.len() + 1 {
d[i][0] = i
}
for i in 0..word2.len() + 1 {
d[0][i] = i
}
for i in 1..word1.len() + 1 {
for j in 1..word2.len() + 1 {
d[i][j] = cmp::min(d[i - 1][j], d[i][j - 1]) + 1;
if word1[i - 1] == word2[j - 1] {
d[i][j] = cmp::min(d[i][j], d[i - 1][j - 1]);
} else {
d[i][j] = cmp::min(d[i][j], d[i - 1][j - 1] + 1);
}
}
}
d[word1.len()][word2.len()] as i32
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::min_distance(String::from("horse"), String::from("ros")),
3
);
assert_eq!(
Solution::min_distance(String::from("intention"), String::from("execution")),
5
);
}
}
太难了……毫无思路直接看题解。
Minimum ASCII Delete Sum for Two Strings¶
- 地址:
https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn minimum_delete_sum(s1: String, s2: String) -> i32 {
let s1: Vec<char> = s1.chars().collect();
let s2: Vec<char> = s2.chars().collect();
let mut del = vec![vec![0; s2.len() + 1]; s1.len() + 1];
for i in 1..s1.len() + 1 {
del[i][0] = del[i - 1][0] + s1[i - 1] as i32;
}
for i in 1..s2.len() + 1 {
del[0][i] = del[0][i - 1] + s2[i - 1] as i32;
}
for i in 1..s1.len() + 1 {
for j in 1..s2.len() + 1 {
if s1[i - 1] == s2[j - 1] {
del[i][j] = cmp::min(
cmp::min(
del[i - 1][j] + s1[i - 1] as i32,
del[i][j - 1] + s2[j - 1] as i32,
),
del[i - 1][j - 1],
);
} else {
del[i][j] = cmp::min(
cmp::min(
del[i - 1][j] + s1[i - 1] as i32,
del[i][j - 1] + s2[j - 1] as i32,
),
del[i - 1][j - 1] + s1[i - 1] as i32 + s2[j - 1] as i32,
);
}
}
}
del[s1.len()][s2.len()]
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::minimum_delete_sum(String::from("sea"), String::from("eat")),
231
);
assert_eq!(
Solution::minimum_delete_sum(String::from("delete"), String::from("leet")),
403
);
}
}
🧮Edit Distance 的变种，将最少操作数变成了最少的 ASCII 之和而已。
一开始审错题，难受。
Longest Common Subsequence¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
let text1: Vec<char> = text1.chars().collect();
let text2: Vec<char> = text2.chars().collect();
let mut d = vec![vec![0; text2.len() + 1]; text1.len() + 1];
for i in 1..text1.len() + 1 {
for j in 1..text2.len() + 1 {
if text1[i - 1] == text2[j - 1] {
d[i][j] = d[i - 1][j - 1] + 1;
} else {
d[i][j] = cmp::max(d[i - 1][j], d[i][j - 1]);
}
}
}
d[text1.len()][text2.len()] as i32
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::longest_common_subsequence(String::from("abcde"), String::from("ace")),
3
);
assert_eq!(
Solution::longest_common_subsequence(String::from("abc"), String::from("abc")),
3
);
assert_eq!(
Solution::longest_common_subsequence(String::from("def"), String::from("def")),
3
);
}
}
涉及两个数组的 DP 问题常常是二维 DP，和 :leetcode:`Edit Distance 的思路有相似之处。
两串为 S1, S2。定义数组 `D[i][j] 表示 S1[0..i] S2[0..j] 的 LCS 长度：
讨论
D[i-1][j],D[i][j-1],D[i-1][j-1]和D[i][j]的递推关系讨论可能的
D[0..i][j],D[i][0..j]的初始化
备注
当 S1[0..i] = A B C D S2[0..j] = A D，不需要在 D[i-1][j] 中讨论
S1[i-1] == D 的加入对 LCS 长度的影响，这部分情况完全由 D[i-1][j-1] 覆盖。
因此递推公式为:
D[i][j] = max(D[i-1][j], D[i][j-1], D[i-1][j-1] + X)
where X = 1 when S1[i-1] == S2[j-1]
当 S1[i-1] == S2[j-1] 时，LCS 延长。
Longest Palindromic Subsequence¶
- 地址:
https://leetcode.com/problems/longest-palindromic-subsequence
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn longest_palindrome_subseq(s: String) -> i32 {
let s: Vec<char> = s.chars().collect();
let mut d = vec![vec![0; s.len() + 1]; s.len() + 1];
for i in 1..s.len() + 1 {
for j in 1..s.len() + 1 {
if s[i - 1] == s[s.len() - j] {
d[i][j] = d[i - 1][j - 1] + 1;
} else {
d[i][j] = cmp::max(d[i - 1][j], d[i][j - 1]);
}
}
}
d[s.len()][s.len()] as i32
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::longest_palindrome_subseq(String::from("bbbab")),
4
);
assert_eq!(Solution::longest_palindrome_subseq(String::from("cbbd")), 2);
}
}
最长回文串。
- 作为
🧮Longest Common Subsequence的变种 将字符串翻转过来作为第二个数组，求 LCS 即可。
待处理
常规解法
Longest Palindromic Substring¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
static mut ANS: (i32, i32) = (0, 0);
pub fn reslove_palindrome(s: &Vec<char>, l: i32, r: i32) {
if l < 0 || r >= s.len() as i32 {
return;
}
if s[l as usize] == s[r as usize] {
unsafe {
if r - l > ANS.1 - ANS.0 {
ANS = (l, r);
}
}
reslove_palindrome(s, l - 1, r + 1);
}
}
impl Solution {
// 递归解法
pub fn longest_palindrome(s: String) -> String {
unsafe { ANS = (0, 0) };
let s: Vec<char> = s.chars().collect();
for i in 0..s.len() {
reslove_palindrome(&s, i as i32, i as i32);
if i >= 1 {
reslove_palindrome(&s, (i - 1) as i32, i as i32);
}
}
let safe_ans = unsafe { (ANS.0 as usize, ANS.1 as usize) };
s[safe_ans.0..safe_ans.1 + 1].iter().collect::<String>()
}
pub fn longest_palindrome2(s: String) -> String {
let s: Vec<char> = s.chars().collect();
let mut res = (0, 0);
let mut d = vec![vec![false; s.len()]; s.len()];
for i in (0..s.len()).rev() {
for j in i..s.len() {
if s[i] == s[j] {
if j - i <= 2 {
d[i][j] = true;
} else {
d[i][j] = d[i + 1][j - 1];
}
}
if d[i][j] {
if j - i > res.1 - res.0 {
println!("update {:?}", res);
res = (i, j);
}
}
}
}
s[res.0..res.1 + 1].iter().collect::<String>()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::longest_palindrome(String::from("babad")), "bab");
assert_eq!(Solution::longest_palindrome(String::from("cbbd")), "bb");
assert_eq!(Solution::longest_palindrome(String::from("a")), "a");
assert_eq!(Solution::longest_palindrome(String::from("aaca")), "aca");
assert_eq!(Solution::longest_palindrome(String::from("bb")), "bb");
assert_eq!(Solution::longest_palindrome2(String::from("babad")), "aba");
assert_eq!(Solution::longest_palindrome2(String::from("cbbd")), "bb");
assert_eq!(Solution::longest_palindrome2(String::from("a")), "a");
assert_eq!(Solution::longest_palindrome2(String::from("aaca")), "aca");
assert_eq!(Solution::longest_palindrome2(String::from("bb")), "bb");
}
}
钻了牛角尖……还不如直接看题解。
- 分情况递归
字符串为
S，开一个全局变量存最大回文字串的区间ANS = (0, 0)，对每一个S[i]，从中间往两边扫，可获得所有的 "YXY" 的奇数回文串。但注意有 "YXXY" 的偶数回文串，则对每一个相等的S[i-1]和S[i]往两边扫。复杂度为 \(O(n^2)\)，感觉可以用记忆化优化一下。
- DP
状态数组
D[i][j]表示S[i..j]是否为回文串。若S[i] == S[j]，则D[i][j]为回文串的话需要：i - j < 2或者
D[i+1][j-1]为回文串 wherei - j < 2
复杂度同为 \(O(n^2)\)。
备注
应当注意两层循环的方向，外层
i = n -> 0，内层j = i -> n是为了保证求D[i][j]时D[i+1][j-1]已解出
待处理
听说有 \(O(n)\) 的做法，改日再学习吧。
Linked List Cycle¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
head1 := head.Next
for head != nil && head1 != nil {
if head == head1 {
return true
}
if head1.Next == nil {
return false
}
head = head.Next
head1 = head1.Next.Next
}
return false
}
func main() {
}
无论如何时间复杂度都是 \(O(n)\)，用哈希标表存 visited 的做法不用说了。
题目要求用 \(O(1)\) 空间，估计我独立做不出来。很久前听 👤pcf 说到用两个指针，所以稍微回忆了一下：用两个步长不一致的指针，一个每次一个节点，一个每次两个节点，如果成环的话总会相遇。
Linked List Cycle II¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
package main
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
fast := head
slow := head
for fast != nil {
slow = slow.Next
if fast.Next == nil {
return nil
}
fast = fast.Next.Next
// println(fast.Val, slow.Val)
if slow == fast {
// cycle detected
ptr := head
for ptr != slow {
// println(ptr.Val, slow.Val)
ptr = ptr.Next
slow = slow.Next
}
return ptr
}
}
return nil
}
func main() {
l3 := &ListNode{Val: 3}
l2 := &ListNode{Val: 2}
l0 := &ListNode{Val: 0}
l4 := &ListNode{Val: 4}
l3.Next = l2
l2.Next = l0
l0.Next = l4
l4.Next = l2
detectCycle(l3)
}
看的题解。
我根本没在动脑子…… :(
Product of Array Except Self¶
- 地址:
- 难度:
- 语言:
:leetcode.language:` <>`
- 思路:
- 日期:
- 参考:
https://cntofu.com/book/186/problems/238.product-of-array-except-self.md
题解
不许用除法，想不出来，看的题解。
- 双前缀数组
巧妙的双前缀数组，时间空间复杂度均为 \(O(n)\)。
- 双前缀数组 无无额外空间
题目希望 \(O(1)\) 的空间复杂度，可以用一个临时变量存累乘结果，直接用存答案的数组的空间。
Trapping Rain Water¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::cmp;
impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {
if height.len() == 0 {
return 0;
}
let mut left = vec![0; height.len()];
let mut right = vec![0; height.len()];
left[0] = height[0];
right[height.len() - 1] = height[height.len() - 1];
for i in 1..height.len() {
left[i] = cmp::max(left[i - 1], height[i]);
}
for i in (0..height.len() - 1).rev() {
right[i] = cmp::max(right[i + 1], height[i]);
}
let mut water = 0;
for i in 0..height.len() {
water += cmp::min(left[i], right[i]) - height[i];
}
water
}
pub fn trap2(height: Vec<i32>) -> i32 {
if height.len() == 0 {
return 0;
}
let mut water = 0;
let mut stack = vec![0 as usize; height.len() + 1];
let mut ptr = 0;
for i in 0..height.len() {
while ptr > 0 && height[stack[ptr]] < height[i] {
let bottom = stack[ptr];
ptr -= 1;
if ptr == 0 {
break;
}
let left = stack[ptr];
let water_height = cmp::min(height[i], height[left]) - height[bottom];
let water_width = (i - left - 1) as i32;
water += water_height * water_width
}
ptr += 1;
stack[ptr] = i;
}
water
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::trap(vec![]), 0);
assert_eq!(Solution::trap(vec![0]), 0);
assert_eq!(Solution::trap(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6);
assert_eq!(Solution::trap(vec![4, 2, 0, 3, 2, 5]), 9);
assert_eq!(Solution::trap2(vec![]), 0);
assert_eq!(Solution::trap2(vec![0]), 0);
assert_eq!(Solution::trap2(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6);
assert_eq!(Solution::trap2(vec![4, 2, 0, 3, 2, 5]), 9);
}
}
似乎 👤pcf 也和我提到过，然而完全忘了。
看题解。
- 动态规划
其实也不像动态规划……倒不如说是
🧮Product of Array Except Self的变种，同样用到两个数组。L[i],R[i]为以第i格为中心，左右的最高点的高度，每一格可能容纳的水量为W[i] = min(L[i], R[i]) - Height[i]。- 单调栈 [2]
利用单调栈的性质，维护一个由高到低的水洼左边，每次 pop 的时候，算该水洼里的一层水
待处理
还有 \(O(1)\) 解法…… 歇会儿。
Next Greater Element I¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::collections::HashMap;
impl Solution {
pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let mut res = vec![-1; nums1.len()];
let mut map = HashMap::new();
for i in 0..nums1.len() {
map.insert(nums1[i], i);
}
let mut stack = vec![0; nums2.len()];
let mut ptr = 1;
stack[ptr - 1] = nums2[nums2.len() - 1];
for i in (0..nums2.len() - 1).rev() {
while ptr > 0 && stack[ptr - 1] < nums2[i] {
ptr -= 1;
}
let next_greater = if ptr > 0 { stack[ptr - 1] } else { -1 };
match map.get(&nums2[i]) {
Some(ii) => res[*ii] = next_greater,
None => (),
}
ptr += 1;
stack[ptr - 1] = nums2[i]
}
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::next_greater_element(vec![2], vec![2]), vec![-1]);
assert_eq!(
Solution::next_greater_element(vec![2, 5], vec![2, 5, 6]),
vec![5, 6]
);
assert_eq!(
Solution::next_greater_element(vec![4, 1, 2], vec![1, 3, 4, 2]),
vec![-1, 3, -1]
);
assert_eq!(
Solution::next_greater_element(vec![2, 4], vec![1, 2, 3, 4]),
vec![3, -1]
);
}
}
读题花了挺久……
暴力法可直接做，复杂度 \(O(m*n)，`m\) 为 nums1 长度，n 为 nums2 长度。
更好的做法是对 nums2 维护一个数组 G[i]，代表在 nums2[i] 右边比它大的元素（即 Next Greater Element），将 nums1[i] => i 的映射存在哈希表中，遍历 nums2 时可以得出答案。
G[i] 的求法为：从 nums2.len() => 0 方向维护一个单调递减的栈，依次尝试 push nums2[i]，当比栈顶大时，将栈中已有元素 pop 出；当比栈顶小时，G[i] = top_of_stack，之后 nums2[i] 入栈。
小技巧
G[i] 不依赖上一次循环的结果，在实际中可以就地求出，不必开辟空间
建哈希表复杂度为 \(O(m)\)，建单调栈复杂度为 \(O(n)\)，总的时间复杂度为 \(O(m+n)\)。
Swap Nodes in Pairs¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
ptr := head
head = ptr.Next // save head
var prev *ListNode
for ptr != nil && ptr.Next != nil {
next := ptr.Next
nextnext := next.Next
if prev != nil {
prev.Next = next
}
next.Next = ptr
ptr.Next = nextnext
prev = ptr
ptr = nextnext
}
return head
}
func main() {
}
用一个步进为 2 的循环即可。
Reverse Linked List¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
package main
import (
"container/list"
"fmt"
)
// for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
rev := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return rev
}
func reverseList2(head *ListNode) *ListNode {
stack := list.New()
for head != nil {
stack.PushBack(head)
tmp := head.Next
head.Next = nil
head = tmp
}
var prev *ListNode
for stack.Back() != nil {
tmp := stack.Remove(stack.Back()).(*ListNode)
if prev != nil {
prev.Next = tmp
prev = tmp
}
if head == nil {
head = tmp
prev = tmp
}
}
return head
}
func main() {
a := reverseList(&ListNode{Val: 1, Next: &ListNode{Val: 2}})
for a != nil {
fmt.Println(a)
a = a.Next
}
a = reverseList2(&ListNode{Val: 1, Next: &ListNode{Val: 2}})
for a != nil {
fmt.Println(a)
a = a.Next
}
}
没啥好说。
- 递归
万万没想到……递归我没写出来。看题解，题解说很明白了。
- 迭代
拿个栈。
Reverse Linked List II¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
import "fmt"
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func reverseBetweenI(head *ListNode, left int, right int, index int) *ListNode {
if head == nil || head.Next == nil {
return head
}
if index < left {
head.Next = reverseBetweenI(head.Next, left, right, index+1)
return head
} else if index > right-1 {
return head
} else {
rev := reverseBetweenI(head.Next, left, right, index+1)
succ := head.Next.Next
head.Next.Next = head
head.Next = succ
return rev
}
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
return reverseBetweenI(head, left, right, 1)
}
func main() {
a := reverseBetween(&ListNode{Val: 1, Next: &ListNode{Val: 2}}, 1, 2)
for a != nil {
fmt.Println(a)
a = a.Next
}
}
🧮Reverse Linked List 的变种。被翻转的链表的 tail 应始终指向右边不翻转的部分，因此处理右边界的时候要花点心思。
Implement Trie Prefix Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
type Trie struct {
Value byte
isWord bool
Children map[byte]*Trie
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{
Children: make(map[byte]*Trie),
}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
next, ok := this.Children[word[0]]
if !ok {
tmp := Constructor()
next = &tmp
next.Value = word[0]
this.Children[word[0]] = next
}
if word[1:] == "" {
next.isWord = true
} else {
next.Insert(word[1:])
}
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
next, ok := this.Children[word[0]]
if !ok {
return false
}
if word[1:] == "" {
return next.isWord
}
return next.Search(word[1:])
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
next, ok := this.Children[prefix[0]]
if !ok {
return false
}
if prefix[1:] == "" {
return true
}
return next.StartsWith(prefix[1:])
}
func main() {
/** Your Trie object will be instantiated and called as such: */
obj := Constructor()
obj.Insert("artist")
println(obj.Search("artist"))
println(obj.Search("artist2"))
println(obj.Search("artis"))
println(obj.Search("artisa"))
println("---")
println(obj.StartsWith("art"))
println(obj.StartsWith("artist"))
println(obj.StartsWith("artist2"))
}
纯数据结构题。
Combination Sum¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
use std::collections::HashSet;
pub fn combination_sum_rec(
res: &mut Vec<Vec<i32>>,
set: &HashSet<i32>,
remaining: i32,
cur: Vec<i32>,
) {
if remaining == 0 {
res.push(cur);
return;
}
if remaining < 0 {
return;
}
let start = if cur.len() > 0 { cur[cur.len() - 1] } else { 1 };
for i in start..remaining + 1 {
if !set.contains(&i) {
continue;
}
let mut next = cur.clone();
next.push(i);
combination_sum_rec(res, set, remaining - i, next);
}
}
impl Solution {
pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut set = HashSet::new();
for i in 0..candidates.len() {
set.insert(candidates[i]);
}
let mut res: Vec<Vec<i32>> = Vec::new();
combination_sum_rec(&mut res, &set, target, vec![]);
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::combination_sum(vec![2, 3, 6, 7], 7),
vec![vec![2, 2, 3], vec![7]]
);
assert_eq!(
Solution::combination_sum(vec![2, 3, 5], 8),
vec![vec![2, 2, 2, 2], vec![2, 3, 3], vec![3, 5]]
);
assert_eq!(Solution::combination_sum(vec![2], 1), vec![]);
assert_eq!(Solution::combination_sum(vec![1], 1), vec![vec![1]]);
}
}
从给定的 candicates 生成 sum 为 target 的组合。
递归可破，和之前的题不一样的是在每一次调用都伴随着一个新的解，所以要带着解的数组一起递归。
Generate Parentheses¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
pub fn generate_parenthesis_rec(
ans: &mut Vec<String>,
remaining: i32,
unclosed: i32,
cur: Vec<char>,
) {
let mut cur = cur.clone();
if remaining == 0 {
for _i in 0..unclosed {
cur.push(')')
}
ans.push(cur.iter().collect());
return;
}
for i in 0..unclosed + 1 {
let mut next = cur.clone();
next.push('(');
generate_parenthesis_rec(ans, remaining - 1, unclosed - i + 1, next);
cur.push(')');
}
}
impl Solution {
pub fn generate_parenthesis(n: i32) -> Vec<String> {
let mut res: Vec<String> = Vec::new();
generate_parenthesis_rec(&mut res, n, 0, vec![]);
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::generate_parenthesis(1), vec!["()"]);
assert_eq!(
Solution::generate_parenthesis(3),
vec!["((()))", "(()())", "(())()", "()(())", "()()()"]
);
}
}
和 🧮Combination Sum 类似的解法。
每一次递归中需要的决策是：要闭合几个未闭合的括号。
Sort an Array¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
题解
pub struct Solution;
pub fn partition(nums: &mut Vec<i32>, l: usize, r: usize) -> usize {
let pivot = nums[r];
// println!("before: {:?}", nums);
// println!("pivot: {}, [{}, {})", pivot, l, r);
let mut ptr = l;
for i in l..r {
// println!("cmp: {} and {}", nums[i], pivot);
if nums[i] <= pivot {
nums.swap(ptr, i);
ptr += 1;
// println!("swap: {} <-> {}", nums[i], nums[ptr]);
}
}
nums.swap(ptr, r);
ptr
}
pub fn rand_int(l: usize, r: usize) -> usize {
let v = vec![2, 3];
let a = &v as *const Vec<i32>;
let n = a as usize;
n % (r - l) + l
}
pub fn partition_rand(nums: &mut Vec<i32>, l: usize, r: usize) -> usize {
let pivot_idx = rand_int(l, r);
nums.swap(r, pivot_idx);
let pivot = nums[r];
// println!("before: {:?}", nums);
// println!("pivot: {}, [{}, {})", pivot, l, r);
let mut ptr = l;
for i in l..r {
// println!("cmp: {} and {}", nums[i], pivot);
if nums[i] <= pivot {
nums.swap(ptr, i);
ptr += 1;
// println!("swap: {} <-> {}", nums[i], nums[ptr]);
}
}
nums.swap(ptr, r);
ptr
}
pub fn quick_sort(nums: &mut Vec<i32>, l: usize, r: usize) {
if l >= r {
return;
}
let m = partition_rand(nums, l, r);
if m > l {
quick_sort(nums, l, m - 1);
}
if r > m {
quick_sort(nums, m + 1, r);
}
}
impl Solution {
pub fn sort_array(nums: Vec<i32>) -> Vec<i32> {
let mut nums = nums.clone();
if nums.len() < 2 {
return nums;
}
let r = nums.len() - 1;
quick_sort(&mut nums, 0, r);
nums
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::sort_array(vec![5, 3, 2, 5]), vec![2, 3, 5, 5]);
assert_eq!(
Solution::sort_array(vec![1, 5, 3, 2, 1, 0]),
vec![0, 1, 1, 2, 3, 5]
);
assert_eq!(Solution::sort_array(vec![]), vec![]);
assert_eq!(Solution::sort_array(vec![1]), vec![1]);
assert_eq!(Solution::sort_array(vec![1, 2]), vec![1, 2]);
}
}
- 2021-07-17:
情绪又不好了，看了近两个小时的快排教程没看进去。
使用固定 pivot 的普通的快排会 TLE，因为有一个近乎有序的大数组 case。
Rust 标准库没有生成随机数的函数……糊了一个。
Combination Sum II¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
pub struct Solution;
pub fn combination_sum2_rec(
res: &mut Vec<Vec<i32>>,
candidates: &Vec<i32>,
remaining: i32,
index: usize,
cur: Vec<i32>,
) {
if remaining == 0 {
res.push(cur);
return;
}
if remaining < 0 {
return;
}
let mut next_index = index;
for i in next_index + 1..candidates.len() {
if candidates[i] != candidates[index] {
next_index = i;
break;
}
}
if index < candidates.len() {
let mut next = cur.clone();
next.push(candidates[index]);
combination_sum2_rec(
res,
candidates,
remaining - candidates[index],
index + 1,
next,
);
}
if next_index != index && next_index < candidates.len() {
combination_sum2_rec(res, candidates, remaining, next_index, cur);
}
}
impl Solution {
pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut candidates = candidates;
candidates.sort();
let mut res: Vec<Vec<i32>> = Vec::new();
combination_sum2_rec(&mut res, &candidates, target, 0, vec![]);
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(
Solution::combination_sum2(vec![10, 1, 2, 7, 6, 1, 5], 8),
vec![vec![1, 1, 6], vec![1, 2, 5], vec![1, 7], vec![2, 6]]
);
assert_eq!(
Solution::combination_sum2(vec![2, 5, 2, 1, 2], 5),
vec![vec![1, 2, 2], vec![5]]
);
assert_eq!(Solution::combination_sum2(vec![1, 1], 1), vec![vec![1]]);
}
}
🧮Combination Sum 的变种。
增加了 candicates 可重复、以及结果不许重复的两个限制。
3Sum¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
- 参考:
https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
题解
pub struct Solution;
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res: Vec<Vec<i32>> = Vec::new();
if nums.len() < 3 {
return res;
}
let mut nums = nums;
nums.sort();
for i in 0..nums.len() - 2 {
if i != 0 && nums[i] == nums[i - 1] {
continue;
}
let mut k = nums.len() - 1;
for j in i + 1..nums.len() - 1 {
if j != i + 1 && nums[j] == nums[j - 1] {
continue;
}
while k > j && nums[i] + nums[j] + nums[k] > 0 {
k -= 1;
}
if k == j {
break;
}
if nums[i] + nums[j] + nums[k] == 0 {
res.push(vec![nums[i], nums[j], nums[k]]);
}
}
}
res
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
// assert_eq!(
// Solution::three_sum(vec![-1, 0, 1, 2, -1, -4]),
// vec![vec![-1, -1, 2], vec![-1, 0, 1]]
// );
// assert_eq!(Solution::three_sum(vec![1, 2, -3]), vec![vec![-3, 1, 2]]);
assert_eq!(
Solution::three_sum(vec![1, -1, -1, -1, 0, 0, 0, 1, 1, 1, 1]),
vec![vec![-1, 0, 1], vec![0, 0, 0]]
);
}
}
题目有双指针的标签，我怎么觉得回溯法就能做？试试看。
不能，评测 TLE 了，本地则是爆栈
- 双指针
看题解，把三重循环优化到二重了，复杂度 \(O(n^2)\)
备注
答案不许重复，
i，j的循环里都有nums[i] == nums[i - 1]的判断以跳过重复元素，但不必要对k判断，因为i，j已经不重复了，k自然不重复
Reverse Nodes In K Group¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
import "fmt"
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// revHead, revTail, ok
func reverseFirstKGroup(head *ListNode, k int) (*ListNode, *ListNode, bool) {
if k == 0 {
return head, nil, true
}
if head.Next == nil {
return head, nil, false
}
rev, _, ok := reverseFirstKGroup(head.Next, k-1)
if !ok {
return head, nil, ok
}
tmp := head.Next.Next
head.Next.Next = head
head.Next = tmp
return rev, head, ok
}
func reverseKGroup(head *ListNode, k int) *ListNode {
var newHead *ListNode
var prevTail *ListNode
next := head
for next != nil {
var tail *ListNode
next, tail, _ = reverseFirstKGroup(next, k-1)
if newHead == nil {
newHead = next
}
if prevTail != nil {
prevTail.Next = next
}
prevTail = tail
if tail == nil {
break
}
next = tail.Next
}
return newHead
}
func print(l *ListNode) {
if l != nil {
fmt.Printf("%d ->", l.Val)
print(l.Next)
} else {
fmt.Println("nil")
}
}
func main() {
print(reverseKGroup(&ListNode{Val: 1}, 1))
print(reverseKGroup(&ListNode{1, &ListNode{Val: 2}}, 1))
print(reverseKGroup(&ListNode{1, &ListNode{Val: 2}}, 2))
print(reverseKGroup(&ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{Val: 5}}}}}, 1))
print(reverseKGroup(&ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{Val: 5}}}}}, 2))
print(reverseKGroup(&ListNode{1, &ListNode{2, &ListNode{Val: 3}}}, 2))
}
🧮Reverse Linked List II 的变种，多了两个返回值： 一个用于返回翻转后的链表 tail，方便接下一段翻转链表，另一个一个用于判断该段需不需要 reverse，比较琐碎。
Evaluate Reverse Polish Notation¶
- 地址:
https://leetcode.com/problems/evaluate-reverse-polish-notation
- 难度:
- 语言:
- 日期:
题解
pub struct Solution;
impl Solution {
pub fn eval_rpn(tokens: Vec<String>) -> i32 {
// op in range [-200, 200]
let mut ops = vec![0];
for i in 0..tokens.len() {
match tokens[i].as_str() {
"+" => {
let op2 = ops.pop().unwrap();
let op1 = ops.pop().unwrap();
ops.push(op1 + op2);
}
"-" => {
let op2 = ops.pop().unwrap();
let op1 = ops.pop().unwrap();
ops.push(op1 - op2);
}
"*" => {
let op2 = ops.pop().unwrap();
let op1 = ops.pop().unwrap();
ops.push(op1 * op2);
}
"/" => {
let op2 = ops.pop().unwrap();
let op1 = ops.pop().unwrap();
ops.push(op1 / op2);
}
_ => {
ops.push(tokens[i].parse::<i32>().unwrap());
}
}
}
ops.pop().unwrap()
}
}
pub fn conv(v: Vec<&str>) -> Vec<String> {
v.iter().map(|x| x.to_string()).collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
assert_eq!(Solution::eval_rpn(conv(vec!["2", "1", "+", "3", "*"])), 9);
assert_eq!(Solution::eval_rpn(conv(vec!["-100"])), -100);
assert_eq!(Solution::eval_rpn(conv(vec!["4", "13", "5", "/", "+"])), 6);
assert_eq!(
Solution::eval_rpn(conv(vec![
"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"
])),
22
);
}
}
模拟题，只是对 rust 的字符串操作不太熟悉。
Balanced Binary Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
import "fmt"
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func abs(a int) int {
if a < 0 {
return -a
} else {
return a
}
}
func isBalancedRec(root *TreeNode) (bool, int) {
if root == nil {
return true, 0
}
okL := true
depthL := 0
if root.Left != nil {
okL, depthL = isBalancedRec(root.Left)
depthL += 1
}
if !okL {
return false, 0
}
okR := true
depthR := 0
if root.Right != nil {
okR, depthR = isBalancedRec(root.Right)
depthR += 1
}
if !okR {
return false, 0
}
return abs(depthR-depthL) <= 1, max(depthL, depthR)
}
func isBalanced(root *TreeNode) bool {
ok, _ := isBalancedRec(root)
return ok
}
func main() {
fmt.Println("vim-go")
}
判断子树是否平衡的时候要同时返回子树深度供父节点用。
Convert Sorted Array To Binary Search Tree¶
- 地址:
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
import "fmt"
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
if len(nums) == 1 {
return &TreeNode{
Val: nums[0],
}
}
mid := len(nums) / 2
root := &TreeNode{
Val: nums[mid],
}
root.Left = sortedArrayToBST(nums[:mid])
root.Right = sortedArrayToBST(nums[mid+1:])
return root
}
func main() {
fmt.Println("vim-go")
}
数组本身排好序了，用二分的方法就能找到每一层的 root。
Balance A Binary Search Tree¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func treeToSortedArray(root *TreeNode) []int {
if root == nil {
return []int{}
}
arr := treeToSortedArray(root.Left)
arr = append(arr, root.Val)
arr = append(arr, treeToSortedArray(root.Right)...)
return arr
}
func sortedArrayToBST(arr []int) *TreeNode {
if len(arr) == 0 {
return nil
}
if len(arr) == 1 {
return &TreeNode{
Val: arr[0],
}
}
mid := len(arr) / 2
root := &TreeNode{
Val: arr[mid],
}
root.Left = sortedArrayToBST(arr[:mid])
root.Right = sortedArrayToBST(arr[mid+1:])
return root
}
func balanceBST(root *TreeNode) *TreeNode {
return sortedArrayToBST(treeToSortedArray(root))
}
func main() {
}
🧮Convert Sorted Array To Binary Search Tree 的变种。
中序遍历 BST 能得到一个有序数组，用二分法构造出来的 BST 就是平衡的。
Ones and Zeroes¶
- 地址:
- 难度:
- 语言:
- 思路:
- 日期:
题解
package main
import "fmt"
func count01(s string) (int, int) {
count0 := 0
count1 := 0
for _, c := range s {
if c == '0' {
count0++
} else {
count1++
}
}
return count0, count1
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func findMaxForm(strs []string, m int, n int) int {
var dp [][]int
for i := 0; i <= m; i++ {
dp = append(dp, make([]int, n+1))
}
c0, c1 := count01(strs[0])
for i := c0; i <= m; i++ {
for j := c1; j <= n; j++ {
dp[i][j] = 1
}
}
for z, s := range strs {
if z == 0 {
continue
}
c0, c1 := count01(s)
for i := m; i >= c0; i-- {
for j := n; j >= c1; j-- {
dp[i][j] = max(dp[i][j], dp[i-c0][j-c1]+1)
}
}
}
return dp[m][n]
}
func main() {
fmt.Println(findMaxForm([]string{"10", "0001", "111001", "1", "0"}, 5, 3))
fmt.Println(findMaxForm([]string{"10", "0", "1"}, 1, 1))
}
01 背包问题，但需要同时填满两个容量不同的背包。
备注
在不优化的情况下，空间复杂度为 \(O(len*m*n)\)，需要一个三维的状态数组，
在 m < count0 && n < count1 的情况下，需要将 dp[i-1] 的状态复制到 dp[i]
反之，可以应用递推公式。
在优化的空间的情况下，第 i 轮循环中，未遍历 dp 的值即为 i-1 轮循环残留的值。
脚注