中级天翼
一、双指针判断回文字符串
bool hw2(string s){
int i=0,j=s.size()-1;
while(i<=j){
if(s[i]!=s[j]){
return 0;
}
i++;
j--;
}
return 1;
}
二、判断质数
bool zs(int n){
if(n==1){
return 0;
}
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
return 0;
}
}
return 1;
}
三、截取单词
s=" "+s+" ";//保证每个单词都被空格包围
for(int i=0;i<s.size();i++){
if(s[i]==' '){//每遇到一个空格
word[cnt++]=s.substr(p+1,i-p-1);//利用空格位置截出一个单词
p=i;
}
}
四、字符串转数字
int n=0;
for(int i=0;i<s.size();i++){
n=n*10+s[i]-'0';
}
五、数字转字符串
while(n){
s=char(n%10+48)+s;
n/=10;
}
李牧晓在2022-02-08 21:47:39追加了内容
啊啊啊啊，臧老师赞我了！！！
李牧晓在2022-02-09 11:27:51追加了内容
六、最小公倍数
for(int i=max(a,b);i<=a*b;i++){
if(i%a==0&&i%b==0){
cout<<i<<" ";
break;
}
}
七、最大公约数（辗转相除法）
while(a%b!=0){
r=a%b;
a=b;
b=r;
}
cout<<b;
李牧晓在2022-02-09 11:29:09追加了内容
第六个缩进多了，复制后自己调一下哈~
李牧晓在2022-02-24 22:45:10追加了内容
/*int hs(int n){
int s=1;
for(int i=1;i<=n;i++){
s*=i;
}
return s;
}
1. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k第一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) {
int left = l, right = r, mid;
while(left<right) { //注意不能写等号，否则可能**循环
mid = left+(right-left)/2;
if(a[mid]<k)
left = mid+1;
else
right = mid;
}
if(a[right]==k) return right;
return -1;
}
2. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k最后一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) {
int left = l, right = r, mid;
while(left<right) { //注意不能写等号，否则可能**循环
mid = left+(right-left+1)/2;
if(a[mid]<=k)
left = mid;
else
right = mid-1;
}
if(a[left]==k) return left;
return -1;
}
左：
l+(r-l)/2
右：
l+(r-l+1)/2
二分查找
void mer(int l,int r){
if(l==r)return ;
int mid=(l+r)/2;
mer(l,mid);
mer(mid+1,r);
int i=l,j=mid+1,cnt=l;
while(i<=mid&&j<=r){
if(a[i]<a[j])b[cnt++]=a[i++];
else b[cnt++]=a[j++];
}
while(i<=mid){
b[cnt++]=a[i++];
}
while(j<=r){
b[cnt++]=a[j++];
}
for(int i=l;i<=r;i++){
a[i]=b[i];
}
} 归并排序
int cmp(int x,int y){
return x<y;
}
void qqs(int l,int r){
int i=l,j=r,k=a[(l+r)/2];
while(i<=j){
while(cmp(a[i],k))i++;
while(cmp(k,a[j]))j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}
if(l<j)qqs(l,j);
if(i<r)qqs(i,r);
}
void qs(int l,int r){
int i=l,j=r,k=a[(l+r)/2];
while(i<=j){
while(a[i]<k)i++;
while(a[j]>k)j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}
if(l<j)qs(l,j);
if(i<r)qs(i,r);
}快排
long long f[100000000]
void ss(int n){
f[1]=1;f[0]=1;
for(int i=2;i*i<=n;i++){
if(!f[i]){
for(int j=i;j<=n/i;j++){
f[i*j]=1;
}
}
}
}
int a[10005],b[10005],c[10005],n;
string f[10005];
string ad(string s1,string s2s){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=s1.size();
b[0]=s2.size();
c[0]=max(a[0],b[0]);
for(int i=1;i<=a[0];i++){
a[i]=s1[a[0]-i]-'0';
}
for(int i=1;i<=a[0];i++){
b[i]=s2[b[0]-i]-'0';
}
int jw=0;
for(int i=1;i<=c[0];i++){
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]%=10;
}
if(jw>0){
c[0]++;
c[c[0]]=1;
}
string s="";
for(int i=c[0];i>=1;i--){
s+=char(c[i]+'0');
}
return s;
}
int ss(int x){
int i;
if(x<=0)return 0;
if(x==1)return 0;
for(i=2;i*i<=x;i++){
if(x%i==0)return 0;
}
return 1;
}
int dx(int m){
int x=0,y;
y=m;
while(y){
x=x*10+y%10;
y/=10;
}
if(m==x)return 1;
return 0;
}
int gcd(int m,int n){
int r;
while(n){
r=m%n;
m=n;
n=r;
}
return m;
}
int gcd(int a, int b){
return a % b ? gcd(b, a % b) : b;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
int fl(int n){
while(n){
int sum+=n%10;
n/=10;
}
return sum;
}
int tgs(int x)
{
int p,r;
if(x<10)
{
p=x*x;
r=p%10;
if (x==r)
{
return 1;
}
else
{
return 0;
}
}
else if(x<100)
{
p=x*x;
r=p%100;
if (x==r)
{
return 1;
}
else
{
return 0;
}
}
else if(x<1000)
{
p=x*x;
r=p%1000;
if (x==r)
{
return 1;
}
else
{
return 0;
}
}
else if(x<10000)
{
p=x*x;
r=p%10000;
if (x==r)
{
return 1;
}
else
{
return 0;
}
}
else if(x<100000)
{
p=x*x;
r=p%100000;
if (x==r)
{
return 1;
}
else
{
return 0;
}
}
}
//
int a[200+10],b[200+10],c[200+10];
string ad(string as,string bs){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int al=as.size(),bl=bs.size();
int cl=max(al,bl)+1;
for(int i=1;i<=al;i++){
a[i]=as[as.size()-i]-'0';
}
for(int i=1;i<=bl;i++){
b[i]=bs[bs.size()-i]-'0';
}
string cs;
for(int i=1;i<=cl;i++){
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]%=10;
}
while(c[cl]==0&&cl>1)cl--;
for(int i=cl;i>=1;i--){
cs+=c[i]+'0';
}
return cs;
}
int zis(int n)
{
if(n<=1) return 0;
int num;
for(int i=2;i*i<=n;i++)while(!(n%i))num=i,n/=i;
if(n>1)num=n;
return num;
}
int cmp(const int &x,const int &y){
return x>y;
}
*/
李牧晓在2022-03-12 00:05:21追加了内容
沈老师也赞我了！
李牧晓在2022-03-12 00:05:51追加了内容
拜托！点赞我的老师真的超帅的好吗！？
李牧晓在2022-04-12 22:40:06追加了内容
呜呜呜，真的没有人看了，我真的是小透明了，浅浅顶一下吧
李牧晓在2022-04-13 19:44:12追加了内容
！！！我真的！！！太激动了！！
李牧晓在2022-04-13 19:44:23追加了内容
！！！我真的！！！太激动了！！
李牧晓在2022-04-22 19:17:18追加了内容
赞赞点一点！~
李牧晓在2022-05-23 22:08:25追加了内容
这个帖已经掉到十万八千里之外了
李牧晓在2022-07-04 12:00:21追加了内容
搜索与回溯的框架
void Search(int x,int y){ //从(x,y)处往外搜
for(int i=1;i<=所有可能;i++){//枚举所有的可能**
if(到达目的点)return
if(满足条件){//约束条件
记录状态
dfs(下个点的位置) //递归搜索
状态恢复
}
}
}
李牧晓在2023-01-07 09:15:36追加了内容
路过的就点个赞吧 已经没有人看这个贴了吧
李牧晓在2023-02-19 23:34:38追加了内容
标准的Floyd：
memset(dis, 0x3f, sizeof(dis));
for(int i=1; i<=m; i++)
dis[u][v] = dis[v][u] = w;
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j] = dis[i][k]+dis[k][j];
Floyd算法判断两点是否连通：
for(int i=1; i<=m; i++)
{
cin >> u >> v;
f[u][v] = true;
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
f[i][j] = f[i][j] || f[i][k] && f[k][j];
}
}
}
李牧晓在2023-02-19 23:37:30追加了内容
并查集:
void init(){
for(int i=1;i<=n;i++)
fa[i]=i;
}//初始化
int find(int x){ //返回x的代表
if(fa[x]==x) return fa[x];
return fa[x]=find(fa[x]);//将find(fa[x]值作为参数传给fa[x] 优化 不然下次再递归到x时，还要继续递归
}//返回x的集合代表
//将x和y合并
void unit(int x,int y){//将x和y合并
x=find(x);
y=find(y);
if(x==y) return ;//如果已经相同了不需要再合并了
fa[y]=x;//x和y此时已经表示各自集合的代表了 令y的代表为x
}
//判断x和y是否属于同一个集合
bool same(int x,int y){//判断x和y是否属于同一个集合
return find(x)==find(y);
}
李牧晓在2023-02-19 23:38:13追加了内容
bfs:
//bfs模板
bfs(st){
q.push(st);//起点入队
vis[st]=true;//起点已访问
while(!q.empty()){//当队列不为空
h=q.front();//取对首元素
q.pop(); //对首出队
if(h==ed) return ;//找到终点 结束
for(int i=1;i<=n;i++){ //枚举当前对首的点能够访问的点
if(!vis[nxt]){//如果可以访问
q.push(nxt);//入队
vis[nxt]=true;//该点已访问
}
}
}
}
李牧晓在2023-02-19 23:39:24追加了内容
vector:
//vector相关函数
a.push_back(x);//在末尾添加元素x
a.pop_back();//删去末尾元素
a.size();//数组长度
a.erase();//删除a中间的某个元素，要用迭代器。
a[idx];//引用位置idx元素
李牧晓在2023-02-19 23:40:16追加了内容
queue:
头文件: #include < queue >
定义: queue< 数据类型 > q;//创建 -一个空队列q
出队: q. pop();
入队: q. push(元素);
取队首: q.front();
判断队空: q. empty();
李牧晓在2023-02-19 23:42:24追加了内容
二分查找：
//1. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k第一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) {
int left = l, right = r, mid;
while(left<right) { //注意不能写等号，否则可能**循环
mid = left+(right-left)/2;
if(a[mid]<k)
left = mid+1;
else
right = mid;
}
if(a[right]==k) return right;
return -1;
}
//2. 在单调递增的有重复元素的数组a中查找元素k，找到则返回k最后一次出现时的位置，找不到则返回-1
int BinarySearch(int a[], int k, int l, int r) {
int left = l, right = r, mid;
while(left<right) { //注意不能写等号，否则可能**循环
mid = left+(right-left+1)/2;
if(a[mid]<=k)
left = mid;
else
right = mid-1;
}
if(a[left]==k) return left;
return -1;
}
李牧晓在2023-02-19 23:43:29追加了内容
回溯法：
//回溯法框架
void Search(int k) {
if(到目的地) 输出解 //边界条件
else
for (i=1;i<=算符总数;i++) //枚举所有可能**
if (满足条件){ //约束条件
保存结果和状态
Search(k+1); //递归搜索
恢复保存结果之前的状态 //状态恢复
}
}
}
李牧晓在2023-02-19 23:45:08追加了内容
迷宫问题：
//1. 边界条件（递归的终点）
//当到达出口 (tx,ty) 时结束
if(x==tx && y==ty) {
输出解/计数/标记；
return;
}
//2. 枚举所有可能**
//从（x,y）往上、下、左、右分别探索
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x+1,y-1);
//或
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0;i<4;i++){
int nx=x+dir[i][0],ny=y+dir[i][1];
dfs(nx,ny);
}
/*
3. 约束条件
1） 不能走到障碍处
这可通过输入的地图信息来判断。比如将地图信息用一个二维数组map[x][y]来存储，map[x][y] = 1表示障碍，map[x][y] = 0表示道路。
2） 不能走出地图边界
如果地图的大小为m*n，且左上角格子下标为（1,1），则到达的坐标（x,y）要满足1<=x<=m, 1<=y<=n
3） 已经走过的位置不能再走
已经走过的位置我们可以通过一个全局的二维数组vis[x][y]来记录。其中可以用vis[x][y] = 1表示(x, y)这个位置已经走过，vis[x][y] = 0表示(x, y)这个位置未走过。
*/
if(map[x][y]==0 && vis[x][y]==0 && x>=1 && x<=m && y>=1 && y<=n){
(x,y)可以走;
}
李牧晓在2023-02-19 23:47:14追加了内容
八皇后：
//八皇后代码实现(标准)
#include <iostream>
using namespace std;
int a[10], b[10], c[20], d[20], cnt;
//a行， b列， c主， d副
void print() {
for(int i=1; i<=8; i++) {
cout << a[i] <<' ';
}
cout << endl;
}
void dfs(int i) {//给第i层放皇后
if(i==9) {
cnt++;
if(cnt<=5)
print();
}
for(int j=1; j<=8; j++) {
if(!b[j] && !c[i-j+8] && !d[i+j]) {
a[i] = j;
b[j] = true;
c[i-j+8] = true;
d[i+j] = true;
dfs(i+1);
b[j] = false;
c[i-j+8] = false;
d[i+j] = false;
}
}
}
int main() {
dfs(1);
cout << cnt;
return 0;
}
李牧晓在2023-02-19 23:48:33追加了内容
前缀和：
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
李牧晓在2023-02-24 23:40:29追加了内容
Dijkstra:
int n;
int cost[MAXN][MAXN];
bool found[MAXN];
int dis[MAXN];
void Dijkstra(int s) {
memset(found, false, sizeof(found));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
while(true) {
int u = -1;
for(int i=1; i<=n; i++)
if(!found[i]&&(u==-1||dis[i]<dis[u]))
u = i;
if(u==-1) return;
found[u] = true;
for(int i=1; i<=n; i++)
// if(cost[u][i]<INF)
dis[i] = min(dis[i], dis[u]+cost[u][i]);
}
}
李牧晓在2023-02-24 23:41:16追加了内容
Prim:
int MST_prim(){
int ans=0;
memset(dis,0x3f,sizeof(dis));
memset(found,false,sizeof(found));
dis[1]=0;
while(1){
int u=-1;
for(int i=0;i<=n;i++){
if(!found[i]&&(u==-1||dis[i]<dis[u])){
u=i;
}
}
if(u==-1) break;
found[u]=true;
ans+=dis[u];
for(int i=0;i<=n;i++){
if(!found[i]&&g[u][i]<dis[i]){
dis[i]=g[u][i];
}
}
}
return ans;
}
李牧晓在2023-02-24 23:41:51追加了内容
90赞啦~
感谢大家的支持
冲一冲突破100吧~
李牧晓在2023-03-20 23:01:36追加了内容
顶一下啦
李牧晓在2023-03-21 18:42:24追加了内容
Prim算法模板：
int MST_prim(){
int ans=0;
memset(dis,0x3f,sizeof(dis));
memset(found,false,sizeof(found));
dis[1]=0;
while(1){
int u=-1;
for(int i=0;i<=n;i++){
if(!found[i]&&(u==-1||dis[i]<dis[u])){
u=i;
}
}
if(u==-1) break;
found[u]=true;
ans+=dis[u];
for(int i=0;i<=n;i++){
if(!found[i]&&g[u][i]<dis[i]){
dis[i]=g[u][i];
}
}
}
return ans;
}
李牧晓在2023-03-21 18:43:40追加了内容
拓扑排序算法模板：
int n,m;
vector<int> g[MAXN];
queue<int> q;
int f[MAXN],in[MAXN];
void Topsort(){
for(int i=1;i<=n;i++){
if(in[i]==0){
q.push(i);
}
}
while(!q.empty()){
int t=q.front();
cout<<t<<" ";
q.pop();
for(int i=0;i<g[t].size();i++){
int idx=g[t][i];
if(--in[idx]==0){
q.push(idx);
}
}
}
}
在这里道个歉，Prim发了两遍~
李牧晓在2023-03-21 18:45:42追加了内容
十进制数转化为k进制：
#include <iostream>
using namespace std;
string s="0123456789ABCDEFGHIJ";
string ans;
int main(){
int n,k;
cin>>n>>k;
while(n){
ans=s[n%k]+ans;
n/=k;
}
cout<<ans;
return 0;
}
李牧晓在2023-03-21 21:03:47追加了内容
纪念一下！~
李牧晓在2023-03-21 21:27:38追加了内容
大家一起努力！
李牧晓在2023-03-28 21:54:56追加了内容
归并排序：
//归并排序在于利用另一个数组进行排序。利用二分查找的思想来实现。一开始二分二分从第一个开始在一个范围里进行排序，使得在这一个区域里所有的数字以升序排列。返回这个序列给上一次调用，然后与上一层调用在以升序。以此类推到最后则调用结束。
#include<iostream>
using namespace std;
int a[101],r[101];
void mergesort (int ,int);
int main(){
int n,i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
mergesort(1,n);
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
void mergesort (int s,int t){
int m,i,j,k;
if(s==t) return ;
m=(s+t)/2;
mergesort(s,m);
mergesort(m+1,t);
i=s;
j=m+1;
k=s;
while(i<=m && j<=t){
if(a[i]<=a[j]){
r[k]=a[i];
i++;
k++;
}
else{
r[k]=a[j];
j++;
k++;
}
}
while(i<=m){
r[k]=a[i];
i++;
k++;
}
while(j<=t){
r[k]=a[j];
j++;
k++;
}
for(i=s;i<=t;i++) a[i]=r[i];
}
斐波那契数列：
F[x]=f[x-1]+f[x-2];
边界条件：f[0]=0,f[1]=1;
前几项数据：0,1,1,2,3,5,8,13,21……
汉罗塔问题：
H[n]=2*H[n-1]+1;
边界：H[1]=1;
前几项数据：1,3,7,15,31,63……
平面分割问题：
A[n]=A[n-1]+2*(n-1);
边界：A[1]=1;
前几项数据：1,3,7,13,21,31……
李牧晓在2023-08-09 10:18:45追加了内容
memset(dp,0x3f,sizeof(dp))//初始dp数组
for(int len=1;len<=n-1;len++){//枚举区间长度
for(int i=1;i<n;i++){//枚举区间的起点
int j=i+len;//根据起点和长度得出终点
if(j>n) break;//符合条件的终点
for(int k=i;k<j;k++)//枚举最优分割点
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程
}
}
区间DP↑
李牧晓在2023-10-05 22:08:30追加了内容
Dijkstra堆优化模板
typedef pair<int,int> P;
int n,m;
struct edge{
int next,w;
};
vector<edge> g[MAXN];
int dis[MAXN];
priority_queue<P,vector<P>,greater<P> > q;
void dijkstra(int st){
memset(dis,0x3f,sizeof(dis));
q.push(P(st,0));
dis[st]=0;
while(!q.empty()){
P h=q.top(); q.pop();
int u=h.first;
if(dis[u]<h.second) continue;
// 小根堆里的队首元素 是最小值，如果满足此条件说明已经被更新过了，就不需要再更新。
dis[u]=h.second;
for(int i=0;i<g[u].size();i++){
edge e=g[u][i];
if(dis[e.next]>dis[u]+e.w){
dis[e.next]=dis[u]+e.w;
q.push(P(e.next,dis[e.next]));
}
}
}
}
李牧晓在2023-10-18 22:00:16追加了内容
填满背包的方案总数
01背包：
j<v[i] 第i件物品一件也放不进去 f[i][j]=f[i-1][j];
j>=v[i] 第i件物品只能放进去一个，f[i][j]=f[i-1][j]+f[i-1][j-v[i]];
即第i件物品一个都不放的情况下填满容量为j的背包的方案数，加上第i件物品只放1件填满容量为j的背包的方案总数
完全背包：
j<v[i] 第i件物品一件也放不进去 f[i][j]=f[i-1][j];
j>=v[i] 第i件物品至少能放进去一个，f[i][j]=f[i-1][j]+f[i][j-v[i]];
即第i件物品一个都不放的情况下填满容量为j的背包的方案数，加上第i件物品至少放1件填满容量为j的背包的方案总数
多重背包：
**多重背包在求方案数时，枚举数量必须从1开始**
初级天翼
我吓得反手一个收藏
高级光能
初级光能
赞赞赞
中级天翼
谢啦，已收藏
初级光能
ding
中级天翼
ding
中级光能
收藏了
初级天翼
你甚至深夜求赞
可惜我点过了
中级天翼
ding
高级光能
最小公倍数可以改成
for(int i=max(a,b);i<=a*b;i+=max(a,b)){
if(i%a==0&&i%b==0){
cout<<i<<" ";
break;
}
}
新手天翼
ding
资深光能
已收藏
新手光能
问一下，你是不是字打错了？
新手光能
ding
初级光能
ding
资深光能
ding
资深光能
大佬NB
修练者
ding
修练者
修练者
ding*INF
高级守护
高级光能
顶
新手光能
ding
中级天翼
ding
初级光能
赞
新手天翼
现在又98力（doge）
新手光能
ding
新手天翼
我是第100赞。。。
初级光能
已点赞+收藏
高级光能
ding
中级天翼
ding
初级光能
后面几个怎么不用图片了？（町）
中级天翼
顶
中级天翼
ding
高级守护
ding
