专栏首页曌的晓痴LeetCode - Nim游戏 & 只出现一次的数字

LeetCode - Nim游戏 & 只出现一次的数字

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游戏这题简单,解题方式也很简单,所以大家都挺快的。

只出现一次的数字,用异或运算毕竟还是比不过更快的啊。

本文分享自微信公众号 - 曌的晓痴(gh_543795945efe),作者:zxyAnkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 有序数组的平方

    原题地址:https://leetcode-cn.com/problems/squares-of-a-sorted-array/

    晓痴
  • LeetCode - 斐波那契数

    LeetCode第509题,斐波那契数,真的是很经典的一道题目,难度系数为简单。很好奇一月4周前做的题目,那不就是两月之前么?

    晓痴
  • LeetCode - 数组拆分

    偷懒了几天,默默的跑去看各种小说,不想更新公众号。接下去的几天,利用休假的机会把前几天看的几本小说都写一下各自的剧情简介。

    晓痴
  • G7获7000万美元投资 启用2杂域名g7.com.cn

    近日国内智慧物联网公司G7宣布,已获得现代物流设施提供商普洛斯与中国银行全资持有的直接投资业务平台中银集团投资有限公司总计7000万美元的战略投资。...

    躲在树上的域小名
  • 面试论文:cpc-hrl 很难

    https://github.com/tensorflow/models/tree/master/research/efficient-hrl

    用户1908973
  • 图片处理(收集文档)

    通过Core Library的文档,我们知道创建颜色有这么几个方法: CGColorCreate CGColorCreateCopy CGColorCrea...

    onety码生
  • [golang]Go net.lookup包

     DNS (Domain Name System 的缩写)的作用非常简单,就是根据域名查出IP地址。 域名系统(通常被称为“DNS”)是一个网络系统,允许我们把...

    landv
  • 《Kotlin 反应式编程》使用 RxKotlin 实现一个极简的 http DSL ( Reactive Programming Using Rx Kotlin )《Kotlin 反应式编程》使用

    我们现在已经基本知道 Kotlin 中 DSL 的样子了。但是这些 DSL 都是怎样实现的呢?本节我们就通过实现一个极简的http DSL来学习创建 DSL 背...

    一个会写诗的程序员
  • Reddit年度盘点:2019年最佳机器学习项目

    为了帮助筛选 2019 年一些令人难以置信的项目、研究、演示等,下面我们将介绍 17 个在机器学习领域最受欢迎、被讨论最多的项目,这些项目由 r/Machine...

    AI研习社
  • 资源 | 伯克利CS294深度强化学习课程资料放出(PPT+录像)

    前段时间,文摘菌给大家推出了一门吴恩达主讲的深度学习课程CS230,并给出了课程的全套PPT和学生project和poster。今天再为大家推荐一门神课——伯克...

    大数据文摘

扫码关注云+社区

领取腾讯云代金券