c语言算法题目求职用

c语言算法题目求职用
1.栈的压入与压出
/*
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。n<=100000

用一个栈作辅助,顺序描述压入序列和弹出序列,如果当前位置上压入序列和弹出序列值相等,直接都向后移一个元素;比较栈顶元素和弹出序列当前值,如果相等,出栈,弹出序列后移一个元素;其余情况,将压入序列当前值压栈,压入序列后移一个元素。如果到最后,弹出序列都处理不完,说明弹出序列不合法。时间复杂度为O(n)。
*/
#include <stdio.h>
#include <stack>
using namespace std;

int qin[100005];
int qout[100005];
int main(void)
{
    int n;
    int i,j;
    while(scanf("%d", &n) == 1)
    {
        for(i=0; i<n; ++i)
            scanf("%d", &qin[i]);
        for(i=0; i<n; ++i)
            scanf("%d", &qout[i]);
        
        stack<int> s;
        i = 0;
        j = 0;
        while(i<n || j<n)
        {
            if(i<n && j<n && qin[i]==qout[j])
            {
                ++i;
                ++j;
            }
            else
            {
                if(s.empty())
                {
                    if(i<n)
                    s.push(qin[i++]);
                }
                else if(s.top() == qout[j])
                {
                    s.pop();
                    ++j;
                }
                else if(i<n)
                {
                    s.push(qin[i++]);
                }
                else
                {
                    break;
                }
            }
        }
        
        if(j==n)
        printf("Yes\n");
        else
        printf("No\n");
    }
    
    return 0;
}
c语言算法题目求职用

2.二叉搜索书的后续遍历序列

c语言算法题目求职用
/*
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。n<=10000。

二叉搜索树的性质之一为:根结点值大于左子树,小于右子树。设后序遍历顺序为 A B C,则有A<C<B。因此,从根结点(遍历的最后一个结点)出发,向前找到所有连续的大于根结点的值作为右子树,再往前的所有连续小于根结点的作为左子树,如果往前还有大于根结点的,则不是二叉搜索树的后序遍历结果。递归处理左子树和右子树。时间复杂度约为O(nlogn)。
*/
#include <stdio.h>

int seq[10005];
bool valid(int x, int y)
{
    if(x >= y)
    return true;
    
    int i=y-1;
    while(i>=x && seq[i]>seq[y])
    {
        --i;
    }
    int j = i;
    while(i>=x && seq[i]<seq[y])
    {
        --i;
    }
    if(i>=x)
    return false;
    
    if(!valid(x, j))
    return false;
    
    if(!valid(j+1, y-1))
    return false;
    
    return true;
}

int main(void)
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        for(int i=0; i<n; ++i)
        scanf("%d", &seq[i]);
        
        if(valid(0, n-1))
        printf("Yes\n");
        else
        printf("No\n");
    }
    
    return 0;
}
c语言算法题目求职用

3.数组中出现次数超过一半的数字

c语言算法题目求职用
/*
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。n<=100000

将出现一半的数与其他数两两抵消,剩余的最后一个数即是答案。具体做法是每次选两个不同的数两两抵消,要么会抵消一个答案数字和一个非答案数字,要么抵消两个非答案数字,到最后剩余的一定是答案。时间复杂度为O(n)。
*/
#include <stdio.h>

int f[100005];
int main(void)
{
    int i,n;
    while(scanf("%d", &n) == 1)
    {
        int ans = 0;
        int count = 0;
        for(i=0; i<n; ++i)
        {
            scanf("%d", &f[i]);
            if(count == 0)
            {
                 ans = f[i];
                 count = 1;
            }
            else if(f[i] == ans)
            {
                ++count;
            }
            else
            {
                --count;
            }
        }
        
        count = 0;
        for(i=0; i<n; ++i)
        {
            if(f[i] == ans)
            ++count;
        }
        
        if(count > n/2)
        printf("%d\n", ans);
        else
        printf("-1\n");
    }
    
    return 0;
}
c语言算法题目求职用

4.整数中1出现的次数

c语言算法题目求职用
/*
求两个整数间的数,10进制各个位上1出现的总次数,0<=a,b<=1,000,000,000 

按位统计,统计每位上1出现的次数。当前位刚好是1和刚好是0需要单独考虑。
*/
#include <stdio.h>

long long CountOne(long long x)
{
    long long base = 1;
    long long ans = 0;
    long long temp;
    long long rec = 0;
    while(x)
    {
        temp = x/10;
        ans += temp * base;
        if(x%10 > 1)
        ans += base;
        else if(x%10 == 1)
        {
            ans += rec + 1;
        }
        rec += x%10 * base;
        base *= 10;
        x /= 10;
    }
    return ans;
}

int main(void)
{
    long long a,b;
    while(scanf("%lld%lld", &a, &b) == 2)
    {
        long long sa = 0, sb = 0;
        if(a>b)
        {
            a += b;
            b = a - b;
            a = a - b;
        }
        if(a>0)
        sa = CountOne(a-1);
        sb = CountOne(b);
        printf("%lld\n", sb-sa);
    }
    return 0;
}
c语言算法题目求职用

5.数组中的逆袭对

c语言算法题目求职用
/*
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 

归并排序,在merge的时候统计逆序对,设需要merge的数组为A,B,A大小为n,B大小为m。如果A[i]>B[j],则逆序数将增加n-i。
*/
#include <stdio.h>

int f[100005];
int g[100005];
long long ans;
void Sort(int x, int y)
{
    if(x >= y)
    return ;
    
    int mid = (x+y)>>1;
    Sort(x, mid);
    Sort(mid+1, y);
    
    int i = x;
    int j = mid+1;
    int k = x;
    while(i<=mid || j<=y)
    {
        if(i>mid)
        {
            g[k++] = f[j++];
        }
        else if(j>y)
        {
            g[k++] = f[i++];
        }
        else if(f[i]<=f[j])
        {
            g[k++] = f[i++];
        }
        else if(f[i]>f[j])
        {
            ans += mid - i + 1;
            g[k++] = f[j++];
        }
    }
    for(k=x; k<=y; ++k)
    f[k] = g[k];
}

int main(void)
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        for(int i=0; i<n; ++i)
        scanf("%d", &f[i]);
        
        ans = 0;
        Sort(0, n-1);
        printf("%lld\n", ans);
    }
    
    return 0;
}
c语言算法题目求职用

6.和为s的两个数字

c语言算法题目求职用
/*
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S。n<=1000000

用两个游标,一个从头开始A[i],一个从尾开始A[j],如果A[i]+A[j]<S,则i后移一格,否则j前移一格,如果相等,则记录结果。算法复杂度为O(n)。
*/
#include <stdio.h>

long long num[1000005];
int main(void)
{
    int n;
    long long m;
    while(scanf("%d%lld", &n, &m) == 2)
    {
        int i,j;
        for(i=0; i<n; ++i)
        scanf("%lld", &num[i]);
        
        i = 0;
        j = n-1;
        long long x=-1, y=-1;
        long long v;
        long long res = num[j]*num[j];
        while(i<j)
        {
            v = num[i] + num[j];
            if(v == m)
            {
                if(num[i]*num[j] <= res)
                {
                    x = num[i];
                    y = num[j];
                    res = num[i]*num[j];
                }
                ++i;
                --j;
            }
            else if(v < m)
            {
                ++i;
            }
            else
            {
                --j;
            }
        }
        printf("%lld %lld\n", x, y);
    }
    
    return 0;
}
c语言算法题目求职用

7.猜数字游戏

c语言算法题目求职用
/*
给定n个骰子,每个骰子点数为m,求按概率排序前3的点数和。 概率值按 4 舍 5 入要求保留 2 位小数, n(0<=n<=10),m(6<=m<=8)。 

递推,令f[i][j]表示前i个骰子,点数和为j的次数。有f[i][j] = f[i-1][j-1]+....+f[i-1][j-m]。也可直接用一维的轮换数组进行计算,即g[j] = f[j-1]+...+f[j-m], f=g。
*/
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct T
{
    int id;
    double v;
};

bool cmp(const T &a, const T &b)
{
    if(a.v>b.v)
        return true;
    else if(a.v<b.v)
        return false;
    else
        return a.id<b.id;
}

int main(void)
{
    int n,m;
    bool first = true;
    while(scanf("%d", &n)==1 && n)
    {
        scanf("%d", &m);
        int f[85] = {0};
        int g[85] = {0};
        int i,j,k;
        for(i=1; i<=m; ++i)
        f[i] = 1;
        
        for(i=1; i<n; ++i)
        {
            for(j=0; j<=80; ++j)
            g[j] = 0;
            
            for(j=1; j<=80; ++j)
            {
                for(k=1; k<=m; ++k)
                {
                    if(j-k>0)
                    {
                        g[j] += f[j-k];
                    }
                }
            }
            
            for(j=0; j<=80; ++j)
            f[j] = g[j];
        }
        
        int sum = 0;
        vector<T> ans;
        T t;
        for(i=1; i<=80; ++i)
        {
            if(f[i] > 0)
            {
                sum += f[i];
                t.id = i;
                t.v = f[i];
                ans.push_back(t);
            }
        }
        for(i=0; i<ans.size(); ++i)
        {
            ans[i].v = ((int)(100.0*ans[i].v/sum+0.5))/100.0;
        }
        sort(ans.begin(), ans.end(), cmp);
        
        if(first)
        first = false;
        else
        printf("\n");
        
        for(i=0; i<3; i++)
        {
            printf("%d %.2lf\n", ans[i].id, ans[i].v);
        }
    }
    
    return 0;
}
c语言算法题目求职用

c语言算法题目求职用,布布扣,bubuko.com

c语言算法题目求职用

上一篇:C++ 的 RTTI


下一篇:Wow C++11