目錄

289. 生命游戲 Game Of Life??????

292. Nim 游戲 Nim Game????

299. 猜數(shù)字游戲 Bulls and Cows??????

?? 每日一練刷題專欄???

Rust每日一練 專欄

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

289. 生命游戲 Game Of Life

生命游戲? 是英國數(shù)學(xué)家約翰·何頓·康威在 1970 年發(fā)明的細(xì)胞自動(dòng)機(jī)。

給定一個(gè)包含?m × n?個(gè)格子的面板，每一個(gè)格子都可以看成是一個(gè)細(xì)胞。每個(gè)細(xì)胞都具有一個(gè)初始狀態(tài)：?1?即為?活細(xì)胞?（live），或?0?即為?死細(xì)胞?（dead）。每個(gè)細(xì)胞與其八個(gè)相鄰位置（水平，垂直，對角線）的細(xì)胞都遵循以下四條生存定律：

1. 如果活細(xì)胞周圍八個(gè)位置的活細(xì)胞數(shù)少于兩個(gè)，則該位置活細(xì)胞死亡；
2. 如果活細(xì)胞周圍八個(gè)位置有兩個(gè)或三個(gè)活細(xì)胞，則該位置活細(xì)胞仍然存活；
3. 如果活細(xì)胞周圍八個(gè)位置有超過三個(gè)活細(xì)胞，則該位置活細(xì)胞死亡；
4. 如果死細(xì)胞周圍正好有三個(gè)活細(xì)胞，則該位置死細(xì)胞復(fù)活；

下一個(gè)狀態(tài)是通過將上述規(guī)則同時(shí)應(yīng)用于當(dāng)前狀態(tài)下的每個(gè)細(xì)胞所形成的，其中細(xì)胞的出生和死亡是同時(shí)發(fā)生的。給你?m x n?網(wǎng)格面板?board?的當(dāng)前狀態(tài)，返回下一個(gè)狀態(tài)。

示例 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.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j]?為?0?或?1

進(jìn)階：

• 你可以使用原地算法解決本題嗎？請注意，面板上所有格子需要同時(shí)被更新：你不能先更新某些格子，然后使用它們的更新后的值再更新其他格子。
• 本題中，我們使用二維數(shù)組來表示面板。原則上，面板是無限的，但當(dāng)活細(xì)胞侵占了面板邊界時(shí)會造成問題。你將如何解決這些問題？

代碼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：使用額外的數(shù)組

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：使用緩存歷史狀態(tài)

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

你和你的朋友，兩個(gè)人一起? 玩 Nim 游戲：

• 桌子上有一堆石頭。
• 你們輪流進(jìn)行自己的回合，?你作為先手?。
• 每一回合，輪到的人拿掉?1 - 3 塊石頭。
• 拿掉最后一塊石頭的人就是獲勝者。

假設(shè)你們每一步都是最優(yōu)解。請編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量為?n?的情況下贏得游戲。如果可以贏，返回?true；否則，返回?false?。

示例 1：

輸入：n = 4
輸出：false 
解釋：以下是可能的結(jié)果:
1. 移除1顆石頭。你的朋友移走了3塊石頭，包括最后一塊。你的朋友贏了。
2. 移除2個(gè)石子。你的朋友移走2塊石頭，包括最后一塊。你的朋友贏了。
3.你移走3顆石子。你的朋友移走了最后一塊石頭。你的朋友贏了。
在所有結(jié)果中，你的朋友是贏家。

示例 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

本題的數(shù)學(xué)本質(zhì)：

假設(shè)當(dāng)前共有 n 塊石頭，每次可以拿 1-3 塊石頭，然后輪到對手。

當(dāng) n <= 3 時(shí)，先手必勝；當(dāng) n = 4 時(shí)，先手拿 1 塊石頭，無論對手拿幾塊，都會剩下 3 塊石頭留給先手，此時(shí)先手必勝；當(dāng) n = 5 時(shí)，先手拿 2 塊石頭，無論對手拿幾塊，都會剩下 3 塊石頭留給先手，此時(shí)先手必勝；同理，當(dāng) n = 6 時(shí)，無論先手拿幾塊，都會剩下 5 塊，對手依然可以通過上述策略獲勝。

推廣到一般情況，當(dāng) n 為 4 的倍數(shù)時(shí)，先手必?cái)?，否則必勝。

func canWinNim(n int) bool {

? ? return n % 4 != 0

}

299. 猜數(shù)字游戲 Bulls and Cows

你在和朋友一起玩 猜數(shù)字（Bulls and Cows）游戲，該游戲規(guī)則如下： ?

寫出一個(gè)秘密數(shù)字，并請朋友猜這個(gè)數(shù)字是多少。朋友每猜測一次，你就會給他一個(gè)包含下述信息的提示：

• 猜測數(shù)字中有多少位屬于數(shù)字和確切位置都猜對了（稱為 "Bulls"，公牛），
• 有多少位屬于數(shù)字猜對了但是位置不對（稱為 "Cows"，奶牛）。也就是說，這次猜測中有多少位非公牛數(shù)字可以通過重新排列轉(zhuǎn)換成公牛數(shù)字。

給你一個(gè)秘密數(shù)字?secret?和朋友猜測的數(shù)字?guess?，請你返回對朋友這次猜測的提示。

提示的格式為?"xAyB"?，x?是公牛個(gè)數(shù)，?y?是奶牛個(gè)數(shù)，A?表示公牛，B?表示奶牛。

請注意秘密數(shù)字和朋友猜測的數(shù)字都可能含有重復(fù)數(shù)字。

示例 1：

輸入：secret = "1807", guess = "7810"
輸出："1A3B"
解釋：數(shù)字和位置都對（公牛）用 '|' 連接，數(shù)字猜對位置不對（奶牛）的采用斜體加粗標(biāo)識。
"1807"
  |
"7810"

示例 2：

輸入：secret = "1123", guess = "0111"
輸出："1A1B"
解釋：數(shù)字和位置都對（公牛）用 '|' 連接，數(shù)字猜對位置不對（奶牛）的采用斜體加粗標(biāo)識。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，兩個(gè)不匹配的 1 中，只有一個(gè)會算作奶牛（數(shù)字猜對位置不對）。通過重新排列非公牛數(shù)字，其中僅有一個(gè) 1 可以成為公牛數(shù)字。

提示：

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret?和?guess?僅由數(shù)字組成

代碼1：數(shù)組

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

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！

?? 點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動(dòng)力！?

???收藏，你的青睞是我努力的方向！?

? 評論，你的意見是我進(jìn)步的財(cái)富！??

??主頁：https://hannyang.blog.csdn.net/?

到了這里，關(guān)于Golang每日一練(leetDay0098) 生命、Nim、猜數(shù)字游戲的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！