早起刷题（Day 11）
洪笳淏 Lv4
 2022-04-13 06:00:00      

LeetCode353. 贪吃蛇

#队列 #设计题

题目描述

请你设计一个 贪吃蛇游戏，该游戏将会在一个 屏幕尺寸 = 宽度 x 高度 的屏幕上运行。如果你不熟悉这个游戏，可以 点击这里 在线试玩。
起初时，蛇在左上角的 (0, 0) 位置，身体长度为 1 个单位。
你将会被给出一个数组形式的食物位置序列 food ，其中 food[i] = (ri, ci) 。当蛇吃到食物时，身子的长度会增加 1 个单位，得分也会 +1 。
食物不会同时出现，会按列表的顺序逐一显示在屏幕上。比方讲，第一个食物被蛇吃掉后，第二个食物才会出现。
当一个食物在屏幕上出现时，保证 不会 出现在被蛇身体占据的格子里。
如果蛇越界（与边界相撞）或者头与 移动后 的身体相撞（即，身长为 4 的蛇无法与自己相撞），游戏结束。

实现 SnakeGame 类：
SnakeGame(int width, int height, int[][] food) 初始化对象，屏幕大小为 height x width ，食物位置序列为 food
int move(String direction) 返回蛇在方向 direction 上移动后的得分。如果游戏结束，返回 -1 。

1
示例 1：

avatar

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
输入：
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
输出：
[null, 0, 0, 1, 1, 2, -1]

解释：
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // 返回 0
snakeGame.move("D"); // 返回 0
snakeGame.move("R"); // 返回 1 ，蛇吃掉了第一个食物，同时第二个食物出现在 (0, 1)
snakeGame.move("U"); // 返回 1
snakeGame.move("L"); // 返回 2 ，蛇吃掉了第二个食物，没有出现更多食物
snakeGame.move("U"); // 返回 -1 ，蛇与边界相撞，游戏结束
 

提示：
1 <= width, height <= 104
1 <= food.length <= 50
food[i].length == 2
0 <= ri < height
0 <= ci < width
direction.length == 1
direction is 'U', 'D', 'L', or 'R'.
最多调用 104 次 move 方法

解题思路

(1). 首先明确结构体中需要什么元素，首先需要一个二维数组来记录蛇身体在的位置，其次还需要一个索引号来记录当前出现的食物是第几个；
(2). 在移动的过程中，首先要根据移动的方向确认🐍头应该出现在的新位置的坐标是否在界限内。然后根据食物应该出现的位置（或者食物被吃完）确定🐍头是否碰触到食物；
(3). 如果碰触到，那么就吃掉，并且食物索引号 +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
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
type SnakeGame struct {
	snakePos [][]int
	width int
	height int
	food [][]int
	foodIndex int
}

func Constructor(width int, height int, food [][]int) SnakeGame {

	return SnakeGame {
		snakePos : [][]int{{0,0}},
		width : width,
		height : height,
		food : food,
		foodIndex : 0,
	}
}

func (this *SnakeGame) Move(direction string) int {

	h, w := 0, 0
	switch direction {
	case "R":
		h, w = this.snakePos[0][0], this.snakePos[0][1]+1
	case "L":
		h, w = this.snakePos[0][0], this.snakePos[0][1]-1
	case "U":
		h, w = this.snakePos[0][0]-1, this.snakePos[0][1]
	case "D":
		h, w = this.snakePos[0][0]+1, this.snakePos[0][1]
	}

	if (h < 0 || h >= this.height) || (w < 0 || w >= this.width) {
		return -1
	}

	this.snakePos = append([][]int{{h,w}}, this.snakePos...)
	if this.foodIndex < len(this.food) {
		if h == this.food[this.foodIndex][0] && w == this.food[this.foodIndex][1] {
			this.foodIndex++
		return this.foodIndex
		} else {
			this.snakePos = this.snakePos[:len(this.snakePos)-1]
			for i:=1; i<len(this.snakePos); i++ {

				if this.snakePos[i][0] == h && this.snakePos[i][1] == w {
					return -1
				}
			}
			return this.foodIndex
		}
	} else {
		this.snakePos = this.snakePos[:len(this.snakePos)-1]
		for i:=1; i<len(this.snakePos); i++ {
			if this.snakePos[i][0] == h && this.snakePos[i][1] == w {
				return -1
			}
		}
	}

	return this.foodIndex
}

/**
* Your SnakeGame object will be instantiated and called as such:
* obj := Constructor(width, height, food);
* param_1 := obj.Move(direction);
*/

LeetCode256. 粉刷房子

#动态规划

题目描述

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。
	 
	 
示例 2：
输入: costs = [[7,6,2]]
输出: 2
 

提示:
costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20

解题思路

动态规划，实时更新分别使用三种油漆作为最后一栋房子的结果。

时间复杂度

O(N)

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func minCost(costs [][]int) int {

	a, b, c := costs[0][0], costs[0][1], costs[0][2]
	for i:=1; i<len(costs); i++ {
		a, b, c = min(b, c)+costs[i][0], min(a, c)+costs[i][1], min(a, b)+costs[i][2]
	}

	return min(a, min(b, c))
}

  

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

LeetCode186. 翻转字符串里的单词 II

#字符串 #双指针

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

1
2
3
4
5
6
7
8
9
10
示例：
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

注意：
单词的定义是不包含空格的一系列字符
输入字符串中不会包含前置或尾随的空格
单词与单词之间永远是以单个空格隔开的

进阶：使用 O(1) 额外空间复杂度的原地解法。

解题思路

单词以空格分隔，先对每个单词进行reverse，再对整个字符串reverse，即可得到翻转单词顺序，但是单词中字母顺序不变的效果。

时间复杂度

O(N)

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reverseWords(s []byte) {

	var reverse func([]byte)
	reverse = func(b []byte) {
		for i:=0; i<len(b)/2; i++ {
			b[i], b[len(b)-i-1] = b[len(b)-i-1], b[i]
		}
	}

	first := 0
	for i:=0; i<=len(s); i++ {
		if i == len(s) || s[i] == ' ' {
			reverse(s[first:i])
			first = i+1
		}
	}

	reverse(s)
}
  • Post title：早起刷题（Day 11）
  • Post author：洪笳淏
  • Create time：2022-04-13 06:00:00
  • Post link：https://jiahaohong1997.github.io/2022/04/13/早起刷题（Day 11）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments