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 为 S_a ，从集合中选出一个子集，使其 sum 刚好为 S_a/2 ，剩下的元素组成的子集的 sum 自然也为 S_a/2。因此问题可以转化为一个 01 背包问题 问题，背包容量为 S_a/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(M_left, M_right, M_middle)，分别为左半边数组的最大子序列，右半边数组的最大子序列，或者是从中间算起，横跨左右的最大子序列。

• 当问题规模缩减至 1 的时候， M_left, M_right, M_middle 显然为数组里唯一的元素

• M_middle 的值不可由子问题推导出来，只能在数组 l 和 r 分别逆序和顺序遍历，求各自的从边缘开始的最大子序列，是一个 \(O(n)\) 的操作 -- 这就决定了这个解法比 DP 慢，在每一轮子问题的解决都要遍历一次

• 二分法，所以问题要 \(O(\log_{2}n)\) 个规模的子问题

复杂度为 \(O(n\log n)\) 。

参见

算法复杂度中的O(logN)底数是多少

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 != nil 和 root.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 的值可能转化为 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

地址:

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->0 和 rr 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 的长度

设数组为 N，F[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 长度，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

地址:

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

备注

答案不许重复，i，j 的循环里都有 nums[i] == nums[i - 1] 的判断以跳过重复元素，但不必要对 k 判断，因为 i，j 已经不重复了，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 轮循环残留的值。

---

脚注

[1]

https://twitter.com/mxcl/status/608682016205344768

[2]

https://oi-wiki.org/ds/monotonous-stack/

评论

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