文章目录
一，买卖股票的最佳时机 III
1，程序简介
-
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
-
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
- 输入：prices = [3,3,5,0,0,3,1,4]
- 输出：6
- 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
- 输入：prices = [1,2,3,4,5]
- 输出：4
- 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
- 输入：prices = [7,6,4,3,1]
- 输出：0
- 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
- 输入：prices = [1]
- 输出：0
提示：
- 1 < = p r i c e s . l e n g t h < = 1 0 5 1 <= prices.length <= 10^5 1<=prices.length<=105
- 0 < = p r i c e s [ i ] < = 1 0 5 0 <= prices[i] <= 10^5 0<=prices[i]<=105
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 8 18:43:26 2022
Function: 买卖股票的最佳时机 III
@author: 小梁aixj
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
k = 2
n = len(prices)
dp_i_1_0 = 0
dp_i_1_1 = -prices[0]
dp_i_2_0 = 0
dp_i_2_1 = -prices[0]
for i in range(1, n):
dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + prices[i])
dp_i_1_1 = max(dp_i_1_1, -prices[i])
dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + prices[i])
dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - prices[i])
return dp_i_2_0
二，单词接龙
1，程序简介
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
- 输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
- 输出：5
- 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
示例 2：
- 输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
- 输出：0
- 解释：endWord “cog” 不在字典中，所以无法进行转换。
提示：
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有字符串 互不相同
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 8 18:44:21 2022
Function: 单词接龙
@author: 小梁aixj
"""
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList:
return 0
if beginWord in wordList:
wordList.remove(beginWord)
wordDict = dict()
for word in wordList:
for i in range(len(word)):
tmp = word[:i] + "_" + word[i + 1 :]
wordDict[tmp] = wordDict.get(tmp, []) + [word]
stack, visited = [(beginWord, 1)], set()
while stack:
word, step = stack.pop(0)
if word not in visited:
visited.add(word)
if word == endWord:
return step
for i in range(len(word)):
tmp = word[:i] + "_" + word[i + 1 :]
neigh_words = wordDict.get(tmp, [])
for neigh in neigh_words:
if neigh not in visited:
stack.append((neigh, step + 1))
return 0
三，二叉树展开为链表
1，程序简介
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历(https://baike.baidu.com/item/%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86/6442839?fr=aladdin) 顺序相同。
示例 1：
- 输入：root = [1,2,5,3,4,null,6]
- 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
- 输入：root = []
- 输出：[]
示例 3：
- 输入：root = [0]
- 输出：[0]
提示：
- 树中结点数在范围 [0, 2000] 内
- -100 <= Node.val <= 100
进阶：
- 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
2，程序代码
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 8 18:44:45 2022
Function: 二叉树展开为链表
@author: 小梁aixj
"""
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
while root != None:
if root.left == None:
root = root.right
else:
pre = root.left
while pre.right != None:
pre = pre.right
pre.right = root.right
root.right = root.left
root.left = None
root = root.right