每日Leetcode—算法（13）

121.买卖股票的最佳时机

算法一（自己）：

    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        mini = prices[0]      #设置一个最小的数
        profit = 0     #初始利润设为0
        for i in range(1,len(prices)):    #从第二个数开始循环
            if mini > prices[i]:   #如果mini非最小数，则更新mini
                mini = prices[i]
            if prices[i] - mini > profit:        #两数相减，大于初始利润，则更新利润
                profit = prices[i] - mini
        return profit

算法二：

def maxProfit(self, prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    profit = 0
    mini = prices[0]
    for i in prices:
        mini = min(i, mini)
        profit = max(i - mini, profit)
    return profit

分析：该方法与我自己的相似，但是运用了几个比较函数，使代码变得更加简洁了。

122.买卖股票的最佳时机II

算法：

def maxProfit(self, prices: List[int]) -> int:
    profit = 0
    for i in range(len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

分析：大佬的算法，逻辑超强。
比如[1,3,5,2,6,1,3]
profit=(3-1)+(5-3)+(6-2)+(3-1)

125.验证回文串

算法：

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

分析：filter函数前面讲过。isalnum() 方法检测字符串是否由字母和数字组成，并返回True或者False。

136.只出现一次的数字

算法：

def singleNumber(self, nums: List[int]) -> int:
    a = 0
    for num in nums:
        a = a ^ num
    return a

分析：算法使用了Python中的异或运算，异或运算将数字看做二进制进行运算。
例如：
a = 60（二进制为0011 1100 ）
b = 13（二进制为0000 1101）
异或要求对应的二进位相异时为1，相同时为0。
a^b结果为0011 0001
且异或满足交换律a ^ b ^ c <=> a ^ c ^ b