无聊的刷题笔记

股票的最大利润

剑指Offer 63

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制:

0 <= 数组长度 <= 10^5

Solution

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
lowest = prices[0]
profit = 0
for i in prices:
if i < lowest:
lowest = i
if i - lowest > profit:
profit = i - lowest
return profit

扑克牌中的顺子

剑指Offer 61

从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制:

数组长度为 5

数组的数取值为 [0, 13] .

Solution

class Solution:
def isStraight(self, nums: List[int]) -> bool:
h = [0]*14
m = 14
n = -1
wang = 0
for i in nums:
if i == 0:
wang += 1
continue
if h[i] == 1:
return False
else:
h[i] = 1
if i < m:
m = i
if i > n:
n = i
# print(n, m ,wang)
if 4 - wang <=n -m<= 4:
return True
return False

连续整数求和

LeetCode 829

给定一个正整数 N,试求有多少组连续正整数满足所有数字之和为 N?

示例 1:

输入: 5
输出: 2
解释: 5 = 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。
示例 2:

输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
示例 3:

输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
说明: 1 <= N <= 10 ^ 9

Solution

class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
res = 0
for i in range(1, int((2*n)**0.5)+1):
if (2*n -i**2 - i) %(2*i) == 0:
res += 1
return res

礼物的最大价值

剑指Offer 47

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示:

0 < grid.length <= 200
0 < grid[0].length <= 200

Solution

class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
m = len(grid[0])
n = len(grid)
value = [[0 for col in range(m)] for row in range(n)]
for i in range(m):
for j in range (n):
value[j][i] = grid[j][i] + max( 0 if j == 0 else value[j-1][i],
0 if i == 0 else value[j][i-1])
return value[n-1][m-1]

二叉搜索树的最近公共祖先

剑指Offer 68

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

Solution

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

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < q.val:
j, k = p, q
else:
j, k = q, p
# j, k = p, q if p.val < q.val else q, p
while root:
if j.val < root.val < k.val:
return root
elif root.val <j.val:
root = root.right
elif root.val > k.val:
root = root.left
elif root.val == j.val or root.val == k.val:
return root
else:
return None

翻转单词顺序

剑指Offer 58-I

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串”I am a student. “,则输出”student. a am I”。

示例 1:

输入: “the sky is blue”
输出: “blue is sky the”
示例 2:

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

Solution

func reverseWords(s string) string {
word := ""
for i := range s {
if s[i] == ' ' {
for s[i] == ' ' {
i++
if i == len(s) {
return word
}
}
if word == "" {
return reverseWords(s[i:])
}
return reverseWords(s[i:]) + " " + word
} else {
word += string(s[i])
}
}
return word
}

左旋转字符串

剑指Offer 58-II

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串”abcdefg”和数字2,该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1:

输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例 2:

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制:

1 <= k < s.length <= 10000

Solution

func reverseLeftWords(s string, n int) string {
return s[n:] + s[:n]
}