LeetCode第292题和第136,难度都是简单。
原题地址:https://leetcode-cn.com/problems/nim-game/ & https://leetcode-cn.com/problems/single-number/
题目描述:
Nim游戏:
你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
只出现一次的数字:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
解题思路:
先说Nim游戏,这题我是用Java解的。两个人轮流拿石头,一次1-3块,那么如果只有1-3块石头,那么肯定是你赢。只要是4块,拿肯定是对手赢。那么放大来看,每次都取走1-3块的你,如果是4的整数倍的石头,那么无论如何都会给对方剩下石头。所以必赢的情况是石头不为4的倍数的时候。
再看只出现一次的数字,这题是用的Golang。我用的方法是遍历所有数字,然后使用异或运算的方式。一个数异或本身等于0。鉴于其他元素都出现了两次,所以唯一的数就是所有数异或的结果。当然还有的办法,比如使用Hash,或者使用列表计数的方式。
中文官网题解:
https://leetcode-cn.com/problems/nim-game/solution/
https://leetcode-cn.com/problems/single-number/solution/
个人题解:
public class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
func singleNumber(nums []int) int {
var result int = 0
for _,v := range nums{
result = result ^ v
}
return result
}
结果:
Nim游戏这题简单,解题方式也很简单,所以大家都挺快的。
只出现一次的数字,用异或运算毕竟还是比不过更快的啊。