早起刷题（Day 15）
洪笳淏 Lv4
 2022-04-17 17:25:00      

本文是对 2022.04.16 双周赛的回顾

LeetCode6060. 找到最接近 0 的数字

#数组

题目描述

给你一个长度为 n 的整数数组 nums ，请你返回 nums 中最 接近 0 的数字。如果有多个答案，请你返回它们中的 最大值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1：
输入：nums = [-4,-2,1,4,8]
输出：1
解释：
-4 到 0 的距离为 |-4| = 4 。
-2 到 0 的距离为 |-2| = 2 。
1 到 0 的距离为 |1| = 1 。
4 到 0 的距离为 |4| = 4 。
8 到 0 的距离为 |8| = 8 。
所以，数组中距离 0 最近的数字为 1 。

示例 2：
输入：nums = [2,-1,1]
输出：1
解释：1 和 -1 都是距离 0 最近的数字，所以返回较大值 1 。
 

提示：
1 <= n <= 1000
-10^5 <= nums[i] <= 10^5

解题思路

(1). 先排序数组，然后看数组是否全体 大于等于 0 或者 小于等于 0，是的话就直接输出答案了；
(2). 否则一次遍历数组，用一个变量记录最大的负数，当遍历到 0，直接输出 0，如果遍历到第一个正数，则比较最大的负数和最小的正数谁距离 0 更近。

时间复杂度

O(Nlog(N))

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findClosestNumber(nums []int) int {

	sort.Ints(nums)
	n := len(nums)
	if nums[0] >= 0 {
		return nums[0]
	} else if nums[n-1] <= 0 {
		return nums[n-1]
	}

	a := 0
	for i:=0; i<len(nums); i++ {
		if nums[i] < 0 {
			a = nums[i]
		} else if nums[i] == 0 {
			return 0
		} else {
			if 0-a < nums[i] {
				return a
			} else {
				return nums[i]
			}
		}
	}

	return 0
}

LeetCode6061. 买钢笔和铅笔的方案数

#动态规划 #枚举

题目描述

给你一个整数 total ，表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。
请你返回购买钢笔和铅笔的 不同方案数目 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：total = 20, cost1 = 10, cost2 = 5
输出：9
解释：一支钢笔的价格为 10 ，一支铅笔的价格为 5 。
- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。
所以买钢笔和铅笔的总方案数为 5 + 3 + 1 = 9 种。

示例 2：
输入：total = 5, cost1 = 10, cost2 = 10
输出：1
解释：钢笔和铅笔的价格都为 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种方案：买 0 支钢笔和 0 支铅笔。
 

提示：
1 <= total, cost1, cost2 <= 10^6

解题思路

(1). 仔细观察示例的解题过程，是通过枚举钢笔的数量来确定铅笔可能的数量，那么我们也可以使用枚举的方式来判断；
(2). 那么怎样能够快速的枚举呢？可以先通过动态规划，确定在总金额不变的情况下，全部用来买钢笔或铅笔能够最多买多少支；
(3). 在枚举钢笔数量的时候，剩余的钱全都可以用来购买铅笔，那么总方案数就可以根据这两者来确定。

时间复杂度

O(N)

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func waysToBuyPensPencils(total int, cost1 int, cost2 int) int64 {

	dp1 := make([]int64, total+1)
	dp2 := make([]int64, total+1)
	
	// 背包问题
	for i:=0; i<=total; i++ {

		if i < cost1 {
			dp1[i] = 0
		} else {
			dp1[i] = dp1[i-cost1]+1
		}

		if i < cost2 {
			dp2[i] = 0
		} else {
			dp2[i] = dp2[i-cost2]+1
		}
	}

	// 枚举
	var ret int64
	for i:=0; i<=int(dp1[total]); i++ {
		rest := total-i*cost1
		ret += dp2[rest]+1
	}

	return ret
}

LeetCode6062. 设计一个 ATM 机器

#模拟 #贪心

题目描述

一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。
取款时，机器会优先取 较大 数额的钱。

  • 比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。
  • 但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器 不能 取 $200 的钞票。

请你实现 ATM 类：

  • ATM() 初始化 ATM 对象。
  • void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。
  • int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-1] （这种情况下 不 取出任何钞票）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
示例 1：

输入：
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
输出：
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

解释：
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 $100 ，2 张 $200 和 1 张 $500 的钞票。
atm.withdraw(600);        // 返回 [0,0,1,0,1] 。机器返回 1 张 $100 和 1 张 $500 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ，1 张 $200 和 1 张 $500 的钞票。
                          // 机器中剩余钞票数量为 [0,1,0,3,1] 。
atm.withdraw(600);        // 返回 [-1] 。机器会尝试取出 $500 的钞票，然后无法得到剩余的 $100 ，所以取款请求会被拒绝。
                          // 由于请求被拒绝，机器中钞票的数量不会发生改变。
atm.withdraw(550);        // 返回 [0,1,0,0,1] ，机器会返回 1 张 $50 的钞票和 1 张 $500 的钞票。
 

提示：
banknotesCount.length == 5
0 <= banknotesCount[i] <= 10^9
1 <= amount <= 10^9
总共 最多有 5000 次 withdraw 和 deposit 的调用。
函数 withdraw 和 deposit 至少各有 一次 调用。

解题思路

(1). 首先我们构建 ATM 类，这个类需要什么元素呢？

  • 首先需要一个数组 paperAmount 来保存所有的钞票面额
  • 一个 map 来记录对应面额的数量
  • 一个变量记录总金额
  • 一个变量记录最大面额对应的 paperAmount 数组中的索引号
    (2). 对于 Deposit 方法，每次更新对应的元素即可；
    (3). 令输出为 ret，首先看银行内总金额是否能支持 amount 数额的兑取，然后 ret 是一个长度为 5 的数组，用于保存各类型钞票的数量；
    (4). 对于 Withdraw 方法，先看是否有对应的面额正好是 amount 的值，如果是的话直接取出；否则就要看最大面额的钞票是否超过了 amount，如果没有超过，则必须从最大面额中先取出，为了避免超时，这里需要尽可能的将能用最大面额 cover 的部分全部取出来；如果超过了，那么就从次大的面额到最小面额依次比对，直到能满足要求；
    (5). 如果没有任何面额能够满足剩余金额的要求，那么只能证明无法取出这个 amount 对应的钞票，要将之前取出来的钞票重新存进银行，那么就要调用 Deposit 方法，将 ret 数组存入银行。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
type ATM struct {
	paperCount map[int]int
	totalCount int
	paperAmount []int
	maxIndex int
}

func Constructor() ATM {

	return ATM {
		paperCount : map[int]int {
			20 : 0,
			50 : 0,
			100 : 0,
			200 : 0,
			500 : 0,
		},
		totalCount : 0,
		paperAmount : []int{20,50,100,200,500},
		maxIndex : -1,
	}
}

func (this *ATM) Deposit(banknotesCount []int) {

	this.paperCount[20] += banknotesCount[0]
	this.paperCount[50] += banknotesCount[1]
	this.paperCount[100] += banknotesCount[2]
	this.paperCount[200] += banknotesCount[3]
	this.paperCount[500] += banknotesCount[4]
	this.totalCount += 20*banknotesCount[0] + 50*banknotesCount[1] + 100*banknotesCount[2] + 200*banknotesCount[3] + 500*banknotesCount[4]

	for i:=4; i>=0; i-- {
		x := this.paperAmount[i]
		if this.paperCount[x] > 0 {
			this.maxIndex = i
			break
		}
	}
}

func (this *ATM) Withdraw(amount int) []int {

	if amount > this.totalCount {
		return []int{-1}
	}

	ret := make([]int, 5)

	for amount > 0 {
		for i:=0; i<5; i++ {
			if amount == this.paperAmount[i] && this.paperCount[this.paperAmount[i]] > 0 {
				ret[i]++
				x := this.paperAmount[i]
				this.totalCount -= x
				this.paperCount[x]--
				if this.paperCount[x] == 0 {
					for i:=this.maxIndex-1; i>=0; i-- {
						y := this.paperAmount[i]
						if this.paperCount[y] > 0 {
							this.maxIndex = i
							break
						}
					}
				}
				
				return ret
			}
		}

		f := 0
		if this.paperAmount[this.maxIndex] < amount {
			x := this.paperAmount[this.maxIndex]
			var n int
			if this.paperCount[x] >= amount/x {
				n = amount/x
			} else {
				n = this.paperCount[x]
			}

			amount -= x*n
			ret[this.maxIndex] += n
			this.paperCount[x] -= n
			if this.paperCount[x] == 0 {
				for i:=this.maxIndex-1; i>=0; i-- {
					y := this.paperAmount[i]
					if this.paperCount[y] > 0 {
						this.maxIndex = i
						break
					}
				}
			}

			this.totalCount -= x *n
		} else {
			i := this.maxIndex-1
			for ; i>=0; i-- {
				x := this.paperAmount[i]
				if x < amount && this.paperCount[x] > 0 {
					amount -= x
					this.totalCount -= x
					this.paperCount[x]--
					ret[i]++
					f = 1
					break
				}
			}

			if f == 0 {
				this.Deposit(ret)
				return []int{-1}
			}
		}
	}

	if amount == 0 {
		return ret
	}

	this.Deposit(ret)
	return []int{-1}
}

 
/**
* Your ATM object will be instantiated and called as such:
* obj := Constructor();
* obj.Deposit(banknotesCount);
* param_2 := obj.Withdraw(amount);
*/

LeetCode6063. 节点序列的最大得分

#图 #枚举

题目描述

给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。
给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。
一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：

  • 序列中每 相邻 节点之间有边相连。
  • 序列中没有节点出现超过一次。
    节点序列的分数定义为序列中节点分数之 和 。
    请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。
1
示例 1:

avatar

1
2
3
4
5
6
7
输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图为输入的图，节点序列为 [0,1,2,3] 。
节点序列的分数为 5 + 2 + 9 + 8 = 24 。
观察可知，没有其他节点序列得分和超过 24 。
注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。
序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。
1
示例 2:

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图为输入的图。
没有长度为 4 的合法序列，所以我们返回 -1 。
 

提示：
n == scores.length
4 <= n <= 5 * 10^4
1 <= scores[i] <= 10^8
0 <= edges.length <= 5 * 10^4
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
不会有重边。

解题思路

(1). 试试枚举可不可以。（做题时优先考虑最简单的算法）枚举谁呢？可以枚举点，也可以枚举边；
(2). 简化问题可以帮助我们找到思路。如果序列只要求 33 个点，要如何枚举？只要求 33 个点的话，可以枚举端点，也可以枚举中间的点；
(3). 枚举中间的点是最方便的，算出与其相邻的分数最大的两个点即可。这意味着枚举中间的相比枚举两边的要更好写，效率也更高。顺着这个思路去思考原问题；
(4). 设序列为 a−x−y−b（− 表示边），枚举 edges 中的每条边，作为序列正中间的那条边，即 x−y；
(5). 我们需要把与 x 相邻的点中，分数最大且不同于 y 和 b 的点作为 a；把与 y 相邻的点中，分数最大且不同于 x 和 a 的点作为 b；
(6). 与 x 相邻的点中，由于只需要与 y 和 b 不一样，我们仅需要保留分数最大的三个点，a 必定在这三个点中；
(7). 剩下要做的，就是在枚举 edges 前，预处理出这三个点。代码实现时，可以用排序、堆、分治（nth_element）或者手动维护求前三大。最优的时间复杂度为 O(n+m)。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func maximumScore(scores []int, edges [][]int) int {

	type node struct {
		to int
		score int
	}

	e := make([][]node, len(scores))
	for i:=0; i<len(edges); i++ {
		x, y := edges[i][0], edges[i][1]
		e[x] = append(e[x], node{y, scores[y]})
		e[y] = append(e[y], node{x, scores[x]})
	}

	for i:=0; i<len(e); i++ {
		sort.Slice(e[i], func(k, j int) bool {
			return e[i][k].score > e[i][j].score
		})

		if len(e[i]) > 3 {
			e[i] = e[i][:3]
		}
	}
	
	ret := -1
	for i:=0; i<len(edges); i++ {
		x, y := edges[i][0], edges[i][1]
		for j:=0; j<len(e[x]); j++ {
			for k:=0; k<len(e[y]); k++ {
				if e[x][j].to != e[y][k].to && e[x][j].to != y && e[y][k].to != x {
					ret = max(ret, e[x][j].score+scores[x]+scores[y]+e[y][k].score)
				}
			}
		}
	}

	return ret
}

  

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

	return b
}
  • Post title：早起刷题（Day 15）
  • Post author：洪笳淏
  • Create time：2022-04-17 17:25:00
  • Post link：https://jiahaohong1997.github.io/2022/04/17/早起刷题（Day 15）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments