IT笔试加分利器

登录 注册

  • 主页/
  • 美团校招-后台开发
美团校招-后台开发
发布于 2017-09-14 20:35 4891 次浏览 0 赞 来自 试题交流  

逻辑题和选择题不算很难，最后两道编程题确实很考验水平了。有人答出第二题帮忙解答一下吗？这个难道要用GAN？

回帖 赞(0) 收藏 印章
34 条回复

考试后再讨论哈~

2017-09-14 20:36

我只能说 这题目 哈哈哈哈哈哈哈------

2017-09-14 20:57

我只能说，我是投Java岗位的，结果考了很多c++的，痛苦

2017-09-14 20:59
5

我的思想是这样的：

要求是全灭了 就赢了。。那最左边如果有亮的 早晚都要解决。

我想 从左到右解决。选择第一个亮的，然后其他反过来。再选择第二个亮的其他反过来。

她俩一人选一次，所以组后执行次数如果是偶数就是bob赢了 如果是奇数就是alice赢了。

为了降低时间复杂度，我考虑：

第一次选择第一个1的灯泡，右侧1全变成0，0全变1，

如果我不改变右侧，那就相当于 选择了第一个1的灯泡之后，，我应该往右找第一个是0的灯泡（这个灯泡如果上一步选择之后 应该变成1，但是我没有改变他）

于是形成一个规律：如果上一次找1的灯泡，这次应该找0的灯泡

    如果上一次找0的灯泡，这一次应该找1的灯泡。

这样本来n方的时间复杂度能降为n

我的代码：




#include "iostream"

using namespace std;

// 获得数字位数

    int a[100000];

int main(){

    int n;

    cin>>n;

    for(int i =0;i<n;i++){

        cin>>a[i];

    }


    int res = 0;

    int k = 1;

    for(int i =0;i<n;i++){

        if(a[i]==k){

            res++;

            if(k==1) k=0;

            else k=1;

        }

    }

    if(res%2==0){

        cout<<"Bob";

    }else{

        cout<<"Alice";

    }


    return 0;

}


2017-09-14 21:04
2

SG 用bitset保存状态

2017-09-14 21:06

第二题超简单的：10行代码就够了，也就是两句话。。。。。

2017-09-14 21:08

感觉两道题都是找规律的题。第二题感觉和一道题有点像，就是有n堆石子，每次只能拿一定的数量，必胜策略是吗

2017-09-14 21:08

4l思路是对的，但是其实只要判断最后一个灯泡是什么就可以了，反正最后一个总要是0的，如果一开始最后一个是0，那么要操作2，4，6...次，Bob赢了，反之Alice获胜。这样就很简单了，哈哈。

我的代码是：

#include <stdio.h>


int main(void) {

    int n, i, l;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {

        scanf("%d", &l);

    }


    if (l == 1) {

        printf("Alice");

    }

    else {

        printf("Bob");

    }

}


2017-09-14 21:09
2

第两题：不需要懂SG什么的，在纸上把1-16个数画一画哪些数必胜就知道了。

2017-09-14 21:10
1
coder_C7ZU45HQ 回复 coder_H2X8KDDA ：

完美啊老哥，最后那个变换0，1简直妙，我考的就没想到，还死死的全给他置反呢，太蠢了我。哎呀，好气，只通过了70%。应该就是复杂度的问题。
2017-09-14 21:10

宽度搜索

2017-09-14 21:10
coder_C7ZU45HQ 回复 coder_JAGHJ74B ：

111？
2017-09-14 21:13
coder_C7ZU45HQ 回复 coder_JAGHJ74B ：

011？
2017-09-14 21:13
coder_JAGHJ74B 回复 coder_C7ZU45HQ ：

111成立，这个只要吹一次就行了，所以Alice胜。
2017-09-14 21:15 1

011, 11100

这题奇数就是Alice，偶数是Bob。 

结果AC

2017-09-14 21:15
coder_JAGHJ74B 回复 coder_C7ZU45HQ ：

011也是吹一次，吹第二个以及右边的
2017-09-14 21:15 1 
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int>bulbs;
    int tmp;
    for(int i=0;i<n;++i){
        cin>>tmp;
        bulbs.push_back(tmp);
    }

    int count=0;
    int position=n-1;
    while(position){
        while(position>0&&bulbs[position]==bulbs[position-1])position--;
        if(position) {
            count++;
            position--;
        }
    }
    if(bulbs[0]==1)count++;
    if(count%2==1)cout<<"Alice";
    else cout<<"Bob";
    return 0;
}


2017-09-14 21:16
coder_C7ZU45HQ 回复 coder_JAGHJ74B ：

有道理啊，你这个更妙啊。。。
2017-09-14 21:18
coder_C7ZU45HQ 回复 coder_JAGHJ74B ：

你的意思是根据奇偶直接看最后一根吹熄亮几次，完全不用管前面的，应为到最后，就是最后一根的判断，哇，太巧了。。。。老哥你脑子真好，我看你评论还反映了半天。。。。
2017-09-14 21:21 2

写完就明白自己做错了 一个悲伤的故事

2017-09-14 21:24
coder_7HHdfB2B 回复 coder_JAGHJ74B ：

你这个可以啊 我完全走远了这道题。。
2017-09-14 21:25

判断最后一个数是0还是1， 是1的话Alice赢，是0的话Bob 赢。我这么写的直接AC了

2017-09-14 21:26
快乐的土豆 回复 coder_b9BCahRq ：

能明白错了也是进步啊，加油啊~
2017-09-14 21:26
coder_5WMZ36GE 回复 coder_5DM3BRKP ：

上次投了C/C++岗位的，结果出了很多JAVA题，桑心
2017-09-14 21:27 
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	if (v[v.size() - 1])
		cout << "Alice";
	else
		cout << "Bob";
	return 0;
}


2017-09-14 21:27
coder_GG2MRF6P 回复 coder_RT79BWES ：

我就是这么做的，结果只通过70%。。。
2017-09-14 21:28
coder_8B3SYWNP 回复 coder_RT79BWES ：

我这么高结果只有50啊 因为明显110就不对
2017-09-14 21:31

被7整除那题，用下面的代码可以吗？我还没来得及试。。。就结束了。。。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int isMulti(vector<int> final){
	int i;
	for( i = 0 ;i <final.size()-1;i++){
		if(final[i] >= 7){
			final[i+1] += final[i]%7;
		}else{
			final[i+1] += final[i]*10;
		}
	}
	if(final[i] % 7 ==0)
		return 1;
	else
		return 0;
}
int isvalid(int n, int m){
	stack<int>first;
	stack<int>second;
	while(n != 0){
		first.push(n%10);
		n/=10; 
	}
	while(m != 0){
		second.push(m%10);
		m/=10; 
	}
	vector<int>final;
	vector<int>secondNum;
	while(!first.empty()){
		final.push_back(first.top());
		first.pop();
	}
	while(!second.empty()){
		final.push_back(second.top());
		second.pop();
	}
	
	return isMulti(final);
}
int main(){
	int n;
	cin>>n;
	vector<int> num;
	for(int i = 0 ;i < n;i++){
		int temp;
		cin>>temp;
		num.push_back(temp);
	}
	int solution = 0;
	for(int i = 0 ;i < n; i++){
		for(int j = 0 ;j < n; j++){
			if(i != j ){
				solution += isvalid(num[i],num[j]);
			}
		}	
	}
	cout<<solution<<endl;
}


2017-09-14 21:31
coder_eejJBE4b 回复 coder_GYDFTNH6 ：

能否讲一下思路，暴力求全部的组合肯定不行的
2017-09-14 21:34
coder_ApyG5EuQ 回复 coder_H2X8KDDA ：

感觉这题出的有bug啊，既然说两个人都足够聪明，都想赢，怎么可能都一直按这个规律做，最后难道眼睁睁看着自己输？
2017-09-14 21:35
coder_W3Y0SHHK 回复 coder_JAGHJ74B ：

老哥，扎心了。。。
2017-09-14 21:36

前面都有人提到判断奇偶，却没人说出原因。

原理是这样的：

1.最后赢得那个人吹的蜡烛一定是即类似00001111这种，左侧全0，右侧全1，才能保证最后一次吹赢。


2.所有的偶数都不符合这个形式。


3.每吹一次改变一次奇偶。


所以只要是奇数Alice就能赢。

2017-09-14 21:36
2
coder_H2X8KDDA 回复 coder_C7ZU45HQ ：

慢慢来嘛，我这思想肯定也不是最好的。见的多了 慢慢就好了。
2017-09-14 21:36 
这样就AC了.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		while(cin.hasNext()){
			int n = cin.nextInt();
			int[] a = new int[n];
			
			int temp = 0;
			for(int i=0;i<n;i++){
				a[i] = cin.nextInt();
				if (a[i]==1) {
					temp = i;
				}
			}
			if (temp == n-1) {
				System.out.println("Alice");
			}else {
				System.out.println("Bob");
			}
			
		}
	}


2017-09-14 21:52
添加回复
注册
回到顶部