LeetCode简单题，主要记录有意思的解法。

20.有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：
*左括号必须用相同类型的右括号闭合。
*左括号必须以正确的顺序闭合。
*注意空字符串可被认为是有效字符串。

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

注：相当于每次筛选出最小的然后连接到之前最小的那个结点，最后返回初始结点。

53.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

# 贪心法
class Solution:
    def maxSubArray(self, nums: 'List[int]') -> 'int':
        n = len(nums)
        curr_sum = max_sum = nums[0]

        for i in range(1, n):
            curr_sum = max(nums[i], curr_sum + nums[i])
            max_sum = max(max_sum, curr_sum)
        return max_sum

注：curr_sum指包括第i个元素的最大值。

# 动态规划
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_num = nums[0]
        for i in range(1,len(nums)):
            if nums[i-1]>0:
                nums[i]+=nums[i-1]
            max_num=max(nums[i],max_num)
        return max_num

注：考虑某个数之前的最大和，即判断是否对当前数有增益，如果有增益就加上，否则当前最大即为该数字。

58.最后一个单词的长度

给定一个仅包含大小写字母和空格’ ’ 的字符串s，返回其最后一个单词的长度。

如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回0。

说明：一个单词是指仅由字母组成、不包含任何空格的 最大子字符串。

示例:

输入: "Hello World"
输出: 5

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.split()[-1]) if s.strip() else 0

注：s.strip()去除所有开头和结尾的空格，返回新字符串。s.rstrip()删除结尾的空格，返回新字符串。（两种方式对原字符串无改变）

66.加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数0之外，这个整数不会以零开头。

示例:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return list(map(int,str(int("".join(map(str,digits)))+1)))

67.二进制求和

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例:

输入: a = "11", b = "1"
输出: "100"

class Solution:
    def addBinary(self, a, b) -> str:
        return '{0:b}'.format(int(a, 2) + int(b, 2))

注：使用format将十进制转二进制字符串

69.x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
     由于返回类型是整数，小数部分将被舍去。

# 牛顿法
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        cur = 1 # 起始的时候在 1 ，这可以比较随意设置
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)

也可以使用二分查找，比直接从1开始查找快多了

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例:

输入: 1->1->2
输出: 1->2

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not (head and head.next):
            return head
        i,j = head,head
        while j:
            # 如果i不等于j，则i前进一位，然后将j的值赋给i
            if i.val!=j.val:
                i = i.next
                i.val = j.val
            # 不管i是否等于j，j每次都前进一位
            j = j.next
        i.next = None
        return head

118.杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0: return []
        res = [[1]]
        while len(res) < numRows:
            newRow = [a+b for a, b in zip([0]+res[-1], res[-1]+[0])]
            res.append(newRow)
        return res

注：使用先对上一行在首和尾添加0，再zip展开成二维数组，相当于错位相加。

125. 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例:

输入: "A man, a plan, a canal: Panama"
输出: true

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(filter(str.isalnum,s)).lower()
        return s==s[::-1]

注：使用filter将不是字符或者数字的去掉。

136.只出现一次的数字

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

示例:

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

法1：hash表 空间复杂度O(n)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        l = {}
        for n in nums:
            if not n in l:
                l[n]=1
            else:
                l.pop(n)
        return l.popitem()[0]

法2：数学 空间复杂度O(n)

class Solution(object):
    def singleNumber(self, nums):
        return 2 * sum(set(nums)) - sum(nums)

法3：位操作 空间复杂度O(1)

class Solution(object):
    def singleNumber(self, nums):
        a = 0
        for i in nums:
            a ^= i
        return a

160.相交链表

编写一个程序，找到两个单链表相交的起始节点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return null
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

注：使用两个指针，分别遍历链表。如果到底则换到另一个链表继续遍历。如果两次遍历都没有相交则在None处相等，此时说明不相交，否则在中间出现相交。

169.多数元素

给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例:

输入: [3,2,3]
输出: 3

使用Counter函数和max指定参数找最大值

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

172.阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        i=0
        while n:
            n=n//5
            i+=n
        return i

注：这里相当于计算阶乘中有多少个5（n次方算n个5）。可以直接计算每次除以5剩下的商，不断除下去再加起来就是结果。

189.旋转数组

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。

法1：切片

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k%=n
        nums[:]=nums[n-k:]+nums[:n-k]

法2：三次翻转

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k%=n
        nums[:] = nums[::-1]
        nums[:k] = nums[:k][::-1]
        nums[k:] = nums[k:][::-1]

注：先整体翻转，然后将前k个翻转，以及后n-k个翻转，得到结果。

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

class Solution:
    def rob(self, nums: List[int]) -> int:
        cur,pre = 0,0
        for i in nums:
            cur,pre = max(pre+i,cur),cur
        return cur

注：使用两个变量足矣，pre相当于两户之前，计算之后cur即为当前的值。

203.移除链表元素

删除链表中等于给定值 val 的所有节点。

方法：增加伪头，使用双指针

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        sentinel = ListNode(0)
        sentinel.next = head
        prev, curr = sentinel, head
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        return sentinel.next

204.计数素数

统计所有小于非负整数n的质数的数量。

欧拉筛 O(n)

class Solution:
    def countPrimes(self, n: int) -> int:
        isprime = [1]*n
        cnt = 0
        prime = []
        for i in range(2,n):
            if isprime[i]:
                prime.append(i)
                cnt+=1
            for j in range(cnt):
                tmp = prime[j]*i
                if tmp>=n:
                    break
                isprime[tmp]=0
                if i%prime[j]==0: #此后元素在之后会筛除，不需要在这步继续
                    break
        return cnt

埃氏筛 O(nlogn*logn)

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        isPrime = [1] * n
        isPrime[0] = isPrime[1] = 0

        # 埃式筛，把不大于根号n的所有质数的倍数剔除
        for i in range(2, int(n ** 0.5) + 1):
            if isPrime[i]:
                isPrime[i * i:n:i] = [0] * ((n - 1 - i * i) // i + 1)
        return sum(isPrime)

258.各位相加

给定一个非负整数num，反复将各个位上的数字相加，直到结果为一位数。

class Solution:
    def addDigits(self, num: int) -> int:
        return (num-1)%9+1 if num>0 else 0

注：任何数字都可以写作所有数字相加和一个9的倍数，故取余即可。

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        flag=-1
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[flag+1],nums[i]=nums[i],nums[flag+1]
                flag+=1
        return nums

注：使用快慢指针，慢指针指向0的位置，快指针遍历。最差情况为全非零。

面试题01.04.回文排列

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        result = 0
        for c in s:
            result ^= 1<< ord(c)

        return result & (result - 1) == 0

注：result最后有多少个1即为有多少个出现基数次的字母。result与result-1即可判断是否只有一个1，如果结果为0说明只有一个1，否则至少2个1