鉴于对算法的感觉太少,广度和深度都不够,故开启刷leetcode,在此记录

Easy 篇

1. Two sum

# Given nums = [2, 7, 11, 15], target = 9,
# Because nums[0] + nums[1] = 2 + 7 = 9,
# return [0, 1].

# nums = [1,2,3,4,5]
# print({i:n for i,n in enumerate(nums)})

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i, n in enumerate(nums):
            for j, m in enumerate(nums):
                if n + m == target and i != j:
                    return [i,j]

    def twoSum2(self, nums, target):
        dic = dict()
        for index,value in enumerate(nums):
            sub = target - value  # 3:0 2:1
            if sub in dic:
                return [dic[sub],index]
            else:
                dic[value] = index

print(Solution().twoSum2(nums=[3,2,4],target=6))
# [1, 2]

第一种方式比较直观,双重遍历数组解决问题
第二种采用由和变差的方式,采用字典存储value与index.当当前dic中的key与之前的sub相等,说明target对应的index已找到

7. Reverse Integer

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        y = x if x > 0 else -x
        z = 0
        while y > 0 :
            z = z * 10 + y % 10
            y //= 10
            
        z = z if x > 0 else -z
        if  z > 0xffffffff or z < -0xffffffff:
            return 0
        else:
            return z

print(Solution().reverse(123))

通过拆分每一个数字的各个位,再进行逆序叠加
注意: 在Python3中, a / b,执行真除法,无论操作数的类型怎样,结果都会返回浮点型.
a // b, 执行Floor除法,返回截除余数的整数部分,若操作数中有浮点型,则结果为浮点型

此题中,若使用 a / b,会出现y=0依然能进入到while循环中,此处为Python的Bug.

9. Palindrome Number

# Determine whether an integer is a palindrome. Do this without extra space.

#Example 1234321

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        if x < 0:
            return False

        des = []
        while x > 0:
            des.append(x % 10)
            x //= 10

        dic = {index:value for index,value in enumerate(des)}

        index = 0
        sub = 0
        dic_len = len(dic) - 1
        for x in range(0,dic_len):
            sub = dic[index] - dic[dic_len - index]
            if sub != 0:
                return False;
        return True;


    def isPalindrome2(self,x):
        if x < 0:
            return False

        render = 1
        while x / render >= 10:
            render *= 10

        # render 为 10000
        while x:
            left = x / render
            right = x % 10
            if left != right:
                return False

            x = (x % render) // 10
            render /= 100

        return True

print(Solution().isPalindrome(12321))

方法一将int数转化为以位数为key的字典,通过循环比较首位和对应的尾位,是否相同来判断是否为回文数
方法二直接将int数的首位和尾位提取出来进行比较

20. Valid Parentheses

# Given a string containing just the characters '(', ')', '{', '}', '[' and ']', 
#determine if the input string is valid.

# The brackets must close in the correct order,
# "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #  ord('a')  -->  97
        # chr(97)    -->  a
        # numList = list(map(lambda x:ord(x), s))
        
        m = {'}':'{', ']':'[', ')':'('}
        tempList = []

        for e in s:
            if tempList and (e in m and tempList[0] == m[e]):
                tempList.pop()
            else:
                tempList.append(e)
        return not tempList

print(Solution().isValid("[]{}()"))

比较巧妙的点1. 既然要判断[ ] { } ( )成对存在,则将其转为字典做判断

2. 数组做中间变量存储,如果至少不存在一对成对,则数组不为空
   由于是判断 [ 和 ], 所以 ] 为 key, [ 为value