LeetCode-算法：151-200（Python）_leetcode 151 python

---

151. 翻转字符串里的单词

思路

1. split()：根据空格分隔单词得到数组
2. list[::-1]：翻转数组
3. " ".join(list())：连接数组为字符串

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(s.split()[::-1])
1
2
3
4
5
6
7

---

152. 乘积最大子数组

思路
参考 53. 最大子序和
动态规划：记录i-1的最大值maxNum和最小值minNum，当nums[i]为正时，乘以最大值（maxNum）得到最大值，nums[i]为负时，当最小值也为负，乘以最小值（minNum）得到最大值。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxNum, minNum, ans = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            maxTmp, minTmp = maxNum, minNum    # i-1的最大值maxNum和最小值minNum   
            maxNum = max(nums[i], maxTmp*nums[i], nums[i]*minTmp)    # 更新maxNum
            minNum = min(nums[i], maxTmp*nums[i], nums[i]*minTmp)    # 更新minNum
            ans = max(ans, maxNum)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

---

153. 寻找旋转排序数组中的最小值

思路
返回比前一个数小的数，如果找不到，返回第一个数即是最小值

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                return nums[i]
        return nums[0]
1
2
3
4
5
6
7
8
9
10

---

154. 寻找旋转排序数组中的最小值 II

思路
搬运 153. 寻找旋转排序数组中的最小值

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i] < nums[i-1]:
                return nums[i]
        return nums[0]
1
2
3
4
5
6
7
8
9
10

---

155. 最小栈

思路
创建栈stack存放元素x，创建辅助栈min_stack存放x对应位置的最小值（如将a压栈入stack，a对应的最小值为a，将a压入min_stack；再将b压入stack时，若a<b，将a压入min_stack。若b在栈内时，a也在栈内，b对应的最小值为a，最小值放在min_stack栈顶）

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = list()
        self.min_stack = [float("inf")]      

    # 将元素 x 推入栈中
    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        self.min_stack.append(min(x, self.min_stack[-1]))    # 始终将最小值放在min_stack栈顶

    # 删除栈顶的元素
    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.min_stack.pop()

    # 获取栈顶元素
    def top(self):    
        """
        :rtype: int
        """
        return self.stack[-1]

    # 检索栈中的最小元素
    def getMin(self):
        """
        :rtype: int
        """
        return self.min_stack[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

---

156-159（无）

---

160. 相交链表

思路
走一走彼此走过的路
A走a+b， B走b+a，有交点时，A和B走的交点的步数一样，终会相遇。无交点时，走完a+b后均为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 = A.next if A else headB    # 当A走到结尾None时，A走B的头结点headB
            B = B.next if B else headA    # 当B走到结尾None时，B走A的头结点headB
        return A
1
2
3
4
5
6
7
8
9
10
11
12
13

---

161（无）

---

162. 寻找峰值

思路
显而易见：返回最大值坐标

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return nums.index(max(nums))
1
2
3
4
5
6
7

思路
二分法

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left+right)//2 
            if nums[mid] > nums[mid+1]:    # nums[mid] > nums[mid+1]说明右边数组是降序，移动right至mid
                right = mid
            else:      # nums[mid] <= nums[mid+1]说明是左边数组是升序，移动left至mid+1
                left = mid + 1
        return left    # 跳出循环后left==right为峰值坐标
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

163（无）

---

164. 最大间距

思路
排序后比较

线性时间复杂度~脑子瓦特啦不想动

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        n = len(nums)
        if n < 2:
            return 0
        ans = abs(nums[1] - nums[0])
        for i in range(2, n):
            temp = abs(nums[i]-nums[i-1])
            ans = max(ans, temp)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

165. 比较版本号

思路

1. 分隔字符串
2. 比较每一位的大小

class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        ver1 = version1.split(".")
        ver2 = version2.split(".")
        for i in range(max(len(ver1), len(ver2))):
            v1 = int(ver1[i]) if i < len(ver1) else 0
            v2 = int(ver2[i]) if i < len(ver2) else 0
            if v1 != v2:
                return 1 if v1 > v2 else -1
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

166. 分数到小数

思路
见代码备注

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator == 0:
            return "0"
        ans = list()
        if (numerator < 0 and denominator > 0) or (numerator > 0  and denominator < 0):    #分子或分母其中一个为负数则结果为负数
            ans.append("-")
        numerator, denominator = abs(numerator), abs(denominator)
        integer, remainder = divmod(numerator, denominator)    # (整数部分，余数部分)
        ans.append(str(integer))   # 整数部分
        if remainder == 0:
            return "".join(ans)    # 余数为0
        ans.append(".")    # 余数不为0，加小数点
        repeat = {remainder:len(ans)}    # 记录余数的位置
        while remainder:
            integer, remainder = divmod(remainder*10, denominator)    # 分母不变，分子为余数*10
            ans.append(str(integer))
            if remainder in repeat:    # 出现重复的余数，添加括号
                ans.insert(repeat[remainder], "(")    # 在第一次出现相关余数的位置添加左括号
                ans.append(")")    # 添加右括号
                break
            repeat[remainder] = len(ans)    # 记录余数的位置
        return "".join(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

167. 两数之和 II - 输入有序数组

思路
双指针

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        left, right = 0, len(numbers) - 1
        while left < right:
            num = numbers[left] + numbers[right]
            if num == target:
                return [left+1, right+1]
            elif num < target:
                left += 1
            else:
                right -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

168. Excel表列名称

思路

1. 下标对应字母创建字符串alphabet
2. 取余数得到对应字母

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        ans = ""
        while n:
            n, remainder = divmod(n-1, 26)
            ans = alphabet[remainder] + ans
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

---

169. 多数元素

思路
Counter得到每个元素每次出现的次数，返回出现次数最大的元素

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counts = Counter(nums)
        return max(counts.keys(), key=counts.get)
1
2
3
4
5
6
7
8

---

170（无）

---

171. Excel表列序号

思路
字母下标加1则是其相应的序列号

class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        ans = 0
        for i in range(len(s)):
            ans = ans*26 + alphabet.index(s[i])+1
        return ans
1
2
3
4
5
6
7
8
9
10
11

思路
字母转数字

class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        for i in range(len(s)):
            ans = ans*26 + ord(s[i]) - ord('A') + 1  # chr(num)): 数字转字母 ord(str): 字母转数字
        return ans
1
2
3
4
5
6
7
8
9
10

---

172. 阶乘后的零

思路
阶层后的零相当于乘以10,10分解质因数得2*5，只要分析阶乘中有多少对2和5。如25！：
$$\begin{gathered} 25!=25\times 24\times 23\times 22\times 21\times 20\times 19\times 18\times 17\times 16\times 15\times 14\times 13\times 12\times 11\times 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1 \\ 25=5\times 5 \\ 24=2\times 2\times 2\times 3 \\ 22=2\times 11 \\ 20=2\times 2\times 5 \\ ... \end{gathered}$$

从以上栗子可以看出，阶乘中相隔2的数字每位至少能得到一个2的质因数，每隔5的数字每位得到一个5的质因数，只需计算出现5的次数

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n > 0:
            count += n // 5
            n //= 5
        return count
1
2
3
4
5
6
7
8
9
10
11

---

173. 二叉搜索树迭代器

思路
见代码备注

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = list()
        self._left = self._inorder(root)
        
        
    def _inorder(self, root):    # 中序遍历，将根结点到最左边的结点一个个的加入至栈中，最左边的结点即是最小的结点
        while root:
            self.stack.append(root)
            root = root.left


    def next(self):
        """
        @return the next smallest number
        :rtype: int
        """
        top_node = self.stack.pop()    # 栈顶部即为最小的结点
        if top_node.right:    # top_node有右结点时，将右子树以中序遍历的方式添加结点至栈stack中
            self._inorder(top_node.right)
        return top_node.val


    def hasNext(self):
        """
        @return whether we have a next smallest number
        :rtype: bool
        """
        return len(self.stack) > 0    # 返回栈中是（True）否（False）还有结点



# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

174. 地下城游戏

思路
动态规划：见代码备注

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float("inf")]*(n+1) for _ in range(m+1)]
        dp[m][n-1], dp[m-1][n] = 1, 1    # 最后一个位置(m-1, n-1)的下方(m, n-1)和右方(m-1, n)设置为1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                # (i, j)的下方(i+1, j)或右方(i, j+1)较小值减去当前位置的健康值得到该位置的最低健康点数，
                # 当计算的结果为负数时（即dungeon[i][j]比下方和右方大），骑士来到该位置只需要1的健康值
                dp[i][j] = max(min(dp[i+1][j], dp[i][j+1])-dungeon[i][j], 1)   
        return dp[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

175. 组合两个表

SQL框架：

Create table Person (PersonId int, FirstName varchar(255), LastName varchar(255))
Create table Address (AddressId int, PersonId int, City varchar(255), State varchar(255))
Truncate table Person
insert into Person (PersonId, LastName, FirstName) values ('1', 'Wang', 'Allen')
Truncate table Address
insert into Address (AddressId, PersonId, City, State) values ('1', '2', 'New York City', 'New York')
1
2
3
4
5
6

思路

1. 表Address中的personId是表 Person 的外关键字，连接这两个表来获取一个人的地址信息
2. 可能不是每个人都有地址信息，应该使用 outer join的left outer join而不是默认的 inner join

# Write your MySQL query statement below
SELECT FirstName, LastName, City, State
FROM Person LEFT JOIN Address
ON Person.PersonId = Address.PersonId
;
1
2
3
4
5

---

176. 第二高的薪水

SQL框架

Create table If Not Exists Employee (Id int, Salary int)
Truncate table Employee
insert into Employee (Id, Salary) values ('1', '100')
insert into Employee (Id, Salary) values ('2', '200')
insert into Employee (Id, Salary) values ('3', '300')
1
2
3
4
5

思路
使用 IFNULL 和 LIMIT 子句

# Write your MySQL query statement below
SELECT
    IFNULL(
      (SELECT DISTINCT Salary
       FROM Employee
       ORDER BY Salary DESC
        LIMIT 1 OFFSET 1),
    NULL) AS SecondHighestSalary;
1
2
3
4
5
6
7
8

---

177. 第N高的薪水

思路
去重

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  RETURN (
      # Write your MySQL query statement below.
      SELECT 
          DISTINCT e.salary
      FROM 
          employee e
      WHERE 
          (SELECT count(DISTINCT salary) FROM employee WHERE salary>e.salary) = N-1
  );
END
1
2
3
4
5
6
7
8
9
10
11
12

---

178. 分数排名

SQL框架

Create table If Not Exists Scores (Id int, Score DECIMAL(3,2))
Truncate table Scores
insert into Scores (Id, Score) values ('1', '3.5')
insert into Scores (Id, Score) values ('2', '3.65')
insert into Scores (Id, Score) values ('3', '4.0')
insert into Scores (Id, Score) values ('4', '3.85')
insert into Scores (Id, Score) values ('5', '4.0')
insert into Scores (Id, Score) values ('6', '3.65')
1
2
3
4
5
6
7
8

思路

1. 降序排列的分数
2. 分数去重后，得到每个分数对应的排名

# Write your MySQL query statement below
SELECT a.Score AS Score,
(SELECT count(DISTINCT b.Score) FROM Scores b WHERE b.Score >= a.Score) AS 'Rank'
FROM Scores a
ORDER BY a.Score DESC
;
1
2
3
4
5
6

---

179. 最大数

思路

1. 自定义排序（冒泡排序）:比较int(str(num1)+str(num2))，int(str(num2)+str(num1))，当第一个数较大时，num1在num2前；当第二个数较大时，num2在num1前
   栗子：
   第一轮排序：
   3, 30, 34, 5, 9
   330 > 303 : 3, 30, 34, 5, 9
   334 < 343 : 34, 30, 3, 5, 9
   345 < 534 : 5, 30, 3, 34, 9
   59 < 95 : 9, 30, 3, 34, 5
   冒泡得到第一位数：9
   第二轮排序：
   303 < 330 : 9, 3, 30, 34, 5
   334 < 343 : 9, 34, 30, 3, 5
   345 < 534 : 9, 5, 30, 3, 34
   冒泡得到第二位数：5
   …
2. 链接数组内的数字，返回结果

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if int(str(nums[i])+str(nums[j])) < int(str(nums[j])+str(nums[i])):
                    nums[i], nums[j] = nums[j], nums[i]
        ans = ""
        for num in nums:
            ans += str(num)
        return str(int(ans))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

180. 连续出现的数字

SQL架构：

Create table If Not Exists Logs (Id int, Num int)
Truncate table Logs
insert into Logs (Id, Num) values ('1', '1')
insert into Logs (Id, Num) values ('2', '1')
insert into Logs (Id, Num) values ('3', '1')
insert into Logs (Id, Num) values ('4', '2')
insert into Logs (Id, Num) values ('5', '1')
insert into Logs (Id, Num) values ('6', '2')
insert into Logs (Id, Num) values ('7', '2')
1
2
3
4
5
6
7
8
9

思路
序号连续的3个数字相等

# Write your MySQL query statement below
SELECT DISTINCT l1.Num AS ConsecutiveNums
FROM Logs l1, Logs l2, Logs l3
WHERE l1.Id=l2.Id-1 AND l2.Id=l3.Id-1 AND l1.Num=l2.Num AND l1.Num=l3.Num
;
1
2
3
4
5

---

181. 超过经理收入的员工

SQL架构：

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, ManagerId int)
Truncate table Employee
insert into Employee (Id, Name, Salary, ManagerId) values ('1', 'Joe', '70000', '3')
insert into Employee (Id, Name, Salary, ManagerId) values ('2', 'Henry', '80000', '4')
insert into Employee (Id, Name, Salary, ManagerId) values ('3', 'Sam', '60000', 'None')
insert into Employee (Id, Name, Salary, ManagerId) values ('4', 'Max', '90000', 'None')
1
2
3
4
5
6
7

思路
无

# Write your MySQL query statement below
SELECT Name Employee 
FROM Employee e 
WHERE Salary > (SELECT Salary FROM Employee WHERE Id=e.ManagerId)
;
1
2
3
4
5

---

182. 查找重复的电子邮箱

SQL架构：

Create table If Not Exists Person (Id int, Email varchar(255))
Truncate table Person
insert into Person (Id, Email) values ('1', 'a@b.com')
insert into Person (Id, Email) values ('2', 'c@d.com')
insert into Person (Id, Email) values ('3', 'a@b.com')
1
2
3
4
5

思路

1. GROUP BY:根据一个或多个列对结果集进行分组
2. HAVING：用于对WHERE和GROUP BY查询出来的分组经行过滤，查出满足条件的分组结果

# Write your MySQL query statement below
SELECT Email
FROM Person
GROUP BY (Email)
HAVING count(Email)>1
;
1
2
3
4
5
6

---

183. 从不订购的客户

SQL架构：

Create table If Not Exists Customers (Id int, Name varchar(255))
Create table If Not Exists Orders (Id int, CustomerId int)
Truncate table Customers
insert into Customers (Id, Name) values ('1', 'Joe')
insert into Customers (Id, Name) values ('2', 'Henry')
insert into Customers (Id, Name) values ('3', 'Sam')
insert into Customers (Id, Name) values ('4', 'Max')
Truncate table Orders
insert into Orders (Id, CustomerId) values ('1', '3')
insert into Orders (Id, CustomerId) values ('2', '1')
1
2
3
4
5
6
7
8
9
10

思路
查询Id不在Orders表中的客户

# Write your MySQL query statement below
SELECT Name Customers
FROM Customers
WHERE Id not in (SELECT CustomerId FROM Orders)
;
1
2
3
4
5

---

184. 部门工资最高的员工

SQL架构：

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, DepartmentId int)
Create table If Not Exists Department (Id int, Name varchar(255))
Truncate table Employee
insert into Employee (Id, Name, Salary, DepartmentId) values ('1', 'Joe', '70000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('2', 'Jim', '90000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('3', 'Henry', '80000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('4', 'Sam', '60000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('5', 'Max', '90000', '1')
Truncate table Department
insert into Department (Id, Name) values ('1', 'IT')
insert into Department (Id, Name) values ('2', 'Sales')
1
2
3
4
5
6
7
8
9
10
11

思路

1. 连接 Employee 和 Department
2. 临时表里用 IN 语句查询部门名字和工资的关系

# Write your MySQL query statement below
SELECT d.name Department, e.name Employee, e.Salary
FROM Employee e JOIN Department d ON e.DepartmentId = d.Id
WHERE (e.DepartmentId, e.Salary) IN (SELECT DepartmentId, MAX(Salary) FROM Employee GROUP BY DepartmentId )
;
1
2
3
4
5

---

185. 部门工资前三高的所有员工

SQL架构：

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, DepartmentId int)
Create table If Not Exists Department (Id int, Name varchar(255))
Truncate table Employee
insert into Employee (Id, Name, Salary, DepartmentId) values ('1', 'Joe', '85000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('2', 'Henry', '80000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('3', 'Sam', '60000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('4', 'Max', '90000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('5', 'Janet', '69000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('6', 'Randy', '85000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('7', 'Will', '70000', '1')
Truncate table Department
insert into Department (Id, Name) values ('1', 'IT')
insert into Department (Id, Name) values ('2', 'Sales')
1
2
3
4
5
6
7
8
9
10
11
12
13

思路

1. 连接表 Employee 和表 Department
2. 前 3 高的薪水意味着有不超过 3 个工资比这些值大

# Write your MySQL query statement below
SELECT d.name Department, e.name Employee, e.Salary
FROM Employee e JOIN Department d ON e.DepartmentId = d.Id
WHERE 3 > (SELECT COUNT(DISTINCT ee.Salary) FROM Employee ee WHERE ee.Salary>e.Salary AND e.DepartmentId = ee.DepartmentId)
;
1
2
3
4
5

---

186（无）

---

187. 重复的DNA序列

思路
创建visited和set集合（可去重），未出现过的DNA序列放入visited中，已出现过在visited中的添加至ans中，返回数组后的ans

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        visited, ans = set(), set()
        for i in range(len(s)-9):
            if s[i:i+10] in visited:
                ans.add(s[i:i+10])
            visited.add(s[i:i+10])
        return list(ans)
1
2
3
4
5
6
7
8
9
10
11
12

---

188. 买卖股票的最佳时机 IV

思路
参考122. 买卖股票的最佳时机 II（多次买卖） 以及 123. 买卖股票的最佳时机 III（两笔买卖）

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k == 0 or not prices:
            return 0
            
        if k >= len(prices)//2:   # 当k大于prices长度的一半时，即可以无限交易
            cost, profit = prices[0], 0
            for i in range(1, len(prices)):
                if prices[i] > cost:    # 当天价格比前一天的价格高时，卖出股票
                    profit += prices[i] - cost
                cost = prices[i]    # 更新成本位当天的价格
            return profit

        dp=[[0, -float("inf")]for _ in range(k)]
        # dp[i][1]:第i次买入股票，dp[i][0]:第i次卖出股票
        for price in prices:
            for i in range(k):
                dp[i][1] = max(dp[i][1], -price) if i==0 else max(dp[i][1], dp[i-1][0]-price)    # 买股票，负数更大表示成本更低
                dp[i][0] = max(dp[i][0], dp[i][1]+price)    # 第i次卖股票
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

189. 旋转数组

思路

1. 翻转整体
2. 翻转前k个数
3. 翻转后n-k个数

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k%n    
        nums.reverse()    # 整体翻转
        for i in range(k//2):    # 翻转前k个数
            nums[i], nums[k-i-1] = nums[k-i-1], nums[i]
        for i in range((n-k)//2):    # 翻转后n-k个数
            nums[k+i], nums[-i-1] = nums[-i-1], nums[k+i]
        return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

190. 颠倒二进制位

思路
见备注

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        i, ans = 32, 0
        while i:
            ans <<= 1    # ans左移一位，最后一位为0
            ans += n&1    # n&1得到n的最后一位二进制，加至ans中
            n>>=1    # n右移一位，去掉n的最后一位二进制
            i -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11

---

191. 位1的个数

思路
见备注

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n:
            ans += n&1    # 加n的最后一位二进制0/1
            n >>= 1    # n右移一位，去掉n的最后一位二进制
        return ans
1
2
3
4
5
6
7
8
9
10
11

---

192. 统计词频

思路

1. `cat文本输出命令
2. xargs分割字符串，n 1每行输出一个，-r–reverse 逆序输出排序结果
3. sort串联排序所有指定文件并将结果写到标准输出,-n–numeric-sort 根据字符串数值比较
4. uniq检查及删除文本文件中重复出现的行列，一般与sort命令结合使用，-c在每列旁边显示该行重复出现的次数

# Read from the file words.txt and output the word frequency list to stdout.
cat words.txt | xargs -n 1 | sort | uniq -c | sort -nr | awk '{print $2" "$1}'
1
2

---

193. 有效电话号码

思路
grep文本行过滤工具，-P使用perl语言的正则表达式引擎进行搜索

# Read from the file file.txt and output all valid phone numbers to stdout.
grep -P '^([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}$' file.txt
1
2

---

194. 转置文件

思路
awk 用于文本处理和报表生成，NF代表一行有多少个域 （也就是一行有多少个单词），NR已经读取的记录数(行数)

# Read from the file file.txt and print its transposed content to stdout.
awk '{    
    for (i=1;i<=NF;i++){
        if(NR==1){
            res[i] = $i
        }
        else{
            res[i] = res[i]" "$i
        }
    }
}
END{
    for(j=1;j<=NF;j++){
        print res[j]
    }
}
' file.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

195. 第十行

awk 'NR==10' file.txt
1

---

196. 删除重复的电子邮箱

# Write your MySQL query statement below
DELETE p2 
FROM Person p1, Person p2
WHERE p1.Email=p2.Email AND p2.Id > p1.Id
1
2
3
4

---

197. 上升的温度

SQL架构

Create table If Not Exists Weather (Id int, RecordDate date, Temperature int)
Truncate table Weather
insert into Weather (Id, RecordDate, Temperature) values ('1', '2015-01-01', '10')
insert into Weather (Id, RecordDate, Temperature) values ('2', '2015-01-02', '25')
insert into Weather (Id, RecordDate, Temperature) values ('3', '2015-01-03', '20')
insert into Weather (Id, RecordDate, Temperature) values ('4', '2015-01-04', '30')
1
2
3
4
5
6

# Write your MySQL query statement below
SELECT w1.Id
FROM Weather w1 join Weather w2 on DATEDIFF(w1.RecordDate, w2.RecordDate)=1 and w1.Temperature > w2.Temperature
1
2
3

---

198. 打家劫舍

思路
见备注

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        dp = [0 for _ in range(n)]
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])    # i-2房屋得到的现金和i房屋相加 与 i-1（不能与i房屋相加）能得到的现金相比较选择较大值
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

199. 二叉树的右视图

思路
层级遍历，保存最后一个数

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        ans = list()
        queue = [root]
        while queue:
            ans.append(queue[-1].val)    
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

200. 岛屿数量

思路
遇到1时，将岛屿数加1，并进行广度优先遍历，将相连的地方修改为0

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    ans += 1
                    visited = [(i, j)]
                    grid[i][j] = "0"    # 置为0，避免重复计算
                    while visited:    # 遇到1的时候，广度优先遍历
                        row, col = visited.pop(0)
                        for x, y in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]:    # 上下左右
                            if 0<=x<m and 0<=y<n and grid[x][y]=="1":    # 判断x, y合法且为1
                                visited.append((x, y))
                                grid[x][y]="0"
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---