leetcode-cn 2021年1月 每日一题(已更新至 8 题)

用于分享leetcode每月中每日一题的解法,希望能抛砖引玉,互相进步

[239. 滑动窗口最大值]

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码内置详细注释

package leetcode

//224ms
func maxSlidingWindow(nums []int, k int) []int {

	if len(nums) < k {
		return nil
	}

	//使用单调队列来实现
	monoQueue := make([]int, 0)
	res := make([]int, 0) //保存结果

	for i, v := range nums {

		//从后往前,如果比monoQueue的最后一个要大,就弹出最后一个.
		for len(monoQueue) > 0 {
			if v > monoQueue[len(monoQueue)-1] {
				monoQueue = monoQueue[:len(monoQueue)-1] //弹出
			} else {
				break //注意如果遇到比monoQueue最后一个要小 或 相等 就需要停止弹出了
			}

		}

		//追加v到monoQueue里面
		monoQueue = append(monoQueue, v)

		//窗口长度还没有满k
		if i < k-1 { //注意这里是要小于k-1
			continue
		}

		//刚好满k
		if i == k-1 {
			res = append(res, monoQueue[0])
			continue
		}

		//sliding窗口最左边的要移除
		top := nums[i-k]
		//top就是最大值,那么monoque需要把左边的也移除
		if top == monoQueue[0] {
			monoQueue = monoQueue[1:]
		}

		res = append(res, monoQueue[0])

	}

	return res
}

跟239类似的题目是1696题,所以在下面也贴出来

[1696. 跳跃游戏 VI]

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步,你最多可以往前跳 k 步,但你不能跳出数组的边界。也就是说,你可以从下标 i 跳到 [i + 1, min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置(下标为 n - 1 ),你的 得分 为经过的所有数字之和。

请你返回你能得到的 最大得分 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game-vi
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码内带详细注释

maxResult_timeout是没有使用单调队列提交超时的做法

package leetcode

//https://github.com/kingeasternsun/leetcode-cn

import "math"

//dp 超时
func maxResult_timeout(nums []int, k int) int {

	if len(nums) == 0 {
		return 0
	}

	dp := make([]int, len(nums)) //表示跳在第i个位置的最大得分
	dp[0] = nums[0]

	for i := 1; i < len(nums); i++ {

		beg := i - k
		if beg < 0 {
			beg = 0
		}

		dp[i] = maxOfSlice(dp[beg:i]) + nums[i]

	}
	return dp[len(nums)-1]

}

func maxOfSlice(dp []int) int {

	res := math.MinInt32
	for _, v := range dp {
		if v > res {
			res = v
		}
	}
	return res
}

func maxResult(nums []int, k int) int {

	if len(nums) == 0 {
		return 0
	}

	dp := make([]int, len(nums)) //表示跳在第i个位置的最大得分
	dp[0] = nums[0]
	monoQueue := []int{nums[0]} //基于dp的滑窗

	for i := 1; i < len(nums); i++ {

		// dp[i] = maxOfSlice(dp[beg:i]) + nums[i]
		//类似 239题目,利用单调队列
		tmpV := monoQueue[0] + nums[i]
		dp[i] = tmpV

		//处理滑窗
		for len(monoQueue) > 0 {

			//tmpV比滑窗最后边的要大,就把最右边的剔除
			if tmpV > monoQueue[len(monoQueue)-1] {
				monoQueue = monoQueue[:len(monoQueue)-1]
			} else {
				break
			}

		}

		monoQueue = append(monoQueue, tmpV)
		// 如果当前sliding的大小超过了k,就需要从dp中剔除左边的一个,时刻让sliding窗口的大小最大为k,
		// 所以每次只需要剔除滑窗左边的一个(也就是i-k位置上的那个)就可以了
		if i >= k {
			//如果dp[i-k]刚好是最大值 ,monoQueue也需要移除左边的最大值
			if dp[i-k] == monoQueue[0] {
				monoQueue = monoQueue[1:]
			}
		}

	}
	return dp[len(nums)-1]

}

86题 分割链表

给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码加注释

维护两个链表,最后拼接起来即可


func partition(head *ListNode, x int) *ListNode {
	if head == nil {
		return nil
	}

	preAHead := &ListNode{} //用于记录大于等于x的节点
	preA := preAHead
	preBHead := &ListNode{} //用于记录小于x的节点
	preB := preBHead

	for ; head != nil; head = head.Next {
		if head.Val >= x {
			preB.Next = head
			preB = preB.Next
		} else {
			preA.Next = head
			preA = preA.Next
		}
	}

	//拼接起来
	preA.Next = preBHead.Next
	preB.Next = nil //重要 记得要置为nil

	return preAHead.Next
}

509 题目

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n ,请计算 F(n) 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

func fib(n int) int {

	cache := make(map[int]int, 0)
	return fibWithCache(n, cache)
}

func fibWithCache(n int, cache map[int]int) int {

	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}

	if v, ok := cache[n]; ok {
		return v
	}

	return fibWithCache(n-1, cache) + fibWithCache(n-2, cache)

}

123. 买卖股票的最佳时机 III

难度困难626收藏分享切换为英文接收动态反馈

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。


func max(i, j int) int {
	if i > j {
		return i
	}

	return j
}

//dp[i][k][0] 表示在第i天,已经执行了k次买入动作,今天是要卖掉
//dp[i][k][1] 表示在第i天,已经执行了k次买入动作,今天仍然持有
func maxProfit(prices []int) int {

	const maxK = 3
	pLen := len(prices)
	if pLen <= 1 {
		return 0
	}

	dp := make([][maxK][2]int, pLen)
	for i := 0; i < pLen; i++ {
		dp[i] = [maxK][2]int{}
	}
	// 对于每一天,如果k是0,也就是说没有执行过买入动作,获取的收益肯定就是0,也就是 dp[i][0][0] dp[i][0][1]都是0没问题

	for i := 0; i < pLen; i++ {

		for k := 1; k < maxK; k++ {

			if i == 0 {
				dp[i][k][0] = 0
				dp[i][k][1] = -prices[i]
			} else {
				//第i天,已经执行了k次买入,当前没有股票;那么可能是在i-1天已经执行了k次买入,手上没有股票 或 是在i-1天已经执行k次买入手上有股票,然后在i天卖出了
				dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
				//第i天,已经执行了k次买入,  当前有股票;那么可能是在i-1天已经执行了k次买入,  手上有股票 或 是在i-1天已经执行k次买入手上没有股票,然后在i天买入了
				dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
			}
		}

	}

	return dp[pLen-1][maxK-1][0]
}

1018. 可被 5 整除的二进制前缀

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

给定由若干 01 组成的数组 A。我们定义 N_i:从 A[0]A[i] 的第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。

返回布尔值列表 answer,只有当 N_i 可以被 5 整除时,答案 answer[i]true,否则为 false

go

func prefixesDivBy5(A []int) []bool {

	res := make([]bool, len(A))

	num := 0
	for i, v := range A {

		num = (num << 1) + v
		num = num % 5
		if num == 0 {
			res[i] = true
		} else {
			res[i] = false
		}

	}
	return res

}

rust



pub struct Solution;

impl Solution {
    pub fn prefixes_div_by5(a: Vec<i32>) -> Vec<bool> {
        let mut res = Vec::new();

        let mut num = 0;

        for v in a{
            num = (num<<1)+v;
            num = num%5;
            if num ==0{
                res.push(true);
            }else{
                res.push(false)
            }
        }

        res

    }
}

#[cfg(test)]
mod tests{
    use super::*;
    #[test]
    fn one(){

        assert_eq!(Solution::prefixes_div_by5(vec![0, 1, 1, 1, 1, 1]),vec![true, false, false, false, true, false]);
        assert_eq!(Solution::prefixes_div_by5(vec![1, 1, 1, 0, 1]),vec![false, false, false, false, false]);
    }
}

1584. 连接所有点的最小费用

给你一个points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-cost-to-connect-all-points
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

package leetcode

import "sort"

type Edge struct {
	x, y   int
	Length int
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func edgeLen(pi, pj []int) int {
	return abs(pi[0]-pj[0]) + abs(pi[1]-pj[1])
}

func getRoot(i int, par []int) int {

	for i != par[i] {
		i = par[i]
	}
	return i
}

func union(i, j int, par []int) bool {

	i = getRoot(i, par)
	j = getRoot(j, par)
	if i == j {
		return false
	}

	par[i] = j
	return true
}

//最小代价生成树
func minCostConnectPoints(points [][]int) int {
	edges := make([]Edge, 0)
	for i, pi := range points {
		for j := i + 1; j < len(points); j++ {
			edges = append(edges, Edge{x: i, y: j, Length: edgeLen(pi, points[j])})
		}
	}

	sort.Slice(edges, func(i, j int) bool {
		return edges[i].Length < edges[j].Length
	})

	parent := make([]int, len(points))
	for i := range parent {
		parent[i] = i
	}

	res := 0
	edgeNum := 0 //加入树的边的个数
	for _, edge := range edges {

		if union(edge.x, edge.y, parent) {
			res += edge.Length
			edgeNum++
			if edgeNum == len(points)-1 {
				return res
			}
		}

	}

	return res
}

628. 三个数的最大乘积

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

给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。


func maximumProduct(nums []int) int {

	if len(nums) == 3 {
		return nums[0] * nums[1] * nums[2]
	}

	sort.Ints(nums)

	rightMost := nums[len(nums)-1] * nums[len(nums)-2] * nums[len(nums)-3]
	//如果大于等于0 或 都小于等于0 ,那么就肯定选最大的三个返回
	if nums[0] >= 0 && nums[len(nums)-1] <= 0 {
		return rightMost
	}

	//有正数,也有负数
	/*
		1.如果只有一个负数,那么肯定还是返回最大的三个数
		2.如果两个或两个以上的负数,那么就从左边选两个最小的负数,再选右边最大的正式
	*/

	if nums[0]*nums[1]*nums[len(nums)-1] < rightMost {
		return rightMost
	}
	return nums[0] * nums[1] * nums[len(nums)-1]
}