289. 生命游戏 Game Of Life
生命游戏 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
示例 1：
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
示例 2：
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 25board[i][j]为0或1
进阶：
- 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
- 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
代码1：原地算法
package main import "fmt" func gameOfLife(board [][]int) { m, n := len(board), len(board[0]) dirs := [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}} for i := 0; i < m; i++ { for j := 0; j < n; j++ { count := 0 for _, d := range dirs { x, y := i+d[0], j+d[1] if x >= 0 && x < m && y >= 0 && y < n { if board[x][y] == 1 || board[x][y] == 2 { count++ } } } if board[i][j] == 1 && (count < 2 || count > 3) { board[i][j] = 2 } else if board[i][j] == 0 && count == 3 { board[i][j] = 3 } } } for i := 0; i < m; i++ { for j := 0; j < n; j++ { if board[i][j] == 2 { board[i][j] = 0 } else if board[i][j] == 3 { board[i][j] = 1 } } } } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i, ar := range arr { res += fmt.Sprint(ar) if i != len(arr)-1 { res += "," } } return res + "]" } res := "[" for i, arr := range array { res += arr2str(arr) if i != len(array)-1 { res += "," } } return res + "]" } func main() { board := [][]int{{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) board = [][]int{{1, 1}, {1, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) }
输出：
[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
[[1,1],[1,1]]
代码2：使用额外的数组
package main import "fmt" func gameOfLife(board [][]int) { m, n := len(board), len(board[0]) dirs := [][]int{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}} newBoard := make([][]int, m) for i := 0; i < m; i++ { newBoard[i] = make([]int, n) copy(newBoard[i], board[i]) } for i := 0; i < m; i++ { for j := 0; j < n; j++ { count := 0 for _, d := range dirs { x, y := i+d[0], j+d[1] if x >= 0 && x < m && y >= 0 && y < n { count += board[x][y] } } if board[i][j] == 1 { if count < 2 || count > 3 { newBoard[i][j] = 0 } } else { if count == 3 { newBoard[i][j] = 1 } } } } for i := 0; i < m; i++ { copy(board[i], newBoard[i]) } } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i, ar := range arr { res += fmt.Sprint(ar) if i != len(arr)-1 { res += "," } } return res + "]" } res := "[" for i, arr := range array { res += arr2str(arr) if i != len(array)-1 { res += "," } } return res + "]" } func main() { board := [][]int{{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) board = [][]int{{1, 1}, {1, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) }
代码3：使用缓存历史状态
package main import ( "fmt" "strconv" ) func gameOfLife(board [][]int) { m, n := len(board), len(board[0]) dirs := [][]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}} cache := make(map[string][]int) for i := 0; i < m; i++ { for j := 0; j < n; j++ { count := 0 for _, d := range dirs { x, y := i+d[0], j+d[1] if x >= 0 && x < m && y >= 0 && y < n { count += board[x][y] } } pos := strconv.Itoa(i) + "," + strconv.Itoa(j) if count < 2 || count > 3 { cache[pos] = []int{0} } else if count == 3 { cache[pos] = []int{1} } else { cache[pos] = []int{board[i][j]} } } } for i := 0; i < m; i++ { for j := 0; j < n; j++ { pos := strconv.Itoa(i) + "," + strconv.Itoa(j) if state, ok := cache[pos]; ok { board[i][j] = state[0] } } } } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i, ar := range arr { res += fmt.Sprint(ar) if i != len(arr)-1 { res += "," } } return res + "]" } res := "[" for i, arr := range array { res += arr2str(arr) if i != len(array)-1 { res += "," } } return res + "]" } func main() { board := [][]int{{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) board = [][]int{{1, 1}, {1, 0}} gameOfLife(board) fmt.Println(Array2DToString(board)) }
292. Nim 游戏 Nim Game
你和你的朋友，两个人一起 玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合， 你作为先手 。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。
示例 2：
输入：n = 1
输出：true
示例 3：
输入：n = 2
输出：true
提示：
1 <= n <= 2^31 - 1
代码：
package main import "fmt" func canWinNim(n int) bool { if n <= 3 { return true } dp := make([]bool, n+1) dp[1] = true dp[2] = true dp[3] = true for i := 4; i <= n; i++ { dp[i] = !(dp[i-1] && dp[i-2] && dp[i-3]) } return dp[n] } func main() { fmt.Println(canWinNim(4)) // false fmt.Println(canWinNim(1)) // true fmt.Println(canWinNim(2)) // true }
输出：
false
true
true
本题的数学本质：
假设当前共有 n 块石头，每次可以拿 1-3 块石头，然后轮到对手。
当 n <= 3 时，先手必胜；当 n = 4 时，先手拿 1 块石头，无论对手拿几块，都会剩下 3 块石头留给先手，此时先手必胜；当 n = 5 时，先手拿 2 块石头，无论对手拿几块，都会剩下 3 块石头留给先手，此时先手必胜；同理，当 n = 6 时，无论先手拿几块，都会剩下 5 块，对手依然可以通过上述策略获胜。
推广到一般情况，当 n 为 4 的倍数时，先手必败，否则必胜。
func canWinNim(n int) bool { return n % 4 != 0 }
299. 猜数字游戏 Bulls and Cows
你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
- 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
- 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
示例 1：
输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
|
"7810"
示例 2：
输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123" "1123"
| or |
"0111" "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
提示：
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret和guess仅由数字组成
代码1：数组
package main import ( "fmt" "strconv" ) func getHint(secret string, guess string) string { bulls, cows := 0, 0 sCount, gCount := [10]int{}, [10]int{} for i := 0; i < len(secret); i++ { if secret[i] == guess[i] { bulls++ } else { sCount[secret[i]-'0']++ gCount[guess[i]-'0']++ } } for i := 0; i < 10; i++ { cows += min(sCount[i], gCount[i]) } return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B" } func min(a, b int) int { if a < b { return a } return b } func main() { fmt.Println(getHint("1807", "7810")) fmt.Println(getHint("1123", "0111")) }
代码2：哈希表
package main import ( "fmt" "strconv" ) func getHint(secret string, guess string) string { bulls, cows := 0, 0 count := make(map[byte]int) for i := 0; i < len(secret); i++ { if secret[i] == guess[i] { bulls++ } else { count[secret[i]]++ } } for i := 0; i < len(guess); i++ { if secret[i] != guess[i] { if count[guess[i]] > 0 { cows++ count[guess[i]]-- } } } return strconv.Itoa(bulls) + "A" + strconv.Itoa(cows) + "B" } func main() { fmt.Println(getHint("1807", "7810")) fmt.Println(getHint("1123", "0111")) }
输出：
1A3B
1A1B
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
