leetcode-cn 2021年3月第一周 每日一题

[Kydaa]

3月2日

304. 二维区域和检索 - 矩阵不可变

二维前缀和

type NumMatrix struct {
    matrix [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    if m == 0 {
        return NumMatrix{}
    }
    n := len(matrix[0])
    newMatrix := make([][]int, m+1) 
    for i:=0; i<=m; i++ {
        newMatrix[i] = make([]int, n+1)
    }
    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            newMatrix[i][j] = newMatrix[i-1][j] + matrix[i-1][j-1] + newMatrix[i][j-1] - newMatrix[i-1][j-1]
        }
    }
    return NumMatrix{newMatrix}
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) (ans int) {
    return this.matrix[row2+1][col2+1] - this.matrix[row2+1][col1] - this.matrix[row1][col2+1] + this.matrix[row1][col1]
}

[kingeasternsun]

303. 区域和检索 - 数组不可变

难度简单298收藏分享切换为英文接收动态反馈

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j （ i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

type NumArray struct {
	PreSum []int //前缀和
}

func Constructor(nums []int) NumArray {

	preSum := make([]int, len(nums))
	for i := range nums {
		if i == 0 {
			preSum[i] = nums[i]
		} else {
			preSum[i] = nums[i] + preSum[i-1]
		}
	}
	return NumArray{PreSum: preSum}
}

func (this *NumArray) SumRange(i int, j int) int {

	if i > j {
		return 0
	}

	if i == 0 {
		return this.PreSum[j]
	}
	return this.PreSum[j] - this.PreSum[i-1]
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(i,j);
 */

 struct NumArray {
    pre_sum: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NumArray {
    fn new(nums: Vec<i32>) -> Self {
        let mut pre = 0;
        let mut pre_sum: Vec<i32> = nums
            .iter()
            .map(|x| {
                pre += x;
                pre
            })
            .collect();

        NumArray { pre_sum: pre_sum }
    }

    fn sum_range(&self, i: i32, j: i32) -> i32 {
        if i > j {
            return 0;
        }
        if i == 0 {
            return self.pre_sum[j as usize];
        }

        return self.pre_sum[j as usize] - self.pre_sum[i as usize - 1];
    }
}

[kingeasternsun]

304

type NumMatrix struct {
	Sum    [][]int
	Matrix [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	if len(matrix) == 0 {
		return NumMatrix{}
	}

	sum := make([][]int, len(matrix))
	for i := range sum {
		sum[i] = make([]int, len(matrix[0]))
	}

	sum[0][0] = matrix[0][0]
	for i := 1; i < len(matrix[0]); i++ {
		sum[0][i] = sum[0][i-1] + matrix[0][i]
	}

	for i := 1; i < len(matrix); i++ {
		sum[i][0] = sum[i-1][0] + matrix[i][0]
	}

	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j]
		}
	}

	return NumMatrix{Sum: sum, Matrix: matrix}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {

	switch {
	case row1 == row2 && col1 == col2:
		return this.Matrix[row1][col2]
	case row1 == 0 && col1 == 0:
		return this.Sum[row2][col2]
	case row1 == 0:
		return this.Sum[row2][col2] - this.Sum[row2][col1-1]
	case col1 == 0:
		return this.Sum[row2][col2] - this.Sum[row1-1][col2]
	default:
		return this.Sum[row2][col2] - this.Sum[row2][col1-1] - this.Sum[row1-1][col2] + this.Sum[row1-1][col1-1]
	}

}

[DDY1024]

// 2021.03.03

func lowbit(x int) int {
    return x & (-x)
}

func countBits(num int) []int {
    bits := make([]int, num+1)
    for i := 1; i <= num; i++ {
          bits[i] = bits[i&(i-1)] + 1
    }
    return bits
}

[Kydaa]

338. 比特位计数

曾经在腾讯面试中遇到过这题
本质上是一道动态规划题。

func countBits(num int) []int {
    ret := make([]int, num+1)
    index, next := 1, 1<<1
    for i:=1 ;i<=num; i++ {
        if i >= next {
            index, next = next, next<<1
        }
        ret[i] = 1 + ret[i-index]
    }
    return ret
}

[kingeasternsun]

338

/*
 * @Description: 338
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-03 11:00:27
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-03 11:07:40
 * @FilePath: \338countBits\338.go
 */
package leetcode

func countBits(num int) []int {
	res := make([]int, num+1)
	for i := 1; i < num+1; i++ {
		res[i] = res[i>>1] + i&1
	}
	return res
}

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-03 11:10:53
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-03 11:22:34
 * @FilePath: \338countBits\count_bits\src\lib.rs
 */
pub struct Solution;
impl Solution {
    pub fn count_bits(num: i32) -> Vec<i32> {
        let num = num as usize;
        let mut res = vec![0i32; num+1];
        for i in 1..res.len() {
            res[i] = res[i >> 1] + (i  & 1) as i32;
        }
        res
    }
    pub fn count_bits1(num: i32) -> Vec<i32> {
        
        (0..=num).map(|x|{
            x.count_ones() as i32
        }).collect()
    }
}
#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::count_bits(5), vec![0, 1, 1, 2, 1, 2]);
        assert_eq!(Solution::count_bits1(5), vec![0, 1, 1, 2, 1, 2]);
    }
}

[kingeasternsun]

354

// 通过提前对信封按照 某一个方向排序，变为求最大递增子序列的问题
func maxEnvelopes(envelopes [][]int) int {

	if len(envelopes) <= 1 {
		return len(envelopes)
	}

	sort.Slice(envelopes, func(i, j int) bool {
		//如果宽度w相同，那么两个就不能互相套进去，所以这里要把高度h大的放在前面。
		//不然的话，就有可能造成把宽度w相同，h小的装进h大的信封里面
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] > envelopes[j][1]
		}

		return envelopes[i][0] < envelopes[j][0]
	})

	//接下来，就根据各个信封的h构成的数组中，查找最大的递增子序列,转为 300 https://leetcode-cn.com/problems/longest-increasing-subsequence/
	hs := []int{}
	for _, v := range envelopes {

		id := sort.SearchInts(hs, v[1])
		if id == len(hs) {
			hs = append(hs, v[1])
		} else {
			hs[id] = v[1]
		}
	}

	return len(hs)

}

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-04 09:44:30
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-04 10:09:29
 * @FilePath: \max_envelopes\src\lib.rs
 */
pub struct Solution;

use std::cmp::Ordering;
impl Solution {
    pub fn max_envelopes(envelopes: Vec<Vec<i32>>) -> i32 {
        if envelopes.len() == 0 {
            return 0;
        }

        let mut envelopes = envelopes;

        //先排序，按照 宽w进行排序。如果宽w相同，就不能互相套，所以要把高h大的放前面
        envelopes.sort_unstable_by(|a, b| {
            if a[0].cmp(&b[0]) == Ordering::Equal {
                b[1].cmp(&a[1])
            } else {
                a[0].cmp(&b[0])
            }
        });


        //接下来转为求 高h 的最长递增子序列
        let mut hs = Vec::new();
        for e in &envelopes{
            let idx =  hs.binary_search(&e[1]).unwrap_or_else(|x|x);
            if idx == hs.len(){
                hs.push(e[1]);
            }else{
                hs[idx] = e[1];
            }
            
        }

        hs.len() as i32

    }
}
#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::max_envelopes(vec![vec![5,4],vec![6,4],vec![6,7],vec![2,3]]),3);
    }
}

[kingeasternsun]

232

//先实现stack
type MyStack []int

func (this *MyStack) Push(x int) {
	*this = append(*this, x)
}

func (this *MyStack) Pop() int {
	x := (*this)[len(*this)-1]
	*this = (*this)[:len(*this)-1]
	return x
}
func (this MyStack) Peek() int {
	return this[len(this)-1]
}
func (this MyStack) Empty() bool {
	return len(this) == 0
}

/*
	1. 双栈，一个用来push，一个用来pop
	2. pop的时候优先从OutStatck中Pop，OutStatck为空,就把InStack中的数据导入到OutStack中，再从OutStatck中Pop
*/
type MyQueue struct {
	InStack   MyStack
	OutStatck MyStack
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
	return MyQueue{}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {

	this.InStack.Push(x)
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
	if !this.OutStatck.Empty() {
		return this.OutStatck.Pop()
	}

	for !this.InStack.Empty() {
		this.OutStatck.Push(this.InStack.Pop())
	}
	return this.OutStatck.Pop()
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
	if !this.OutStatck.Empty() {
		return this.OutStatck.Peek()
	}
	for !this.InStack.Empty() {
		this.OutStatck.Push(this.InStack.Pop())
	}
	return this.OutStatck.Peek()
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
	return this.InStack.Empty() && this.OutStatck.Empty()
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

[Kydaa]

503. 下一个更大元素 II

单调栈

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    queue := make([]int, 0)
    ret := make([]int, n)
    for i := range ret {
        ret[i] = -1
    }
    var helper func() 
    helper = func() {
        for i := range nums {
            for len(queue)>0 && nums[queue[len(queue)-1]]<nums[i] {
                ret[queue[len(queue)-1]] = nums[i]
                queue = queue[:len(queue)-1]
            }
            queue = append(queue, i)
        }
    }
    helper()
    helper()
    return ret
}

[kingeasternsun]

503

单调栈

/*
 * @Description: 503
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-06 13:04:11
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-06 14:00:10
 * @FilePath: /503nextGreaterElements/503.go
 */

/*
构造递减栈，保存的是nums中的下标，
当要加入一个新 nums[i] value的时候，从栈顶到栈地逐个比较，
	如果栈顶比value小，这个value就是比栈顶 nums[j]大的第一个元素，然后弹出栈顶
	最后终止后，将i加入到栈
*/
package leetcode

func nextGreaterElements(nums []int) []int {
	if len(nums) == 0 {
		return nil
	}
	cnt := len(nums)
	res := make([]int, cnt)
	for i := 0; i < cnt; i++ {
		res[i] = -1
	}
	decreStack := make([]int, 0)
	for i := 0; i < cnt*2; i++ {

		for len(decreStack) > 0 && nums[decreStack[len(decreStack)-1]] < nums[i%cnt] {
			res[decreStack[len(decreStack)-1]] = nums[i%cnt]
			decreStack = decreStack[:len(decreStack)-1]
		}

		decreStack = append(decreStack, i%cnt)

	}
	return res
}

/*
 * @Description: 
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-03-06 14:06:20
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-03-06 14:15:15
 * @FilePath: /503nextGreaterElements/next_greater_elements/src/lib.rs
 */

pub struct Solution;
impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
       
        let mut res = vec![-1;nums.len()];
        let mut decre_stack = Vec::new();

        for i in 0..nums.len()*2{
            while let Some(v) = decre_stack.last(){
                if nums[*v] >= nums[i%nums.len()]{
                    break;
                }

                res[*v] = nums[i%nums.len()];
                decre_stack.pop();
            }

            decre_stack.push(i%nums.len());
        }
        res
    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::next_greater_elements(vec![1,2,1]),vec![2,-1,2]);
    }
}

[DDY1024]

// 2021.03.08

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minCut(s string) int {
    n := len(s)
    is := make([][]bool, n)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = 0x3f3f3f3f
        is[i] = make([]bool, n)
        is[i][i] = true
    }
    for l := 2; l <= n; l++ {
        for i := 0; i + l - 1 < n; i++ {
            j := i + l - 1
            if s[i] == s[j] {
                if i + 1 > j - 1 { // len = 2
                    is[i][j] = true
                } else {
                    is[i][j] = is[i+1][j-1]
                }
            }
        }
    }

    var calc = func(idx int) int {
        if idx < 0 {
            return 0
        }
        return dp[idx]
    }
    
    for i := 0; i < n; i++ {
        for j := 0; j <= i; j++ {
            if is[j][i] {
                dp[i] = minInt(dp[i], calc(j-1)+1)
            }
        }
    }
    return dp[n-1] - 1
}