一些取巧的算法题

过不了几个月就要开始找实习了，决定最近多搓点题免得莫得实习TAT。每天整他个五六题，最后应该不会找不着实习了吧~

先整个简单的找点自信：

Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

输入：n = 4
输出：false 
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

想法：俺寻思，只要一直使剩余块数为4的倍数时，到最后永远是后手能拿完剩下的，在这题中咱先手，拿过一次就相当于是后手了，所以就是要判断拿过一次剩下的石头，能否为4的倍数。

class Solution:
    def canWinNim(self, n: int) -> bool:
        if n >= 4 :
            if (n-1)%4==0 or (n-2)%4==0 or (n-3)%4==0:
                return True
            else:
                return False
        elif n <=3:
            return True

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）

输入：x = 123
输出：321
输入：x = -123
输出：-321

class Solution:
    def reverse(self, x: int) -> int:
        numstr = str(x)
        temp = ''
        first = numstr[0]
        numstr = numstr[1:]
        for each in reversed(numstr):
            temp = temp+each
        if first !='-':
            temp = temp + first
        else:
            temp = first +temp
        itemp = int(temp)
        if itemp > 2**31-1 or itemp < -2**31:
            return 0
        else:
            return itemp

ps:reversed()是python内置函数，用于将一个迭代器对象反序

回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

输入：x = 121
输出：true
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

想法：上面两题均是和数字相关的题目，俺寻思通过转化为字符串的方式去写在一些情况下可以避免高复杂度运算，而且代码看着简洁些。

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4

这题想了会，既要线性时间复杂度还不能用额外空间，寻思先排个序然后就好找单独的数了，但是感觉这种题目应该都有很精简的解决方法才对，果然一看答案，我：震惊。

答案使用了异或来解决这个问题，众所周知，

a^a == 0 ，

 a^0 == a。

因此，a^a^b == 0^b == b

所以只要将整个序列全部异或，最后的结果就是单独的那个数。

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        temp = 0
        for i in range(len(nums)):
            temp = temp ^ nums[i]
        return temp

总结：刷这种能偷懒的题贼有意思诶嘿嘿嘿（误）