大数相加
#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int>& a, vector<int>& b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size() || i < b.size(); i++)
{
if (i < a.size()) t += a[i];
if (i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if (t) c.push_back(1);
return c;
}
int main()
{
string sa, sb;
cin>>sa>>sb;
vector<int>a, b;
for (int i = sa.size() - 1; i >= 0; i--)
{
a.push_back(sa[i] - '0');
}
for (int i = sb.size() - 1; i >= 0; i--)
{
b.push_back(sb[i] - '0');
}
auto c = add(a, b);
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
}
大数减法
#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int>& a, vector<int>& b) //判断ab大小
{
if (a.size() != b.size()) return a.size() > b.size();
else
{
for (int i = a.size()-1;i >= 0; i--)
{
if (a[i] != b[i]) return a[i]>b[i];
}
}
return true;
}
vector<int> sub(vector<int>& a, vector<int>& b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i++)
{
t = a[i] - t; //减去借位数
if (i < b.size()) t -= b[i]; //
c.push_back((t + 10) % 10);
if (t < 0) t = 1; //小于0 则需要借位
else t = 0;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();//去前导零
return c;
}
int main()
{
string sa, sb;
cin >> sa >> sb;
vector<int>a, b;
for (int i = sa.size() - 1; i >= 0; i--)
{
a.push_back(sa[i] - '0');
}
for (int i = sb.size() - 1; i >= 0; i--)
{
b.push_back(sb[i] - '0');
}
if (cmp(a, b))
{
auto c = sub(a , b);
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
}
else
{
auto c = sub(b , a);
cout << "-";
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
};
}
大数乘法（高精度乘低精度）
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int>& a, int b)
{
vector<int> c;
int t = 0; //进位
for (int i = 0; i < a.size() || t; i++)
{
if (i < a.size()) t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while(c.size()>1&&c.back()==0) c.pop_back();//去前导零
return c;
}
int main()
{
string sa;
int b;
cin >> sa>>b;
vector<int>a;
for (int i = sa.size() - 1; i >= 0; i--)
{
a.push_back(sa[i] - '0');
}
auto c = mul(a , b);
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
}
大数除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int>& a, int b,int& r)
{
vector<int> c;
for (int i = a.size()-1; i >=0 ; i--) //从高位开始算
{
r = r * 10 + a[i];
c.push_back(r / b);
r%=b;
}
reverse(c.begin(),c.end()); //翻转
while (c.size() > 1 && c.back() == 0) c.pop_back();//去前导零
return c;
}
int main()
{
string sa;
int b;
cin >> sa>>b;
vector<int>a;
for (int i = sa.size() - 1; i >= 0; i--)
{
a.push_back(sa[i] - '0');
}
int r=0;
auto c = div(a, b, r);
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
cout<<endl;
cout<<r<<endl;
}
前缀和
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
int arr[N];
int sum[N];
int main()
{
int n, m;
cin >> n >> m;
int s = 0;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
s += arr[i];
sum[i] = s;
}
while (m--)
{
int l, r;
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;
}
}
- 求[l,r]的和，计算sum[r]-sum[l-1]；
- 下标从1开始
数组模拟单链表
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+100;
int head=0,cur=1;
int v[N],n[N];
void toHead(int val)
{
v[cur]=val;
n[cur]=head;
head=cur;
cur++;
}
void deleteNum(int k)
{
if(k==0) head=n[head];
else n[k]=n[n[k]];
}
void insertNum(int k,int val)
{
v[cur]=val;
n[cur]=n[k];
n[k]=cur;
cur++;
}
int main()
{
int m;
cin>>m;
while (m -- )
{
char c;
cin>>c;
if(c=='H')
{
int x;
cin>>x;
toHead(x);
}
else if(c=='D')
{
int x;
cin>>x;
deleteNum(x);
}
else if(c=='I')
{
int k,x;
cin>>k>>x;
insertNum(k,x);
}
}
for(int i=head;i!=0;i=n[i])
{
cout<<v[i]<<" ";
}
}
数组模拟双链表
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6;
int v[N], n[N], pre[N], l = 0, r = 1;
int cur=2; //第k个数下标为k+1
void insert(int k, int val) //在第k个数右边添加
{
v[cur] = val;
pre[n[k]] = cur;
n[cur] = n[k];
pre[cur] = k;
n[k] = cur;
cur++;
}
void del(int k) //删除第k个数
{
pre[n[k]] = pre[k];
n[pre[k]] = n[k];
}
int main()
{
n[l] = r;
pre[r] = l;
int m;
cin >> m;
while (m--)
{
string c;
cin >> c;
if (c == "L")
{
int x;
cin >> x;
insert(l, x);
}
else if (c == "R")
{
int x;
cin >> x;
insert(pre[r], x);
}
else if (c == "D")
{
int k;
cin >> k;
del(k+1);
}
else if (c == "IL")
{
int k, x;
cin >> k >> x;
insert(pre[k+1], x);
}
else if (c == "IR")
{
int k, x;
cin >> k >> x;
insert(k+1, x);
}
}
for (int i = n[l]; i != r; i = n[i])
cout << v[i] << " ";
}
139. 单词拆分
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> st;
for(auto &s:wordDict)
{
st.insert(s);
}
vector<bool> dp(s.size()+1);
dp[0]=true;
for(int r=1;r<=s.size();r++)
{
for(int l=0;l<r;l++)
{
if(dp[l]&&st.count(s.substr(l,r-l)))
{
dp[r]=true;
break;
}
}
}
return dp[s.size()];
}
};
51. N 皇后
class Solution {
public:
void dfs(int x,int n,vector<string>& s,vector<vector<string>>& vec,vector<bool>& col,vector<bool>&dg,vector<bool>& udg)
{
if(x==n) //一共需要放置n个棋子
{
vec.push_back(s);
return;
}
for(int i=0;i<n;i++)
{
if(!col[i]&&!dg[x+i]&&!udg[n-x+i])
{
col[i]=dg[x+i]=udg[n-x+i]=true;
s[x][i]='Q';
dfs(x+1,n,s,vec,col,dg,udg);
s[x][i]='.';
col[i]=dg[x+i]=udg[n-x+i]=false;
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> vec;
vector<string> s(n);
vector<bool> col(2*n),dg(2*n),udg(2*n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
s[i].push_back('.');
}
}
dfs(0,n,s,vec,col,dg,udg);
return vec;
}
};
bfs
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
#include<iostream>
#include<queue>
using namespace std;
const int N = 120;
int a[N][N], d[N][N]; //d为到起点的距离
queue<pair<int, int>> q;
int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
int n, m;
int bfs()
{
q.push({ 0,0 }); //初始状态，在0,0点
//距离全部初始化为-1，表示未经过此点
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
d[i][j] = -1;
}
}
d[0][0] = 0; //初始化距离
while (!q.empty())
{
for (int i = 0; i < 4; i++)
{
int x = q.front().first + dx[i];
int y = q.front().second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1 && a[x][y] == 0)
{
d[x][y] = d[q.front().first][q.front().second] + 1;
q.push({ x,y });
}
}
q.pop();
}
return d[n - 1][m - 1]; //返回终点到起点的距离
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
cout << bfs();
}
Q.E.D.