LC easy

这个gitbook改版过后简直像坨屎一样！居然不能批量删除我也是醉了。简直是越改越烂。垃圾软件毁我青春！不过我已经开了一个Issue 让他们开心一下。

我们先把leetcode上的tag题目给做了吧。 因为太久没刷题了，所以我们先从11道easy下手。

P.1 Convert Sorted Array to Binary Search Tree

好久不写差点都写不来了！

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return self.helper(nums)

    def helper(self, nums):
        if not nums:
            return None
        mid = len(nums)//2
        node = TreeNode(nums[mid])
        node.left = self.helper(nums[:mid])
        node.right = self.helper(nums[mid+1:])
        return node

s = Solution()
nums = [1, 2, 3]
ans = s.sortedArrayToBST(nums)
print(ans.val)
print(ans.left.val)
print(ans.right.val)

P2. Add Strings

这道题有点像big number。想了一下，还是把短的数往长的数上面加比较容易，然后再补进位。

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if len(num1)<len(num2):
            s, l = num1[::-1], num2[::-1]
        else:
            s, l = num2[::-1], num1[::-1]
        res = ''
        carry = 0
        for i in range(len(l)):
            s_num = int(s[i]) if i<len(s) else 0
            l_num = int(l[i])
            res += str((s_num + l_num + carry)%10)
            carry = (s_num + l_num + carry)//10
        if carry:
            res += str(carry)

        return res[::-1]

s = Solution()
num1 = '125'
num2 = '956'
ans = s.addStrings(num1, num2)
print(ans)

P.3 题号 202. Happy Number

我记得这道题目超级经典。没想到今天又刷到了。看来要祭出python的黑魔法了！大概就是用一个set来存visit过的数字。然后那个黑魔法是把数字按位打散，然后再加起来。

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """

        memo = set()

        while n not in memo and n!=1:
            memo.add(n)
            n = sum(map(lambda x: x**2, map(int, list(str(n)))))
        return n==1

s = Solution()
ans = s.isHappy(12)
print(ans)

P.4 198. House Robber

太久没练习，居然连这道题都生得不行！！

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        if len(nums)<=2:
            return max(nums)

        dp = [0]*len(nums)
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        return dp[-1]


args = [[1,2,3,4,5,6]]
s = Solution()
ans = s.rob(*args)
print(ans)

然后这道题 可以优化成用constant space

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pre2 = pre1 = cur = 0
        for num in nums:
            cur = max(pre2 + num, pre1)
            pre2 = pre1
            pre1 = cur

        return cur

args = [[1,2,3,4,5,6]]
s = Solution()
ans = s.rob(*args)
print(ans)

P5. Two Sum

天天考别人。也该自己做一下了。这道可真是祖传的好题啊。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}

        for i, num in enumerate(nums):
            if target - num not in dic:
                dic[num] = i
            else:
                return [dic[target - num], i]

        return None

args = [[1,2,3,4,5,6], 8]
s = Solution()
ans = s.twoSum(*args)
print(ans)

P6. Valid Parentheses

这道题是一道经典的stack的题目呀。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        dic = {
            "}": "{",
            "]": "[",
            ")": "(",
        }

        for a in s:
            if a in "{[(":
                stack.append(a)
            else:
                if stack and stack[-1]==dic[a]:
                    stack.pop()
                else:
                    return False

        return stack==[]


args = ["()[]{"]
s = Solution()
ans = s.isValid(*args)
print(ans)

P7. Contains Duplicate

PY黑魔法！

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(set(nums))!=len(nums)

P8. Single Number

我的心，我的心，是那python魔法闪耀！

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(lambda x, y: x ^ y, nums)

P9. Contains Duplicate II

大概就是维护一个长度为k的hash set。

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        tmp = set()

        for i in range(len(nums)):
            num = nums[i]
            if num in tmp:
                return True
            else:
                tmp.add(num)
                if len(tmp)>k:
                    tmp.remove(nums[i-k]) 

        return False


args = [[1, 1], 0]
s = Solution()
ans = s.containsNearbyDuplicate(*args)
print(ans)

P10. Intersection of Two Linked Lists

哎哟，简直都要忘完了！ 捡起来，捡起来！

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        a, b = headA, headB
        while a!=b:
            a = headB if not a else a.next
            b = headA if not b else b.next

        return a


a = ListNode(1)
b = a
args = [a, b]
s = Solution()
ans = s.getIntersectionNode(*args)
print(ans)

P11. Reverse Bits

好吧，这道题用python比较取巧。。

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        return int(bin(n)[2:].zfill(32)[::-1], 2)

好吧，11道easy就是这么不禁打！我们meduim见。