8.21 网易笔试A卷投票+全A代码

A.正解应该是二分找最大值，但暴力可以过，那没事了

#include <bits/stdc++.h>

using namespace std;

int num[100005];
int n;
int main()
{
    n = 0;
    int tmp;
    while(scanf("%d",&tmp)!=EOF){
        num[++n] = tmp;
    }
    int ans = 0;
    sort(num+1,num+n);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(num[i]+num[j]<=num[n])
                ans++;
            else
                break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

B. 将字符串分为三段，然后递归着去找相对应的字符，只有最后一段需要处理下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回Sn的第k位字符
     * @param n int整型 Sn的n
     * @param k int整型 需要返回的字符下标位
     * @return char字符型
     */
    // Sn 2*n+1
    
    char findKthBit(int n, int k) {
        // write code here

        int cnt = 1<<(n-1);
        if(k<cnt)
            return findKthBit(n-1, k);
        if(k==cnt)
            return 'a'+n-1;
        //大于n
        k = k-cnt;
        return 'a'+'z'-findKthBit(n-1, (1<<(n-1))-k);
        }
};

C. leetcode分发糖果的升级版，我只是多加了num[n]和num[1]的大小比较就过了，但其实没有那么清楚为啥只加这一个条件就过了，感觉这个问题挺复杂的，也许是数据水了

#include <bits/stdc++.h>

using namespace std;

int n;
int num[1005];
int val[1005];
int main()
{
    n = 0;
    int tmp;
    while(scanf("%d",&tmp)!=EOF)
    {
        num[++n] = tmp;
    }
    val[1] = 1;
    for(int i=2; i<=n; i++)
    {
        if(num[i]>num[i-1])
            val[i] = val[i-1] + 1;
        else
            val[i] = 1;
    }

    for(int i=n-1; i>=1; i--)
    {
        if(num[i]>num[i+1])
        {
            val[i] = max(val[i],val[i+1]+1);
        }
    }
    //只多加了这一行
    if(num[n]>num[1])
        val[n] = max(val[n],val[1]+1);

    int ans = 0;
    for(int i=1; i<=n; i++)
        ans = ans + val[i];

    printf("%d\n",ans);
    return 0;
}

D.优先队列bfs裸题

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最小航行费用
     * @param input int整型vector<vector<>> 二维网格
     * @return int整型
     */
    int dirx[4]= {0,0,1,-1};
    int diry[4]= {1,-1,0,0};
    int vis[105][105];
    struct node
    {
        node(int xx,int yy,int s)
        {
            x = xx;
            y = yy;
            spend = s;
        }
        int x,y;
        int spend;
        friend bool operator<(const node& x,const node& y)
        {
            return x.spend>y.spend;
        }
    };

    int minSailCost(vector<vector<int> >& input)
    {
        // write code here
        priority_queue<node>q;
        int n = input.size();
        int m = input[0].size();
        vis[0][0] = 1;
        q.push(node(0,0,0));
        while(!q.empty())
        {
            node now  = q.top();
            q.pop();
            if(now.x==n-1&&now.y==m-1)
                return now.spend;
            for(int i=0; i<4; i++)
            {
                int dx = now.x + dirx[i];
                int dy = now.y + diry[i];
                if(dx<0||dy<0||dx>=n||dy>=m||vis[dx][dy]==1||input[dx][dy]==2)
                    continue;
                vis[dx][dy] = 1;
                int v = now.spend;
                if(input[dx][dy]==1)
                    v++;
                else
                    v+=2;
                q.push(node(dx,dy,v));
            }
        }
        return -1;
    }
};

#网易笔试##笔试题目##笔经##秋招#