18.9.10 LeetCode刷题笔记

本人算法还是比较菜的，因此大部分在刷基础题，高手勿喷

选择Python进行刷题，因为坑少，所以不太想用CPP；

1.买股票的最佳时期2

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：买高不买低，向上即可

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        # only for up no for down
        result = 0
        begin = prices[0]
        for p in prices:
            if p > begin:
                result += p - begin
                begin = p
            else:
                begin = min(begin, p)
        return result

2.数组reverse

学到了：Python传入数组对数组进行修改的时候需要

num[:] = re1+re2

3.只出现一次的数字

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

学到了：a 异或 b 异或 a = b

因此解法就是 sum ^= item 每个数，就可以得到b

4.给定两个数组，编写一个函数来计算它们的交集。

import collections
a, b = map(collections.Counter, (nums1, nums2))
return list((a&b).elements())

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        #x取值从0一直到n（不包括n）
        for x in range(n):
            #y取值从x+1一直到n（不包括n）
            #用x+1是减少不必要的循环,y的取值肯定是比x大
            for y in range(x+1,n):
                #假如 target-nums[x]的某个值存在于nums中
                if nums[y] == target - nums[x]:
                    #返回x和y
                    return x,y
                    break
                else:
                    continue

6.反转字符串

可以使用str_arr = list(str);str_arr.reverse();str = "".join(str_arr);

PS str_arr的返回值是None 是直接在str_arr上进行操作的。

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

class Solution:
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        import collections
        dic=collections.Counter(s)#使用字典
        for i in range(len(s)):
            if dic[s[i]]==1:#如果字典中value为1
                return i
        return -1

8. ATOI实现

class Solution:
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        if not str:
            return 0
        str = str.strip() # 去掉相关的前置后置空格
        if len(str) < 1:
            return 0
        number, flag = 0, 1
        if str[0] == '-':
            str = str[1:]
            flag = -1
        elif str[0] == '+':
            str = str[1:]
        for c in str:
            if c >= '0' and c <= '9':
                number = 10 * number + ord(c) - ord('0')
            else:
                break
        number = flag * number
        number = number if number <= 2147483647 else 2147483647
        number = number if number >= -2147483648 else -2147483648
        return number

学到了：

1.Python List 反转 a[::-1]

2.collections.Counter()可以计算哪些元素出现多少次并且使用 map() -> (a&b).elements() 求出交集