首页 / 算法 / 牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7015字，纯文字阅读大概需要11分钟。

内容图文

这套题的难受还是有的，不过有些题想想还是可以做的，只是有些题用暴力的方法感觉有点失望。

Q1:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片

解题思路：这个题很明显，一个只能产奇数，一个只能产偶数，倒着分奇偶跑一遍就行啦～

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        stack<int> s;
        while(n)
        {
            if(n&1)
            {
                n >>= 1;
                s.push(1);
            }
            else
            {
                n = (n-2)>>1;
                s.push(2);
            }
        }
        while(!s.empty())
        {
            printf("%d",s.top());
            s.pop();
        }
        printf("\n");
    }
    return 0;
}

Q2:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片

解题思路：这题没说的，直接算就行了。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
    int n;
    while (~scanf("%d",&n))
    {
        int re = 0;
        int temp = n;
        while (temp)
        {
            re = re*10 + temp%10;
            temp /= 10;
        }
        printf("%d\n",re+n);
    }
    return 0;
}

Q3:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片

解题思路：也是过一遍就行了，没难度。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
    char str[55];
    while (~scanf("%s",str))
    {
        char pre = str[0];
        int length = 1;
        int cnt = 1;
        int l = strlen(str);
        int sum = 0;
        for (int i = 1 ; i < l ; i++)
        {
            if (str[i] != pre)
            {
                pre = str[i];
                cnt++;
                sum += length;
                length = 1;
            }
            else
                length++;
        }
        sum += length;
        printf("%.2lf\n",(double)sum/cnt);
    }
    return 0;
}

Q4:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片
解题思路：这个题就有点意思了。用贪心的思想，首先尽量向深处走(使用dfs查看深度)，然后就分两种情况：1.把所有步数用光也走不到底，那么答案就是步数。2.如果可以走到最深处，那么剩下的步数就每两步走一个格子(这一句是关键，举几个例子就能想通了)。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
vector<int> edge[55];
int max_deep;
 
void dfs(int from, int fa, int deep)
{
    max_deep = max(max_deep, deep);
    for (int i = 0 ; i < edge[fa].size() ; i++)
    {
        if (edge[fa][i] == from)
            continue;
        dfs(fa, edge[fa][i], deep+1);
    }
}
int main()
{
    int n, l;
    while(~scanf("%d %d",&n,&l))
    {
        for (int i = 0 ; i < n ; i++)
            edge[i].clear();
        max_deep = 0;
        for (int i = 1 ; i < n ; i++)
        {
            int t;
            scanf("%d",&t);
            edge[i].push_back(t);
            edge[t].push_back(i);
        }
        dfs(0, 0, 0);
        //如果最深的一层走不完，那直接就有结果了
        if (l <= max_deep)
            printf("%d\n",l+1);
        else
            printf("%d\n",max_deep+1+min(n-1-max_deep, (l-max_deep)>>1));
    }
    return 0;
}

Q5:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片
解题思路：这个题也有点意思，需要想明白下面几点：1.不是2的倍数的数必须和4的倍数相邻。2.2的倍数的那些数，可以考虑为一个数，例如2 2 2 2其实和一个2是同样的效果，也必须和4相邻(如果不在边界的话)。
所以问题就简单了，统计2的倍数(不是4的倍数)，4的倍数，其它奇数的数量，如果4的数量可以满足足够插在上面的数字中，则可以满足。下面代码更直观一些。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        int cnt1 = 0;       //是4的倍数
        int cnt2 = 0;       //不是4的倍数
        int cnt3 = 0;       //这里还要考虑不是2的倍数的数，如果没有，也是Yes
        for (int i = 1 ; i <= n ; i++)
        {
            int t;
            scanf("%d",&t);
            if (t%4 == 0)
                cnt1++;
            else if (t%2 == 0)
                cnt2++;
            else
                cnt3++;
        }
        if (cnt1 >= cnt3+(cnt2!=0)-1 || cnt3 == 0)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

Q6:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片
好题啊！！！
解题思路：本以为是个什么dp的问题(因为dp不好，一碰见没思路的计数问题就想到dp)。结果后来看了解题思路，发现就是暴力题：枚举每一个位置的括号，尝试放在各个位置，这时候的LCS一定是length-1，因为只有我们枚举的这个字符位置变了，这个也是最大的LCS，因为我们就移动了一个字符。然后我们把枚举成功的字符串放进set里，结果就是set.size()-1

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <iostream>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
    string str;
    while (cin >> str)
    {
        set<string> s;
        s.insert(str);
        //取每个字符
        for (int i = 0 ; i < str.size() ; i++)
        {
            string pre = str.substr(0, i) + str.substr(i+1);
            //枚举每个位置
            for (int pos = 0 ; pos < pre.size() ; pos++)
            {
                string new_string = pre.substr(0,pos) + str[i] + pre.substr(pos);
                //判断是否合法
                int num = 0;
                for (int j = 0 ; j < new_string.size() ; j++)
                {
                    if (new_string[j] == '(')
                        num++;
                    else
                        num--;
                    if (num < 0)
                        break;
                }
                if (num == 0)
                    s.insert(new_string);
            }
        }
        cout << s.size()-1 << endl;
    }
    return 0;
}

Q7:

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片
还是一个好题
解题思路：考虑dp，我们反向思考。先画个抽象的图，dp[i][j]表示小Q演奏到i，牛博士演奏到j，可以想到dp[i][j] == dp[j][i]，我们假设有三个音符：

可以发现右半边没画，就是因为两边其实是一样的。
每个结点表示当前结点和下面最优的结点(即花费最小)的贡献之和。
再看看状态是怎么转移的：比如我们看dp[1][2]这个结点，下来要演奏的是3号音符。如果让小Q演奏，那么状态就到了dp[3][2]上，代价为dp[3][2]+abs(num[3]-num[1])。其它的结点也就同理了。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
LL dp[2005][2005];
int v[2005];
int n;
LL dfs(int i,int j)
{
    int ne = max(i, j) + 1;
    //如果没有下一个音符
    if (ne == n+1)
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
 
    dp[i][j] = 1e6*2000+5;
    dp[i][j] = min(dp[i][j], dfs(ne, j) + (i ? abs(v[ne] - v[i]) : 0));
    dp[i][j] = min(dp[i][j], dfs(i, ne) + (j ? abs(v[ne] - v[j]) : 0));
    dp[j][i] = dp[i][j];
    return dp[i][j];
}
int main()
{
    scanf("%d",&n);
    for (int i = 1 ; i <= n ; i++)
        scanf("%d",&v[i]);
    CLR(dp, -1);
    printf("%lld\n",dfs(0,0));
    return 0;
}

Q8：

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & ) - 文章图片
解题思路：枚举三个点(确定十字)，然后统计在这个十字上的点的数量即可。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct Dot
{
    int x,y;
}dot[55];
 
bool is_line(int i, int j, int k)
{
    int x1 = dot[i].x - dot[j].x;
    int y1 = dot[i].y - dot[j].y;
     
    int x2 = dot[k].x - dot[j].x;
    int y2 = dot[k].y - dot[j].y;
 
    return (x1*y2 - x2*y1) == 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1 ; i <= n ; i++)
        scanf("%d",&dot[i].x);
    for (int i = 1 ; i <= n ; i++)
        scanf("%d",&dot[i].y);
     
    int ans = min(n, 3);
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = 1 ; j <= n ; j++)
        {
            if (i == j)
                continue;
            for (int k = 1 ; k <= n ; k++)
            {
                if (j == k || i == k)
                    continue;
                int num = 3;
                for (int p = 1 ; p <= n ; p++)
                {
                    if (p==i || p==j || p==k)
                        continue;
                    if (is_line(i,j,p))
                        num++;
                    else if ((dot[i].x-dot[j].x)*(dot[k].x-dot[p].x) + (dot[i].y-dot[j].y)*(dot[k].y-dot[p].y) == 0)
                        num++;
                }
                ans = max(ans, num);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

内容总结

以上是互联网集市为您收集整理的牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )全部内容，希望文章能够帮你解决牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/853274.html

来源：【匿名】

【上一篇】邻接矩阵 Dijkstra 算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )】教程文章相关的互联网学习教程文章

编程算法 - K路归并排序(k-way merge sort) 代码(C++)【图】

K路归并排序(k-way merge sort) 代码(C++)本文地址: http://blog.csdn.net/caroline_wendyK路归并排序作为经典的外部排序算法, 是程序员必须要掌握的.知识概念参考: <数据结构>主要思想: 在k个已排序的文件中, 选择第一个值, 采用败者树, 更新二叉树结构, 最终选择最优值.代码仅供参考, 如最小值用(-1)代替, 最大值用(100)代替./** main.cpp** Created on: 2014年9月11日* Author: Spike*/#include <fstream> #include <iost...

十大编程算法助程序员走上高手之路

算法一：快速排序算法算法二：堆排序算法算法三：归并排序算法四：二分查找算法算法五：BFPRT(线性查找算法)算法六：DFS（深度优先搜索）算法七：BFS(广度优先搜索)算法八：Dijkstra算法算法九：动态规划算法算法十：朴素贝叶斯分类算法算法一：快速排序算法快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通...

编程实现哈希存储算法的简单实例

编程实现哈希存储算法的简单实现实例。通过编写一个简单的哈希实例来加强对哈希算法的理解。下面实例包括存储与查找算法。拉链法解决冲突问题。如果时间长了对哈希算法的理论知识不够了解，可以先阅读前面转载的两篇文档：字符串哈希到整数函数，算法：http://blog.csdn.net/hzhsan/article/details/25552153Hash算法冲突解决方法分析：http://blog.csdn.net/hzhsan/article/details/25555127// 假设现在要实现一个存储学生信息的...

算法编程学习之递归【代码】

递归:程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递...

编程算法 - 快速排序(QuickSort)和二分查找(BinarySearch)【图】

快速排序(QuickSort)和二分查找(BinarySearch)本文地址: http://blog.csdn.net/caroline_wendy快速排序和二分查找的定义, 网上书上都有, 本文主要是讲解如何写出这两个经典算法.程序员必须掌握的两种算法, 使用任何语言, 使用纸都是必须的.快速排序(C):/** main.cpp** Created on: 2014年9月10日* Author: Spike*/#include <stdio.h> #include <stdlib.h> #include <iostream> #include <exception>int RandomInRange(int st...

编程算法 - 食物链并查集代码(C)【图】

食物链并查集代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 有N只动物, 分别编号为1,2,...,N. 所有动物都属于A,B,C中的一种. 已知A吃B, B吃C, C吃A.按顺序给出两种信息K条.第一种: x和y属于同一类.第二种: x吃y. 信息之间可能会出错和矛盾, 求不正确的信息数.例如:有N=10只动物, 给定K=7条信息.(1) 1: x=101, y=1; 出错:没有101的动物.(2) 2: x=1, y=2; 动物1吃动物2.(3) 2: x=2, y=3; 动物2吃动物3.(4) 2: x=3, y...

编程算法 - 背包问题(记忆化搜索) 代码(C)【图】

背包问题(记忆化搜索) 代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目参考: http://blog.csdn.net/caroline_wendy/article/details/37912949使用记忆化搜索, 需要存储每组的值, 下次不需要进行继续迭代, 可以降低至时间复杂度O(nW).代码:/** main.cpp** Created on: 2014.7.17* Author: spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h> #include <memory.h> #include <limits.h>#include <utility> #inclu...

编程算法 - 最好牛线(Best Cow Line) 代码(C)【图】

最好牛线(Best Cow Line) 代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 给定长度为N的字符串S, 要构造一个长度为N的字符串T. 反复进行如下任意操作.从S的头部删除一个字符, 放入T的尾部;从S的尾部删除一个字符, 放入T的尾部;目标是要构造字典序尽可能小的字符串T.使用贪心算法, 不断选取S首尾最小的字符, 放入T, 如果相等, 则再次向内查找, 找到内部最小的.代码:/** main.cpp** Created on: 2014.7.17* Autho...

排序算法锻炼编程思维：冒泡，选择，插入，快速，归并【代码】

冒泡，选择，插入，快速，归并这五个排序是所有编程语言初学者所遇到过的，可能在实际的编程应用中不会遇到，但对于锻炼编程思维，还是有很好的作用。冒泡排序冒泡排序的就是让大的数向后冒，让小的数向前冒。通过前后两个数据比较，不断将大的元素移动到尾部。 1publicstaticvoid main(String[] args) {2// TODO Auto-generated method stub 3int []arr= {-10, 2, 3, 246, -100, 0, 5};4for(int i=0;i<arr.length-1;i++) {5for(in...

算法及shell脚本编程基础

bash存在多命令执行的特性，例如：# COMMAND1 $(COMMAND2)；还有进程之间的通信（IPC）：# COMMAND1 | COMMAND2…一、命令执行结构与算法命令执行中，存在顺序执行结构：分号分隔 # COMMAND1 ; COMMAND2 ; …。同时存在选择执行结构：逻辑运算与、或、非、异或，其中最主要的为选择执行结构，具体讨论如下。1、与：逻辑乘法 &&状态返回值：0对应TRUE，1-255对应FALSE具体算法为：True &&true == true True && false == ...

机器学习算法原理与编程实践之朴素贝叶斯分类【图】

在介绍朴素贝叶斯分类之前，首先介绍一下大家都比较了解的贝叶斯定理，即已知某条件概率，如何得到两个时间交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)？可以通过如下公式求得：而朴素贝叶斯分类是一种简单的分类算法，称其朴素是因为其思想基础的简单性：就文本分类而言，它认为词袋中的两两词之间的关系是相互独立的，即一个对象的特征向量中的每个维度都是相互独立。朴素贝叶斯分类的正式定义如下：（1）设为一个待...

声明式编程：程序＝数据＋逻辑（what）＋算法（控制＋计算）

接口：what；实现：算法；指令；命令式编程通过一系列改变程序状态的指令来完成计算，声明式编程只描述程序应该完成的任务。命令式编程模拟电脑运算，是行动导向的，关键在于定义解法，即“怎么做”，因而算法是显性而目标是隐性的；声明式编程模拟人脑思维，是目标驱动的，关键在于描述问题，即“做什么”，因而目标是显性而算法是隐性的。 https://www.cnblogs.com/feng9exe/p/10190716.html 原文：https://www.cnblogs.com/fen...

编程算法 - 背包问题(三种动态规划) 代码(C)【图】

背包问题(三种动态规划) 代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目参考: http://blog.csdn.net/caroline_wendy/article/details/37912949可以用动态规划(Dynamic Programming, DP)求解, 可以通过记忆化搜索推导出递推式, 可以使用三种不同的方向进行求解.动态规划主要是状态转移, 需要理解清晰.代码:/** main.cpp** Created on: 2014.7.17* Author: spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h> #...

LeetCode算法编程之连载四（二分法）【代码】

1、题目 – Sqrt(x)Implement int sqrt(int x).Compute and return the square root of x.题目意思很简单，就是求出x的平方根。分析：一看这题目，感觉很简单，很容易想到的是二分法，我最开始的解法是从1、2、4、8 … 2 * n，计算出n < x < 2n，然后再在 n 和 2n间，用二分法，找到平方根结果。这种方法比较麻烦的一点是，乘积是有可能越界的，要处理乘积越界的情况，代码可读性不强。class Solution { public:int sqrt(int x) {i...

Python的函数式编程-传入函数、排序算法、函数作为返回值、匿名函数、偏函数、装饰器【代码】

函数是Python内建支持的一种封装，我们通过把大段代码拆成函数，通过一层一层的函数调用，就可以把复杂任务分解成简单的任务，这种分解可以称之为面向过程的程序设计。函数就是面向过程的程序设计的基本单元。传入函数函数的本身也可以作为参数。Python内建的mapreduce的函数。（来源于谷歌的，后来被道格这家伙开源了，成为当今处理大数据最火热的hadoop中的计算模型---MapReduce）我们先看map。map()函数接收两个参数，一个是函数...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )

牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )

内容导读

内容图文

Q1:

代码如下：

Q2:

代码如下：

Q3:

代码如下：

Q4:

代码如下：

Q5:

代码如下：

Q6:

代码如下：

Q7:

代码如下：

Q8：

代码如下：

内容总结

内容备注

内容手机端

【牛客刷题 - 网易2018校招编程题(思维 & 贪心 & )】教程文章相关的互联网学习教程文章

编程 - 相关标签

算法 - 最新教程

算法 - 最热教程