第一章数组part01

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let x = nums.partition_point(|&x| x < target);
        if x == nums.len() { return -1 }
        if nums[x] == target { return x as i32 }
        -1
    }
}
}

手写的二分查找

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid;
            } else {
                return mid as i32
            }
        }
        -1
    }
}
}

学习感想

对区间的定义没有想清楚，区间的定义就是不变量，在操作的过程中保持不变量

在左闭右闭区间的情况下由于right 要 -1，所以要考虑right=0 - 1的情况

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0isize;
        let mut right = nums.len() as isize - 1;
        while left <= right {
            let mid = (left + (right - left) / 2) as usize;
            if nums[mid] < target {
                left = mid as isize + 1
            } else if nums[mid] > target {
                right = mid as isize - 1;
            } else {
                return mid as i32
            }
        }
        -1
    }
}
}

重写

喜欢用左闭右开的区间
match arm不需要用,结尾也是合法的语法
Ordering::Less => { right = mid } 要注意“右开” 又写错了

#![allow(unused)]
fn main() {
struct Solution {}
use std::cmp::Ordering;

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left: usize = 0;
        let mut right: usize = nums.len();
        while left < right {
            let mid: usize = left + (right - left) / 2;
            let mid_num: &i32 = &nums[mid];
            
            match target.cmp(mid_num) {
                Ordering::Equal => { return mid as i32 }
                Ordering::Less => { right = mid }
                Ordering::Greater => { left = mid + 1 }
            }
        }
        -1i32
    }
}

}

使用rust std

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        match nums.binary_search(&target) {
            Ok(idx) => { idx as i32 }
            Err(_) => { -1i32 }
        }
    }
}
}

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let idx: usize = nums.partition_point(|&x| x < target);
        if idx == nums.len() { return -1i32 }
        if nums[idx] != target { return -1i32 }
        idx as i32
    }
}

}

27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100

解题思路

线性算法，找到一个要移除的元素就和最后一个交换

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let n = nums.len();
        if n == 0 { return 0 }
        // [i,j) 表示还需要处理的区间，在这个区间之外的都是无需处理的
        let mut i = 0;
        let mut j = n;
        while i < j {
            if nums[i] == val {
                j -= 1;
                nums[i] = nums[j];
            } else {
                i += 1;
            }
        }
        j as i32
    }
}
}

学习感想

一开始想的时候其实有不变量的思想在里面

写一下双指针的版本

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut a = 0;
        let mut b = 0;
        let n = nums.len();
        while b < n {
            if nums[b] == val { b += 1 }
            else {
                nums[a] = nums[b];
                a += 1;
                b += 1;
            }
        }
        a as i32
    }
}
}

std强大的标准库 Vec上retain方法

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        nums.retain(|&x| x != val);
        nums.len() as i32
    }
}

}

slow指针用来存储需要留下元素应该存放的地址，fast指针是当前处理的元素

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut slow: usize = 0usize;    // the result elem
        let mut fast: usize = 0usize;    // the processing elem
        while fast < nums.len() {
            if nums[fast] == val { fast += 1usize }
            else {
                nums[slow] = nums[fast]; // move elem
                slow += 1usize;
                fast += 1usize;
            }
        }
        slow as i32
    }
}
}

第一章数组part02

977.有序数组的平方 y，209.长度最小的子数组，59.螺旋矩阵II ，总结

建议大家先独立做题，然后看视频讲解，然后看文章讲解，然后在重新做一遍题，把题目AC，最后整理成今日当天的博客

拓展题目可以先不做

详细布置

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/ 文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html 视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

209.长度最小的子数组

题目建议：本题关键在于理解滑动窗口，这个滑动窗口看文字讲解还挺难理解的，建议大家先看视频讲解。拓展题目可以先不做。

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/ 文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html 视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

59.螺旋矩阵II

题目建议：本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/ 文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html 视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

总结

题目建议：希望大家也做一个自己对数组专题的总结

文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html

977. 有序数组的平方

题目描述

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

解题思路

有个很直接的方法是，先取绝对值，然后sort，然后平方

但是这个是nlogn的算法，想要一个n的算法，那很显然需要用到数组有序这个特性。

其实平方是无关紧要的操作。

找到最小的元素，然后向两边双边移动？

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> {
        nums.iter_mut()
            .filter(|&&mut x| x < 0)
            .for_each(|x| *x = -*x);
        let low = nums.iter().enumerate()
            .fold((0, nums[0]), |(idx, v), (jdx, &x)| {
                if x < v { (jdx, x) } else { ( idx, v ) }
            }).0;
        if low == 0 { return nums.iter().map(|x| x**x).collect() }
        let mut left = low as isize - 1;
        let mut right = low + 1;
        let n = nums.len();
        let mut v = Vec::with_capacity(n);
        v.push(nums[low]);
        // left -> 还需要处理的左侧第一个元素
        // right 还需要处理的右侧第一个元素
        while left >= 0 && right < n {
            // 判断两侧
            if nums[left as usize] < nums[right] {
                v.push(nums[left as usize]);
                left -= 1;
            } else {
                v.push(nums[right]);
                right += 1;
            }
        }
        if left < 0 {
            while right < n {
                v.push(nums[right]);
                right += 1;
            }
        } else {
            while left >= 0 {
                v.push(nums[left as usize]);
                left -= 1;
            }
        }
        v.iter().map(|x| x**x).collect()
    }
}
}

写出来了，但是很长，确实定义的每一个变量的明确含义一定要在写之前就很清楚

学习感想

数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

我是从最小数开始构建，确实麻烦，从最大的数开始构建就是一个简单一点的从两侧开始的双指针了。

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut v = Vec::with_capacity(n);
        let mut a = 0;
        let mut b = n as isize - 1;
        while a <= b {
            if nums[a as usize].abs() < nums[b as usize].abs() {
                v.push(nums[b as usize]);
                b -= 1;
            } else {
                v.push(nums[a as usize]);
                a += 1;
            }
        }
        v.iter().map(|x| x**x).rev().collect()
    }
}
}

注意是abs比较，a和b都是闭区间

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut res: Vec<i32> = vec![0i32; nums.len()];
        let mut idx: usize = 0usize;
        let mut left: usize = 0usize;
        let mut right: usize = nums.len() - 1usize;
        while idx < res.len() {
            let left_square: i32 = nums[left].pow(2u32);
            let right_square: i32 = nums[right].pow(2u32);
            use std::cmp::Ordering;
            match left_square.cmp(&right_square) {
                Ordering::Less => {
                    right -= 1usize;
                    res[nums.len() - 1usize - idx] = right_square;
                }
                _ => {
                    left += 1usize;
                    res[nums.len() - 1usize - idx] = left_square;
                }
            }
            idx += 1;
        }
        res
    }
}
}

209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解题思路

哎写出来了但是很长，用双指针维护一个区间，相当于是循环不变量，

有一个观察：就是找到一个可行解后，第二个元素开始的可行解的最后一个元素一定大于或等于当前最后一个元素

所以不断地右侧生长去找到一个可行解，然后左侧缩小去尝试更小的解

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut a = 0;
        let mut b = 0;
        let mut s = 0;
        let mut res = 0;
        while s < target && b < n {
            s += nums[b];b += 1;
        }
        if s < target &&  b == n { return 0 }
        res = b;
        loop {

            while s >= target && a < b {
                s -= nums[a];
                res = res.min(b - a);
                a += 1;
            }
            while s < target && b < n {
                s += nums[b];b += 1;
            }
            if s >= target {
                res = res.min(b - a);
            }
            if b == n && s < target { break }
        }

        res as i32
    }
}
}

学习感想

首先要思考如果用一个for循环，那么应该表示滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入暴力解法的怪圈。

所以只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。

原来是滑动窗口，只用一个变量来表示结束的位置

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = i32::MAX;
        let mut s = 0;
        let mut a = 0;
        for b in 0..n {
            s += nums[b];
            while s >= target {
                res = res.min((b - a + 1) as i32);
                s -= nums[a];
                a += 1;
            }
        }
        if res == i32::MAX {0} else {res as i32}
    }
}

}

在闭包中使用pattern matching来去除变量前边的引用的时候，有时候不要去除多了

    pub fn min_sub_array_len(nums: Vec<i32>) {
        nums.iter().scan(1i32, |&mut st, &x| {
            st += x;
            Some(st)
        });
    }

类似这个时候，st绑定到的就永远都是输入的那个1 到闭包函数内了，起不到修改闭包外的1的效果。

所以这个引用就不要自动匹配掉了，就手动解引用吧

思路：前缀和+双指针

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        // prefix sum
        let pre_sum: Vec<i32> = nums.iter().scan(0i32, |st, &x| {
            *st += x;
            Some(*st)
        }).collect();
        let idx: usize = pre_sum.partition_point(|&x| x < target);
        if idx == nums.len() { return 0i32 }
        let mut res: usize = idx + 1usize;
        let mut right: usize = idx;
        let mut left: usize = 0usize;
        while right < nums.len() {
            while pre_sum[right] - pre_sum[left] >= target {
                left += 1usize;
            }
            let candidate: usize = right - left + 1usize;
            res = std::cmp::min(candidate, res);
            right += 1usize;
        }
        res as i32
    }
}
}

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let mut sum: i32 = 0i32;
        let mut left: usize = 0usize;
        let mut res: usize = usize::MAX;
        for right in 0usize..nums.len() {
            sum += nums[right];
            while sum >= target {
                res = std::cmp::min(res, right - left + 1usize);
                sum -= nums[left];
                left += 1usize;
            }
        }
        match res {
            usize::MAX => 0,
            _ => res as i32,
        }
    }
}
}

59. 螺旋矩阵II

题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

解题思路

好像就是en做写出来了但是很长，就是按照题目的意思进行模拟（迭代），每次迭代填入最外层的一圈

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut v = vec![vec![0; n]; n];
        // idx,idx 左上角的坐标， n 这一行的所有元素个数-1  右上角坐标idx,idx+n
        pub fn f(v: &mut Vec<Vec<i32>>, idx: usize, n: usize, start: i32) -> i32 {
            if n == 0 { v[idx][idx] = start; return start + 1 }
            let mut cur = start;
            for j in 0..n {
                v[idx][idx+j] = cur ; cur += 1;
            }
            for i in 0..n {
                v[idx+i][idx+n] = cur ; cur += 1;
            }
            for j in 0..n {
                v[idx+n][idx+n-j] = cur ; cur += 1;
            }
            for i in 0..n {
                v[idx+n-i][idx] = cur ; cur += 1;
            }
            cur
        }
        let mut start = 1;
        let mut x = n as isize - 1;
        let mut i = 0;
        while x >= 0 {
            start = f(&mut v, i, x as usize, start);
            i += 1;
            x -= 2;
        }
        v
    }
}

}

学习感想

本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

坚持循环不变量原则

确实，定义一定要非常明确，明确了定义之后就牢牢地实现这个定义

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

然后好像就是我这种模拟的做法

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut m: Vec<Vec<i32>> = vec![vec![0i32; n as usize]; n as usize];
        let mut current: i32 = 1i32;
        for i in 0usize .. (n as usize + 1usize) / 2usize {
            Self::f(&mut m, i, &mut current);
        }
        m
    }

    pub fn f(m: &mut Vec<Vec<i32>>, start: usize, start_num: &mut i32) {
        let width: usize = m.len() - start * 2usize - 1usize;
        if width == 0 { m[start][start] = *start_num; return; }
        for i in 0..width {
            m[start][start + i] = *start_num;
            *start_num += 1i32;
        }
        for j in 0..width {
            m[start + j][start + width] = *start_num;
            *start_num += 1i32;
        }
        for i in 0..width {
            m[start + width][start + width - i] = *start_num;
            *start_num += 1i32;
        }
        for j in 0..width {
            m[start + width - j][start] = *start_num;
            *start_num += 1i32;
        }
    }
}


}

第二章链表part01

day1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG 今日任务

● 链表理论基础 ● 203.移除链表元素 ● 707.设计链表 ● 206.反转链表

详细布置

链表理论基础

建议：了解一下链接基础，以及链表和数组的区别

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

建议：本题最关键是要理解虚拟头结点的使用技巧，这个对链表题目很重要。

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.设计链表

建议：这是一道考察链表综合操作的题目，不算容易，可以练一练使用虚拟头结点

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反转链表

建议先看我的视频讲解，视频讲解中对反转链表需要注意的点讲的很清晰了，看完之后大家的疑惑基本都解决了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

203. 移除链表元素

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

解题思路

链表题，hhhh，不是特别想用rust，不多说，直接操作ownersheip

#![allow(unused)]
fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut head = Some(Box::new(ListNode { val: 0, next: head }));
        let mut a: &mut Option<Box<ListNode>> = &mut head;
        while a.as_deref_mut().unwrap().next.is_some() {
            //         ^  Option<&mut ListNode>
            //    
            let v = a.as_deref_mut().unwrap().next.as_deref().unwrap().val;
            if v == val {
                let mut b = a.as_deref_mut().unwrap().next.take();
                let c = b.as_deref_mut().unwrap().next.take();
                a.as_deref_mut().unwrap().next = c;
            } else {
                let b = &mut a.as_deref_mut().unwrap().next;
                a = b;
            }
        }
        head.unwrap().next
    }
}
}

属实有点恶心了，看着太复杂了，这就是不用take的后果

学习感想

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}


impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut dummyHead = Box::new(ListNode::new(0));
        dummyHead.next = head;
        let mut cur: &mut ListNode = dummyHead.as_mut();
	// 使用take()替换std::men::replace(&mut node.next, None)达到相同的效果，并且更普遍易读
        while let Some(nxt) = cur.next.take() {
            if nxt.val == val {
                cur.next = nxt.next;
            } else {
                cur.next = Some(nxt);
                cur = cur.next.as_mut().unwrap();   // coercion
                //           ^ Option<Box<ListNode>>
                //                    ^ Option<&mut Box<ListNode>>
                //                             ^ &mut Box<ListNode>
                //            deref   coerce ->     & mut ListNode
            }
        }
        dummyHead.next
    }
}
}

向这位老哥学习，使用take，管它用不用，先取下来再说。并且先把option刨了

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

impl Solution {
    pub fn remove_elements(mut head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut res: Option<Box<ListNode>> = None;
        let mut ptr: &mut Option<Box<ListNode>> = &mut res;
        while let Some(mut x) = head {
            head = x.next.take();
            if x.val != val {
                *ptr = Some(x);
                ptr = &mut ptr.as_mut().unwrap().next;
            }
        }
        res
    }
}
}

链表的ownership还是非常容易理清楚的

一个Option不是owner没法直接unwrap，但是as_mut了之后可以随意unwrap，这也是容器穿透

707. 设计链表

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。 void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。 void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

解题思路

#![allow(unused)]
fn main() {
struct MyLinkedList {
    val: i32,
    next: Option<Box<MyLinkedList>>
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyLinkedList {

    fn new() -> Self {
        Self { val: 0, next: None }
    }
    
    fn get(&self, index: i32) -> i32 {
        let mut dummpy = self.next.as_deref();
        let mut cnt = 0;
        while let Some(node) = dummpy {
            if index == cnt { return node.val }
            dummpy = node.next.as_deref();
            cnt += 1;
        }
        -1
    }
    
    fn add_at_head(&mut self, val: i32) {
        self.next = Some(Box::new(
            MyLinkedList {
                val: val, 
                next: self.next.take()
            }
        ));
    }
    
    fn add_at_tail(&mut self, val: i32) {
        let mut dummpy = self;
        while dummpy.next.is_some() {
            dummpy = dummpy.next.as_mut().unwrap();
        }
        dummpy.next = Some(Box::new(
            MyLinkedList {
                val: val, 
                next: None
            }
        ));
    }
    
    fn add_at_index(&mut self, index: i32, val: i32) {
        let mut cnt = 0;
        let mut dummpy = self;
        while dummpy.next.is_some() {
            if cnt == index {
                let nxt = dummpy.next.take();
                dummpy.next = Some(Box::new(
                    MyLinkedList {
                        val: val, 
                        next: nxt
                    }
                ));
                return;
            }
            dummpy = dummpy.next.as_mut().unwrap();
            cnt += 1;
        }
        if cnt == index {
            dummpy.next = Some(Box::new(
                MyLinkedList {
                    val: val, 
                    next: None
                }
            ));
        }
    }
    
    fn delete_at_index(&mut self, index: i32) {
        let mut cnt = 0;
        let mut dummpy = self;
        while dummpy.next.is_some() {
            if cnt == index {
                let nxt = dummpy.next.take().unwrap();
                dummpy.next = nxt.next;
                return;
            }
            dummpy = dummpy.next.as_mut().unwrap();
            cnt += 1;
        }
    }
}
}

学习感想

也没啥好说的，rust只要写出来，基本是对的，没有用take的形式，而是全部去除了option用ref

#![allow(unused)]
fn main() {
struct MyLinkedList {
    head: Option<Box<ListNode>>,
    cnt: i32,
}

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyLinkedList {

    fn new() -> Self {
        Self {
            head: None,
            cnt: 0i32,
        }
    }
    
    fn get(&self, mut index: i32) -> i32 {
        if index >= self.cnt { return -1i32 }
        let mut ptr: & Box<ListNode> = self.head.as_ref().unwrap();
        while index > 0i32 {
            ptr = ptr.next.as_ref().unwrap();
            index -= 1i32;
        }
        ptr.val
    }
    
    fn add_at_head(&mut self, val: i32) {
        self.add_at_index(0i32, val);
    }
    
    fn add_at_tail(&mut self, val: i32) {
        self.add_at_index(self.cnt, val);
    }
    
    fn add_at_index(&mut self, mut index: i32, val: i32) {
        if index > self.cnt { return }
        let mut ptr: &mut Option<Box<ListNode>> = &mut self.head;
        while index > 0i32 {
            ptr = &mut ptr.as_mut().unwrap().next;
            index -= 1i32;
        }
        self.cnt += 1i32;
        *ptr = Some(Box::new(ListNode { val: val, next: ptr.take() }))
    }
    
    fn delete_at_index(&mut self, mut index: i32) {
        if index >= self.cnt { return }
        let mut ptr: &mut Option<Box<ListNode>> = &mut self.head;
        while index > 0i32 {
            ptr = &mut ptr.as_mut().unwrap().next;
            index -= 1i32;
        }
        let nxt: Option<Box<ListNode>> = ptr.take().unwrap().next.take();
        *ptr = nxt;
        self.cnt -= 1i32;
    }
}

}

206. 反转链表

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路

这就很简单了，一边出栈一边入

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}


impl Solution {
    pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode { val: 0, next: None });
        while let Some(mut node) = head {
            let tmp = dummy.next.take();
            let n = node.next.take();
            node.next = tmp;
            dummy.next = Some(node);
            head = n;
        }
        dummy.next
    }
}
}

学习感想

所以我这个算是什么方式

#![allow(unused)]


fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

impl Solution {
    pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut res: Option<Box<ListNode>> = None;
        while let Some(mut x) = head {
            head = x.next.take();
            x.next = res;
            res = Some(x);
        }
        res
    }
}
}

第二章链表part02

● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY ● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG ● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6

今日任务

● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II ● 总结

详细布置

24. 两两交换链表中的节点

用虚拟头结点，这样会方便很多。

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

19.删除链表的倒数第N个节点

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向第N个节点的前一个节点，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

面试题 02.07. 链表相交

本题没有视频讲解，大家注意数值相同，不代表指针相同。

题目链接/文章讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

142.环形链表II

算是链表比较有难度的题目，需要多花点时间理解确定环和找环入口，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

24. 两两交换链表中的节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路

? 还是一边出一边入

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

impl Solution {
    pub fn swap_pairs(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode { val: 0, next: None });
        let mut cdummy = &mut dummy;
        while let Some(mut x) = head.take() {
            if x.next.is_none() {
                cdummy.next = Some(x);
                return dummy.next;
            }
            if let Some(mut y) = x.next.take() {
                head = y.next.take();
                y.next = Some(x);
                cdummy.next = Some(y);
                cdummy = cdummy.next.as_mut().unwrap();
                cdummy = cdummy.next.as_mut().unwrap();
            }
        }
        dummy.next
    }
}

}

学习感想

我发现我做链表逆序两两交换的时候都是直接新建一个存返回链表的dummy头节点，然后按照操作来把节点从原来的链表里取出来插入新的链表中，根本不用想怎么修改指针

19. 删除链表的倒数第 N 个结点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路

之前用dummy 重新构造新的链表来做的

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

impl Solution {
    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(-1);
        while let Some(mut x) = head {
            head = x.next;
            x.next = dummy.next;
            dummy.next = Some(x);
        }
        let mut ptr = &mut dummy;
        for _ in 1..n { ptr = ptr.next.as_deref_mut().unwrap() }
        let drop = ptr.next.take();
        ptr.next = drop?.next.take();
        head = dummy.next.take();
        while let Some(mut x) = head {
            head = x.next;
            x.next = dummy.next;
            dummy.next = Some(x);
        }
        dummy.next
    }
}
}

学习感想

双指针法这道题用safe rust没法写，因为需要同时持有链表的两个引用，并且头部的引用还必须是可变引用，这是没法做到的

#![allow(unused)]

fn main() {
struct Solution {}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        unsafe {
            let dummy = ListNode { val: -1, next: head };
            let mut ptr = &dummy;
            for _ in 0..n { ptr = ptr.next.as_deref()? }
            let mut ptr2 = &dummy as *const ListNode as *mut ListNode;
            while ptr.next.is_some() {
                ptr = ptr.next.as_deref()?;
                ptr2 = (*ptr2).next.as_deref()? as *const ListNode as *mut ListNode;
            }
            let mut rigoff = (*ptr2).next.take()?;
            let nxt = rigoff.next.take();
            (*ptr2).next = nxt;
            dummy.next
        }
    }
}
}

所以这就是我用unsafe的原因

Unsafe Superpowers

To switch to unsafe Rust, use the unsafe keyword and then start a new block that holds the unsafe code. You can take five actions in unsafe Rust that you can’t in safe Rust, which we call unsafe superpowers. Those superpowers include the ability to:

Dereference a raw pointer
Call an unsafe function or method
Access or modify a mutable static variable
Implement an unsafe trait
Access fields of unions

It’s important to understand that unsafe doesn’t turn off the borrow checker or disable any other of Rust’s safety checks: if you use a reference in unsafe code, it will still be checked. The unsafe keyword only gives you access to these five features that are then not checked by the compiler for memory safety. You’ll still get some degree of safety inside of an unsafe block.

面试题 02.07. 链表相交

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

解题思路

这题没有rust选

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        la = 1
        lb = 1
        ptra = headA
        ptrb = headB
        if ptra is None or ptrb is None:
            return None
        while ptra.next != None:
            la += 1
            ptra = ptra.next
        while ptrb.next != None:
            lb += 1
            ptrb = ptrb.next
        if la < lb:
            ptra, ptrb = headB, headA
        else:
            ptra, ptrb = headA, headB

        d = abs(la - lb)
        print(d, la, lb)
        for i in range(d):
            ptra = ptra.next
        for i in range(min(la,lb)):
            if ptra is ptrb:
                return ptra
            else:
                ptra = ptra.next
                ptrb = ptrb.next
        return None

学习感想

看解析之前没有想到这个做法

重点是尾部对其，

142.环形链表II

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

解题思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast != None and fast.next != None and fast.next.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                # found in loop
                newindex = head
                while not newindex is fast:
                    fast = fast.next
                    newindex = newindex.next
                return fast
        return None

学习感想

一刷数学题不会，快慢指针会的，但是数学推导没有想到

休息日

休息日我用来补进度了

第三章哈希表part01

今日任务

● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和

详细布置

哈希表理论基础

建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。

什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。这句话很重要，大家在做哈希表题目都要思考这句话。

文章讲解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

242.有效的字母异位词

建议：这道题目，大家可以感受到数组用来做哈希表给我们带来的遍历之处。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

349. 两个数组的交集

建议：本题就开始考虑什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。尝试去使用set。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

202. 快乐数

建议：这道题目也是set的应用，其实和上一题差不多，就是套在快乐数一个壳子

题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

1. 两数之和

建议：本题虽然是力扣第一题，但是还是挺难的，也是代码随想录中数组，set之后，使用map解决哈希问题的第一题。

建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

242. 有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        use std::collections::HashMap;
        if s.len() != t.len() { return false }
        let mut freq: HashMap<char, usize> = HashMap::new();
        for c in s.chars() {
            *freq.entry(c).or_default() += 1;
        }
        for c in t.chars() {
            let entry = freq.entry(c).or_default();
            if *entry == 0 { return false }
            *entry -= 1;
        }
        true
    }
}

}

学习感想

Rust 一个char的大小永远就是4字节，在&str里，永远都是utf8编码的，但是占用的长度可能是1-4个字节

Sequences: Vec, VecDeque, LinkedList Maps: HashMap, BTreeMap Sets: HashSet, BTreeSet Misc: BinaryHeap

Borrow 的一个常见应用场景是 HashMap 之类的容器类型。在 HashMap 中，可以用 Borrow 来允许使用不同但兼容的类型进行查找或删除操作。比如，HashMap<String, V> 可以接受 &str 作为键，因为 String 实现了 Borrow。

impl 块在 Rust 中是全局可见的，因为它定义了类型的行为，Rust 需要确保这些行为在整个程序中保持一致。 use 语句只在局部可见，这样可以避免命名冲突，并且保持模块系统的封装性和灵活性。

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        use std::collections::HashMap;
        let mut m: HashMap<char, usize> = HashMap::new();
        for ch in s.chars() {
            m.entry(ch).and_modify(|x| *x += 1usize).or_insert(1usize);
        }
        for ch in t.chars() {
            use std::collections::hash_map::Entry;
            match m.entry(ch) {
                Entry::Occupied(mut o) => {
                    let x: &mut usize = o.get_mut();
                    *x -= 1usize;
                    if *x == 0usize { o.remove(); }
                },
                Entry::Vacant(_) => { return false },
            }
        }
        m.len() == 0
    }
}
}

349. 两个数组的交集

题目描述

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        use std::collections::HashSet;
        let mut set1 = HashSet::new();
        let mut set2 = HashSet::new();
        for i in nums1 {
            set1.insert(i);
        }
        for i in nums2 {
            set2.insert(i);
        }
        set1.intersection(&set2).copied().collect()
    }
}

}

学习感想

优雅

#![allow(unused)]
fn main() {
struct Solution {}
use std::iter::FromIterator;
impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        use std::collections::HashSet;
        let set1: HashSet<i32> = HashSet::from_iter(nums1);
        let set2: HashSet<i32> = HashSet::from_iter(nums2);
        // set1.intersection(&set2).map(|&x| x).collect()
        set1.intersection(&set2).copied().collect()
    }
}

}

202. 快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果这个过程结果为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 true ；不是，则返回 false 。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn is_happy(mut n: i32) -> bool {
        use std::collections::HashSet;
        let mut set = HashSet::new();
        set.insert(n);
        fn f(mut n: i32) -> i32 {
            let mut res = 0;
            while n != 0 {
                let x = n % 10;
                res += x * x;
                n /= 10;
            }
            res
        }
        loop {
            n = f(n);
            if n == 1 { return true }
            if set.contains(&n) { return false }
            set.insert(n);
        }
    }
}
}

学习感想

一下子不知道怎么做，但是把false的例子弄明白就知道了

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn is_happy(mut n: i32) -> bool {
        use std::collections::HashSet;
        let mut set: HashSet<i32> = HashSet::from([n]);
        loop {
            let mut new = 0i32;
            while n != 0i32 {
                new += (n % 10i32).pow(2u32);
                n /= 10i32;
            }
            if new == 1i32 { break true }
            if set.contains(&new) { break false }
            set.insert(new);
            n = new;
        }
    }
}
}

1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}


impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let mut map: HashMap<i32, i32> = HashMap::new();
        for (idx, i) in nums.iter().enumerate() {
            if map.contains_key(&(target - i)) {
                return vec![*map.get(&(target - i)).unwrap(), idx as i32]
            } else {
                map.insert(*i, idx as i32);
            }
        }
        todo!()
    }
}
}

学习感想

第三章哈希表part02

今日任务

● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和 ● 总结

详细布置

454. 四数相加II

建议：本题是使用map 巧妙解决的问题，好好体会一下哈希法如何提高程序执行效率，降低时间复杂度，当然使用哈希法会提高空间复杂度，但一般来说我们都是舍空间换时间，工业开发也是这样。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

383. 赎金信

建议：本题和 242.有效的字母异位词是一个思路，算是拓展题

题目链接/文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

15. 三数之和

建议：本题虽然和两数之和很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下双指针法的思路，文章中讲解的，没问题哈希法很麻烦。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

18. 四数之和

建议：要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。本题思路整体和三数之和一样的，都是双指针，但写的时候有很多小细节，需要注意，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

454. 四数相加 II

题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解题思路

首先是一种愚蠢的做法，以为On2就是两个for循环

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let n = nums1.len();
        use std::collections::HashMap;
        let mut res = 0;
        let mut map3: HashMap<i32, usize> = HashMap::new();
        let mut map4: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            *map3.entry(nums3[i]).or_default() += 1;
            *map4.entry(nums4[i]).or_default() += 1;
        }
        for i in 0..n {
            for j in 0..n {
                let mut target = - nums1[i] - nums2[j];
                for (&a, &b) in map3.iter() {
                    let d = target - a;
                    if map4.contains_key(&d) {
                        res += b * map4.get(&d).unwrap();
                    }
                }
            }
        }
        res as i32
    }
}
}

这里面白白浪费了i和j的和

学习感想

#![allow(unused)]


fn main() {
struct Solution {}


impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let n = nums1.len();
        use std::collections::HashMap;
        let mut res = 0;
        let mut map: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            for j in 0..n {
                let target = nums1[i] + nums2[j];
                *map.entry(target).or_default() += 1;
            }
        }
        for i in 0..n {
            for j in 0..n {
                let target = - nums3[i] - nums4[j];
                if map.contains_key(&target) {
                    res += map.get(&target).unwrap();
                }
            }
        }
        res as i32
    }
}
}

地一下子还是没有想到要用hashmap做，感觉可能是双指针

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut map: HashMap<i32, usize> = HashMap::new();
        for a in nums1 {
            for &b in nums2.iter() {
                map.entry(a + b)
                    .and_modify(|x| *x += 1usize)
                    .or_insert(1usize);
            }
        }
        let mut res: usize = 0usize;
        for c in nums3 {
            for &d in nums4.iter() {
                map.entry(0i32 - c - d)
                    .and_modify(|&mut x| res += x);
            }
        }
        res as i32
    }
}
}

383. 赎金信

题目描述

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        use std::collections::HashMap;
        let mut map: HashMap<char, usize> = HashMap::new();
        for c in magazine.chars() {
            *map.entry(c).or_default() += 1;
        }
        for c in ransom_note.chars() {
            if ! map.contains_key(&c) { return false }
            let a = map.get_mut(&c).unwrap();
            *a -= 1;
            if *a == 0 { map.remove(&c); }
        }
        true
    }
}
}

学习感想

普通hashmap 的使用

15. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn three_sum(mut v: Vec<i32>) -> Vec<Vec<i32>> {
        v.sort();
        let mut ans = vec![];
        for i in 0..v.len() - 2 {
            if i > 0 && v[i] == v[i - 1] {
                continue;
            }
            let mut j = i + 1;
            let mut k = v.len() - 1;
            while j < k {
                if v[j] + v[k] + v[i] == 0 {
                    ans.push(vec![v[i], v[j], v[k]]);
                    j += 1;
                    while j < k && v[j] == v[j - 1] {
                        j += 1
                    }
                    k -= 1;
                    while j < k && v[k] == v[k + 1] {
                        k -= 1
                    }
                } else if v[j] + v[k] < -v[i] {
                    j += 1
                } else {
                    k -= 1
                }
            }
        }
        ans
    }
}
}

双指针做法还是想不到

学习感想

想不到用双指针

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res: Vec<Vec<i32>> = Vec::new();
        for i in 0..nums.len() - 2usize {
            if i > 0 && nums[i] == nums[i-1usize] { continue }
            let mut left: usize = i + 1usize;
            let mut right: usize = nums.len() - 1usize;
            use std::cmp::Ordering;
            while left < right {
                let s: i32 = nums[i] + nums[left] + nums[right];
                match s.cmp(&0i32) {
                    Ordering::Less => left += 1usize,
                    Ordering::Greater => right -= 1usize,
                    _ => {
                        let to_push: Vec<i32> = vec![nums[i], nums[left], nums[right]];
                        if res.is_empty() || Some(&to_push) != res.last() {
                            res.push(to_push);
                        }
                        left += 1usize;
                        right -= 1usize;
                    }
                }
            }
        }
        res
    }
}

}

18. 四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按任意顺序返回答案。

解题思路

有两个坑：

首先是n < 4的情况是存在的
其次四个数的加和可以超过i32的最大值

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum(mut v: Vec<i32>, t: i32) -> Vec<Vec<i32>> {
        v.sort();
        let n = v.len();
        let mut res = vec![];
        if n < 4 { return res }
        for i in 0..n-3 {
            if i > 0 && v[i] == v[i-1] { continue }
            for l in (i+3..n).rev() {
                if l < n - 1 && v[l] == v[l+1] { continue }
                let mut j = i + 1;
                let mut k = l - 1;
                while j < k {
                    if v[i] as isize + v[j] as isize + v[k] as isize + v[l] as isize == t as isize {
                        res.push(vec![v[i], v[j], v[k], v[l]]);
                        j += 1;
                        while j < k && v[j] == v[j-1] { j += 1 }
                        k -= 1;
                        while j < k && v[k] == v[k+1] { k -= 1 }
                    } else if (v[i] as isize + v[j] as isize + v[k] as isize + v[l] as isize) < t as isize {
                        j += 1;
                    } else {
                        k -= 1;
                    }
                }
            }
        }
        res
    }
}
}

学习感想

第四章字符串part01

今日任务

● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串

详细布置

344.反转字符串

建议：本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下平时刷题什么时候用库函数，什么时候不用库函数

题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

541. 反转字符串II

建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

剑指Offer 05.替换空格

建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。题目链接/文章讲解：https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html

151.翻转字符串里的单词

建议：这道题目基本把刚刚做过的字符串操作都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

剑指Offer58-II.左旋转字符串

建议：题解中的解法如果没接触过的话，应该会想不到

题目链接/文章讲解：https://programmercarl.com/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

344. 反转字符串

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn reverse_string(s: &mut Vec<char>) {
        let n = s.len();
        for i in 0..n/2 {
            let tmp = s[i];
            s[i] = s[n-1-i];
            s[n-1-i] = tmp;
        }
    }
}
}

学习感想

541. 反转字符串 II

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

解题思路

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn reverse_str(s: String, k: i32) -> String {
        let s = s.chars().collect::<Vec<char>>();
        let mut v: Vec<char> = vec![];
        let mut rev = true;
        for i in s.chunks(k as usize) {
            if rev {
                v.extend(i.iter().rev());
            } else {
                v.extend(i);
            }
            rev = !rev;
        }
        v.iter().collect()
    }
}
}

type system好优雅，真的优雅，真的好优雅，

slice是实现std::iter::DoubleEndedIterator的，所以可以reverse，iter返回的不是不同的迭代器而是std::slice::Iter

Vec是实现Extend trait的，所以可以用slice的copy_from_slice实现extend

学习感想

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn reverse_str(s: String, k: i32) -> String {
        let mut s: Vec<u8> = s.bytes().collect();
        let mut i: usize = 0usize;
        loop {
            let start: usize = i * k as usize * 2usize;
            if start >= s.len() { break }
            i += 1usize;
            let end: usize = std::cmp::min(start + k as usize, s.len());
            s[start .. end].reverse()
        }
        String::from_utf8(s).unwrap()
    }
}
}

剑指 Offer 05. 替换空格

题目描述

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

解题思路

一开始没有想到用双指针

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn replace_space(s: String) -> String {
        let mut s = s.chars().collect::<Vec<char>>();
        let cnt = s.iter().filter(|&&x| x == ' ').count();
        let n = s.len();
        s.resize(n + 2 * cnt, ' ');
        let mut tail = s.len() - 1;
        let mut head = n as isize - 1;
        while head >= 0 {
            if s[head as usize] == ' ' {
                s[tail] = '0';
                s[tail - 1] = '2';
                s[tail - 2] = '%';
                tail -= 3;
            } else {
                s[tail] = s[head as usize];
                tail -= 1;
            }
            head -= 1;
        }
        s.iter().collect()
    }
}
}

学习感想

151. 反转字符串中的单词

题目描述

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路

不能用库函数自己写的话还是有点烦，但是不难

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    // O(1) space O(n) time
    pub fn reverse_words(s: String) -> String {
        let mut v: Vec<char> = vec![];
        for c in s.chars().rev() {
            if c == ' ' {
                let a = v.last();
                if a.is_none() { continue }
                if *a.unwrap() == ' ' { continue }
            }
            v.push(c);
        }
        if v[v.len() - 1] == ' ' { v.pop(); }
        // reverse each word
        let mut start = 0;
        while start < v.len() {
            let mut end = start + 1;
            while end < v.len() && v[end] != ' ' { end += 1 }
            Self::reverse(&mut v[start..end]);
            start = end + 1;
        }
        v.iter().collect()
    }

    pub fn reverse(s: &mut [char]) {
        let n = s.len();
        for i in 0..n/2 {
            let tmp = s[i];
            s[i] = s[n-1-i];
            s[n-1-i] = tmp;
        }
    }
}
}

学习感想

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.split_ascii_whitespace().rev().collect::<Vec<&str>>().join(" ")
        //  ^ String -> &str
        //                   ^ iter  Target=&str           ^ Vec<&str>
    }
}
}

剑指 Offer 58 - II. 左旋转字符串

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

解题思路

想不到的思路

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn reverse_left_words(s: String, n: i32) -> String {
        let mut v: Vec<char> = s.chars().collect();
        Self::reverse2(&mut v[..n as usize]);
        Self::reverse2(&mut v[n as usize..]);
        Self::reverse2(&mut v[..]);
        v.iter().collect()
    }
    
    pub fn reverse2(s: &mut [char]) {
        let n = s.len();
        for i in 0..n/2 {
            let tmp = s[i];
            s[i] = s[n-1-i];
            s[n-1-i] = tmp;
        }
    }
}
}

学习感想

第四章字符串part02

今日任务

●28. 实现 strStr() ●459.重复的子字符串 ●字符串总结 ●双指针回顾

详细布置

28. 实现 strStr() （本题可以跳过）

因为KMP算法很难，大家别奢求一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会好懂很多。

或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。

因为大家算法能力还没到，细扣很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事，等自己有算法基础和思维了，在看多看几遍视频，慢慢就理解了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

459.重复的子字符串（本题可以跳过）

本题算是KMP算法的一个应用，不过对KMP了解不够熟练的话，理解本题就难很多。我的建议是 KMP和本题，一刷的时候，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

字符串总结

比较简单，大家读一遍就行

题目链接/文章讲解：https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html

双指针回顾

此时我们已经做过10到双指针的题目了，来一起回顾一下，大家自己也总结一下双指针的心得

文章讲解：https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html

28. 找出字符串中第一个匹配项的下标

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

解题思路

KMP 对我来说太烧脑了，不得不写点笔记

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

因为前缀表要求的就是相同前后缀的长度

定义两个指针i和j

j指向前缀末尾位置(不包含)
i指向后缀末尾位置(包含)

next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 对当前字符串，j指向上一个字符串的最大前后缀的位置
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j ++ ;
        }
        next[i] = j; // 赋值
    }
}

举例

     j
 aabaabaaf
         i
 012345678
  0 01234

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let n = needle.len();
        let mut next = vec![0; n];
        let hay = haystack.chars().collect::<Vec<char>>();
        let s = needle.chars().collect::<Vec<char>>();
        let mut j = 0;
        for i in 1..n {
            while j >= 1 && s[i] != s[j] {
                j = next[j - 1];
            }
            if s[i] == s[j] {
                j += 1;
            }
            next[i] = j;    // next 表示以i结尾的字符串最大前后缀长度
        }
        // dbg!(&next);
        // build next ok
        if n == 0 { return 0 }
        j = 0;
        for i in 0..hay.len() {
            // dbg!(i, j);
            while j >= 1 && hay[i] != s[j] {
                j = next[j - 1];
            }
            if hay[i] == s[j] {
                j += 1;
            }
            if j == n {
                return (i + 1 - n) as i32
            }
        }
        -1
    }
}
}

学习感想

还得学习复习

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        if let Some(x) = haystack.find(&needle) {
            x as i32
        } else {
            -1i32
        }
    }
}

}

459. 重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

解题思路

例子

abcabcabcabc
000123456789

abaaba
001123

abacabacabac
001012345678

abac
0010

abcabc
000123

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let n = s.len();
        let mut next = vec![0; n];
        let s = s.chars().collect::<Vec<char>>();
        let mut j = 0;
        for i in 1..n {
            while j >= 1 && s[i] != s[j] {
                j = next[j - 1];
            }
            if s[i] == s[j] {
                j += 1;
            }
            next[i] = j;    // next 表示以i结尾的字符串最大前后缀长度
        }
        let a = *next.last().unwrap();
        if a == 0 { return false }
        let b = n - a;
        if n % b != 0 { return false }
        else { true }
    }
}

}

学习感想

什么时候该用KMP很懵

next 数组 -- 前缀表内容是什么？？next[i] 记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

前缀表是用来回退的，它记录了模式串P与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

记住例子

abcdabcd
00001234

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let s: Vec<u8> = s.bytes().collect();
        // next[i] -> max length of common prefix & suffix of string s[0..=i]
        let mut next: Vec<usize> = vec![0usize; s.len()];
        let mut left: usize = 0usize;   // the current max length of common pre/suf-fix
        for right in 1usize .. next.len() { // calculate each next[right]
            while left > 1usize && s[right] != s[left] {
                left = next[left - 1usize];
            }
            if s[right] == s[left] {
                left += 1usize;
            }
            next[right] = left;
        }
        let x: usize = s.len() - *next.last().unwrap();
        match s.len() % x {
            0 => true,
            _ => false,
        }
    }
}
}

第五章栈与队列part01

今日任务： ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈理论基础

了解一下栈与队列的内部实现机智，文中是以C++为例讲解的。

文章讲解：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

232.用栈实现队列

大家可以先看视频，了解一下模拟的过程，然后写代码会轻松很多。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

225. 用队列实现栈

可以大家惯性思维，以为还要两个队列来模拟栈，其实只用一个队列就可以模拟栈了。

建议大家掌握一个队列的方法，更简单一些，可以先看视频讲解

题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

232. 用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

解题思路

#![allow(unused)]


fn main() {
struct MyQueue {
    is: Vec<i32>,
    os: Vec<i32>,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyQueue {

    fn new() -> Self {
        Self { is: vec![], os: vec![] }
    }

    fn o2i(&mut self) {
        while let Some(i) = self.os.pop() {
            self.is.push(i);
        }
    }

    fn i2o(&mut self) {
        while let Some(i) = self.is.pop() {
            self.os.push(i);
        }
    }
    
    fn push(&mut self, x: i32) {
        self.o2i();
        self.is.push(x);
    }
    
    fn pop(&mut self) -> i32 {
        self.i2o();
        self.os.pop().unwrap()
    }
    
    fn peek(&mut self) -> i32 {
        self.i2o();
        self.os.last().copied().unwrap()
    }
    
    fn empty(&self) -> bool {
        self.is.is_empty() && self.os.is_empty()
    }
}
}

学习感想

225. 用队列实现栈

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

解题思路

#![allow(unused)]

fn main() {
struct MyStack {
    q: std::collections::VecDeque<i32>,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyStack {

    fn new() -> Self {
        Self { q: std::collections::VecDeque::new() }
    }
    
    fn push(&mut self, x: i32) {
        self.q.push_back(x);
    }
    
    fn pop(&mut self) -> i32 {
        let n = self.q.len();
        for _ in 1..n {
            let x = self.q.pop_front().unwrap();
            self.q.push_back(x);
        }
        self.q.pop_front().unwrap()
    }
    
    fn top(&mut self) -> i32 {
        let n = self.q.len();
        for _ in 1..n {
            let x = self.q.pop_front().unwrap();
            self.q.push_back(x);
        }
        let x = self.q.pop_front().unwrap();
        self.q.push_back(x);
        return x;
    }
    
    fn empty(&self) -> bool {
        self.q.is_empty()
    }
}

}

学习感想

第五章栈与队列part02

今日内容：

● 20. 有效的括号 ● 1047. 删除字符串中的所有相邻重复项 ● 150. 逆波兰表达式求值

详细布置

20. 有效的括号

讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。

大家先自己思考一下有哪些不匹配的场景，在看视频我讲的都有哪些场景，落实到代码其实就容易很多了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

1047. 删除字符串中的所有相邻重复项

栈的经典应用。

要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了遍历数组当前元素时候，前一个元素是什么。

题目链接/文章讲解/视频讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

150. 逆波兰表达式求值

本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题

题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

20. 有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut v = vec![]; // only }])
        for c in s.chars() {
            if c == '(' || c == '[' || c == '{' {
                v.push(Self::mutate(c));
            } else {
                if let Some(&x) = v.last() {
                    if x == c { v.pop(); }
                    else { return false }
                } else {
                    return false
                }
            }
        }
        v.is_empty()
    }
    fn mutate(x: char) -> char {
        if x == '(' { return ')' }
        else if x == '[' { return ']' }
        else {return '}'}
    }
}
}

学习感想

#![allow(unused)]

fn main() {
struct Solution {}
impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();
        for c in s.chars() {
            if ['{', '(', '['].contains(&c) {
                stack.push(c);
            } else {
                if let Some(x) = stack.pop() {
                    if x == '{' && c != '}' { return false }
                    else if x == '(' && c != ')' { return false }
                    else if x == '[' && c != ']' { return false }
                } else {
                    return false
                }
            }
        }
        stack.is_empty()
    }
}

}

1047. 删除字符串中的所有相邻重复项

题目描述

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut v = vec![];
        for c in s.chars() {
            if let Some(&x) = v.last() {
                if x == c { v.pop(); }
                else { v.push(c) }
            } else { v.push(c) }
        }
        v.iter().collect()
    }
}
}

学习感想

150. 逆波兰表达式求值

题目描述

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。每个操作数（运算对象）都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位整数表示

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn eval_rpn(tokens: Vec<String>) -> i32 {
        let mut v = vec![];
        for s in tokens {
            let a = vec!["+","-","*","/"];
            if a.contains(&&s[..]) {
                let x = v.pop().unwrap();
                let y = v.pop().unwrap();
                match &s[..] {
                    "+" => {v.push(x+y)},
                    "-" => {v.push(y-x)},
                    "*" => {v.push(y*x)},
                    "/" => {v.push(y/x)},
                    _ => {},
                }
            } else {
                v.push(s.parse::<i32>().unwrap());
            }
        }
        v.pop().unwrap()
    }
}
}

学习感想

休息日

小红书笔试薄砂我

第五章栈与队列part03

今日内容：

● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 ● 总结

详细布置

239. 滑动窗口最大值（一刷至少需要理解思路）

之前讲的都是栈的应用，这次该是队列的应用了。

本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

347.前 K 个高频元素（一刷至少需要理解思路）

大/小顶堆的应用，在C++中就是优先级队列

本题是大数据中取前k值的经典思路，了解想法之后，不算难。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

总结

栈与队列做一个总结吧，加油

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html

239. 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn max_sliding_window(v: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = v.len();
        let mut res = vec![];
        let mut q = std::collections::VecDeque::new();
        for i in 0..n {
            if i >= k && v[i - k] == q[0] {
                q.pop_front();
            }
            // add last
            while let Some(&x) = q.back() {
                if x < v[i] { q.pop_back(); }
                else { break }
            }
            q.push_back(v[i]);
            if i >= k - 1 {
                res.push(q[0]);
            }
        }
        res
    }
}
}

学习感想

一开始确实以为大顶堆就行了，其实要用单调栈，之前也有做过单调栈的题目

单调队列是不能够删除一个指定的元素的，单调栈里维护需要的最大值

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::VecDeque;
        let mut v: VecDeque<i32> = VecDeque::new();
        let k: usize = k as usize;
        let mut res: Vec<i32> = vec![];
        for idx in 0 .. nums.len() {
            if idx >= k  {
                let to_delete: i32 = nums[idx - k];
                if to_delete == v[0] { v.pop_front(); }
            }
            let cur: i32 = nums[idx];
            while let Some(&bck) = v.back() {
                if bck < cur {
                    v.pop_back();
                } else { break }
            }
            v.push_back(cur);
            if idx >= k - 1 { res.push(v[0]); }
        }
        res
    }
}
}

347. 前 K 个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
#[derive(PartialEq, Eq)]
struct Y { a: i32, b: usize, }
type Z = Y;
use std::cmp::Ordering;
impl PartialOrd<Z>for Z{fn partial_cmp(&self,o:&Z)->Option<Ordering>{Some(self.cmp(o))}}
impl Ord for Z{fn cmp(&self,o:&Z)->Ordering{o.b.cmp(&self.b)}}
impl Solution {
    pub fn top_k_frequent(v: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::HashMap;
        use std::collections::BinaryHeap;
        let mut m: HashMap<i32, usize> = HashMap::new();
        let mut q: BinaryHeap<Z> = BinaryHeap::new();
        for i in v {
            *m.entry(i).or_default() += 1;
        }
        for (a, b) in m {
            q.push(Z {a:a, b:b});
            if q.len() > k as usize { q.pop(); }
        }
        let mut res = vec![];
        for i in q {
            res.push(i.a);
        }
        res
    }
}
}

学习感想

map+小顶堆

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::{HashMap, BinaryHeap};
        let mut map: HashMap<i32, usize> = HashMap::new();
        nums.iter().for_each(|&i| {
            map.entry(i).and_modify(|x| *x += 1usize).or_default();
        });
        let mut res: Vec<i32> = Vec::new();
        let mut pq: BinaryHeap<(usize, i32)> = BinaryHeap::new();
        for (k, v) in map {
            pq.push((v, k));
        }
        (0i32 .. k) .for_each(|_| {
            res.push(pq.pop().unwrap().1);
        });
        res
    }
}


}

第六章二叉树part01

今日内容：

● 理论基础 ● 递归遍历
● 迭代遍历 ● 统一迭代

详细布置

理论基础

需要了解二叉树的种类，存储方式，遍历方式以及二叉树的定义

文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

递归遍历（必须掌握）

二叉树的三种递归遍历掌握其规律后，其实很简单

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

迭代遍历（基础不好的录友，迭代法可以放过）

题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html

统一迭代（基础不好的录友，迭代法可以放过）

这是统一迭代法的写法，如果学有余力，可以掌握一下

题目链接/文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html

144. 二叉树的前序遍历

题目描述

解题思路


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res ;
        traverse(root, res);
        return res ;
    }

    void traverse(TreeNode* root, vector<int>& vec) {
        if (root == NULL) return ;
        vec.push_back(root->val);
        traverse(root->left, vec);
        traverse(root->right, vec);
    }
};

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中

递归的实质就是迭代

统一格式法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res ;
        vector<TreeNode *> s ;
        if (root != NULL) s.push_back(root);
        while (!s.empty()) {
            TreeNode* last = s.back();
            s.pop_back();
            if (last == NULL) {
                TreeNode* last = s.back();
                s.pop_back();
                res.push_back(last->val);
            } else {
                s.push_back(last);
                s.push_back(NULL);
                if (last->right) s.push_back(last->right);
                if (last->left) s.push_back(last->left);
            }
        }
        return res ;
    }
};

学习感想

为什么当时没有用rust做呢

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        if let Some(r) = root {
            // use std::ops::DerefMut;
            // let mut ref_node: std::cell::RefMut<TreeNode> = r.borrow_mut();
            // let node: &mut TreeNode = &mut ref_node;
            let mut res: Vec<i32> = vec![r.borrow().val];
            res.append(&mut Self::preorder_traversal(r.borrow_mut().left.take()));
            res.append(&mut Self::preorder_traversal(r.borrow_mut().right.take()));
            res
        } else {
            vec![]
        }
    }
}

第六章二叉树 part02

今日内容：

● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉树 2

详细布置

层序遍历

看完本篇可以一口气刷十道题，试一试，层序遍历并不难，大家可以很快刷了十道题。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

226.翻转二叉树（优先掌握递归）

这道题目一些做过的同学理解的也不够深入，建议大家先看我的视频讲解，无论做过没做过，都会有很大收获。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

101. 对称二叉树（优先掌握递归）

先看视频讲解，会更容易一些。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

102. 二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

解题思路

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>  res ; 
        if (root == NULL) return res ;
        deque<TreeNode*> v;
        v.push_back(root);
        while (!v.empty()) {
            int size = v.size();
            vector<int> level_res ;
            for (int i = 0; i < size; i ++) {
                TreeNode * ptr = v.front();
                v.pop_front();
                level_res.push_back(ptr->val);
                if (ptr->left) v.push_back(ptr->left);
                if (ptr->right) v.push_back(ptr->right);
            }
            res.push_back(level_res) ;
        }
        return res;
    }
};

学习感想

107. 二叉树的层序遍历 II

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>  res ; 
        if (root == NULL) return res ;
        deque<TreeNode*> v;
        v.push_back(root);
        while (!v.empty()) {
            int size = v.size();
            vector<int> level_res ;
            for (int i = 0; i < size; i ++) {
                TreeNode * ptr = v.front();
                v.pop_front();
                level_res.push_back(ptr->val);
                if (ptr->left) v.push_back(ptr->left);
                if (ptr->right) v.push_back(ptr->right);
            }
            res.push_back(level_res) ;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

199. 二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res ; 
        if (root == NULL) return res ;
        deque<TreeNode*> v;
        v.push_back(root);
        while (!v.empty()) {
            int size = v.size();
            vector<int> level_res ;
            for (int i = 0; i < size; i ++) {
                TreeNode * ptr = v.front();
                v.pop_front();
                level_res.push_back(ptr->val);
                if (ptr->left) v.push_back(ptr->left);
                if (ptr->right) v.push_back(ptr->right);
            }
            res.push_back(level_res.back());
        }
        return res;
    }
};

637. 二叉树的层平均值

226. 翻转二叉树

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        traverse(root);
        return root;
    }
    void traverse(TreeNode* root) {
        if (root == NULL) return ;
        swap(root->left, root->right);
        traverse(root->left);
        traverse(root->right);
    }
};

学习感想

101. 对称二叉树

题目描述

解题思路

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def f(self,a,b):
        if a == None and b != None:
            return False
        elif a == None and b == None:
            return True
        elif a != None and b == None:
            return False
        else:
            if a.val != b.val:
                return False
            else:
                res1 = self.f(a.left, b.right)
                res2 = self.f(a.right, b.left)
                return res1 and res2
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        else:
            return self.f(root.left, root.right)

学习感想

第六章二叉树part03

今日内容：

● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树的最小深度 ● 222.完全二叉树的节点个数

迭代法，大家可以直接过，二刷有精力的时候再去掌握迭代法。

详细布置

104.二叉树的最大深度（优先掌握递归）

什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。

大家要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

111.二叉树的最小深度（优先掌握递归）

先看视频讲解，和最大深度看似差不多，其实差距还挺大，有坑。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

222.完全二叉树的节点个数（优先掌握递归）

需要了解，普通二叉树怎么求，完全二叉树又怎么求

题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

104. 二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

解题思路

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        else {
            int l = maxDepth(root->left);
            int r = maxDepth(root->right);
            int m = max(l, r);
            return m + 1;
        }
    }
};

学习感想

递归

111. 二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

解题思路

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return 1;
        if (root->left == NULL) return minDepth(root->right) + 1;
        if (root->right == NULL) return minDepth(root->left) + 1;
        else return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

学习感想

写到这里我根本没有想明白为什么这个是对的。

222. 完全二叉树的节点个数

题目描述

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

解题思路

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        int leftcnt = 0;
        int rightcnt = 0;
        TreeNode* ptr = root;
        while (ptr ->left != NULL) {
            ptr = ptr->left;
            leftcnt ++ ;
        }
        ptr = root;
        while (ptr ->right != NULL) {
            ptr = ptr->right;
            leftcnt ++ ;
        }
        if (leftcnt == rightcnt) {
            return (2 << leftcnt) - 1;
        }
        else {
            return countNodes(root->left) + countNodes(root->right) + 1;
        }

    }
};

学习感想

时间复杂度为Logn

第六章二叉树part04

今日内容：

● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和

详细布置

迭代法，大家可以直接过，二刷有精力的时候再去掌握迭代法。

110.平衡二叉树（优先掌握递归）

再一次涉及到，什么是高度，什么是深度，可以巩固一下。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html

257. 二叉树的所有路径（优先掌握递归）

这是大家第一次接触到回溯的过程，我在视频里重点讲解了本题为什么要有回溯，已经回溯的过程。

如果对回溯似懂非懂，没关系，可以先有个印象。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html

404.左叶子之和（优先掌握递归）

其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html

110. 平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

解题思路

class Solution {
public:
    int f(TreeNode* root) {
        if (root == NULL) return 0;
        int l = f(root->left);
        if (l == -1) return -1;
        int r = f(root->right);
        if (r == -1) return -1;
        if (abs(l-r)>1) return -1;
        return max(l,r)+1;
    }

    bool isBalanced(TreeNode* root) {
        return f(root) != -1 ? true : false;
    }
};

学习感想

257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。

解题思路

class Solution {
    void f(TreeNode* root, string path, vector<string> &res) {
        path += to_string(root->val);
        if (!root->left && !root->right) {
            res.push_back(path);
            return;
        }
        if(root->left)f(root->left,path+"->",res);
        if(root->right)f(root->right,path+"->",res);
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;
        if (!root) return res;
        f(root, path, res);
        return res;
    }
};

学习感想

404. 左叶子之和

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

解题思路

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int r=0;
        if (root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL)r+=root->left->val;
        return r+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
};

学习感想

第六章二叉树 part05

今日内容

● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

详细布置

找树左下角的值

本地递归偏难，反而迭代简单属于模板题，两种方法掌握一下

题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

路径总和

本题又一次设计要回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解

路径总和，和 113. 路径总和ii 一起做了。优先掌握递归法。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

从中序与后序遍历序列构造二叉树

本题算是比较难的二叉树题目了，大家先看视频来理解。

106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树一起做，思路一样的

题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

513. 找树左下角的值

题目描述

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。

假设二叉树中至少有一个节点。

解题思路

迭代法简单

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        deque<TreeNode* > v;
        int res=0;
        v.push_back(root);
        while (!v.empty()) {
            res=v.front()->val;
            int n = v.size();
            for (int i = 0; i < n;i++) {
                TreeNode* ptr=v.front();v.pop_front();
                if(ptr->left)v.push_back(ptr->left);
                if(ptr->right)v.push_back(ptr->right);
            }
        }
        return res;
    }
};

递归法

class Solution {
public:
    void f(TreeNode*p,int d,int&res,int&resd) {
        if(!p)return;
        if(d>resd){resd=d;res=p->val;}
        f(p->left,d+1,res,resd);
        f(p->right,d+1,res,resd);
    }
    int findBottomLeftValue(TreeNode*root) {
        int res=0,resd=0;
        f(root,1,res,resd);
        return res;
    }
};

学习感想

112. 路径总和

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

解题思路

class Solution {
public:
    bool hasPathSum(TreeNode*p,int t) {
if(!p)return false;if(!p->left&&!p->right)return p->val==t;return hasPathSum(p->left,t-p->val)||hasPathSum(p->right,t-p->val);
    }
};

113. 路径总和 II

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

解题思路

class Solution {
public:
    void f(vector<int>&path,TreeNode*p,vector<vector<int>>&res,int t){if(!p)return;path.push_back(p->val);
if(!p->left&&!p->right)if(t==p->val)res.push_back(path);f(path,p->left,res,t-p->val);f(path,p->right,res,t-p->val);path.pop_back();}
    vector<vector<int>> pathSum(TreeNode*p,int t) {
vector<vector<int>> res;vector<int> path;f(path,p,res,t);return res;
    }
};

学习感想

106. 从中序与后序遍历序列构造二叉树

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

解题思路

class Solution {
public:
    TreeNode* buildTree(vector<int> ino, vector<int> posto) {
        if(ino.empty())return NULL;
        int l=posto.back();
        auto it=find(ino.begin(),ino.end(),l);
        int i =distance(ino.begin(),it);
        TreeNode*left=buildTree(vector<int>(ino.begin(), it),vector<int>(posto.begin(),posto.begin()+i));
        TreeNode*right=buildTree(vector<int>(it+1,ino.end()),vector<int>(posto.begin()+i,posto.end()-1));
        return new TreeNode(l, left, right);
    }
};

105. 从前序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int> preorder, vector<int>ino) {
        if(ino.empty())return NULL;
        int l =preorder.front();
        auto it=find(ino.begin(),ino.end(),l);
        int i =distance(ino.begin(),it);
        TreeNode*left=buildTree(vector<int>(preorder.begin()+1,preorder.begin()+i+1),vector<int>(ino.begin(), it));
        TreeNode*right=buildTree(vector<int>(preorder.begin()+i+1,preorder.end()),vector<int>(it+1,ino.end()));
        return new TreeNode(l,left,right);
    }
};

学习感想

#![allow(unused)]

fn main() {
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;
struct Solution {}
impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::build_tree_ref(&inorder, &postorder)
    }

    pub fn build_tree_ref(inorder: &[i32], postorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        if inorder.len() == 0usize { return None }
        let n: usize = inorder.len();
        let mut num = postorder[n - 1usize];
        let pos: usize = inorder.iter().position(|&x| x == num).unwrap();
        let mut tn: TreeNode = TreeNode::new(num);
        tn.left = Self::build_tree_ref(&inorder[..pos], &postorder[..pos]);
        tn.right = Self::build_tree_ref(&inorder[pos + 1usize .. ], &postorder[pos .. n - 1usize]);
        Some(Rc::new(RefCell::new(tn)))
    }
}
}

休息日

corctf 还是一题也做不出我没用

654. 最大二叉树

题目描述

给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回 nums 构建的最大二叉树。

解题思路

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int> nums) {
        if(!nums.size())return NULL;
        int m=-1;for(int i=0;i<nums.size();i++)m=nums[i]>m?nums[i]:m;
        auto i=find(nums.begin(),nums.end(),m);
        TreeNode*l=constructMaximumBinaryTree(vector<int>(nums.begin(),i));
        TreeNode*r=constructMaximumBinaryTree(vector<int>(i+1,nums.end()));
        return new TreeNode(*i,l,r);
    }
};

学习感想

#![allow(unused)]

fn main() {
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;
struct Solution {}
impl Solution {
    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if nums.len() == 0 { return None }
        let (pos, &num): (usize, &i32) = nums.iter().enumerate().max_by_key(|(_, &x)| x).unwrap();
        let mut tn: TreeNode = TreeNode::new(num);
        tn.left = Self::construct_maximum_binary_tree(nums[.. pos].to_owned());
        tn.right = Self::construct_maximum_binary_tree(nums[pos + 1usize .. ].to_owned());
        Some(Rc::new(RefCell::new(tn)))
    }
}
}

617. 合并二叉树

题目描述

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

解题思路

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* r1, TreeNode* r2) {
        if(!r1&&!r2)return 0;
        TreeNode*l=mergeTrees(r1?r1->left:0,r2?r2->left:0);
        TreeNode*r=mergeTrees(r1?r1->right:0,r2?r2->right:0);
        return new TreeNode((r1?r1->val:0)+(r2?r2->val:0),l,r);
    }
};

学习感想

700. 二叉搜索树中的搜索

题目描述

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

解题思路

class Solution {
public:
    TreeNode* searchBST(TreeNode* r, int val) {
        if(!r)return 0;
        if (r->val==val)return r;
        if (val<r->val)return searchBST(r->left,val);
        return searchBST(r->right,val);
    }
};

学习感想

98. 验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

解题思路

class Solution {
public:
    bool f(TreeNode*r,long long l,long long ri){
        if(!r)return 1;
        if(r->val>=ri||r->val<=l)return 0;
        return f(r->left,l,r->val)&&f(r->right,r->val,ri);
    }
    bool isValidBST(TreeNode* r) {
        return f(r,(long long)(-2147483648)-1,(long long)2147483647+1);   
    }
};

学习感想

int 范围好坑啊

f(r,-2147483648-1,2147483647+1); 这样不会自动类型转换成longlong

第六章二叉树part07

今日内容

● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

详细布置

530.二叉搜索树的最小绝对差

需要领悟一下二叉树遍历上双指针操作，优先掌握递归题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html 视频讲解：https://www.bilibili.com/video/BV1DD4y11779

501.二叉搜索树中的众数

和 530差不多双指针思路，不过这里涉及到一个很巧妙的代码技巧。

可以先自己做做看，然后看我的视频讲解。

https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

236. 二叉树的最近公共祖先

本题其实是比较难的，可以先看我的视频讲解

https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html 视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

530. 二叉搜索树的最小绝对差

题目描述

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路

一开始没有理解题意写出来的代码，只考虑了一个节点左边和右边，没考虑相隔两层的情况

class Solution {
public:
    int getMinimumDifference(TreeNode*r) {
        if(!r)return 1<<30;
        int res = 1<<30;
        if(r->left){
            int a=r->val-r->left->val;
            res=min(res,a);
            int b=getMinimumDifference(r->left);
            res=min(res,b);
        }
        if(r->right){
            int a=r->right->val-r->val;
            res=min(res,a);
            int b=getMinimumDifference(r->right);
            res=min(res,b);
        }

        return res;
    }
};

class Solution {
public:
vector<int>v;
void f(TreeNode*r){if(!r)return;f(r->left);v.push_back(r->val);f(r->right);}
    int getMinimumDifference(TreeNode*r) {
        v.clear();
        f(r);
        int a=INT_MAX;
        for(int i=1;i<v.size();i++)a=min(a,v[i]-v[i-1]); 
        return a;
    }
};

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

二叉搜索树顺序遍历：

class Solution {
public:
int res = INT_MAX;
TreeNode* pre = NULL;
void f(TreeNode*r){
    if(!r)return;
    f(r->left);
    if(pre){res=min(res,r->val-pre->val);}
    pre=r;
    f(r->right);
}
    int getMinimumDifference(TreeNode*r) {
        f(r);
        return res;
    }
};

学习感想

501. 二叉搜索树中的众数

题目描述

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值小于等于当前节点的值结点右子树中所含节点的值大于等于当前节点的值左子树和右子树都是二叉搜索树

解题思路

对我来说有点难了

class Solution {
public:
TreeNode*pre=0;
int cnt=0;
int maxcnt=0;
vector<int>res;
void f(TreeNode*p){
    if(!p)return;
    f(p->left);
    if(!pre)cnt=1;else{
        if(p->val==pre->val)cnt ++;
        else cnt=1;
    }
    if (cnt>maxcnt){
        maxcnt=cnt;res.clear();res.push_back(p->val);
    } else if (cnt==maxcnt){
        res.push_back(p->val);
    }
    pre=p;
    f(p->right);
}
    vector<int> findMode(TreeNode*r) {
        res.clear();
f(r);
return res;
    }
};

学习感想

236. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路

class Solution {
public:
TreeNode*pp;
TreeNode*res=0;
TreeNode*qq;
int f(TreeNode*r){
    if(!r)return 0;
    int left=f(r->left);int right=f(r->right);
    int a=r==pp||r==qq?1:0;
    a+=left+right;
    if(!res&&a==2){res=r;}return a;
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        pp=p;qq=q;
        f(root);
        return res;
    }
};

f表示在子树中找到的个数，找到2个的时候就设置res就行了

学习感想

第六章二叉树part08

今日内容：

● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

详细布置

235. 二叉搜索树的最近公共祖先

相对于二叉树的最近公共祖先本题就简单一些了，因为可以利用二叉搜索树的特性。

题目链接/文章讲解：https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1Zt4y1F7ww

701.二叉搜索树中的插入操作

本题比想象中的简单，大家可以先自己想一想应该怎么做，然后看视频讲解，就发现本题为什么比较简单了。

题目链接/文章讲解：https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html
视频讲解：https://www.bilibili.com/video/BV1Et4y1c78Y

450.删除二叉搜索树中的节点

相对于插入操作，本题就有难度了，涉及到改树的结构

题目链接/文章讲解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
视频讲解：https://www.bilibili.com/video/BV1tP41177us

235. 二叉搜索树的最近公共祖先

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

解题思路

当pq同时在两边的话，就是找到了；不是的话，那肯定就是在某一边

class Solution {
public:
    int mi, ma;
    TreeNode*f(TreeNode*r){
        if(!r)return 0;
        if(mi<=r->val&&r->val<=ma)return r;
        if(mi>r->val)return f(r->right);return f(r->left);
    }
    TreeNode* lowestCommonAncestor(TreeNode* r, TreeNode* p, TreeNode* q) {
        mi=min(p->val,q->val);
        ma=max(p->val,q->val);
        return f(r);
    }
};

学习感想

701. 二叉搜索树中的插入操作

题目描述

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

解题思路

class Solution {
public:
    int v;
    TreeNode*f(TreeNode*r) {if(!r)return new TreeNode(v);
        if(r->val<v)r->right=f(r->right);else r->left=f(r->left);return r;
    }
    TreeNode* insertIntoBST(TreeNode* r, int val) {
        v=val;r=f(r);return r;
    }
};

WA: 输入的树可能为空树

学习感想

450. 删除二叉搜索树中的节点

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；如果找到了，删除它。

解题思路

思路：使用子树代替删除的节点。如果都有的话，随意左还是右。

通用选择右子树，那么子树的子树如何处理？右子树的右子树变成右子树，右子树的左子树变成被删除节点子树上最右侧叶节点的子树。

class Solution {
public:
    int k;
    TreeNode*f(TreeNode* r) {if(!r)return r;
        if(r->val==k) {
            if(!r->left&&!r->right)return 0;
            if(!r->left)return r->right;
            if(!r->right)return r->left;
            TreeNode*save=r->right->left;
            r->right->left=r->left;
            r=r->right;TreeNode*p=r->left;
            while(p->right)p=p->right;p->right=save;
            return r;
        } 
        if (r->val<k)r->right=f(r->right);else r->left=f(r->left);return r;
    }
    TreeNode* deleteNode(TreeNode* r, int key) {
        k=key;r=f(r);return r;
    }
};

学习感想

第六章二叉树part09

今日内容：

● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇

详细布置

669. 修剪二叉搜索树

这道题目比较难，比添加增加和删除节点难的多，建议先看视频理解。

题目链接/文章讲解： https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解： https://www.bilibili.com/video/BV17P41177ud

108.将有序数组转换为二叉搜索树

本题就简单一些，可以尝试先自己做做。

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL

538.把二叉搜索树转换为累加树

本题也不难，在求二叉搜索树的最小绝对差和众数那两道题目都讲过了双指针法，思路是一样的。

https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP

总结篇

好了，二叉树大家就这样刷完了，做一个总结吧

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html

669. 修剪二叉搜索树

题目描述

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

解题思路

class Solution {
public:
    int l, ri;
    TreeNode*f(TreeNode*r){
        if(!r)return r;
        if(r->val>=l&&r->val<=ri) {
            r->left=f(r->left);
            r->right=f(r->right);
            return r;
        }
        if(r->val<l)return f(r->right);return f(r->left);
    }
    TreeNode* trimBST(TreeNode* r, int low, int high) {
        l=low;ri=high;r=f(r);return r;
    }
};

学习感想

108. 将有序数组转换为二叉搜索树

题目描述

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路

class Solution {
public:
    vector<int>v;
    TreeNode*f(int l,int r){
        int n=r-l;if(n<=0)return 0;
        int m=l+n/2;return new TreeNode(v[m],f(l,m),f(m+1,r));
    }
    TreeNode* sortedArrayToBST(vector<int>&ve) {
        v=ve;int n=v.size();
        return f(0,n);
    }
};

学习感想

538. 把二叉搜索树转换为累加树

题目描述

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

解题思路

class Solution {
public:
    int s=0;
    TreeNode* convertBST(TreeNode*r) {
        if(!r)return r;
        convertBST(r->right);
        s+=r->val;
        r->val=s;
        convertBST(r->left);
        return r;
    }
};

学习感想

第七章回溯算法part01

今日内容：

● 理论基础 ● 77. 组合

详细布置

理论基础

其实在讲解二叉树的时候，就给大家介绍过回溯，这次正式开启回溯算法，大家可以先看视频，对回溯算法有一个整体的了解。

题目链接/文章讲解：https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
视频讲解：https://www.bilibili.com/video/BV1cy4y167mM

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

77. 组合

对着在回溯算法理论基础给出的代码模板，来做本题组合问题，大家就会发现写回溯算法套路。

在回溯算法解决实际问题的过程中，大家会有各种疑问，先看视频介绍，基本可以解决大家的疑惑。

本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。

题目链接/文章讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv 剪枝操作：https://www.bilibili.com/video/BV1wi4y157er

77. 组合

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

解题思路

class Solution {
public:
    vector<vector<int>>res;
    vector<int>cur;
    int n,k;
    void bt(int start){
        if(cur.size()==k){res.push_back(cur);return;}
        for(int i=start;i<=n-(k-cur.size())+1;i++){
            cur.push_back(i);
            bt(i+1);
            cur.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        this->n=n;this->k=k;bt(1);return res;
    }
};

学习感想

第七章回溯算法part02

今日内容：

● 216.组合总和III ● 17.电话号码的字母组合

详细布置

216.组合总和III

如果把组合问题理解了，本题就容易一些了。

题目链接/文章讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
视频讲解：https://www.bilibili.com/video/BV1wg411873x

17.电话号码的字母组合

本题大家刚开始做会有点难度，先自己思考20min，没思路就直接看题解。

题目链接/文章讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html
视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug

216. 组合总和 III

题目描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9 每个数字最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解题思路

class Solution {
public:
    vector<vector<int>>res;
    vector<int>cur;
    int cursum=0;
    int k,n;
    void bt(int start){
        if(cur.size()==k&&cursum==n){res.push_back(cur);return;}
        for(int i=start;i<10&&cursum<n;i++){
            cur.push_back(i);cursum+=i;
            bt(i+1);
            cur.pop_back();cursum-=i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        this->k=k;this->n=n;bt(1);return res;
    }
};

学习感想

17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解题思路

class Solution {
public:
const string a[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    vector<string>res;
    string cur;
    string digits;
    void b(int start) {
        if(cur.size()==digits.size()){res.push_back(cur);return;}
        string letters=a[digits[start]-'0'];
        for(char c:letters){
            cur.push_back(c);
            b(start+1);
            cur.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {if(digits.size()==0)return vector<string>{};
        this->digits=digits;b(0);return res;
    }
};

学习感想

第七章回溯算法part03

详细布置

39. 组合总和

本题是集合里元素可以用无数次，那么和组合问题的差别其实仅在于 startIndex上的控制

题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html 视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ

40.组合总和II

本题开始涉及到一个问题了：去重。

注意题目中给我们集合是有重复元素的，那么求出来的组合有可能重复，但题目要求不能有重复组合。

题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A

131.分割回文串

本题较难，大家先看视频来理解分割问题，明天还会有一道分割问题，先打打基础。

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6

39. 组合总和

class Solution {
public:
    vector<vector<int>>res;
    vector<int>cur;vector<int>candidates;
    int s=0,t;
    void bt(int start){
        if(s>=t){if(s==t)res.push_back(cur);return;}
        for(int j=start;j<candidates.size();j++){int i=candidates[j];
            cur.push_back(i);s+=i;
            bt(j);
            cur.pop_back();s-=i;
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        t=target;this->candidates=candidates;bt(0);return res;
    }
};

40.组合总和II

class Solution {
public:
    vector<vector<int>>res;
    vector<int>cur;vector<int>candidates;
    int s=0,t;
    void bt(int start){
        if(s>=t){if(s==t)res.push_back(cur);return;}
        for(int j=start;j<candidates.size();j++){
            int i=candidates[j];
            
            if(j>start&&candidates[j]==candidates[j-1])continue;
            cur.push_back(i);s+=i;
            bt(j+1);
            cur.pop_back();s-=i;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        t=target;sort(candidates.begin(),candidates.end());this->candidates=candidates;bt(0);return res;
    }
};

if(j>start&&candidates[j]==candidates[j-1])continue;这而想了很久，一直以为是j大于0

为了结果不重复，所以剪枝是必须要进行的操作

131.分割回文串

class Solution {
public:
    string s;vector<vector<string>>res;vector<string>cur;
    bool valid(int l,int r){
        int lptr=l,rptr=r;while(lptr<=r){if(s[lptr]!=s[rptr])return false;lptr++;rptr--;}return true;
    }
    void bt(int start){
        if(start==s.size()){res.push_back(cur);return;}
        for(int i=start;i<s.size();i++){
            if(valid(start,i)){
                cur.push_back(s.substr(start,i-start+1));
                bt(i+1);
                cur.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        this->s=s;bt(0);return res;
    }
};

28 第七章回溯算法

● 93.复原IP地址 ● 78.子集 ● 90.子集II

详细布置

93.复原IP地址

本期本来是很有难度的，不过大家做完分割回文串之后，本题就容易很多了

题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/

78.子集

子集问题，就是收集树形结构中，每一个节点的结果。整体代码其实和回溯模板都是差不多的。

题目链接/文章讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci

90.子集II

大家之前做了 40.组合总和II 和 78.子集，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。

题目链接/文章讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J

93.复原IP地址

class Solution {
public:
    vector<string>res;string cur;string s;void bt(int start,int cnt){
        if(cnt==4||start>=s.size()){if(cnt==4&&start==s.size())res.push_back(string(cur.begin(),cur.end()-1));return;}
        for(int i=1;i<=3;i++){
            string sub=string(s.begin()+start,s.begin()+start+i);
            if(valid(sub)){
                auto l=cur.size();
                cur+=sub+".";
                bt(start+i,cnt+1);
                cur.erase(l);
            }
        }
    }
    bool valid(string s){
        if(s.size()==0)return false;
        if(s[0]=='0')return s.size()==1;
        int a=stoi(s);return a>=0 && a<=255;
    }
    vector<string> restoreIpAddresses(string s) {this->s=s;
        bt(0,0);return res;
    }
};

78.子集

class Solution {
public:vector<vector<int>>res;vector<int>cur;vector<int>v;void bt(int start){res.push_back(cur);
    if(start>=v.size())return;for(int i=start;i<v.size();i++){
        cur.push_back(v[i]);bt(i+1);cur.pop_back();
    }
}
    vector<vector<int>> subsets(vector<int>& nums) {
        v=nums;bt(0);return res;
    }
};

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

90.子集II

class Solution {
public:vector<vector<int>>res;vector<int>cur;vector<int>v;void bt(int start){res.push_back(cur);
    if(start==v.size())return;for(int i=start;i<v.size();i++){
        if(i>start&&v[i]==v[i-1])continue;
        cur.push_back(v[i]);bt(i+1);cur.pop_back();
    }
}
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());v=nums;bt(0);return res;
    }
};

第七章回溯算法part05

491.递增子序列
46.全排列
47.全排列 II

详细布置

491.递增子序列

本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。 https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v

46.全排列

本题重点感受一下，排列问题与组合问题，组合总和，子集问题的区别。为什么排列问题不用 startIndex https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W

47.全排列 II

本题就是我们讲过的 40.组合总和II 去重逻辑和 46.全排列的结合，可以先自己做一下，然后重点看一下文章中我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行

https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm

491.递增子序列

class Solution {
    public:vector<vector<int>>res;
    vector<int>cur;
    vector<int>v;
    void bt(int start){
        if(cur.size()>1)res.push_back(cur);
        if(start>=v.size())return;
        unordered_set<int> uset; 
        for(int i=start;i<v.size();i++){
            if(cur.empty()||v[i]>=cur.back())
            {
                if(uset.find(v[i])!=uset.end())continue;
                uset.insert(v[i]);
                cur.push_back(v[i]);bt(i+1);cur.pop_back();
            }
        }

    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {v=nums;bt(0);return res;}
};

本层访问过的元素不再访问，误以为是前后不用重复的就行，需要使用set

46.全排列

https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

class Solution {
public:
    vector<int>used;
    vector<int>cur;
    vector<int>v;
    vector<vector<int>>res;
    void bt() {
        if(cur.size()==v.size())
        {res.push_back(cur);return;}
        for(int i=0;i<v.size();i++){
            if(used[i]==0){
                used[i]=1;cur.push_back(v[i]);bt();cur.pop_back();used[i]=0;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        v=nums;used=vector<int>(v.size(),0);bt();return res;
    }
};

47.全排列 II

class Solution {
public:
    vector<int>used;
    vector<int>cur;
    vector<int>v;
    vector<vector<int>>res;
    void bt() {
        if(cur.size()==v.size()){
            res.push_back(cur);return;
        }
        for(int i=0;i<v.size();i++){
            if(used[i]==1)continue;
            if(i>0&&v[i]==v[i-1]&&used[i-1]==0)continue;
            used[i]=1;
            cur.push_back(v[i]);
            bt();
            cur.pop_back();
            used[i]=0;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        v=nums;sort(v.begin(),v.end());
        used=vector<int>(v.size(),0);
        bt();
        return res;
    }
};

如何剪枝同一层使用过的：&&used[i-1]==0，一下子想不到。

第七章回溯算法part06

● 332.重新安排行程 ● 51. N皇后 ● 37. 解数独 ● 总结

详细布置

今天这三道题都非常难，那么这么难的题，为啥一天做三道？

因为一刷也不求大家能把这么难的问题解决，所以大家一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。

大家今天的任务，其实是对回溯算法章节做一个总结就行。

重点是看回溯算法总结篇： https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

332.重新安排行程（可跳过）

https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html

51. N皇后（可跳过）

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
视频讲解：https://www.bilibili.com/video/BV1Rd4y1c7Bq

37. 解数独（可跳过）

https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
视频讲解：https://www.bilibili.com/video/BV1TW4y1471V

总结 https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

332.重新安排行程

51. N皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> chess;
    int N;
    bool checkpos(int i, int j) {
        for(int k=i+1;k<N;k++){
            if(chess[k][j]=='Q')return false;
        }
        for(int k=0;k<N;k++){
            int x = i+k;
            int y = j+k;
            if(x>=N||y>=N)break;
            if(chess[x][y]=='Q')return false;
        }
        for(int k=0;k<N;k++){
            int x = i+k;
            int y = j-k;
            if(x>=N||y<0)break;
            if(chess[x][y]=='Q')return false;
        }
        return true;
    }
    void bt(int depth) {
        if (depth < 0) {
            res.push_back(chess);
            return;
        }
        for(int pos=0;pos<N;pos++){
            if(checkpos(depth,pos)) {
                chess[depth][pos] = 'Q';
                bt(depth - 1);
                chess[depth][pos] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        N=n;
        for (int i=0;i<n;i++){
            chess.push_back(string(n,'.'));
        }
        bt(n-1);
        return res;
    }
};

我是从棋盘底部从下往上构造的哈哈

37. 解数独

class Solution {
public:
    vector<vector<char>> b;
    bool check(int i,int j,int val) {
        for(int k=0;k<9;k++)if(b[i][k]==val||b[k][j]==val)return false;
        int ibase = i/3*3, jbase = j/3*3;
        for(int u=0;u<3;u++)for(int v=0;v<3;v++)if(b[ibase+u][jbase+v]==val)return false;
        return true;
    }
    bool bt(int pos) {
        int i = pos/9, j = pos%9;
        if(i==9)return true;
        if(b[i][j]!='.')return bt(pos+1);
        for(int v=1; v<=9; v++) {
            if(check(i,j,'0'+v)) {
                b[i][j]='0'+v;
                if(bt(pos+1))return true;
                b[i][j]='.';
            }
        }
        return false; // unreachable
    }
    void solveSudoku(vector<vector<char>>& board) {
        b=board;
        bt(0);
        // for(int i=0;i<9;i++){
        //     for(int j=0;j<9;j++){
        //         cout<<b[i][j];
        //     }
        //     cout<<endl;
        // }
        board=b;
    }
};

第八章贪心算法 part01

● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法就了解它没有规律的本质就够了。

不用花心思去研究其规律，没有思路就立刻看题解。

基本贪心的题目有两个极端，要不就是特简单，要不就是死活想不出来。

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

详细布置

理论基础

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

455.分发饼干

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

376. 摆动序列

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

53. 最大子序和

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

455. 分发饼干

// Custom comparator function for sorting in reverse order
bool reverseComparator(int a, int b) {
    return a > b; // '>' will sort in descending order (reverse), '<' will sort in ascending order
}
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(),s.end(),reverseComparator);
        sort(g.begin(),g.end(),reverseComparator);
        int cnt = 0;
        int p = 0;
        for (int cookiesize : s) {
            while (p < g.size() && g[p] > cookiesize) p ++ ;
            if (p >= g.size()) break;
            // if (cookiesize >= g[p]) {
                cnt ++ ;
                p ++;
            // }
        }
        return cnt;
    }
};

376. 摆动序列

class Solution {
public:
    int wiggleMaxLength(vector<int>&v) {
        //
        auto tail = unique(v.begin(),v.end());
        v.erase(tail,v.end());
        //
        if(v.size()<=2)return v.size();
        int cnt = 0;
        for (int i = 1; i < v.size() - 1; i ++ ) {
            int pdir = v[i] - v[i-1];
            int cdir = v[i+1] - v[i];
            cnt += pdir*cdir<0?1:0;
        }
        return cnt+2;
    }
};

去重之后就不用考虑这么多复杂的情况

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cnt = 0;
        for (int num : nums) {
            cnt += num;
            res = max(res,cnt);
            if (cnt < 0) cnt = 0;
        }
        return res;
    }
};

res = max(res,cnt);和if (cnt < 0) cnt = 0;这两行顺序一开始搞错了，导致input只是一个-1的时候有问题

第八章贪心算法 part02

● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

详细布置

122.买卖股票的最佳时机II

本题解法很巧妙，大家可以看题思考一下，在看题解。

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

55. 跳跃游戏

本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解

https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

45.跳跃游戏II

本题同样不容易想出来。贪心就是这样，有的时候会感觉简单到离谱，有时候，难的不行，主要是不容易想到。

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

122. 买卖股票的最佳时机 II

如果想到其实最终利润是可以分解的，那么本题就很容易了！

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for ( int i = 1; i < prices.size(); i ++ ) {
            int a = prices[i] - prices[i-1];
            res += a>0?a:0;
        }
        return res;
    }
};

55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int dst = 0;
        int i = 0;
        while (i <= dst) { 
            dst = max(dst,i+nums[i]);
            i ++ ;
            if (dst >= nums.size() - 1) return true;
        }
        return false;
    }
};

45.跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 1;
        int predist = nums[0];
        int maxdist = predist;
        int i = 0;
        if(nums.size()==1)return 0;
        if (maxdist>=nums.size()-1) return 1;
        while (i <= maxdist) {
            int nextdist = i+nums[i];
            maxdist=max(maxdist,nextdist);
            if (maxdist>=nums.size()-1) break;
            if (i == predist) {
                res ++ ;
                predist = maxdist;
            }
            i ++ ;

        }
        return res + 1;
    }
};

第八章贪心算法 part03

● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果

详细布置

1005.K次取反后最大化的数组和

本题简单一些，估计大家不用想着贪心，用自己直觉也会有思路。 https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

134. 加油站

本题有点难度，不太好想，推荐大家熟悉一下方法二 https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

135. 分发糖果

本题涉及到一个思想，就是想处理好一边再处理另一边，不要两边想着一起兼顾，后面还会有题目用到这个思路 https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

1005.K次取反后最大化的数组和

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& v, int k) {
        sort(v.begin(),v.end());
        for(int& i: v){
            if (i >= 0) break;
            i=-i;k--;if(k==0)break;
        }if(k==0)return accumulate(v.begin(), v.end(), 0);
        sort(v.begin(),v.end());
        while (k>0){v[0]=-v[0];k--;}
        return accumulate(v.begin(), v.end(), 0);
    }
};

134. 加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& g, vector<int>& c) {
        int n = g.size();
        vector<int> h(n,0);
        // h[i] -> gas change from i-1 -> i
        h[0] = g[n-1] - c[n-1];
        for (int i = 1 ; i < n ; i ++ ) {
            h[i] = g[i-1]-c[i-1];
        }
        int start = 0;
        int pos = start;
        int csum = 0;
        while (pos < start + n && start < n) {
            csum += h[(1+pos)%n];
            if (csum < 0) {
                start = pos + 1;
                csum = 0;
            }
            pos ++ ;
        }
        return start<n?start:-1;
    }
};

贪心算法（方法一）还挺巧妙的，我这个就是个最大子数组的算法

135. 分发糖果

class Solution {
public:
    int candy(vector<int>& v) {
        // 1,3,4,5,2
        // 1,2,3,4,1
        // 
        vector<int>res(v.size(),1);
        for (int i = 1 ; i < v.size() ; i ++ ) {
            if (v[i] > v[i-1]) res[i] = res[i-1] + 1;
        }
        for (int i = v.size() - 2; i >= 0 ; i -- ) {
            if (v[i] > v[i+1] && res[i] <= res[i+1]) res[i] = res[i+1] + 1;
        }
        return accumulate(res.begin(),res.end(),0);
    }
};

WA了一发漏了&& res[i] <= res[i+1]

第八章贪心算法 part04

● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

详细布置

860.柠檬水找零

本题看上好像挺难，其实挺简单的，大家先尝试自己做一做。 https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

406.根据身高重建队列

本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。 https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html

452. 用最少数量的箭引爆气球

本题是一道重叠区间的题目，好好做一做，因为明天三道题目，都是重叠区间。 https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html

860.柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int c5 = 0, c10 = 0;
        for ( int bill : bills) {
            switch (bill) {
                case 5:
                    c5 ++ ;
                    break;
                case 10:
                    if (c5 == 0) return false;
                    c5 -- ;
                    c10 ++ ;
                    break;
                default:
                    if (c10>0&&c5>0) {
                        c10 -- ; c5 -- ; continue;
                    }
                    if (c5 >= 3) {
                        c5 -= 3; continue;
                    }
                    return false;
                    break;
            }
        }
        return true;
    }
};

模拟题

406.根据身高重建队列

错误解答


bool f(const vector<int>&a, const vector<int>&b) {
    if (a[1]==b[1])return a[0]>b[0];return a[1]<b[1];
}
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        vector<vector<int>> res;
        sort(p.begin(),p.end(),f);
        for ( auto peo: p ) {
            if (peo[1]!=0) break;
            res.push_back(peo);
        }
        reverse(res.begin(),res.end());
        for (int i = res.size(); i < p.size(); i ++ ) {
            auto x = p[i];
            int insert_pos = 0; int cnt = 0;
            while ( cnt < x[1] + 1 ) {
                if (p[insert_pos][0] >= x[0]) cnt ++ ;
                insert_pos ++ ;
            }
            res.insert(res.begin()+insert_pos - 1,x);
        }
        return res;
    }
};

这道题我没有能够做出来

在135. 分发糖果 (opens new window)我就强调过一次，遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

如果两个维度一起考虑一定会顾此失彼。

我就是错误的按照k来从小到大排序了


bool f(vector<int>& a, vector<int>& b){
    if(a[0]==b[0])return a[1]<b[1];return a[0]>b[0];
}
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        vector<vector<int>> res;
        sort(p.begin(),p.end(),f);
        for (int i = 0; i < p.size(); i ++ ) {
            auto x = p[i];
            int pos = x[1];
            res.insert(res.begin()+pos,x);
        }
        return res;
    }
};

先按照身高排序，固定住规律。按照k排序没法获得额外的规律

452. 用最少数量的箭引爆气球

想不出来用什么数据结构

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& v) {
        int res = 1;
        sort(v.begin(),v.end());
        for ( int i = 1 ; i < v.size(); i ++ ) {
            if ( v[i][0] > v[i-1][1] ) {
                res ++ ;
            } else {
                v[i][1] = min(v[i][1],v[i-1][1]);
            }
        }
        return res;
    }
};

发现不用数据结构，要点是每次右端点取重合的最小值

        ======        
====================

第八章贪心算法 part05

● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

详细布置

今天的三道题目，都算是重叠区间问题，大家可以好好感受一下。都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！还是属于那种，做过了也就会了，没做过就很难想出来。不过大家把如下三题做了之后，重叠区间基本上差不多了

435. 无重叠区间

https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

763.划分字母区间

https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html

56. 合并区间

本题相对来说就比较难了。

https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

435. 无重叠区间

bool f(const vector<int>&a,const vector<int>&b) {
    if(a[0]==b[0])return a[1]>b[1];return a[0]<b[0];
}
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& v) {
        int res = 0;
        sort(v.begin(),v.end(),f);
        for ( int i = 1 ; i < v.size(); i ++ ) {
            cout << v[i][0] << v[i][1] << endl;
            if ( v[i][0] >= v[i-1][1] ) {
            } else {
                res ++ ;
                // v[i][1] = min(v[i][1],v[i-1][1]);
            }
        }
        return res;
    }
};

不会做，不知道怎么处理这种情况

 -------  -------  ------- -------
====== ======= ====== ======= =====

求需要移除区间的最小数量，使剩余区间互不重叠 -> 求最大的不交叉区间个数

bool f(const vector<int>&a,const vector<int>&b) {
    return a[1]<b[1];
}
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& v) {
        int cnt = 1;
        sort(v.begin(),v.end(),f);
        int rend = v[0][1];
        for ( int i = 1 ; i < v.size(); i ++ ) {
            if (rend <= v[i][0]) {
                rend = v[i][1];
                cnt ++ ;
            }
        }
        return v.size() - cnt;
    }
};

通用技巧，求不重合区间的最大个数

763.划分字母区间

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int v[26] = {0};
        vector<int> res;
        for (int i = 0; i < s.size(); i ++ ) {
            v[s[i]-'a']=i;
        }
        int last = v[s[0]-'a'];
        int pre = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            last = max(last,v[s[i]-'a']);
            if (last == i) {
                res.push_back(i - pre + 1);
                pre = i + 1;
            }
        }
        return res;
    }
};

56. 合并区间

bool f(const vector<int>&a,const vector<int>&b) {
    if(a[0]==b[0])return a[1]<b[1];return a[0]<b[0];
}
class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int>> merge(vector<vector<int>>& v) {
        sort(v.begin(),v.end(),f);
        int l = v[0][0], r = v[0][1];
        for ( int i = 1; i < v.size(); i ++ ) {
            if (v[i][0]<=r) r = max(r,v[i][1]);
            else {
                res.push_back(vector<int>{l, r});
                l = v[i][0];
                r = v[i][1];
            }
        }
        res.push_back(vector<int>{l, r});
        return res;
    }
};

这个很直接

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = Vec::new();
        intervals.sort_by_key(|v| v[0]);
        let mut left: i32 = intervals[0][0];
        let mut right: i32 = intervals[0][1];
        intervals.iter().skip(1usize).for_each(|v| {
            if v[0] <= right {
                right = std::cmp::max(v[1], right);
            } else {
                // non overlap
                res.push(vec![left, right]);
                left = v[0];
                right = v[1];
            }
        });
        res.push(vec![left, right]);
        res
    }
}
}

第八章贪心算法 part06

● 738.单调递增的数字 ● 968.监控二叉树 ● 总结

详细布置

738.单调递增的数字

https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

968.监控二叉树（可以跳过）

本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。 https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

总结

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。 https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html

738.单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        vector <int> a;
        int nn = n;
        while(n > 0) {
            int item = n % 10;
            a.push_back(item);
            n /= 10;
        }
        reverse(a.begin(),a.end());
        for (int i = 1; i < a.size(); i ++ ) {
            if (a[i] < a[i-1]) {
                int cnt = a.size() - i;
                int shift = cnt;
                int right = 0;
                while (cnt > 0) {
                    right *= 10;
                    right += 9;
                    cnt -- ;
                }
                int left = 0;
                for (int j = 0; j < i; j ++ ) {
                    left *= 10;
                    left += a[j];
                }
                left = monotoneIncreasingDigits(left - 1);
                return left * 10 * shift + right;
            }
        }
        return nn;
        // 1232 -> 1229
        // 2312 -> 2299
        // 9123 -> 8999
        // 100001 -> 
    }
};

332 -- 329 × 332 -- 299 √ 想不出了，原来是要从后往前

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size();
        for ( int i = s.size() - 1; i > 0; i -- ) {
            if (s[i-1] > s[i]) {
                flag = i;
                s[i-1] -- ;
            }
        }
        for ( int i = flag; i < s.size() ; i ++ ) {
            s[i] = '9';
        }
        return stoi(s);
    }
};

草真优雅

968.监控二叉树

class Solution {
public:
    int cnt = 0;
    bool f(TreeNode*r) { // should not be null
        // if(!r)return true;
        if(!r->left&&!r->right)return false; // no monitor
        bool lres = false;
        if(r->left)res=f(r->left);
        if(!res&&r->right)res=f(r->right);
        if(res == true) return false;
        else {
            cnt ++ ;
            return true;
        }
    }
    int minCameraCover(TreeNode* r) {if(!r->left&&!r->right)return 1;
        f(r);
        return cnt;
    }
};

想不明白：在二叉树中如何从低向上推导呢？

class Solution {
public:
    int cnt = 0;
    int f(TreeNode*p) {
        // 0 -- 没有覆盖
        // 1 -- 有覆盖了
        // 2 -- 有摄像头
        if(!p)return 1;
        int l = f(p->left);
        int r = f(p->right);
        if (l==1 && r==1) return 0;//////
        if (l==0 || r==0) {//////////////
            cnt ++ ;
            return 2;
        }
        return 1;
    }
    int minCameraCover(TreeNode* r) {if(!r->left&&!r->right)return 1;
        if(f(r)==0)cnt++;///////
        return cnt;
    }
};

[0,0,null,null,0,0,null,null,0,0] 0 0 n n 0 0 n n 0 0

第九章动态规划part01

● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

详细布置

今天正式开始动态规划！

理论基础

无论大家之前对动态规划学到什么程度，一定要先看我讲的动态规划理论基础。

如果没做过动态规划的题目，看我讲的理论基础，会有感觉是不是简单题想复杂了？

其实并没有，我讲的理论基础内容，在动规章节所有题目都有运用，所以很重要！

如果做过动态规划题目的录友，看我的理论基础就会感同身受了。

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 视频：https://www.bilibili.com/video/BV13Q4y197Wg

509. 斐波那契数

很简单的动规入门题，但简单题使用来掌握方法论的，还是要有动规五部曲来分析。

https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
视频：https://www.bilibili.com/video/BV1f5411K7mo

70. 爬楼梯

本题大家先自己想一想，之后会发现，和斐波那契数有点关系。

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频：https://www.bilibili.com/video/BV17h411h7UH

746. 使用最小花费爬楼梯

这道题目力扣改了题目描述了，现在的题目描述清晰很多，相当于明确说第一步是不用花费的。

更改题目描述之后，相当于是文章中「拓展」的解法

https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频讲解：https://www.bilibili.com/video/BV16G411c7yZ

509. 斐波那契数

class Solution {
public:
    int fib(int n) {
        vector <int> dp = vector<int>(n+1,0);
        if (n <= 1) return n;
        dp[0] = 0;
        dp[1] = 1;
        for ( int i = 2; i < n+1; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

70. 爬楼梯

class Solution {
public:
// 1-> 1; 2 -> 2; 3-> 3
    int climbStairs(int n) {
        vector<int>dp(n);if(n<=3)return n;
        dp[0]=1;dp[1]=2;for(int i=2;i<n;i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n-1];
    }
};

746. 使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // dp[i] => 到达i的最小花费
        // dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        int n=cost.size();
        vector<int>dp(n+1);
        dp[0]=0;dp[1]=0;
        for(int i=2;i<n+1;i++)dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[n];
    }
};

第九章动态规划part02

● 62.不同路径 ● 63. 不同路径 II

今天开始逐渐有 dp的感觉了，题目不多，就两个不同路径，可以好好研究一下

详细布置

62.不同路径

本题大家掌握动态规划的方法就可以。数论方法有点非主流，很难想到。

https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu

63. 不同路径 II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6

62. 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m, vector<int>(n));
        // dp[i][j] 到达坐标ij的不同路径树
        // dp[i][j] = (i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        for(int j=0;j<n;j++)dp[0][j]=1;
        for(int i=1;i<m;i++)for(int j=0;j<n;j++){
            dp[i][j] = (i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        }
        return dp[m-1][n-1];
    }
};

63. 不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // dp[i][j] 到达坐标ij的不同路径树
        // dp[i][j] = obstacleGrid[i][j]==1?0:(i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        int m=obstacleGrid.size();int n=obstacleGrid[0].size();
        vector<vector<int>>dp(m, vector<int>(n,0));
        int cnt = 1;
        for(int j=0;j<n;j++){
            if (obstacleGrid[0][j]==1)cnt = 0;
            dp[0][j]=cnt;
        }
        for(int i=1;i<m;i++)for(int j=0;j<n;j++){
            dp[i][j] = obstacleGrid[i][j]==1?0:(i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        }
        return dp[m-1][n-1];
    }
};

第九章动态规划part03

● 343. 整数拆分 ● 96.不同的二叉搜索树

详细布置

今天两题都挺有难度，建议大家思考一下没思路，直接看题解，第一次做，硬想很难想出来。

343. 整数拆分

https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ

96.不同的二叉搜索树

https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视屏讲解：https://www.bilibili.com/video/BV1eK411o7QA

343. 整数拆分

class Solution {
public:
    int integerBreak(int n) {
        // dp[i] -> 对于正整数i 将其拆分为k个数之和的乘机最大值
        vector<int> dp(n+1);
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        for (int i = 3; i <= n; i ++ ) {
            for (int j = 1; j <= i - j; j ++) {
                dp[i] = max(dp[i], j * max(i-j,dp[i-j]));
            }
        }
        return dp[n];
    }
};

96.不同的二叉搜索树

想了一下，不会做

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        if (n<=2)return n;
        if (n==3)return 5;
        // dp[i] -> 恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        for ( int i = 4; i <= n; i ++ )
            for ( int j = 0; j < i; j ++ )
                dp[i] += dp[j]*dp[i-j-1];
        return dp[n];
    }
};

居然是要看形状，有点在猜一个公式的感觉

第九章动态规划part04

● 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！滚动数组
● 416. 分割等和子集

正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。

如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解这是干什么的。

如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。

背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。

详细布置

01背包问题二维

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6

01背包问题一维

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
视频讲解：https://www.bilibili.com/video/BV1BU4y177kY

416. 分割等和子集

本题是 01背包的应用类题目 https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE

416. 分割等和子集

第一眼不会

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // dp[i] 容量为s//2的01背包
        int sum = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            sum += nums[i];
        }
        if (sum & 1) return false;
        int target = sum >> 1;
        vector<int> dp (1+target);
        for (int i = 0; i < nums.size(); i ++ ) {
            for (int j = target; j >= nums[i]; j -- ) {
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }
};

一下子想不出转换成01背包的想法

第九章动态规划 part05

● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

详细布置

1049. 最后一块石头的重量 II

本题就和昨天的 416. 分割等和子集很像了，可以尝试先自己思考做一做。视频讲解：https://www.bilibili.com/video/BV14M411C7oV https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html

494. 目标和

大家重点理解递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问我们还会用到。
视频讲解：https://www.bilibili.com/video/BV1o8411j73x https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html

474.一和零

通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面对于完全背包，多重背包还有单独讲解。视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html

1049. 最后一块石头的重量 II

class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            sum += nums[i];
        }
        int target = sum >> 1;
        vector<int> dp (1+target,0);
        for (int i = 0; i < nums.size(); i ++ ) {
            for (int j = target; j >= nums[i]; j -- ) {
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return sum - dp[target]*2;
    }   
};

494.目标和

一开始不会做，一种心的dp推导公式

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            sum += nums[i];
        }
        int left = (target + sum);
        if (left & 1) return 0;
        left = left >> 1;
        vector<int>dp(left+1);
        dp[0] = 1;
        // dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
        for ( int i = 0; i < nums.size() ; i ++ ) {
            for (int j = dp.size() - 1; j >= nums[i] ; j -- ) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[left];
    }
};

474.一和零

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // dp[i][j] 表示子集中最多i个0和j个1的最大子集长度
        vector<vector<int>>dp(1+m,vector<int>(1+n,0));
        // x = count(s.begin(),s.end(),'0');
        // y = s.size() - x;
        // dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1)
        for (int u = 0; u < strs.size() ; u ++ ) {
            string s = strs[u];
            int x = count(s.begin(),s.end(),'0');
            int y = s.size() - x;
            for ( int i = m ; i >= x; i -- ) {
                for ( int j = n ; j >= y; j -- ) {
                    dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1);
                }
            }
        }
        return dp[m][n];
    }
};

这个题很舒服，自己一下写过的

第九章动态规划part06

● 完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

详细布置

力扣上没有纯粹的完全背包的题目，所以大家看本篇了解一下完全背包的理论

后面的两道题目，都是完全背包的应用，做做感受一下

完全背包

视频讲解：https://www.bilibili.com/video/BV1uK411o7c9 https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

518. 零钱兑换 II

视频讲解：https://www.bilibili.com/video/BV1KM411k75j https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html

377. 组合总和 Ⅳ

视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6 https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html

518. 零钱兑换 II

第一道完全背包的题目，抄了随想录

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // dp[j]：凑成总金额j的货币组合数为dp[j]
        vector<int>dp(amount+1);
        dp[0]=1;
        // dp[j] += dp[j - coins[i]];
        for(int i = 0; i < coins.size(); i ++ ) {
            for (int j = coins[i]; j <= amount; j ++ ) { // 完全背包，需要重复计算之前的组合数
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

不会做，抄了随想录

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // dp[i] 表示总和为i的元素组合的个数
        vector<unsigned int>dp(1+target);
        dp[0]=1;
            for(int j=0;j<=target;j++){
        for(int i=0;i<nums.size();i++){
            if(j>=nums[i])
                dp[j]+=dp[j-nums[i]];
            }
        } 
        return dp[target];
    }   
};

第九章动态规划part07

● 70. 爬楼梯（进阶） ● 322. 零钱兑换 ● 279.完全平方数

详细布置

70. 爬楼梯（进阶）

这道题目爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html

322. 零钱兑换

如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

这句话结合本题大家要好好理解。视频讲解：https://www.bilibili.com/video/BV14K411R7yv https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

279.完全平方数

本题和 322. 零钱兑换基本是一样的，大家先自己尝试做一做视频讲解：https://www.bilibili.com/video/BV12P411T7Br https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

70. 爬楼梯（进阶）

class Solution {
public:
    int climbStairs(int n) {
        int m = 2;
        // dp[i] -> 爬到有i个台阶的楼顶，有dp[i]种方法
        vector<int> dp(1+n);
        dp[0]=1;
        for(int i=0;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(i-j>=0)
                    dp[i]+=dp[i-j];
            }
        }
        return dp[n];
    }
};

322. 零钱兑换

抄了随想录

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // if (amount == 0) return 0;
        // dp[i] -> 可以凑成i所需的 最少的硬币个数
        // dp[i] = min(dp[i],dp[i-coins[j]]+1)
        vector<int>dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=INT_MAX)
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }
};

279.完全平方数

喜喜这个自己做的

class Solution {
public:
    int numSquares(int n) {
        // dp[i] 和为 i 的完全平方数的最少数量 
        // dp[j] = min(dp[j],dp[j-i*i]+1)
        vector<int>dp(1+n,INT_MAX);
        dp[0]=0;
        for(int i = 1; i * i <= n; i ++ ) {
            for(int j = i*i; j <= n; j ++ ) {
                dp[j] = min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};

第九章动态规划part08

● 139.单词拆分 ● 关于多重背包，你该了解这些！ ● 背包问题总结篇！

详细布置

关于多重背包，力扣上没有相关的题目，所以今天大家的重点就是回顾一波自己做的背包题目吧。

139.单词拆分

视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

关于多重背包，你该了解这些！

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html

背包问题总结篇！

https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html

139. 单词拆分

不会

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // dp[i] -> 长度为i的字符串是否可以拼出来
        // dp[j] = true if dp[j-i] == true and [i:j] in wordDict
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool>dp(s.size()+1,false);
        dp[0]=true;
        for (int i = 1 ; i<=s.size();i++) {
            for (int j = 0; j < i; j ++ ) {
                string word = s.substr(j,i-j);
                if (dp[j] && wordSet.find(word)!= wordSet.end())
                    dp[i] = true;
            }
        }
        return dp[s.size()];
    }
};

第九章动态规划part09

● 198.打家劫舍 ● 213.打家劫舍II
● 337.打家劫舍III

详细布置

今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。

198.打家劫舍

视频讲解：https://www.bilibili.com/video/BV1Te411N7SX https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html

213.打家劫舍II

视频讲解：https://www.bilibili.com/video/BV1oM411B7xq https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

337.打家劫舍III

视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html

198. 打家劫舍

这个是抄随想录的

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        // dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
        // dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.size() - 1];
    }
};

213. 打家劫舍 II

这个是自己写的

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        // dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
        // dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        vector<int> dp(nums.size());
        // skip index 0 first
        int res = 0;
        dp[0] = 0;
        dp[1] = nums[1];
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        res = dp[nums.size()-1];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size() - 1; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        res = max(res,dp[nums.size()-2]);
        return res;
    }
};

337.打家劫舍III

自己做的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
// <r1,r2> r1 如果偷当前节点，得到的最大值 ； r2 不偷当前节点的最大值
    pair<int,int> f(TreeNode*root) {
        if(!root){return make_pair(0,0);}
        auto leftr = f(root->left);
        auto rightr = f(root->right);
        int takeleft = leftr.first;
        int notakeleft = leftr.second;
        int takeright = rightr.first;
        int notakeright = rightr.second;
        int r1 = notakeleft + notakeright + root->val;
        int r2 = max(takeleft,notakeleft) + max(takeright,notakeright);
        return make_pair(r1, r2);
    }
    int rob(TreeNode* root) {
        auto res = f(root);
        return max(res.first, res.second);
    }
};

第九章动态规划part10

● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

详细布置

股票问题是一个动态规划的系列问题，今日安排的题目不多，大家可以慢慢消化。

121. 买卖股票的最佳时机

视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html

122.买卖股票的最佳时机II

视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

121. 买卖股票的最佳时机

一开始这样子没有用动规

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int cmin = INT_MAX;
        for (int i = 0; i < prices.size(); i ++ ) {
            cmin = min(cmin, prices[i]);
            if (prices[i] > cmin) {
                res = max(res, prices[i] - cmin);
            }
        }
        return res;
    }
};

122. 买卖股票的最佳时机 II

抄了随想录

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2, 0));
        // dp[i][0] 表示第i天持有股票所得现金。
        // dp[i][1] 表示第i天不持有股票所得最多现金

// 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

// 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
// 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]


// 再来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

// 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
// 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];


    }
};

第九章动态规划part11

● 123.买卖股票的最佳时机III
● 188.买卖股票的最佳时机IV

详细布置

123.买卖股票的最佳时机III

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。视频讲解：https://www.bilibili.com/video/BV1WG411K7AR https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html

188.买卖股票的最佳时机IV

本题是123.买卖股票的最佳时机III 的进阶版
视频讲解：https://www.bilibili.com/video/BV16M411U7XJ https://programmercarl.com/0188.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIV.html

123.买卖股票的最佳时机III

自己写的时候漏掉了dp[0][3]=-prices[0];这个条件

class Solution {
public:
    int maxProfit(vector<int>& prices) {
//         一天一共就有五个状态，

// 没有操作 （其实我们也可以不设置这个状态）
// 第一次持有股票
// 第一次不持有股票
// 第二次持有股票
// 第二次不持有股票
// dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
vector<vector<int>>dp(prices.size(), vector<int>(5,0));
dp[0][1]=dp[0][3]=-prices[0];

for(int i=1;i<prices.size();i++){
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
}
return max(dp[prices.size()-1][2],dp[prices.size()-1][4]);
    }
};

188.买卖股票的最佳时机IV

不过度确实好难啊，不过是自己写的，就类比一下上一道题

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>>dp(prices.size(), vector<int>(2*k+1,0));
        for(int j=0;j<k;j++)dp[0][2*j+1]=-prices[0];
        for(int i=1;i<prices.size();i++){
            for(int j=1;j<=k;j++){
                dp[i][2*j-1] = max(dp[i - 1][2*j-2] - prices[i], dp[i - 1][2*j-1]);
                dp[i][2*j]   = max(dp[i - 1][2*j-1] + prices[i], dp[i - 1][2*j]);   // 表示不持有
            }
        }
        int res = -1;
        for(int j=1;j<=k;j++)res=max(res,dp[prices.size()-1][2*j]);
        return res;
    }
};

第九章动态规划part12

● 309.最佳买卖股票时机含冷冻期
● 714.买卖股票的最佳时机含手续费
●总结

309.最佳买卖股票时机含冷冻期

本题加了一个冷冻期，状态就多了，有点难度，大家要把各个状态分清，思路才能清晰视频讲解：https://www.bilibili.com/video/BV1rP4y1D7ku

https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html

714.买卖股票的最佳时机含手续费

相对122.买卖股票的最佳时机II ，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的，可以尝试自己做一做。视频讲解：https://www.bilibili.com/video/BV1z44y1Z7UR https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

股票总结

股票问题做一个总结吧 https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%82%A1%E7%A5%A8%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93%E7%AF%87.html

309.最佳买卖股票时机含冷冻期

我自己定义的状态

class Solution {
public:
    int maxProfit(vector<int>& v) {
        // dp[i][j] 表示第i天的最大现金
        // 0 持有
        // 1 非持有且不在冷冻期
        // 2 非持有且冷冻期(刚出售)
        vector<vector<int>>dp(v.size(),vector<int>(3,0));
        dp[0][0]=-v[0];
        for(int i=1;i<v.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-v[i]);// 原本就持有 / 解冻后买入
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]);// 原本就不在冷冻期 / 新的解锁
            dp[i][2]=dp[i-1][0]+v[i];
        }
        return max(dp[v.size()-1][1],dp[v.size()-1][2]);
    }
};

714.买卖股票的最佳时机含手续费

class Solution {
public:
    int maxProfit(vector<int>& v, int fee) {
        // dp[i][j]
        // 0 持有
        // 1 不持有
        vector<vector<int>>dp(v.size(),vector<int>(2,0));
        dp[0][0]=-v[0];
        for(int i=1;i<v.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-v[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+v[i]-fee);
        }
        return max(dp[v.size()-1][0],dp[v.size()-1][1]);
    }
};

第九章动态规划part13

● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

详细布置

300.最长递增子序列

今天开始正式子序列系列，本题是比较简单的，感受感受一下子序列题目的思路。视频讲解：https://www.bilibili.com/video/BV1ng411J7xP https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html

674. 最长连续递增序列

本题相对于昨天的动态规划：300.最长递增子序列最大的区别在于“连续”。先尝试自己做做，感受一下区别
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v https://programmercarl.com/0674.%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E9%80%92%E5%A2%9E%E5%BA%8F%E5%88%97.html

718. 最长重复子数组

稍有难度，要使用二维dp数组了视频讲解：https://www.bilibili.com/video/BV178411H7hV https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html

300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& v) {
        // dp[i] 表示以i结尾的LIS的长度
        int res = 1;
        vector<int>dp(v.size(),1);
        for(int i = 1;i<v.size();i++){
            for(int j = 0;j<i;j++) {
                if(v[i]>v[j])dp[i]=max(dp[i],dp[j]+1);
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

674. 最长连续递增序列

好像比上一题还简单

class Solution {
public:
    int findLengthOfLCIS(vector<int>& v) {
        // dp[i] 表示以i结尾的CLIS的长度
        int res = 1;
        vector<int>dp(v.size(),1);
        for(int i = 1;i<v.size();i++){
            if(v[i]>v[i-1])dp[i]=max(dp[i],dp[i-1]+1);
            res = max(res, dp[i]);
        }
        return res;
    }
};

718. 最长重复子数组

抄了随想路

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

第九章动态规划part14 ● 1143.最长公共子序列 ● 1035.不相交的线
● 53. 最大子序和动态规划

详细布置

1143.最长公共子序列

体会一下本题和 718. 最长重复子数组的区别
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html

1035.不相交的线

其实本题和 1143.最长公共子序列是一模一样的，大家尝试自己做一做。视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html

最大子序和

这道题我们用贪心做过，这次再用dp来做一遍视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5 https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

1143.最长公共子序列

抄了随想录

class Solution {
public:
    int longestCommonSubsequence(string v, string w) {
        // dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        vector<vector<int>>dp(v.size()+1, vector<int>(w.size()+1, 0));
        int result = 0;
        for (int i = 1; i <= v.size(); i++) {
            for (int j = 1; j <= w.size(); j++) {
                if (v[i - 1] == w[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

1035.不相交的线

原来需要转化成‘最长公共子序列的长度’，一下子真不会

class Solution {
public:
    int maxUncrossedLines(vector<int>& v, vector<int>& w) {
        // dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        vector<vector<int>>dp(v.size()+1, vector<int>(w.size()+1, 0));
        int result = 0;
        for (int i = 1; i <= v.size(); i++) {
            for (int j = 1; j <= w.size(); j++) {
                if (v[i - 1] == w[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

53. 最大子序和

自己做的喜喜

class Solution {
public:
    int maxSubArray(vector<int>& v) {
        // dp[i] 以前i个数结尾的连续子数组最大和
        int res = v[0];
        vector<int>dp(v.size(),0);
        dp[0]=res;
        for(int i=1;i<v.size();i++){
            dp[i]=max(v[i],dp[i-1]+v[i]);
            res=max(res,dp[i]);
        }
        return res;
    }
};

第九章动态规划part15

详细布置

392.判断子序列

这道题目算是编辑距离问题的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的编辑距离问题了

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

115.不同的子序列

但相对于刚讲过 392.判断子序列，本题就有难度了，感受一下本题和 392.判断子序列的区别。

https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

392.判断子序列

抄了随想录

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // dp[i][j] 表示以下标i-1为结尾的字符串s，
        // 和以下标j-1为结尾的字符串t，
        // 相同子序列的长度为dp[i][j]
        vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=1;i<s.size()+1;i++){
            for(int j=i;j<t.size()+1;j++){
                if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=dp[i][j-1];
            }
        }
        return dp[s.size()][t.size()]==s.size();
    }
};

115.不同的子序列

扇贝力扣

最后一个测试案例答案是-1

递推公式想不清楚啊啊嗷嗷啊

class Solution {
public:
    int numDistinct(string s, string t) {
        // dp[i][j] = s[0:i-1]的子序列中t[0:j-1]出现的次数
        vector<vector<unsigned long long>>dp(s.size()+1,vector<unsigned long long>(t.size()+1,0));
        dp[0][0]=1;
        // for(int i=1;i<t.size()+1;i++)dp[0][i]=1;
        for(int j=1;j<s.size()+1;j++)dp[j][0]=1;
        // dp[i][j]+=dp[i][j-1]
        // if(s[i-1]==t[j-1])dp[i][j]+=dp[i-1][j-1]
        for(int i=1;i<s.size()+1;i++)
        for(int j=1;j<t.size()+1;j++){
            if(s[i-1]==t[j-1])
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            else
            dp[i][j]=dp[i-1][j];
        }
        return int(dp[s.size()][t.size()]);
    }
};

第九章动态规划part16

详细布置

583. 两个字符串的删除操作

自己做的喜喜

class Solution {
public:
    int minDistance(string s, string t) {
        // dp[i][j]：s[0:i-1] vs t[0:j-1]
        // 想要达到相等，所需要删除元素的最少次数
        vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int j=1;j<t.size()+1;j++)dp[0][j]=j;
        for(int j=1;j<s.size()+1;j++)dp[j][0]=j;
        for(int i=1;i<s.size()+1;i++)
        for(int j=1;j<t.size()+1;j++)
        {
            if(s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
        return dp[s.size()][t.size()];
    }
};

72. 编辑距离

class Solution {
public:
    int minDistance(string s, string t) {
        // s[0:i-1] vs t[0:j-1] 最近编辑距离为dp[i][j]
        vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int j=1;j<t.size()+1;j++)dp[0][j]=j;
        for(int j=1;j<s.size()+1;j++)dp[j][0]=j;

        for(int i=1;i<s.size()+1;i++)
        for(int j=1;j<t.size()+1;j++)
        {
            if(s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1];
            } else {
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
        return dp[s.size()][t.size()];
    }
};

第九章动态规划part17

● 647. 回文子串
● 516.最长回文子序列 ● 动态规划总结篇

今天我们就要结束动态规划章节了，大家激不激动！！！

详细布置

647. 回文子串

动态规划解决的经典题目，如果没接触过的话，别硬想直接看题解。 https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html

516.最长回文子序列

回文子串，求的是回文子串，而本题要求的是回文子序列，大家要搞清楚两者之间的区别。 https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html

动态规划总结篇

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html

647. 回文子串

抄了随想录

class Solution {
public:
    int countSubstrings(string s) {
        // 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

516.最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
        vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& v) {
        vector<int>res(v.size(),0);
        // 1
        // 1 1
        // 1 1 1
        vector<int>s;
        for(int i=0;i<v.size();i++){
            while(!s.empty()&&v[s.back()]<v[i])
            {
                int idx=s.back();
                s.pop_back();
                res[idx]=i-idx;
            }
            s.push_back(i);
        }
        return res;
    }
};

496. 下一个更大元素 I

从代码来看，v1的作用就是用来映射一次，增加了一层映射

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>&v1,vector<int>&v2) {
        vector<int>res(v1.size(),-1);
        unordered_map<int, int> m; // key:下标元素，value：下标
        for (int i = 0; i < v1.size(); i++) {
            m[v1[i]] = i;
        }
        vector<int>s;
        for(int i=0;i<v2.size();i++){
            while(!s.empty()&&v2[s.back()]<v2[i]){
                int idx = s.back();
                s.pop_back();
                if (m.find(v2[idx])!=m.end()){
                    res[m[v2[idx]]]=v2[i];
                }
            }
            s.push_back(i);
        }
        return res;
    }
};

503.下一个更大元素II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& v) {
        vector<int>res(v.size(),-1);
        vector<int>s;
        int n = v.size();
        for(int i=0;i<n*2;i++){
            while(!s.empty()&&v[s.back()]<v[i%n]){
                int idx = s.back();
                s.pop_back();
                res[idx]=v[i%n];
            }
            s.push_back(i%n);
        }
        return res;
    }
};

42. 接雨水

需要考虑前两个

class Solution {
public:
    int trap(vector<int>& v) {
        int res = 0;
        vector<int>s;
        for(int i=0;i<v.size();i++){
            while(!s.empty()&&v[s.back()]<=v[i]){
                int idx = s.back();
                s.pop_back();
                if(!s.empty()){
                    int left =  s.back();
                    int width = i - left - 1;
                    int height = min(v[left],v[i]) - v[idx];
                    res += width * height;
                }
            }
            s.push_back(i);
        }
        return res;
    }
};

84.柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& v) {
        int res = 0;
        vector<int>rightfirstsmallerthanmine(v.size(),v.size());
        vector<int>leftffirstsmallerthanmine(v.size(),-1);
        vector<int>s;
        for(int i=0;i<v.size();i++){
            while(!s.empty()&&v[s.back()]>v[i]){
                int idx = s.back();
                s.pop_back();
                rightfirstsmallerthanmine[idx]=i;
            }
            s.push_back(i);
        }
        s.clear();
        for(int i=v.size()-1;i>=0;i--){
            while(!s.empty()&&v[s.back()]>v[i]){
                int idx = s.back();
                s.pop_back();
                leftffirstsmallerthanmine[idx]=i;
            }
            s.push_back(i);
        }
        for(int i=0;i<v.size();i++){
            int width = rightfirstsmallerthanmine[i] - leftffirstsmallerthanmine[i]-1;
            int height = v[i];
            res = max(res, width*height);
        }
        return res; 
    }
};

代码随想录算法训练营刷题笔记