大数相加

#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.