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#

地址:

https://leetcode.com/problems/two-sum

难度:

Easy

语言:

rust

题解
// 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#

地址:

https://leetcode.com/problems/valid-parentheses

难度:

Easy

语言:

rust

日期:

2021-05-04

题解
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#

地址:

https://leetcode.com/problems/lru-cache

难度:

Medium

语言:

go

日期:

2021-05-08

题解
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://leetcode.com/problems/lfu-cache

难度:

Medium

语言:

go

日期:

2021-05-08 2021-7-22

参考:

halfrost/Halfrost-Field

题解
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#

地址:

https://leetcode.com/problems/add-two-numbers

难度:

Medium

语言:

go

日期:

2021-05-13

题解
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#

地址:

https://leetcode.com/problems/partition-equal-subset-sum

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-06-21 2024-04-01

题解
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] = -Inf where j != 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#

地址:

https://leetcode.com/problems/merge-two-sorted-lists

难度:

Easy

语言:

go

思路:

链表

日期:

2021-07-05

题解
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#

地址:

https://leetcode.com/problems/maximum-subarray

难度:

Easy

语言:

go

思路:

动态规划 分治法

日期:

2021-07-05 2021-07-06

题解
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#

地址:

https://leetcode.com/problems/climbing-stairs

难度:

Easy

语言:

go

思路:

搜索 动态规划

日期:

2021-07-06

参考:

https://blog.csdn.net/zgpeace/article/details/88382121

题解
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#

地址:

https://leetcode.com/problems/binary-tree-inorder-traversal

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-06

题解
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#

地址:

https://leetcode.com/problems/symmetric-tree

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-06

参考:

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/

题解
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#

地址:

https://leetcode.com/problems/maximum-depth-of-binary-tree

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-07

题解
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

难度:

Easy

语言:

rust

思路:

动态规划

日期:

2021-07-07

参考:

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/bao-li-mei-ju-dong-tai-gui-hua-chai-fen-si-xiang-b/

题解
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]), where j < 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#

地址:

https://leetcode.com/problems/invert-binary-tree

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-07

题解
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

难度:

Easy

语言:

rust

思路:

动态规划

日期:

2021-07-07

题解
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

难度:

Hard

语言:

rust

思路:

动态规划

日期:

2021-07-07 2021-07-28

参考:

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/

题解
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#

地址:

https://leetcode.com/problems/single-number

难度:

Easy

语言:

rust

思路:

位操作

日期:

2021-07-07

参考:

https://www.cnblogs.com/grandyang/p/4130577.html

题解
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#

地址:

https://leetcode.com/problems/diameter-of-binary-tree

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-08

参考:

https://www.cnblogs.com/wangxiaoyong/p/10449634.html

题解
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 != nilroot.Right != nil 的情况,总之是对的,但因为思路的不明确,实现了一个 func maxInts(s ...int) 的函数,在递归前存了 res 在数组里,在递归后拿它来做运算…… 非常典型的错误

解法2

仅修正了比较前的 res 被覆盖的问题,AC ,但 maxInts 很慢。

解法3

标准解法,参考里的题解有个莫名其妙的 +1-1 ,没有用。

Merge Two Binary Trees#

地址:

https://leetcode.com/problems/merge-two-binary-trees

难度:

Easy

语言:

go

思路:

二叉树

日期:

2021-07-09

题解
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#

地址:

https://leetcode.com/problems/maximum-product-subarray

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-07-09

参考:

https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/

题解
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 的值可能转化为 PP 的值可能也转化为 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#

地址:

https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted

难度:

Medium

语言:

rust

日期:

2021-07-09

题解
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->0rr in len(N)-1 -> r 两个方向找恰好 N[ll] < N[rr] 即为答案,递归可做。

备注

注意整个数组有序的边界条件。

House Robber#

地址:

https://leetcode.com/problems/house-robber

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-07-09

题解
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

难度:

Medium

语言:

rust

思路:

动态规划 二分法

日期:

2021-07-12

参考:

https://blog.csdn.net/lxt_Lucia/article/details/81206439

题解
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 的长度

设数组为 NF[i] 为以 i 结尾的最长上升子序列的长度,有递推式:F[i] = F[j]+1,where N[i] < N[j],这个 j 得通过一个 0..i 的循环获取,因此复杂度 为 \(O(n^2)\)

维护长度为 i 的 LIS 结尾元素的最小值

复杂度 \(O(n\log n)\),是我想不出来的解法 T_T。

备注

感觉没有说明白,算了。

Edit Distance#

地址:

https://leetcode.com/problems/edit-distance

难度:

Hard

语言:

rust

思路:

动态规划

日期:

2021-07-12

参考:

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

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-07-12

题解
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#

地址:

https://leetcode.com/problems/longest-common-subsequence

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-07-13

题解
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

难度:

Medium

语言:

rust

思路:

动态规划

日期:

2021-07-13

题解
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#

地址:

https://leetcode.com/problems/longest-palindromic-substring

难度:

Medium

语言:

rust

思路:

递归 动态规划

日期:

2021-07-13

题解
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] 为回文串 where i - j < 2

复杂度同为 \(O(n^2)\)

备注

应当注意两层循环的方向,外层 i = n -> 0,内层 j = i -> n 是为了保证求 D[i][j]D[i+1][j-1] 已解出

待处理

听说有 \(O(n)\) 的做法,改日再学习吧。

Linked List Cycle#

地址:

https://leetcode.com/problems/linked-list-cycle

难度:

Easy

语言:

go

思路:

链表 快慢指针

日期:

2021-07-13

题解
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 说到用两个指针,所以稍微回忆了一下:用两个步长不一致的指针,一个每次一个节点,一个每次两个节点,如果成环的话总会相遇。

参见

👤lifeiren解法 惊为天人

Linked List Cycle II#

地址:

https://leetcode.com/problems/linked-list-cycle-ii

难度:

Medium

语言:

go

思路:

链表 快慢指针

日期:

2021-07-15

参考:

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

题解
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#

地址:

https://leetcode.com/problems/product-of-array-except-self

难度:

Medium

语言:

:leetcode.language:` <>`

思路:

前缀数组

日期:

2021-07-15

参考:

https://cntofu.com/book/186/problems/238.product-of-array-except-self.md

题解

不许用除法,想不出来,看的题解。

双前缀数组

巧妙的双前缀数组,时间空间复杂度均为 \(O(n)\)

双前缀数组 无无额外空间

题目希望 \(O(1)\) 的空间复杂度,可以用一个临时变量存累乘结果,直接用存答案的数组的空间。

Trapping Rain Water#

地址:

https://leetcode.com/problems/trapping-rain-water

难度:

Hard

语言:

rust

思路:

动态规划 双指针 单调栈

日期:

2021-07-15

题解
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#

地址:

https://leetcode.com/problems/next-greater-element-i

难度:

Easy

语言:

rust

思路:

单调栈

日期:

2021-07-16

题解
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 长度,nnums2 长度。

更好的做法是对 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#

地址:

https://leetcode.com/problems/swap-nodes-in-pairs

难度:

Medium

语言:

go

思路:

链表

日期:

2021-07-16

题解
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#

地址:

https://leetcode.com/problems/reverse-linked-list

难度:

Easy

语言:

go

思路:

链表

日期:

2021-07-16

参考:

https://zhuanlan.zhihu.com/p/86745433

题解
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#

地址:

https://leetcode.com/problems/reverse-linked-list-ii

难度:

Medium

语言:

go

思路:

链表

日期:

2021-07-16

题解
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#

地址:

https://leetcode.com/problems/implement-trie-prefix-tree

难度:

Medium

语言:

go

思路:

Tire树

日期:

2021-07-16

题解
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#

地址:

https://leetcode.com/problems/combination-sum

难度:

Medium

语言:

rust

思路:

回溯

日期:

2021-07-17

题解
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#

地址:

https://leetcode.com/problems/generate-parentheses

难度:

Medium

语言:

rust

思路:

回溯

日期:

2021-07-17

题解
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#

地址:

https://leetcode.com/problems/sort-an-array

难度:

Medium

语言:

rust

思路:

排序

日期:

2021-07-19

参考:

https://rust-algo.club/sorting/quicksort

题解
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#

地址:

https://leetcode.com/problems/combination-sum-ii

难度:

Medium

语言:

rust

思路:

回溯

日期:

2021-07-19

题解
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.com/problems/3sum

难度:

Medium

语言:

rust

思路:

双指针

日期:

2021-07-19

参考:

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)\)

备注

答案不许重复,ij 的循环里都有 nums[i] == nums[i - 1] 的判断以跳过重复元素,但不必要对 k 判断,因为 ij 已经不重复了,k 自然不重复

Reverse Nodes In K Group#

地址:

https://leetcode.com/problems/reverse-nodes-in-k-group

难度:

Hard

语言:

go

思路:

链表

日期:

2021-07-19

题解
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

难度:

Medium

语言:

rust

日期:

2021-07-20

题解
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#

地址:

https://leetcode.com/problems/balanced-binary-tree

难度:

Easy

语言:

go

思路:

二叉树 平衡二叉树

日期:

2021-07-20

题解
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

难度:

Easy

语言:

go

思路:

二叉树 二叉搜索树

日期:

2021-07-20

题解
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#

地址:

https://leetcode.com/problems/balance-a-binary-search-tree

难度:

Medium

语言:

go

思路:

二叉树 平衡二叉树

日期:

2021-07-20

题解
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#

地址:

https://leetcode.com/problems/ones-and-zeroes

难度:

Medium

语言:

go

思路:

动态规划

日期:

2021-07-28

题解
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 轮循环残留的值。


脚注

评论

如果你有任何意见,请在此评论。 如果你留下了电子邮箱,我可能会通过 回复你。