题目： 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
暴力法:
思路1：索引i和j围成的矩形面积为s=(j-i+1)*min(heights[i:j+1])
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
#暴力法
if not heights:return 0
res = 0
for i in range(0,len(heights)):
Min = heights[i]
for j in range(i,len(heights)):
Min = min(Min,heights[j])
res = max(res,(j-i+1)*Min)
#print(i,j,Min)
return res
#改进：第二次循环可以将j移到最后一个大于Min的位置，避免多余计算。思路2：以索引i为中心向左右扩展，找到左右最后一个大于heights[i]的索引left和right，此时矩形面积为s=heights[i]*(right-left+1).矩形意义是以heights[i]为高能围成的最大矩形。
进阶：
单调栈：单调栈是一种特殊的栈，栈内元素保持递增或者递减。 单调栈有两个性质： 1.满足从栈顶到栈底的元素具有严格的单调性 2.满足栈的后进先出特性越靠近栈底的元素越早进栈 利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置，在某些问题中可以将时间复杂度从O(N^2)降低为O(N)
维护逻辑：元素大于栈顶进栈，小于则栈顶出栈直到栈顶小于该元素
#stack存元素的索引
class Solution(object):
def largestRectangleArea(self, heights):
heights.append(-1)
stack = []
maxArea = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
height = heights[stack.pop()]
width = i if not stack else i-stack[-1]-1
maxArea = max(maxArea,height*width)
stack.append(i)
#print(stack)
return maxArea题目：给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
思路：对每一行求出向上的连续为1的柱状图，使用题目84的解法即可。
class Solution:
def largestRectangleArea(self, heights):
heights.append(-1)
stack = []
maxArea = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
height = heights[stack.pop()]
width = i if not stack else i-stack[-1]-1
maxArea = max(maxArea,height*width)
stack.append(i)
#print(stack)
return maxArea
#柱状图采取递归的方式求
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:return 0
last = [int(i) for i in matrix[0]]
res = self.largestRectangleArea(last)
for i in range(1,len(matrix)):
heights = [int(i)+j if int(i) > 0 else 0 for i,j in zip(matrix[i],last)]
print(heights)
res = max(res,self.largestRectangleArea(heights))
last = heights
return res题目：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
思路1：沿用最大长方形的思路，面积计算修改。
class Solution:
def largestRectangleArea(self, heights):
heights.append(-1)
stack = []
maxArea = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
height = heights[stack.pop()]
width = i if not stack else i-stack[-1]-1
#修改面积计算公式
maxArea = max(maxArea,min(height,width)**2)
stack.append(i)
#print(stack)
return maxArea
#柱状图采取递归的方式求
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:return 0
last = [int(i) for i in matrix[0]]
res = self.largestRectangleArea(last)
for i in range(1,len(matrix)):
heights = [int(i)+j if int(i) > 0 else 0 for i,j in zip(matrix[i],last)]
print(heights)
res = max(res,self.largestRectangleArea(heights))
last = heights
return res思路2：直接动态规划
定义dp矩阵，dp[i][j]表示以第i行第j列为右下角的正方形的最大边长。则有递推关系如下
if matrix[i][j] == 0:dp[i][j] = 0
if matrix[i][j] != 0:dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
注：补充全零的行列，便于计算。
#java version
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if(m < 1) return 0;
int n = matrix[0].length;
int max = 0;
int[][] dp = new int[m+1][n+1];
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(matrix[i-1][j-1] == '1') {
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
max = Math.max(max, dp[i][j]);
}
}
}
return max*max;
}
} 题目：一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。为了尽快到达公主，骑士决定每次只向右或向下移动一步。
题目：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。
思路1：建立最小堆，大小为n。依次输出栈顶元素，第k次输出的元素即为所求。时间复杂度为
O(n)+k*log(n)。
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
def heap_sink(heap,index):
left = index*2 + 1
right = index*2 + 2
smallest = index
if left < len(heap) and matrix[heap[left][0]][heap[left][1]] < matrix[heap[smallest][0]][heap[smallest][1]]:
smallest = left
if right < len(heap) and matrix[heap[right][0]][heap[right][1]] < matrix[heap[smallest][0]][heap[smallest][1]]:
smallest = right
if smallest == index:
return
else:
heap[smallest],heap[index] = heap[index],heap[smallest]
heap_sink(heap,smallest)
n = len(matrix)
indexs = [(i,0) for i in range(n)]
for line in matrix:
print(line)
count = 0
heap = sorted(indexs,key=lambda x:matrix[x[0]][x[1]])
while count < k:
top = heap[0]
elem = matrix[top[0]][top[1]]
if top[0] < n and top[1]+1 < n:
heap[0] = (top[0],top[1]+1)
else:
heap[0] = heap[-1]
heap.pop()
heap_sink(heap,0)
count += 1
return elem思路2：二分查找
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击(即两个棋子不能相邻)。
思路：进行递归求解。设当前进行到第i行，前面的棋子记录为record，将i行的棋子每一个与record进行匹配，看是否满足与rocord中的任意棋子不冲突，对满足的棋子继续进行递归。
class Solution:
def totalNQueens(self, n: int) -> int:
def is_valid(record,x,y):
for x1,y1 in record:
if x1 == x or y1 == y or abs(y1-y) == abs(x1-x):
return False
return True
def helper(record,i,n):
if i == n:
self.solution += 1
return
#print(record)
for j in range(n):
if is_valid(record,i,j):
helper(record+[(i,j)],i+1,n)
self.solution = 0
helper([],0,n)
return self.solution题目：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符/删除一个字符/替换一个字符
思路：动态规划。建立dp矩阵，
dp[i][j]表示string1[:i]和string2[:j]的编辑距离。则有如下递推关系：dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(string1[i-1] != string2[j-1]))
矩阵初始化：dp[0][j]=j,dp[i][0]=i
解释：在计算string1[:i]和string2[:j]的编辑距离时，对其末尾有如下四种处理方式，对应递推式右边的四种情况。1.删掉
string1[i-1]
2.删掉string2[j-1]
3.同时删掉string1[i-1]和string2[j-1]
4.同时保留string1[i-1]和string2[j-1],此时有string1[i-1] == string2[j-1]
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if not word1:
return len(word2)
if not word2:
return len(word1)
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)):
dp[i+1][0] = i+1
for j in range(len(word2)):
dp[0][j+1] = j+1
#print(dp)
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
#print(i,j)
dp[i][j] = min(dp[i-1][j-1]+(word1[i-1]!=word2[j-1]),dp[i-1][j]+1,dp[i][j-1]+1)
return dp[-1][-1]题目：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
思路：和编辑距离的思路一致。唯一不同的是，在
string1[i-1] ！= string2[j-1]时，删除操作的步数加2。
#略题目：给定一个字符串 s，找到 s 中最长的回文子串
思路：s前加上标记字符#，建立dp数组，
dp[i]指以s[dp[i-1]]为结尾的最长回文子串。则有如下递推关系：
if s[i] == s[i-1-dp[i-1]]:dp[i]=2+dp[i-1]
if s[i] != s[i-1-dp[i-1]]:dp[i]=max(i-j+1，j从i-1-dp[i-1]取到i使得s[j:i+1]是回文串)
注：第二种情况j的取值不能超出以s[i-1]为结尾的最长回文子串的范围，否则最长的定义相悖。
class Solution:
def longestPalindrome(self, s: str) -> str:
#判断回文串
def is_palindromic(string):
start = 0
end = len(string)-1
while start < end:
if string[start] != string[end]:
return False
start += 1
end -= 1
return True
s = '#' + s
dp = [0]*(len(s))
for i in range(1,len(s)):
if s[i] == s[i-1-dp[i-1]]:
dp[i] = 2 + dp[i-1]
else:
for j in range(i-1-dp[i-1],i+1):
if is_palindromic(s[j:i+1]):
dp[i] = i-j+1
break
Max = max(dp)
for i in range(len(dp)):
if dp[i] == Max:
return s[i-Max+1:i+1]题目：给定一个字符串s，找到其中最长的回文子序列。
思路：建立dp矩阵，
dp[i][j]表示s[i:j+1]的最长回文序列长度，则递推关系如下：
dp[i][j] = max(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]+2*(s[i] == s[j]))
注：dp应该依对角线更新。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
if not s:return 0
if s == s[::-1]:return len(s)
df = [[0]*len(s) for _ in range(len(s))]
for i in range(len(s)):
df[i][i] = 1
for margin in range(1,len(s)):
for i in range(len(s)-margin):
j = i + margin
#print(i,j)
df[i][j] = max(df[i+1][j],df[i][j-1],df[i+1][j-1]+2*(s[i] == s[j]))
return df[0][len(s)-1]题目：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
思路：建立dp数组，
dp[i]表示s[:i+1]的回文子串数目。则有：
dp[i] = dp[i-1] + #(以s[i]结尾的回文串数目)。
class Solution:
def countSubstrings(self, s: str) -> int:
def is_palindrome(s):
start = 0
end = len(s) - 1
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
df = [0]*len(s)
df[0] = 1
#记录从头开始一直相同的序列长度
Len = 0
for i in range(len(s)):
if s[i] != s[0]:
break
Len += 1
#print(Len)
for i in range(1,len(s)):
#特殊情况
if i <= Len-1:
df[i] = (i+1)*(i+2)//2
continue
df[i] = df[i-1]
for j in range(i+1):
if is_palindrome(s[j:i+1]):
df[i] += 1
return dp[-1]题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。
思路1：直接dp。复杂度较高
O(n^2)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:return 0
#以nums[i]结尾的上升子序列的长度
dp = [0]*len(nums)
dp[0] = 1
for i in range(1,len(nums)):
res = 1
for j in range(i):
if nums[i] > nums[j]:
res = max(res,1+dp[j])
dp[i] = res
#print(dp)
return max(dp)思路2：O(n*logn)。todo
#java版本
class Solution {
public int lengthOfLIS(int[] nums) {
/**
dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度.
对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
数组尾部, 并将最长递增序列长度maxL加1
2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
**/
int maxL = 0;
int[] dp = new int[nums.length];
for(int num : nums) {
// 二分法查找, 也可以调用库函数如binary_search
int lo = 0, hi = maxL;
while(lo < hi) {
int mid = lo+(hi-lo)/2;
if(dp[mid] < num)
lo = mid+1;
else
hi = mid;
}
dp[lo] = num;
if(lo == maxL)
maxL++;
}
return maxL;
}
}题目：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度<=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
思路：双指针+贪心即可
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if not s:
return True
index_s = 0
index_t = 0
while index_s < len(s) and index_t < len(t):
if s[index_s] == t[index_t]:
index_s += 1
index_t += 1
else:
index_t += 1
return index_s == len(s)扩展：如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
思路：用一个二维的数组存每个字母在t中出现的位置。第一次遍历t字符串后数组被保存下来，后续判断s是否是子串只需要直接找二维数组中对于s的所有字母是否有一个递增的位置序列即可。 代码如下：
#java version
class Solution {
public boolean isSubsequence(String s, String t) {
if(t == null){
return false;
}
if(s == null || s.length() == 0){
return true;
}
//记录26个字母的出现位置
ArrayList<ArrayList<Integer>> list = new ArrayList<>(26);
for(int i = 0; i < 26; i++){
list.add(new ArrayList<Integer>());
}
for(int i = 0; i < t.length(); i++){
//添加位置信息
list.get(t.charAt(i) - 'a').add(i);
}
int prePos = -1;
ArrayList<Integer> tempList = null;
for(int i = 0; i < s.length(); i++){
tempList = list.get(s.charAt(i) - 'a');
//找到比prePos大的位置的值
boolean flag = false;
for(int j = 0; j < tempList.size(); j++){
//这个地方其实可以用二分法优化，因为一定是有序的
if(tempList.get(j) > prePos){
prePos = tempList.get(j);
flag = true;
break;
}
}
//没找到
if(flag == false){
return false;
}
}
return true;
}
}题目：给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
思路：
- 用哈希表存储每个端点值对应连续区间的长度
- 若数已在哈希表中：跳过不做处理
- 若是新数加入：
- 取出其左右相邻数已有的连续区间长度 left 和 right
- 计算当前数的区间长度为：cur_length = left + right + 1
- 根据 cur_length 更新最大长度 max_length 的值
- 更新区间两端点的长度值
class Solution(object):
def longestConsecutive(self, nums):
hash_dict = dict()
max_length = 0
for num in nums:
if num not in hash_dict:
left = hash_dict.get(num - 1, 0)
right = hash_dict.get(num + 1, 0)
cur_length = 1 + left + right
if cur_length > max_length:
max_length = cur_length
hash_dict[num] = cur_length
hash_dict[num - left] = cur_length
hash_dict[num + right] = cur_length
return max_length题目：找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
思路：
题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。
思路：维护历史最小价格，当前价格大于最小价格时，更新结果。
#一次买进卖出的最大利润
def maxProfitByOne(prices):
profit = 0
#维护历史最小价格
min_stack = []
for i in prices:
if not min_stack or min_stack[-1] >= i:
min_stack.append(i)
else:
profit = max(profit,i-min_stack[-1])
return profit题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：对所有连续递增子数组首尾进行计算即可。简化计算方式：
profit += max(0,prices[j]-prices[j-1])。
#略题目：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路1：借助
买卖一次股票的最大利润，暴力将prices数组拆成两部分。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
#一次买进卖出的最大利润
def maxProfitByOne(prices):
profit = 0
#维护历史最小价格
min_stack = []
for i in prices:
if not min_stack or min_stack[-1] >= i:
min_stack.append(i)
else:
profit = max(profit,i-min_stack[-1])
return profit
res = 0
for i in range(len(prices)):
res = max(res,maxProfitByOne(prices[:i])+maxProfitByOne(prices[i:]))
return res思路2：维护四个状态
min_stack,max_stack,dp1,dp2。min_stack[i]表示前i个元素的最小值，max_stack[i]表示后i个元素的最大值，dp1[i]表示对prices[:i]一次买入卖出的最大利润，dp2[i]表示对prices[-i-1:]一次买入卖出的最大利润。更新模式如下：
dp1[i] = max(dp1[i-1],prices[i-1]-min_stack[i-1])
dp2[i] = max(dp2[i-1],max_stack[i-1]-prices[::-1][i-1])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
#可以同时更新
#min_stack和max_stack计算
min_stack = []
max_stack = []
for i in prices:
if not min_stack or i < min_stack[-1]:
min_stack.append(i)
else:
min_stack.append(min_stack[-1])
for i in prices[::-1]:
if not max_stack or i > max_stack[-1]:
max_stack.append(i)
else:
max_stack.append(max_stack[-1])
#dp1和dp2计算
dp1 = [0]*(len(prices)+1)
dp2 = [0]*(len(prices)+1)
for i in range(2,len(prices)+1):
dp1[i] = max(dp1[i-1],prices[i-1]-min_stack[i-1])
for j in range(2,len(prices)+1):
dp2[j] = max(dp2[j-1],max_stack[j-1]-prices[-j])
return max([i+j for i,j in zip(dp1,dp2[::-1])])思路3：巧妙定义dp变量。对于任意一天考虑四个变量:
fstBuy: 在该天第一次买入股票可获得的最大收益fstSell: 在该天第一次卖出股票可获得的最大收益secBuy: 在该天第二次买入股票可获得的最大收益secSell: 在该天第二次卖出股票可获得的最大收益 分别对四个变量进行相应的更新, 最后secSell就是最大 收益值(secSell >= fstSell)
#java version
class Solution {
public int maxProfit(int[] prices) {
int fstBuy = Integer.MIN_VALUE, fstSell = 0;
int secBuy = Integer.MIN_VALUE, secSell = 0;
for(int p : prices) {
fstBuy = Math.max(fstBuy, -p);
fstSell = Math.max(fstSell, fstBuy + p);
secBuy = Math.max(secBuy, fstSell - p);
secSell = Math.max(secSell, secBuy + p);
}
return secSell;
}
}题目：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路1：暴力递归
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) <= 1:return 0
self.res = 0
def helper(profit,prices,k):
#print(profit,prices,k)
#简单情况
if len(prices) <= 1 or k == 0:
self.res = max(self.res,profit)
return
#找到第一个非递减的
for j in range(1,len(prices)):
if prices[j] > prices[j-1]:
break
Min = prices[j-1]
#可能不取
helper(profit,prices[j:],k)
for i in range(j,len(prices)):
if prices[i] > Min:
helper(profit+prices[i]-Min,prices[i+1:],k-1)
helper(0,prices,k)
return self.res思路2：巧妙的dp。dp数组的定义如下。当k大于等于数组长度一半时, 问题退化为贪心问题此时采用
尽可能买卖股票最大利润的贪心方法解决可以大幅提升时间性能, 对于其他的k,可以采用两次买进卖出的最大利润的方法来解决,两次买进卖出的最大利润[思路3]中定义了两次买入和卖出时最大收益的变量, 在这里就是k组这样的变量,t[i][0]和t[i][1]分别表示第i笔交易买入和卖出时各自的最大收益。
#java version
class Solution {
public int maxProfit(int k, int[] prices) {
#简单情况
if(k < 1) return 0;
#贪心情况
if(k >= prices.length/2) return greedy(prices);
#一般情况
int[][] t = new int[k][2];
for(int i = 0; i < k; ++i)
t[i][0] = Integer.MIN_VALUE;
for(int p : prices) {
t[0][0] = Math.max(t[0][0], -p);
t[0][1] = Math.max(t[0][1], t[0][0] + p);
for(int i = 1; i < k; ++i) {
t[i][0] = Math.max(t[i][0], t[i-1][1] - p);
t[i][1] = Math.max(t[i][1], t[i][0] + p);
}
}
return t[k-1][1];
}
#贪心情况
private int greedy(int[] prices) {
int max = 0;
for(int i = 1; i < prices.length; ++i) {
if(prices[i] > prices[i-1])
max += prices[i] - prices[i-1];
}
return max;
}
}题目：给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:1.你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。2.卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
思路：
题目：给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
思路：维护两个变量cash和hold，分别表示当前不持股和持股的最大收益。然后dp即可。
class Solution(object):
def maxProfit(self, prices, fee):
cash, hold = 0, -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee)
hold = max(hold, cash - prices[i])
return cash题目：编写一个程序，找出第 n 个丑数。丑数就是只包含质因数 2, 3, 5 的正整数。
思路：维护3个指针
id2,id3,id5，每一次向res添加
min(res[id2]*2,res[id3]*3,res[id5]*5)。得出最小数的指针加一。
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
res = [1]
idx2 = 0
idx3 = 0
idx5 = 0
for i in range(n-1):
res.append(min(res[idx2]*2,res[idx3]*3,res[idx5]*5))
if res[-1] == res[idx2]*2:
idx2 += 1
if res[-1] == res[idx3]*3:
idx3 += 1
if res[-1] == res[idx5]*5:
idx5 += 1
return res[-1]题目：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
思路1：建立dp数组。dp[i]表示i的最小平方加和数。则有如下的关系：
dp[i] = min([1+dp[i-j*j] for j in range(1,int(i**0.5)+1)])
但是算法的效率不高，主要在于额外计算了不需要的dp[i]。
#花式超时
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = {0:0,1:1,2:2,3:3}
for i in range(4,n+1):
res = i
sqrti = int(i**0.5)
#简单情况
if sqrti*sqrti == i:
dp[i] = 1
continue
for j in range(1,sqrti+1):
res = min(res,1+dp[i-j*j])
dp[i] = res
return dp[n]思路2：todo
#todo题目：约瑟夫问题的三种解法：1.数组模拟2.循环单链表模拟3.递归解法。n个人排成环，编号0到n-1,从0开始报数，报到m的人出去，然后下一个人继续报数，求第k个出来的人的编号。
思路1：数组模拟
def josephus_sequence_solution(n,m,k):
'''
顺序表模拟
'''
index_table = [1]*n
cur_index = 0 #当前位置
count1 = 0 #记录当前报数数
count2 = 0 #记录出队人数
res = []
while count2 < k:
if index_table[cur_index] == 1:
count1 += 1
if count1 == m:
index_table[cur_index] = 0
res.append(cur_index)
count1 = 0
count2 += 1
if count2 == k:break
cur_index = (cur_index+1) % n
#print(res)
return res思路2：链表模拟（循环单链表）
def josephus_linkList_solution(n,m,k):
'''
循环单链表解法
'''
head = CycleSingleLinkList(range(n))
pre = None
cur = head.next
count1 = 0 #记录当前报数数
count2 = 0 #记录出队人数
res = []
while count2 < k:
if cur:
count1 += 1
if count1 == m:
# 记录
res.append(cur.val)
count2 += 1
count1 = 0
# 删节点
if not pre:
head.next = cur.next # 表长为1怎么办？
else:
pre.next = cur.next
cur = pre.next
else:
pre,cur = cur,cur.next
if count2 == k:
#print(res)
return res递归：
def _josephus_recursive_solution(n,m,k):
'''
递归解法
此时的含义是第k次出队的序号
'''
if k > n:return
if k == 1:
return (n+m-1) % n
else:
return (_josephus_recursive_solution(n-1,m,k-1)+m) % n
def josephus_recursive_solution(n,m,k):
'''
用矩阵来记录老的计算结果
'''
res = []
for i in range(1,k+1):
res.append(_josephus_recursive_solution(n,m,i))
#print(res)
return res