leetcode-cn 2021年1月 2021年2月 每日一题

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

GitHub - kingeasternsun/leetcode-cn: leetcode with golang rust 觉得有帮助 还请赏个 :star:

[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]
}

1319. 连通网络的操作次数

难度中等93

用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0n-1。线缆用 connections 表示,其中 connections[i] = [a, b] 连接了计算机 ab

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections,你可以拔开任意两台直连计算机之间的线缆,并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 -1 。

DFS

//DFS 递归做法
func makeConnectedDFS(n int, connections [][]int) int {

	/*

		1. 对计算机进行dfs或bfs遍历,看用到多少边 used
		2. 计算m个孤立网络
		3. 看剩余的边数是否 大于m-1
	*/

	g := make(map[int][]int, 0)
	for _, c := range connections {

		g[c[0]] = append(g[c[0]], c[1])
		g[c[1]] = append(g[c[1]], c[0])
	}


	usedEdge := 0
	visited := make([]bool, n)

	groupNum := 0

	var dfs func(i int)
	dfs = func(i int) {
		if visited[i] {
			return
		}

		visited[i] = true

		//访问i的相邻主机
		for _, j := range g[i] {
			if visited[j] {
				continue
			}

			usedEdge++
			// visited[j] = true
			dfs(j)

		}

	}

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

		if visited[i] {
			continue
		}

		groupNum++
		dfs(i)

	}

	if len(connections)-usedEdge < (groupNum - 1) {
		return -1
	}

	return groupNum - 1
}


BFS



func makeConnected(n int, connections [][]int) int {

	/*

		1. 对计算机进行dfs或bfs遍历,看用到多少边 used
		2. 计算m个孤立网络
		3. 看剩余的边数是否 大于m-1
	*/

	g := make(map[int][]int, 0)
	for _, c := range connections {

		g[c[0]] = append(g[c[0]], c[1])
		g[c[1]] = append(g[c[1]], c[0])
	}

	//bfs遍历
	usedEdge := 0
	visited := make([]bool, n)

	groupNum := 0

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

		if visited[i] {
			continue
		}

		groupNum++
		usedEdge += bfs(g, i, visited)

	}

	if len(connections)-usedEdge < (groupNum - 1) {
		return -1
	}

	return groupNum - 1
}

func bfs(g map[int][]int, root int, visited []bool) (usedEdge int) {

	cur := []int{root}
	visited[root] = true

	for len(cur) > 0 { //cur中都是已经被标注过访问的

		next := make([]int, 0)

		for _, i := range cur {

			for _, j := range g[i] {

				if visited[j] {
					continue
				}

				visited[j] = true
				usedEdge++
				next = append(next, j)
			}

		}

		cur = next
	}

	return
}

959. 由斜杠划分区域

难度中等138

在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /\ 或空格构成。这些字符会将方块划分为一些共边的区域。

(请注意,反斜杠字符是转义的,因此 \"\\" 表示。)。

返回区域的数目。


func findRoot(i int, parent []int) int {

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

func union(i int, j int, parent []int) {

	i = findRoot(i, parent)
	j = findRoot(j, parent)
	parent[j] = i

}

//讲每个方块分为4部分 进行合并
func regionsBySlashes(grid []string) int {

	rows := len(grid)
	if rows == 0 {
		return 0
	}

	cols := len(grid[0])
	if cols == 0 {
		return 0
	}

	parent := make([]int, 4*rows*cols)
	for i := 0; i < len(parent); i++ {
		parent[i] = i
	}

	//向左,向上合并
	for rowID := 0; rowID < rows; rowID++ {

		for colID := 0; colID < cols; colID++ {
			squreID := rowID*cols + colID //方块的id

			//分为4块,顺时针编号,0号肯定和上面的2号能够合并, 3号肯定和左边的1号能够合并
			// 0 号和上面的2合并
			if rowID > 0 {
				union(squreID*4, (squreID-cols)*4+2, parent)
			}

			//3 号和左边的1合并
			if colID > 0 {
				union(squreID*4+3, (squreID-1)*4+1, parent)
			}

			// 当前方块中的 1和2可以合并,3和0可以合并
			if grid[rowID][colID] == '/' {
				union(squreID*4+1, squreID*4+2, parent)
				union(squreID*4, squreID*4+3, parent)

			} else if grid[rowID][colID] == '\\' { // 当前方块中的 0和1可以合并,2和3可以合并
				union(squreID*4, squreID*4+1, parent)
				union(squreID*4+2, squreID*4+3, parent)
			} else {
				union(squreID*4+1, squreID*4+2, parent)
				union(squreID*4+2, squreID*4+3, parent)
				union(squreID*4, squreID*4+3, parent)
			}

		}

	}

	groupSet := make(map[int]struct{}, 0)
	for i := 0; i < 4*rows*cols; i++ {
		groupSet[findRoot(i, parent)] = struct{}{}
	}

	return len(groupSet)
}

1579. 保证图可完全遍历


/*
解析:
由图论可知一个n结点无向连通图至少要n-1
假设最优类型1选择了 x条,类型2选择了y 条,类型3选择了z条
x+z=n-1 (1)
y+z=n-1 (2)
图上说要删除最多的边
那其实就是要求x+y+z最小。
对1,2式相加并移项
x+y+z=2n-2-z
从上式可以看出 z大越大越好,也就是类型3的边越多越好。
所以,结论就是先把类型3的边用了,再用1,2.

疑问1 有没有可能先用类型3的边然后导致构造不出连通图。
答:先选择3,可以认为在原来1,2的基础上增加了一些边(这种情况只会增加连通的可能性)。根据最小生成树原理,在权值相同的情况下,选择的顺序是不影响连通性的。

疑问2 有没有可能选择了类型3中的某条边,会导致最终结果不是最优的。
答:结论是不会。假设alice, bob现在都已经连通了,也就是他们都选择了 x=n-1, y=n-1, 现在有一条3边过来,
加入到alice, bob以后必然会产生环,所以必然可以拿走一条原来的边。相当于只要类型3选择一条,就可以拿走1,2各一条。从公式也可以反应出来。
 */

/*
并查集,判连通用
*/
type UnionFindSet struct {
	father  []int // 存储结点的父亲
	height  []int // 存储结点的父亲
	nodeNum int   // 总结点个数
}

func (us *UnionFindSet) InitUnionSet(n int) {
	us.nodeNum = n + 1 // 不加也可以,有人喜欢以0开头
	us.father = make([]int, us.nodeNum)
	us.height = make([]int, us.nodeNum)
	for i, _ := range us.father {
		us.father[i] = i
		us.height[i] = 1
	}
}

func (us *UnionFindSet) FindV2(x int) int {
	root := x // 保存好路径上的头结点
	for us.father[root] != root {
		root = us.father[root]
	}
	/*
		从头结点开始一直往根上遍历
		把所有结点的father直接指向root。
	*/
	for us.father[x] != x {
		// 一定要先保存好下一个结点,下一步是要对us.father[x]进行赋值
		temp := us.father[x]
		us.father[x] = root
		x = temp
	}

	return root
}

/*
需要加入height[]属性,初始化为1.
*/
//合并结点
func (us *UnionFindSet) UnionV2(x, y int) bool {
	x = us.FindV2(x)
	y = us.FindV2(y)
	if x == y {
		return false
	}
	if us.height[x] < us.height[y] {
		us.father[x] = y
	} else if us.height[x] > us.height[y] {
		us.father[y] = x
	} else {
		us.father[x] = y
		us.height[y]++
	}
	return true
}

func isLinked(us *UnionFindSet, n int) bool {
	rootNum :=0
	for i:=1;i<=n;i++ {
		if us.FindV2(i)==i{
			rootNum++
		}
	}

	return rootNum==1
}

func maxNumEdgesToRemove(n int, edges [][]int) int {
	// 排序,把类型为3的排到最前面
	sort.Slice(edges, func(i, j int) bool {
		return edges[i][0] > edges[j][0]
	})

	usAlice, usBob := &UnionFindSet{}, &UnionFindSet{} // 初始化alice 和bob的并查集
	usAlice.InitUnionSet(n + 1)                        // 编号从1开始的
	usBob.InitUnionSet(n + 1)

	sum := 0 // 去除的边
	for _, edge := range edges {
		switch edge[0] {
		case 3:
			if !usAlice.UnionV2(edge[1], edge[2]) { // 加不上, 删除一条边
				sum++
			}
			usBob.UnionV2(edge[1], edge[2]) // bob同步加上

		case 2:
			// 往bob上加
			if !usBob.UnionV2(edge[1], edge[2]) { // 加不上删除一条
				sum++
			}
		case 1:
			// 往alice上加
			if !usAlice.UnionV2(edge[1], edge[2]) { // 加不上删除一条
				sum++
			}
		}
	}

	// 判断是不是都连通了
	if !isLinked(usAlice, n) || !isLinked(usBob, n) {
		// 至少有一个未连通
		return -1
	}

	return sum
}
1赞

1579 最大删除边数

//  1、反证法:类型 3 的边对应着两个连通图中的两条边,如果将该条边删除通过添加类型 1 或 类型 2 的边使得两个连通图均保持连通性,则需要加两条边。所以优先选择类型 3 的边。
// 2. 无向连通图只看不存在环情况下的边数,第 3 类边的选择不会影响图连通性;因为有环情况下回到了结论 1
func findSet(x int, parent[]int) int {
    if parent[x] < 0 {
        return x
    }
    parent[x] = findSet(parent[x], parent)
    return parent[x]
}

func unionSet(x, y int, parent []int) int {
    r1, r2 := findSet(x, parent), findSet(y, parent)
    if r1 == r2 {
        return 0
    }
    if parent[r1] < parent[r2] {
        parent[r1] += parent[r2]
        parent[r2] = r1
    } else {
        parent[r2] += parent[r1]
        parent[r1] = r2
    }
    return 1
}

func maxNumEdgesToRemove(n int, edges [][]int) int {
    p1, p2 := make([]int, n+1), make([]int, n+1)
    for i := 0; i <= n; i++ {
        p1[i], p2[i] = -1, -1
    }
    
    c1, c2, c3, m := 0, 0, 0, len(edges)
    for i := 0; i < m; i++ {
        // switch edges[i][0] {
        //     case
        // }
        if edges[i][0] == 3 {
            c3 += unionSet(edges[i][1], edges[i][2], p1)|unionSet(edges[i][1], edges[i][2], p2)
        }
    }
    for i := 0; i < m; i++ {
        //if edges[i][0] == 1 {
        switch edges[i][0] {
            case 1:
                c1 += unionSet(edges[i][1], edges[i][2], p1)
            case 2:
                c2 += unionSet(edges[i][1], edges[i][2], p2)
        }
        //} 
    }
    r1, r2 := findSet(1, p1), findSet(1, p2)
    if -p1[r1] < n || -p2[r2] < n {
        return -1
    }
    return m - c3 - c1 - c2
}
1赞

// 力扣 → 724
// 从左向右枚举

func pivotIndex(nums []int) int {
    n, sum := len(nums), 0
    for i := 0; i < n; i++ {
        sum += nums[i]
    }
    for i, cur := 0, 0; i < n; i++ {
        if sum - cur - nums[i] == cur {
            return i
        }
        cur += nums[i]
    }
    return -1 
}
1赞

1579. 保证图可完全遍历

难度困难109

Alice 和 Bob 共有一个无向图,其中包含 n 个节点和 3 种类型的边:

  • 类型 1:只能由 Alice 遍历。
  • 类型 2:只能由 Bob 遍历。
  • 类型 3:Alice 和 Bob 都可以遍历。

给你一个数组 edges ,其中 edges[i] = [typei, ui, vi] 表示节点 uivi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下,找出可以删除的最大边数。如果从任何节点开始,Alice 和 Bob 都可以到达所有其他节点,则认为图是可以完全遍历的。

返回可以删除的最大边数,如果 Alice 和 Bob 无法完全遍历图,则返回 -1 。


type Graph struct {
	Parent []int
	Height []int //以当前点为root节点的树的高度,不用height就会超时
}

func (g *Graph) Init(n int) {

	g.Parent = make([]int, n)
	g.Height = make([]int, n)
	for i := range g.Parent {
		g.Parent[i] = i
	}
	return
}

func (g *Graph) GetRoot(i int) int {
	for i != g.Parent[i] {
		i = g.Parent[i]
	}

	return i
}

func (g *Graph) Union(i, j int) bool {
	i = g.GetRoot(i)
	j = g.GetRoot(j)
	if i == j {
		return false
	}

	hi := g.Height[i]
	hj := g.Height[j]
	if hi > hj {
		g.Parent[j] = i
	} else if hi < hj {
		g.Parent[i] = j
	} else {
		g.Parent[j] = i
		g.Height[i]++
	}

	return true
}

//是否全连接
func (g *Graph) IfLinkAll() bool {
	pre := g.GetRoot(0)
	for i := 1; i < len(g.Parent); i++ {
		if g.GetRoot(i) != pre {
			return false
		}
	}
	return true
}

/*
参考
https://mp.weixin.qq.com/s/Ug324o1wPf4YoaLrH30khQ
1. 优先通过两个窦可以访问的边进行连接
*/
func maxNumEdgesToRemove(n int, edges [][]int) int {

	if n <= 1 {
		return 0
	}

	// gA, gB := Graph{}, Graph{}
	// gA.Init(n)
	// gB.Init(n)

	gs := make([]Graph, 2)
	for i := range gs {
		gs[i].Init(n)
	}

	delNum := 0
	//公共边放在前面
	// sort.Slice(edges, func(i, j int) bool {
	// 	return edges[i][0] > edges[j][0]
	// })

	for _, edge := range edges {

		if edge[0] == 3 {

			ua := gs[0].Union(edge[1]-1, edge[2]-1)
			ub := gs[1].Union(edge[1]-1, edge[2]-1)
			if ua || ub { //必须的,不能删除
				continue
			}

			delNum++
		}

	}

	for _, edge := range edges {

		if edge[0] == 3 {
			continue
		}
		u := gs[edge[0]-1].Union(edge[1]-1, edge[2]-1)
		if !u {
			delNum++
		}

	}

	for _, g := range gs {
		if !g.IfLinkAll() {
			return -1
		}
	}

	return delNum

}

微信图片_20210129144408

1631. 最小体力消耗路径

难度中等138

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ,其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ,且你希望去最右下角的格子 (rows-1, columns-1) (注意下标从 0 开始编号)。你每次可以往 四个方向之一移动,你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值


//二分法 加DFS  76 ms	7.8 MB
func minimumEffortPathDFS(heights [][]int) int {
	if len(heights) == 0 && len(heights[0]) == 0 {
		return 0
	}

	beg := 0
	end := 1000000
	for beg < end {
		mid := (end-beg)/2 + beg
		g := NewGraph(heights)
		if g.DFS(0, 0, mid) { //如果可以,就缩小高度再尝试
			end = mid
		} else {
			beg = mid + 1
		}

	}

	return beg

}

//184 ms	7.3 MB
func minimumEffortPathBFS(heights [][]int) int {
	if len(heights) == 0 && len(heights[0]) == 0 {
		return 0
	}

	beg := 0
	end := 1000000
	for beg < end {
		mid := (end-beg)/2 + beg
		g := NewGraph(heights)
		if g.BFS(mid) { //如果可以,就缩小高度再尝试
			end = mid
		} else {
			beg = mid + 1
		}

	}

	return beg

}

var dirs = []int{0, 1, 0, -1, 0}

func abs(x int) int {
	if x > 0 {
		return x
	}

	return -x
}

type Graph struct {
	heights [][]int
	visted  []bool
	rows    int
	cols    int
}

func NewGraph(heights [][]int) *Graph {

	return &Graph{
		heights: heights,
		rows:    len(heights),
		cols:    len(heights[0]),
		visted:  make([]bool, len(heights)*len(heights[0])),
	}
}

//判断h是否可以
func (g *Graph) DFS(x, y int, h int) bool {

	g.visted[x*g.cols+y] = true
	//可以到达最下角
	if x == g.rows-1 && y == g.cols-1 {
		return true
	}

	//对于4个方向
	for i := 0; i < 4; i++ {
		nx := x + dirs[i]
		ny := y + dirs[i+1]
		if 0 <= nx && nx < g.rows && 0 <= ny && ny < g.cols {
			if g.visted[nx*g.cols+ny] {
				continue
			}

			//体力消耗不大于h,就可以跳入nx,ny
			if abs(g.heights[x][y]-g.heights[nx][ny]) <= h {
				if g.DFS(nx, ny, h) {
					return true
				}
			}
		}

	}

	return false
}

func (g *Graph) BFS(h int) bool {

	cur := []int{0}
	g.visted[0] = true
	for len(cur) > 0 {

		newPoints := make([]int, 0)
		for _, v := range cur {
			x := v / g.cols
			y := v % g.cols

			if x == g.rows-1 && y == g.cols-1 {
				return true
			}

			//对于4个方向
			for i := 0; i < 4; i++ {
				nx := x + dirs[i]
				ny := y + dirs[i+1]
				if 0 <= nx && nx < g.rows && 0 <= ny && ny < g.cols {
					if g.visted[nx*g.cols+ny] {
						continue
					}

					//体力消耗不大于h,就可以跳入nx,ny
					if abs(g.heights[x][y]-g.heights[nx][ny]) <= h {
						g.visted[nx*g.cols+ny] = true
						newPoints = append(newPoints, nx*g.cols+ny)
					}
				}

			}

		}

		cur = newPoints

	}
	return false
}

// 力扣
// 1. 最大值最小 → 二分 + 判定
// 至于连通性判断:搜索 、并查集均可;搜索效率更高。

func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func findSet(x int, parent []int) int {
	if parent[x] < 0 {
		return x
	}
	parent[x] = findSet(parent[x], parent)
	return parent[x]
}

func unionSet(x, y int, parent []int) int {
	r1, r2 := findSet(x, parent), findSet(y, parent)
	if r1 == r2 {
		return 0
	}
	if parent[r1] < parent[r2] {
		parent[r1] += parent[r2]
		parent[r2] = r1
	} else {
		parent[r2] += parent[r1]
		parent[r1] = r2
	}
	return 1
}

func minimumEffortPath(heights [][]int) int {
    n, m := len(heights), len(heights[0])
    parent := make([]int, n*m)
    maxH, dx, dy := 0, []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            for k := 0; k < 4; k++ {
                ii, jj := i + dx[k], j + dy[k]
                if ii >= 0 && ii < n && jj >= 0 && jj < m {
                    maxH = maxInt(maxH, absInt(heights[i][j]-heights[ii][jj]))
                }
            }
        }
    }
    var check = func(h int) bool {
        for i := 0; i < n*m; i++ {
            parent[i] = -1
        }
        for i := 0; i < n; i++ {
            for j := 0; j < m; j++ {
                for k := 0; k < 4; k++ {
                    ii, jj := i + dx[k], j + dy[k]
                    if ii >= 0 && ii < n && jj >= 0 && jj < m && absInt(heights[i][j]-heights[ii][jj]) <= h {
                        unionSet(i*m+j, ii*m+jj, parent)
                    }
                }
            }
        }
        return findSet(0, parent) == findSet(n*m-1, parent)
    }
    l, r, ans := 0, maxH, -1
    for l <= r {
        mid := l + (r-l)/2
        if check(mid) {
            ans = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return ans
}

// 2. 最短路径 → dijkstra + heap 、spfa

func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	dis := make([]int, n*m)
	for i := 1; i < n*m; i++ {
		dis[i] = 0x3f3f3f3f
	}
	dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
	que := make([]int, 0, 1000000)
	inq := make([]bool, n*m)
	que = append(que, 0)
	inq[0] = true
	for len(que) > 0 {
		u := que[0]
		que = que[1:]
		inq[u] = false
		x, y := u/m, u%m
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m {
				v := xx*m + yy
				w := maxInt(dis[u], absInt(heights[x][y]-heights[xx][yy]))
				if dis[v] > w {
					dis[v] = w
					if !inq[v] {
						inq[v] = true
						que = append(que, v)
					}
				}
			}
		}
	}
	return dis[n*m-1]
}

778. 水位上升的泳池中游泳

并查集,给每个结点按从小到大排序,然后按序取出,并将该节点四周高度小于该节点的点并入并查集。

type UnionSet struct {
    parent []int
}

func NewUnionSet(size int) *UnionSet {
    parent := make([]int, size)
    for i:=0; i<size; i++ {
        parent[i] = i
    }
    return &UnionSet{parent}
}

func (us *UnionSet) Find(x int) int {
    if us.parent[x] != x {
        us.parent[x] = us.Find(us.parent[x])
    }
    return us.parent[x]
}

func (us *UnionSet) Union(x, y int) {  
    us.parent[us.Find(y)] = us.Find(x)
}

func (us *UnionSet) InSameSet(x, y int) bool {  
    return us.Find(x) == us.Find(y)
}

type point struct {
    x, y, height int
}

func swimInWater(grid [][]int) int {
    n := len(grid)
    total := n*n
    
    points := []point{}
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            points = append(points, point{i, j, grid[i][j]})
        }
    }

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

    us := NewUnionSet(total)
    for i:=0; i<total; i++ {
        idx := points[i].x * n +points[i].y
        if points[i].x > 0 &&  points[i].height >= grid[points[i].x-1][points[i].y]{
            us.Union(idx, idx-n)
        }
        if points[i].y > 0 &&  points[i].height >= grid[points[i].x][points[i].y-1]{
            us.Union(idx, idx-1)
        }
        if points[i].x < n-1 &&  points[i].height >= grid[points[i].x+1][points[i].y]{
            us.Union(idx, idx+n)
        }
        if points[i].y < n-1 &&  points[i].height >= grid[points[i].x][points[i].y+1]{
            us.Union(idx, idx+1)
        }
        if us.InSameSet(0, total-1) {
            return points[i].height
        }
    }

    return grid[n-1][n-1]
    
}

888. 公平的糖果棒交换

难度简单116

爱丽丝和鲍勃有不同大小的糖果棒:A[i] 是爱丽丝拥有的第 i 根糖果棒的大小,B[j] 是鲍勃拥有的第 j 根糖果棒的大小。

因为他们是朋友,所以他们想交换一根糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)

返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案,你可以返回其中任何一个。保证答案存在。


/*
最后等价转换为求两个有序数组中的相同数字
*/
func fairCandySwap(A []int, B []int) []int {
	sumA := 0
	sumB := 0
	for _, v := range A {
		sumA += v
	}

	for _, v := range B {
		sumB += v
	}

	sort.Ints(A)
	sort.Ints(B)

	//双指针遍历 A,B,判断是否存在 a=b+target
	target := (sumA - sumB) / 2
	i := 0
	j := 0
	for i < len(A) && j < len(B) {

		if A[i] == B[j]+target {
			return []int{A[i], B[j]}
		}

		if A[i] < B[j]+target {
			i++
		} else {
			j++
		}

	}

	// }

	return []int{0, 0}
}

424. 替换后的最长重复字符

难度中等258

给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

**注意:**字符串长度 和 k 不会超过 104。


/*
424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

注意:字符串长度 和 k 不会超过 104。
1. 二分法,每次定义最长的重复字符长度 winLen
2. 通过滑窗判断是否可以满足 ; 计算滑窗内各个字符的个数,然后得到频率最大的字符个数 cnt, 判断 cnt+k>= winLen ,就返回true
*/

/*
424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

注意:字符串长度 和 k 不会超过 104。
1. 二分法,每次定义最长的重复字符长度 winLen
2. 通过滑窗判断是否可以满足 ; 计算滑窗内各个字符的个数,然后得到频率最大的字符个数 cnt, 判断 cnt+k>= winLen ,就返回true
*/
func characterReplacement(s string, k int) int {
	if len(s) == 0 || k >= len(s)-1 {
		return len(s)
	}

	sb := []byte(s)
	start := k
	best := -1
	end := len(s)
	for start <= end {
		mid := (end-start)/2 + start
		if judge(sb, mid, k) {
			best, start = mid, mid+1
		} else {
			end = mid - 1
		}
	}

	return best

}

func judge(s []byte, winEnd, k int) bool {

	charCnt := make([]int, 26)
	for i := 0; i < winEnd; i++ {
		charCnt[s[i]-'A']++
	}

	if windowCanfill(charCnt, winEnd, k) {
		return true
	}

	for i := winEnd; i < len(s); i++ {
		charCnt[s[i]-'A']++
		charCnt[s[i-winEnd]-'A']--
		if windowCanfill(charCnt, winEnd, k) {
			return true
		}

	}

	return false

}

/*
1. 求窗口内频率最高的字符 c
2. 把窗口内c之外的字符个数如果小于等于k,那么就可以把其他的字符都换为c
*/
func windowCanfill(charCnt []int, winEnd, k int) bool {

	maxCnt := 0
	for _, v := range charCnt {
		if v > maxCnt {
			maxCnt = v
		}
	}
	if maxCnt+k >= winEnd {
		return true
	}
	return false
}

相似题目

1004. 最大连续1的个数 III

难度中等142

给定一个由若干 01 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。


/*
 相似题目 424,1493,1004.
 替换后的最长重复字符
 利用二分法加滑窗
*/
func longestOnesBinary(A []int, K int) int {
	if K >= len(A) {
		return len(A)
	}

	start := K
	end := len(A)
	best := -1
	for start <= end {

		mid := (end-start)/2 + start
		if judege(A, mid, K) {
			best, start = mid, mid+1
		} else {
			end = mid - 1
		}

	}
	return best
}

func judege(A []int, winLen, K int) bool {
	numberCnt := [2]int{} //记录0,1的个数
	for i := 0; i < winLen; i++ {
		numberCnt[A[i]]++
	}

	if numberCnt[1]+K >= winLen {
		return true
	}

	for i := winLen; i < len(A); i++ {
		numberCnt[A[i-winLen]]--
		numberCnt[A[i]]++
		if numberCnt[1]+K >= winLen {
			return true
		}
	}

	return false

}

//双指针方法
func longestOnes(A []int, K int) int {
	if K >= len(A) {
		return len(A)
	}
	if K == 0 {
		return findMaxConsecutiveOnes(A)
	}

	numCnt := [2]int{}
	start, end := 0, 0 //左闭,右开区间,包含start,不包含end
	maxLen := 0
	for start <= end && end < len(A) {
		//要加的end是1,可以继续加 或 要加入的是0, 而且目前窗口中0 的数量还小于 K,可以继续加 0
		if A[end] == 1 || numCnt[0] < K {
			numCnt[A[end]]++
			end++
			if end-start > maxLen {
				maxLen = end - start
			}
			continue
		}

		//当前窗口中0的数量等于k,就不能再往里面加0了,就需要把窗口左边缩小
		numCnt[A[start]]--
		start++

	}

	return maxLen

}

func findMaxConsecutiveOnes(nums []int) int {
	maxLen := 0
	curLen := 0
	for _, v := range nums {

		if v == 1 {
			curLen++
		} else {
			if curLen > maxLen {
				maxLen = curLen
			}
			curLen = 0
		}
	}

	if curLen > maxLen {
		maxLen = curLen
	}
	return maxLen
}

1493. 删掉一个元素以后全为 1 的最长子数组

难度中等20

给你一个二进制数组 nums ,你需要从中删掉一个元素。

请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组,请返回 0 。


/*
 相似题目 424,1493,1004.
二分法
https://github.com/kingeasternsun/leetcode-cn
*/
func longestSubarrayBinary(nums []int) int {

	start := 0
	end := len(nums)
	best := -1
	for start <= end {

		mid := (end-start)/2 + start
		if judege(nums, mid) {
			best, start = mid, mid+1
		} else {
			end = mid - 1
		}

	}
	if best > 0 {
		return best - 1
	}
	return best

}

func judege(nums []int, winLen int) bool {
	numCnt := [2]int{}
	for i := 0; i < winLen; i++ {
		numCnt[nums[i]]++
	}

	if numCnt[0] <= 1 {
		return true
	}

	for i := winLen; i < len(nums); i++ {
		numCnt[nums[i-winLen]]--
		numCnt[nums[i]]++
		if numCnt[0] <= 1 {
			return true
		}

	}

	return false
}

func longestSubarray(nums []int) int {

	maxLen := 0
	numCnt := [2]int{}
	beg, end := 0, 0 //左闭右开区间
	for beg <= end && end < len(nums) {
		//如果当前end上是1 或 [beg,end)里面没有0 ,就可以把 当前end加入窗口
		if nums[end] == 1 || numCnt[0] == 0 {
			numCnt[nums[end]]++
			end++
			if end-beg-1 > maxLen {
				maxLen = end - beg - 1
			}
			continue
		}
		//end上是0 ,而且 [beg,end)里面已经有一个0了,就需要去掉左边的beg
		numCnt[nums[beg]]--
		beg++

	}

	return maxLen
}