常见简单编程题

判断回文数

问题：
用户输入一个4位的整数，如果是回文数显示True，如果不是回文数显示False。
分析：
回文数：回文数，就是反过来的数字和正着的数字是相同的，如1221，倒过来的数还是1221，这就是一个回文数，1234倒过来是4321，不相等，就不是回文数。
append()函数将n的每位进行倒序插入，所以后面直接进行计算就可以

n=int(input("请输入一个整数"))
n1=n
s=[]
num=0
sum1=0
while n>0:
    temp=n%10
    n=n//10
    #s.insert(0,temp)
    s.append(temp)
#print(s)
for i in range(len(s)-1,-1,-1):
    #print(s[i])
    sum1+=s[i]*(10**num)
    num+=1
#print(sum1)
if sum1==n1:
    print("yes")
else:
    print("no")

高精度加减法

/*#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int carry=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) carry+=A[i];
        if(i<B.size()) carry+=B[i];
        C.push_back(carry%10);
        carry=carry/10;
    }
    if(carry) C.push_back(carry);
    return C;
}
int main()
{
    string a,b;
    cin>>a>>b;
    vector<int> A,B,C;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    C=add(A,B);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;
    return 0;
}
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool comp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;

    return true;
}
vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    for(int i=0,borrow=0;i<A.size();i++)
    {
        borrow=A[i]-borrow;
        if(i<B.size()) borrow-=B[i];
        C.push_back((borrow+10)%10);
        if(borrow<0) borrow=1;
        else    borrow=0;
    }

    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
int main()
{
    string a,b;
    cin>>a>>b;
    vector<int>A,B,C;

    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    if(comp(A,B)) C=sub(A,B);
    else C=sub(B,A),cout<<'-';
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;
    return 0;
}

归并排序

#include<iostream>
using namespace std;
const int N=1e5+1;
int q[N],temp[N];
int n;
void Merge_sort(int L,int R)
{
    if(L>=R) return;
    else
    {
        int mid=(L+R)>>1;
        Merge_sort(L,mid);
        Merge_sort(mid+1,R);
        int i=L,j=mid+1,k=0;
        while(i<=mid&&j<=R)
        {
            if(q[i]<=q[j]) temp[k++]=q[i++];
            else temp[k++]=q[j++];
        }
        while(i<=mid) temp[k++]=q[i++];
        while(j<=R) temp[k++]=q[j++];
        for(int i=L,j=0;i<=R;i++,j++)
        {
            q[i]=temp[j];
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    Merge_sort(0,n-1);
    for(int i=0;i<n;i++) cout<<q[i]<<' ';
    return 0;
}

快速排序

#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
void quick_sort(int L,int R)
{
    if(L>=R) return;
    int i=L-1,j=R+1,x=a[(L+R)>>1];
    while(i<j)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(L,j);
    quick_sort(j+1,R);
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    quick_sort(0,n-1);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

逆序对的数量

#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e5+1;
int q[N],temp[N];
int n;
int Merge_sort(int L,int R)
{
    int res=0;
    if(L>=R) return 0;
    else
    {
        int mid=(L+R)>>1;
        res+=Merge_sort(L,mid);
        res+=Merge_sort(mid+1,R);
        int i=L,j=mid+1,k=0;
        while(i<=mid&&j<=R)
        {
            if(q[i]<=q[j]) temp[k++]=q[i++];
            else
            {
                temp[k++]=q[j++];
                res=mid-i+1;
            }
        }
        while(i<=mid) temp[k++]=q[i++];
        while(j<=R) temp[k++]=q[j++];
        for(int i=L,j=0;i<=R;i++,j++)
        {
            q[i]=temp[j];
        }
    }
    return res;
}
int main()
{
    cin>>n;
    LL num;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    num=Merge_sort(0,n-1);
    cout<<num<<endl;
    return 0;
}