Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏-Toy模板网

这篇具有很好参考价值的文章主要介绍了Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

289. 生命游戏 Game Of Life 🌟🌟

292. Nim 游戏 Nim Game 🌟

299. 猜数字游戏 Bulls and Cows 🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练专栏

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

289. 生命游戏 Game Of Life

生命游戏 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

输入：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：

Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 25
board[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 <= 1000
secret.length == guess.length
secret 和 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）暂停更文章来源地址https://www.toymoban.com/news/detail-485939.html

到了这里，关于Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

	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）暂停更文章来源地址https://www.toymoban.com/news/detail-485939.html

Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

289. 生命游戏 Game Of Life

292. Nim 游戏 Nim Game

299. 猜数字游戏 Bulls and Cows

🌟 每日一练刷题专栏 🌟

Rust每日一练专栏

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

289. 生命游戏 Game Of Life

292. Nim 游戏 Nim Game

299. 猜数字游戏 Bulls and Cows

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

Rust每日一练专栏

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏