12月15日
因为报了明年的蓝桥杯，博主此时要学习python的算法了，以后有什么收获都会发在这个页面里面
更新ing。。。。
12月17日
快排算法分享
介绍：给定一个数组，要求对数组进行升序排序。而快排就是把数组排序好的基础上时间复杂度最低的，非常之nb，同时，效果越好，索要的代码复杂度就会提升，本章节就将对快排的思想进行进一步的加深，以及代码中可能会出现的小问题。
思想：
- 一列数组，有左指针和右指针，以及一个key（一般都设置为数组第一个即a[0]），左指针起始在0号位置（数组左边）右指针起始在最右边。
- 移动右指针，依次与key比较，若大于key就right–（指针左移），直到a[right]<key,就将左指针上的值（a[left]）设为右指针上的值，即a[left] = a[right],执行第三步
- 移动左指针，依次与key比较，若小于key就left++（指针右移动）,直到a[left]>key,就将右指针上的值（a[right]）设为左指针上的值,即a[right] = a[left],执行第四步
- 判断left是否等于right，若等于，则退出循环，执行第五步.若不等于，则重复23步
- 最终让a[left] = key，此时key在数组中，key的左边即为比key小的数，右边即为比key大的数，把左边和右边分别看成两个新的数组，然后重复1234步（递归的思想）
代码如下
#include <stdio.h>
void print(int a[] ,int n)
{//输出数组元素，数字之间以一个空格为界，输出结束后换一行
if(n==1) return ;
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void qSort(int a[] ,int left, int right) //
{
if(left>=right) return ;//这一步非常关键，保证了不会重复排序
int L = left;
int R = right;
int key = a[left];
while(left!=right)
{
for(;right>left;right--)
{
if(a[right]<key)
{
a[left] = a[right];
break;
}
}
if(right==left)
{
break;
}
for(;left<right;left++)
{
if(a[left]>key)
{
a[right] = a[left];
break;
}
}
}
//printf("右边是%d\n左边是%d\n",R,L);
//printf("关键变量是%d\n",key);
//if(L==left&&R==right) return ;
a[right] = key;
print(a,R+1);
if(left!=0) qSort(a ,L,left-1);//左指针和右指针的位置很关键
if(right<R)qSort(a ,left+1,R);
}
int main(void)
{
int num ;
scanf("%d",&num);
int data[num];
for(int i=0;i<num;i++)
scanf("%d",&data[i]);
qSort(data ,0,num-1);
print(data,num);
}参考资料：
后续学到有趣的算法也会分享到这里，尽情期待。。。。
1月12日（dp和递归问题）
详情见力扣1月12日周赛题目（点我）
这题用的是动态规划的解法
class Solution:
def maximumAmount(self, coins: List[List[int]]) -> int:
# 每一个格子等于max(dfs(i-1,j,k),dfs(i,j-1,k))+x,多考虑一个要不要感化
@cache# 这个很nb，记忆化搜索，防止超出时间限制
def dfs(n,m,k):
if n<0 or m<0:
return -inf
x = coins[n][m]
if n==0 and m==0:
return max(x,0) if k else x
big = max(dfs(n-1,m,k),dfs(n,m-1,k))+x
if x<0 and k>0:
big = max(big,dfs(n-1,m,k-1),dfs(n,m-1,k-1))
return big
return dfs(len(coins)-1,len(coins[0])-1,2)本题目的思想是从后往前推，不断递归，化繁为简
相类似的题目还有这题（点我）
3月4日
# 输入处理
n, q = map(int, input().split())
s = input()
queries = [tuple(map(int, input().split())) for _ in range(q)]
p,t = fun(s)3月9日
通过counter函数来进行以下操作：记录列表中每个元素出现的次数，并用字典key，value的形式呈现，而且时间复杂度低
from collections import Counter
q,n = map(int,input().split())
#print(q,n)
def cha(t):
ans = 0
c = Counter(t)
for a,b in c.items():
ans+=b*(b-1)//2
return ans4月10日
家谱（题目出处）
# 输入一定要加上.strip()!!!!!!!!!
# 我今天被狠狠恶心了，因为我没加.strip(),使得我的答案看起来一样却总# 是不对
# 一下为并查集的代码，
pre = {}
def find(a):
if pre[a]==a:
return a
else:
pre[a] = find(pre[a])
return pre[a]
def union(a,b):# a为儿子,b为爸爸
if find(a)!=find(b):
pre[find(a)] = find(b) # 祖先连接
else:
return
father = ''
while(1):
a = input().strip()
#print(a)
if a[0]=='#':
name = a[1:]
if name not in pre:
pre[name] = name
father = a[1:]
if a[0]=='+':
name = a[1:]
if name not in pre:
pre[name] = name
union(a[1:],father)
if a[0]=='?':
name = a[1:]
if name not in pre:
pre[name] = name # 初始化父节点为自己
print(name, find(name))
if a[0]=='$':
break
# 堆代码
### 以下是堆的简单用法
from heapq import *
hp = []
n = int(input().strip())
for _ in range(n):
m = list(map(int,input().strip().split()))
if m[0]==1:
heappush(hp,m[1])
if m[0]==2:
print(hp[0])
if m[0]==3:
heappop(hp)
### 进阶
for i in range(m):
heappush(hq，(s[i]，i)) # 添加元组（进行堆排序的时候优先比较元组第一个的值，若一样再比较第二个值，谁小谁就排前面）
for R in range(m, n):
heappush(hq，(s[R]，R))
mn,mni= heappop(hq)
while mni <L:
mn,mni = heappop(hq)
res += mn
L= mni + 1
print(res)
01背包算法
t,m = map(int,input().strip().split())
cost = [-1]*(m+1)
val = [-1]*(m+1)
for i in range(m):
time,v = map(int,input().strip().split())
cost[i+1] = time
val[i+1] = v
dp = [[0]*(t+1) for _ in range(m+1)]
# dp[i][j]表示前i个物品，总重量不超过j的所有选择方案的集合中，获得# 的最大价值
for i in range(1,m+1):
for j in range(1,t+1):
if j>=cost[i]:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+val[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[m][t])