经典编程题
1. 0-1背包问题
有N件物品和一个容量为V的背包。
第i件物品的体积是vi，价值是wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包流量，且总价值最大。
f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
不选第i个物品：f[i][j]=f[i-1][j]
选第i个物品：f[i][j]=f[i-1][j-v[i]]+w[i]
取两者的最大值
python解法
n, v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
# 初始化，先全部赋值为0，这样至少体积为0或者不选任何物品的时候是满足要求
dp = [[0 for i in range(v+1)] for j in range(n+1)]
for i in range(1, n+1):
for j in range(1,v+1):
dp[i][j] = dp[i-1][j] # 第i个物品不选
if j>=goods[i-1][0]:# 判断背包容量是不是大于第i件物品的体积
# 在选和不选的情况中选出最大值
dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1][0]]+goods[i-1][1])
print(dp[-1][-1])2.最长公共子序列
3.回文子串的个数
Input : str = "abcd"
Output : 4
Explanation :- palindromic subsequence are : "a" ,"b", "c" ,"d"
Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"
与leetcode 647相似
def countPS(str):
N = len(str)
# Create a 2D array to store the count of palindromic subsequence
cps = [[0 for i in range(N + 2)]for j in range(N + 2)]
# palindromic subsequence of length 1
for i in range(N):
cps[i][i] = 1
# check subsequence of length L
# is palindrome or not
for L in range(2, N + 1):
for i in range(N):
k = L + i - 1
if (k < N):
if (str[i] == str[k]):
cps[i][k] = (cps[i][k - 1] +
cps[i + 1][k] + 1)
else:
cps[i][k] = (cps[i][k - 1] +
cps[i + 1][k] -
cps[i + 1][k - 1])
# return total palindromic subsequence
return cps[0][N - 1]
# Driver program
str = "abcb"
print("Total palindromic subsequence are : ", countPS(str))4.计算器
给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算数表达式(括号除外)，计算其结果。表达式仅包含非负整数，+， - ，，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
from collections import deque
class Solution:
def calculate(self, s: str) -> int:
n = len(s)
s = deque(s)
num = 0
sign = "+"
res = []
for i in range(n):
char = s.popleft()
if char.isdigit():
num = num * 10 + int(char)
if char == "(":
num = self.calculate(s)
if (not char.isdigit() and char != " ") or not s:
if sign == "+":
res.append(num)
if sign == "-":
res.append(-num)
if sign == "*":
res.append(res.pop() * num)
if sign == "/":
res.append(int(res.pop() / num))
num = 0
sign = char
if char == ")":
break
return sum(res)5. 二进制求和
可以转换为其他进制的求和
class Solution:
def addBinary(self, a: str, b: str) -> str:
r, p = '', 0
d = len(b) - len(a)
# 默认是b大于a，补充使两者一样长
a = '0' * d + a
b = '0' * -d + b
# a,b逆序
for i, j in zip(a[::-1], b[::-1]):
s = int(i) + int(j) + p
r = str(s % 2) + r
p = s // 2
return '1' + r if p else r6. 丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, N):
# write code here
if N <= 0:
return 0
index2,index3,index5=0
res=[1]
for i in range(1,N):
u2=res[index2]*2
u3=res[index3]*3
u5=res[index5]*5
res.append(min(min(u2,u3),u5))
# res中的数是2,3,5的倍数
if res[i]/2==res[index2]:
index2+=1
if res[i]/3==res[index3]:
index3+=1
if res[i]/5==res[index5]:
index5+=1
return res.pop()6.1 京东8.27笔试第一题
2，3，5组成的所有数的第n个数
解法一：使用队列deque
from collections import deque
def find_num(self,n):
if n<=0:
return None
res=[2,3,5]
res=deque(res)
k=0
while res:
temp=res.popleft()
k+=1
if k==n:
return temp
res.append(temp*10+2)
res.append(temp*10+3)
res.append(temp*10+5)解法二：转换为3进制
7. 买卖股票的最佳时期
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
解法一：两个变量，minPrice存储最小价格，maxProfit存储最大收益，遍历整个数组
def maxProfit(self,prices):
if len(prices)==0:
return 0
# 正无穷
minPrice=float("inf")
maxProfit=0
for i in prices:
if i<minPrice:
minPrice=i
if i-minPrice>maxProfit:
maxProfit=i-minPrice
return maxProfit解法二：动态规划
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
n = len(prices)
dp = [[0 for i in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,n):
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1],-prices[i])
return dp[n-1][0]
