leetcode笔记--3 Niim game

question:

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

my answer:

重点:

1 怎么计算,有些糊涂

2 python 除法

转自 https://segmentfault.com/a/1190000003912449

1.整数除法

对两个不能整除的整数做除法,就要面对舍入的问题。和大多数编程语言一样,Java的基本策略是向零取整(round to zero),也就是向绝对值变小的方向取整。举几个香甜的小栗子:3/2=1, -3/2=-1。而对于Python而言,情况就有所不同了。

>>>-1/10
-1

显然如果按照Java的取整策略,-1/10应该得0,而Python给出的结果是-1。事实上Python的取整方式是向下取整,也就是向着数轴上负无穷的方向取整。好吧,Java和Python的取整方式不同,夺大点事儿啊…那么如果我们要在Python下采用向零取整的结果,咋整?一种比较直接的方式是:

>>>int(float(-1)/10)
0

2.取余

谁说没大事?( ̄▽ ̄)大事来了!

Java和Python整数除法都遵循下面这个公式:

(a/b)*b+c=a

也就是说:

a mod b=c=a-(a/b)*b

这里的/表示的是整数除法。既然它们的取整方式不一样,那么取余也会受到影响:

For Java: -2 % 3==-2
For Python: -2 % 3==1

在某些实际应用中,我们可能会被要求得到一个整数的各位数字。如果输入的整数的正的,Java和Python都可以用相同的方法来解决:

def func(a):
    pos, res=1, []
    while a/pos:
        res+=(a/pos)%10,
        pos*=10
    return res

Java代码也差不多就是这样了。但如果输入的整数是一个负数,Java版本的代码还是可以得到正确的结果,而Python不能(曾经在这里被坑的,举手)。那怎样用Python正确地搞定这个问题嘞?可以先去绝对值和符号,当正数来处理,最后再在结果里搭上符号。

3. Follow-ups

3.1 Python中的另一个除法操作

我们知道,在Python中,基本的除号“/”是被重载了的。当两个操作数都是整数时,进行整数除法,得到整数结果,否则进行浮点数除法(真除法),得到浮点数结果。从Python 2.2开始,另一个除号被引入://,它只执行整数除法。注意,//的结果类型依操作数而定。

>>>1.0/2
0.0
>>>1.0//2.0
0.0
>>>1//2
>0

另外,如果想同时得到商和余数,可以使用内建的函数divmod,结果是一个tuple。

>>>divmod(7, 2)
(3, 1)
>>>divmod(7.0, 2)
(3.0, 1.0)

3.2 Python中的舍入

除了缺省的舍入方式,Python还有多种舍入可供选择。
Floor rounding:

>>>import math
>>>math.floor(1.2)
1.0
>>>math.floor(-1.2)
-2.0

Ceiling rounding:

>>>math.ceil(1.2)
2.0
>>>math.ceil(-1.2)
-1.0

Round-off:

>>>round(0.5)
1.0
>>>round(-0.4)
-0.0
>>>round(-0.5)
-1.0

内嵌的round函数也可以一个指定保留小数位数的参数:

>>>round(0.21, 1)
0.2
>>>round(0.21, 2)
0.21

Caution !

>>>round(2.675, 2)
2.67

咦?bug啦?!当然不是。这里要明确一件事:计算机只认识0,1(量子计算机?懵)。就是说,我们输入的十进制数,在计算机内部都是用二进制来表示的。有的十进制数可以用二进制准确地表示出来,比如十进制的0.125可以表示为0b0.001;然而很多的小数是没法用二进制数精确表示的,计算机里存储的是它们的近似值,例如十进制的0.1,用二进制表示,可以近似为:0b0.00011001100110011001100110011001100110011001100110011010,所以当我们把它换回十进制数以输出或者使用,得到的值就是0.1000000000000000055511151231257827021181583404541015625。也就是说,0.1在计算机里并不是刚好等于1/10的。你看:

>>>0.1+0.2
0.30000000000000004

同样,当我们运行round()函数,也是对计算机中实际存储的值近似取舍。2.67实际上近似

2.67499999999999982236431605997495353221893310546875,第三位小数是4,那么round(2.675, 2)就相当于round(2.674, 2),结果当然是2.67。值得注意的是,这种现象是广泛存在于各种计算机和各种编程语言的,不是bug,只是有的语言选择了不让你看到。

时间: 09-23

leetcode笔记--3 Niim game的相关文章

leetcode笔记

leetcode 笔记 Linked List 2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a

[leetcode笔记] Remove Duplicates from Sorted List II

问题描述: Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example,Given 1->2->3->3->4->4->5, return 1->2->5.Given 1->1->1->2->3, return 2-&

leetcode笔记:Pascal's Triangle

一. 题目描写叙述 Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 二. 题目分析 关于帕斯卡三角形的定义,可參考:http://baike.baidu.com/link?url=qk_-urYQnO4v6v3P4BuMtCa0tMNUqJUk

LeetCode 笔记26 Single Number II

Given an array of integers, every element appears three times except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 没辙,智商碾压题.楼主没遇到之前就只会这种做法. public int si

[LeetCode笔记]-237-Delete Node in a Linklist

上LeetCode后做的第一道题.删除一个链表节点.两个写法.第一个8ms,第二个4ms.先这么写吧. /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* solution 1 // The normal one I can think immediately. void deleteNode(struct ListNode* nod

LeetCode 笔记28 Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negat

leetcode笔记:2Sum

一.题目描述 基本意思是给定一组整数和一个常数target,试图在这一组数里找到两个数使得两者的和等于target,结果要求返回两个数的下标. 二.解题思路 思路一:使用暴力算法实现,这种情况下空间复杂度为O(1),但是时间复杂度为O(n^2),会超时. 思路二:使用hash表,存储每个数对应的下标,事件复杂度为O(n).这样在查找某个值存不存在只需要常数时间. //LeetCode, Two Sum // 时间复杂度O(n),空间复杂度O(n) class Solution { public:

leetcode笔记:Find Median from Data Stream

一. 题目描述 Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] , the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 De

leetcode笔记:Combination Sum III

一. 题目描述 Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Ensure that numbers within the set are sorted in ascending order. E

leetcode笔记:Combination Sum II

一. 题目描述 Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C once number of times. Note: ? All numbers (including target)