***def twoSum():
nums=list(eval(input()))
target = int(input())
n = len(nums)
for i in range(n):
for j in range(i+1,n):
if nums[i]+nums[j]==target:
print([i,j])
if __name__=='__main__':
twoSum()
1、最大子数组和
import ast class Solution(object):
def maxSubArray(self, nums):
for i in range(1, len(nums)):#range使用方法：range(start,stop[,step])
nums[i]= nums[i] + max(nums[i-1], 0)
return max(nums)
def main():
obj = ast.literal_eval(input()) use1 = Solution() print(use1.maxSubArray(obj)) if __name__ == '__main__':
main()
2、买卖股票的最佳时机
import ast class Solution:
def maxProfit(self, prices) -> int:
if len(prices) <= 1:
return 0
min_input = prices[0]
max_profit = 0
for p in prices[1:]:
min_input = min(p, min_input)
max_profit = max(max_profit, p - min_input)
print(min_input)
print(p)
return max_profit
def main():
list1 = ast.literal_eval(input()) obj = Solution() print(obj.maxProfit(list1)) if __name__ == '__main__':
main()
3、消失的数字
import ast class Solution:
def missingNumber(self, nums) -> int:
n = len(nums)
sum = n*(n+1)//2 #地板除 ：先做除法，向下取整
for i in nums:
sum -= i
return sum+max(nums)
def main(): list1 = ast.literal_eval(input()) obj = Solution() print(obj.missingNumber(list1)) if __name__ == '__main__':
main()
4、 勾股定理，黑板能否被搬进去
import ast class Solution:
def problem(self, nums):
c = nums[0] ** 2 + nums[1] ** 2
if c >= nums[2] ** 2 or c >= nums[3] ** 2:
print("Just do it.\n")
else:
print("We have a problem.\n")
def main():
list1 = ast.literal_eval(input()) obj = Solution() print(obj.problem(list1)) if __name__ == '__main__':
main()
5、分发饼干
class Solution:
# 思路1：优先考虑胃饼干
def findContentChildren(self, g, s):
g.sort()
s.sort()
res = 0
for i in range(len(s)):
if res <len(g) and s[i] >= g[res]: #小饼干先喂饱小胃口
res += 1
return res
def main(): list1 = list(map(int, input().split())) list2 = list(map(int, input().split())) use1 = Solution() print(use1.findContentChildren(list1,list2)) if __name__ == '__main__':
main()
6、种花问题
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
tmp = [0]+flowerbed+[0]
for i in range(1, len(tmp)-1):
if tmp[i-1] == 0 and tmp[i] == 0 and tmp[i+1] == 0:
tmp[i] = 1 # 在 i 处栽上花
n -= 1
return n <= 0 # n 小于等于 0 ，表示可以栽完花
def main(): list1 = list(map(int, input().split())) n = int(input()) obj = Solution() print(obj.canPlaceFlowers(list1, n)) if __name__ == '__main__':
main()
7、组合总和
class Solution:
def combinationSum4(self, nums, target):
dp = [1] + [0] * target
for i in range(1, target + 1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]
def main():
list1 = list(map(int, input().split()))
n = int(input())
obj = Solution()
print(obj.combinationSum4(list1, n))
if __name__ == '__main__':
main()
8、三角形最小路径和
class Solution:
def minimumTotal(self, triangle):
for i in range(len(triangle) - 1, 0, -1):
for j in range(i):
triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1])
return triangle[0][0]
def main():
n = int(input())
a = []
list1 = []
for _ in range(n):
a.append(list(map(int, input().rstrip().split())))
for i in range(n):
a[i] = a[i]
obj = Solution()
print(obj.minimumTotal(list1))
if __name__ == '__main__':
main()
9、不同路径
from math import comb class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)
def main():
m = int(input())
n = int(input())
obj = Solution()
print(obj.uniquePaths(m,n))
if __name__ == '__main__':
main()
10、在排序数组中查找元素的第一个和最后一个位置
import bisect class Solution:
def searchRange(self, nums, target) :
nums.sort()
print(nums)
lo = bisect.bisect_left(nums, target)
hi = bisect.bisect_right(nums, target)
return [lo, hi-1] if lo != hi else [-1, -1]
def main():
list1 = list(map(int, input().split()))
p = int(input())
obj = Solution()
print(obj.searchRange(list1, p))
if __name__ == '__main__':
main()
11、分解正整数
def division(n, m, string):
if n == 0:
print(string)
else:
if m > 1:
division(n, m - 1, string)
if m <= n:
division(n - m, m, str(m) + ' ' + string)
def main():
print('输入一个正整数：')
n = int(input())
m = n
print('%d的划分如下：' % n)
division(n, m, '')
if __name__ == '__main__':
main()
12、装箱问题 （c++）
using namespace std;
int main(){
int i,j,n;
int v[N];//物品的容量
int a[N];//箱子的容量
int count=0;
int k[N];//装箱下标
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];//每个物品的容量
v[i]=100;//每个箱子容量
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(a[i]<=v[j]){//如果物品容量小于箱子容量，则装箱
v[j]=v[j]-a[i];
k[i]=j;//记录装箱的箱子号
if(count<j)
count=j;//记录箱子个数
break;
}
}
}
for(i=1;i<=n;i++)
cout<<a[i]<<" "<<k[i]<<endl;
cout<<count<<endl;
return 0;
}
13、质数乘积
import math
def isPrime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def Prime_cj(p):
cj = 1
for i in range(2, p + 1):
if isPrime(i) == True:
cj *= i
return cj
def main():
p = int(input())
print(Prime_cj(p) % 5000)
if __name__ == '__main__':
main()
14、恢复二叉搜索树（java）
class Solution {
TreeNode t1, t2, pre; public void recoverTree(TreeNode root) { inorder(root); int temp = t1.val; t1.val = t2.val; t2.val = temp; } public void inorder(TreeNode root){ if (root == null) return ; inorder(root.left); if (pre != null && pre.val > root.val) { if (t1 == null) t1 = pre; t2 = root; } pre = root; inorder(root.right); } } 15、第k个数
class Solution:
def getKthMagicNumber(self, k: int) -> int:
ans, a, b, c = [1], 0, 0, 0
for _ in range(k - 1):
ans.append(min(ans[a] * 3, ans[b] * 5, ans[c] * 7))
a += ans[-1] == ans[a] * 3
b += ans[-1] == ans[b] * 5
c += ans[-1] == ans[c] * 7
return ans[-1]
def main():
k = int(input())
obj = Solution()
print(obj.getKthMagicNumber(k))
if __name__ == '__main__':
main()
16.通过删除字母匹配到字典里最长单词
class Solution:
def findLongestWord(self, s: str, dictionary) -> str:
res = ""
for t in dictionary:
i = j = 0
while i < len(t) and j < len(s):
if t[i] == s[j]:
i += 1
j += 1
if i == len(t):
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res
def main():
s = input()
dic = list(input().split())
obj = Solution()
print(obj.findLongestWord(s,dic))
if __name__ == '__main__':
main()
4.删除有序数组中的重复项 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 def deletNumber(nums:list)->int:
if not nums:
return 0
n=len(nums)
fast=slow=1
while fast<n:
if nums[fast]!=nums[fast-1]:
nums[slow]=nums[fast]
slow +=1
fast +=1
return slow
def main():
nums=list(eval(input()))
print(deletNumber(nums))
if __name__=='__main__':
main()
17、三数之和
from typing import List def threeSum(nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
def main():
list1 = list(map(int, input().split()))
print(threeSum(list1))
if __name__ == '__main__':
main()
18、用最少量的箭引爆气球
from typing import List class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda balloon: balloon[1])
pos = points[0][1]
ans = 1
for balloon in points:
if balloon[0] > pos:
pos = balloon[1]
ans += 1
return ans
def main():
print('请输入共几个气球')
n = int(input())
list1 = [[int(item) for item in input().split()] for row in range(n)]
obj = Solution()
print(obj.findMinArrowShots(list1))
if __name__ == '__main__':
main()
19、无重叠区间
from typing import List def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
if len(intervals) == 0: return 0
intervals.sort(key=lambda x: x[1])
count = 1 # 记录非交叉区间的个数
end = intervals[0][1] # 记录区间分割点
for i in range(1, len(intervals)):
if end <= intervals[i][0]:
count += 1
end = intervals[i][1]
return len(intervals) - count
def main():
print('请输入共几个区间')
n = int(input())
list1 = [[int(item) for item in input().split()] for row in range(n)]
print(eraseOverlapIntervals(list1))
if __name__ == '__main__':
main()
20、化学表达式
def Huaxue(n):
dicta = {
'C': 12.01,
'H': 1.008,
'O': 16.00,
'N': 14.01
}
res = []
for _ in range(n):
s = input()
res.append(s)
for str in res: # 遍历每个化学式
score = 0 # 最终分子数
i = len(str) - 1 # i为最后一个字符，即从最后一个字符开始遍历
if len(str) == 1: # 长度为一，说明就一个分子 直接返回
print(dicta[str[i]])
continue
while i >= 0:
if len(str) == 1: # 这句其实可有可无
break
if str[i].isdigit(): # 判断该字符是否是数字
if i > 0 and str[i - 1].isalpha(): # 判断前一个是否是字母
temp = dicta[str[i - 1]]
score += float(temp * float(str[i]))
i -= 2
continue
if i > 0 and str[i - 1].isdigit(): # 判断前一个是否是数字，如果是 说明该分子式大于10
num = 0
num = int(str[i - 1]) * 10 + int(str[i])
temp = dicta[str[i - 2]]
score += float(temp * float(num))
i -= 3
continue
else:
score += float(dicta[str[i]])
i -= 1
print(score)
def main():
print('请输入一共有几个化学表达式')
n = int(input())
Huaxue(n)
if __name__ == '__main__':
main()
21、周期串
def findTheo():
str1=str(input())
l=len(str1)
for t in range(1,l):
flag = 1
if(l%t==0):
for i in range(t,l):
if str1[i]!=str1[i%t]:
flag=0
break
if flag==1:
print(t)
break
def main():
t=int(input())
while t:
findTheo()
t = t-1
if __name__=='__main__':
main()
3.二叉树中和为某一值的路径 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
class Solution: def pathSum(self, root: TreeNode, target: int) -> List[List[int]]: ret = list() path = list() def dfs(root: TreeNode, target: int): if not root: return path.append(root.val) target -= root.val if not root.left and not root.right and target == 0: ret.append(path[:]) dfs(root.left, target) dfs(root.right, target) path.pop() dfs(root, target) return ret 1.拼车 假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限 制，车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为 一个向量）。 这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息： 必须接送的乘客数量； 乘客的上车地点； 以及乘客的下车地点。 这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一 定在你的行驶方向上）。 请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有 乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请 返回 false）。 示例 1： 输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false def carPooling(trip:list,cap:int)->bool:
hashmap={}#记录站点信息，站点序号：上车人数，下车人数
maxsite=0#记录最大站点数
for i in trip:
for j in range(1,3):
if i[j] not in hashmap:
hashmap[i[j]]=[0,0]#创建新的站点
if j==1:#上车站点
hashmap[i[j]][0]=i[0]#在该站点上车人数
else:#下车站点
hashmap[i[j]][1]=i[0]#在该站点下车人数
if i[j]>maxsite:
maxsite=i[j]
i,c=0,0
while i<maxsite+1:
if i in hashmap:#遍历站点
c -= hashmap[i][1]#先下车
c += hashmap[i][0]#再上车
if c>cap:
return False
break
i = i+1
return True
def main():
trip=list(eval(input('请输入信息')))
cap=int(input('请输入容量'))
print(carPooling(trip,cap))
if __name__=='__main__':
main()
2.二维区域和检索 矩阵不可变 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下 角 (row2, col2) 所描述的子矩阵的元素 总和 。
解释: NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和) 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 200 class NumMatrix:
def __init__(self, matrix: List[List[int]]): if not matrix or not matrix[0]: M, N = 0, 0 else: M, N = len(matrix), len(matrix[0]) self.preSum = [[0] * (N + 1) for _ in range(M + 1)] for i in range(M): for j in range(N): self.preSum[i + 1][j + 1] = self.preSum[i][j + 1] + self.preSum[i + 1][j] - self.preSum[i][j] + matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: return self.preSum[row2 + 1][col2 + 1] - self.preSum[row2 + 1][col1] - self.preSum[row1][col2 + 1] + self.preSum[row1][col1] 第七组 1.最小操作次数使数组元素相等 给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
示例 1： 输入：nums = [1,2,3] 输出：3 解释： 只需要 3 次操作（注意每次操作会增加两个元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
def minMove():
nums=list(eval(input()))
print(sum(nums)-min(nums)*len(nums))
if __name__=='__main__':
minMove()
2.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 # 终止条件，直到两个链表都空 if not l2: return l1 if l1.val <= l2.val: # 递归调用 l1.next = self.mergeTwoLists(l1.next,l2) return l1 else: l2.next = self.mergeTwoLists(l1,l2.next) return l2 3.炒股
def maxTick():
num = int(input())
s = input().split()
pre = -1
cnt,ans =0,0#cnt记录当前增长天数，ans记录最大增长周期
for i in range(num):
if(int(s[i])>int(pre)):
cnt = cnt+1
ans = max(cnt,ans)
else:
cnt=1#增长结束，从0开始
pre = s[i]
print(ans)
if __name__=='__main__':
maxTick()
4.替换空格 请实现一个函数，把字符串s 中的每个空格替换"%20"。 示例 1： 输入：s = "We are happy." 输出："We%20are%20happy." def repBlank():
s=str(input())
print(s.replace(" ","%20"))
if __name__=='__main__':
repBlank()
5.两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组 中找出 和为目标值target 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在 答案里不能重复出现。 你可以按任意顺序返回答案。 def twoSum():
nums=list(eval(input()))
target = int(input())
n = len(nums)
for i in range(n):
for j in range(i+1,n):
if nums[i]+nums[j]==target:
print([i,j])
if __name__=='__main__':
twoSum()