IT笔试加分利器

登录 注册

  • 主页/
  • 美团笔试，被7整除
美团笔试，被7整除
发布于 2017-09-14 21:17 5840 次浏览 0 赞 来自 我要提问  

美团笔试，被7整除

题目描述：

她想用这些数制造出更多的能够被 7 整除的数。于是她从这 n 个数中选出两个数，然后将

输入

第一行包含一个整数n。2 ≤n≤ 105

第二行包含n个正整数ai。1 ≤ai≤109

样例输入

3

127 1996 12

样例输出

4


Hint

一共有 4 种组合方式，其中：把 12 写在 1996 前面得到 121996；把 127 写在 12 前面得到12712；把 1996 写在 12 前面得到 199612；把 1996 写在 127 前面得到 1996127；都是可以被 7 整除的，其余的组合方式不能被 7 整除。



我自己写的代码，提交之后运行过不去，但是给的用例可以过去，求帮忙看看哪里有问题

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int num = 0;
		int count = 0;
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			num = scanner.nextInt();
			int[] arr = new int[num];
			for (int i = 0; i < num; i++) {
				arr[i] = scanner.nextInt();
			}
			int temp = 0;
			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num; j++) {
					if (i != j) {
						String string = "" + arr[i] + arr[j];
						temp = Integer.parseInt(string);
						if (temp % 7 == 0) {
							count++;
						}
					}
				}
			}
			System.out.println(count);
			count = 0;
		}

	}
}


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

直接转换int不怕溢出吗

2017-09-14 21:19
2
coder_I2TOCM8w 回复 acmcodermIGTmt5I ：

对哦，我忘考虑了
2017-09-14 21:21
coder_I2TOCM8w 回复 acmcodermIGTmt5I ：

除去这里还哪里有问题吗
2017-09-14 21:21

我的思路跟你的一样但是说时间超限了。。

2017-09-14 21:23

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

for(int j=i+1;j<n;j++) {

long num=Long.valueOf(arr[i]+""+arr[j]);

if(num%7==0) {

count++;

}

num=Long.valueOf(arr[j]+""+arr[i]);

if(num%7==0) {

count++;

}

}

}


70% 超时了····已经交卷了

2017-09-14 21:24
2
coder_JJBGJSSG 回复 coder_I2TOCM8w ：

arr[i][j] 与 arr[j][i]
2017-09-14 21:25
coder_I2TOCM8w 回复 coder_YNBDZGM4 ：

我也交卷了才来问的
2017-09-14 21:25

大数+重复剔除

2017-09-14 21:25

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Scanner;


public class Main {


    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner in  = new Scanner(System.in);

        while(in.hasNext())

        {

       int n=in.nextInt();

       int[] num=new int[n];

       

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

       num[i]=in.nextInt();

       }

       int sum=gets(num);

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

//        for(int j=0;j<n;j++){

//        if(i==j){

//        continue;

//        }else{

//        int yunum2=(int) (num[i]%7*Math.pow(10, (num[j]+"").length()))+num[j];

//        if(yunum2%7==0){

//        sum++;

//        }

//        }

//        }

//        }

       System.out.println(sum);

       

       

       

        }

      }

    public static int gets(int[] num){

    int sum=0;

    int n=num.length;

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

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

        if(i==j){

        continue;

        }else{

        int yunum2=(int) (num[i]%7*Math.pow(10, (num[j]+"").length()))+num[j];

        if(yunum2%7==0){

        sum++;

        }

        }

        }

        }

        return sum;

    }

}


2017-09-14 21:26
coder_YDA6G9C9 回复 coder_8B3SYWNP ：

me 2
2017-09-14 21:26

我也是这样做的，但是时间超限，通过率70%。我的tmp用的是 long。

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i ++) {
			arr[i] = in.nextInt();
		}
		long count = 0;
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < n; j ++) {
				if(i != j) {
					int remain = arr[i] % 7;
					String str = (remain == 0 ? "" : "" + remain);
					str += arr[j];
					long tmp = Long.parseLong(str);
//					System.out.println(tmp);
					if(tmp % 7 == 0) {
						count ++;
					}
				}
			}
		}
		System.out.println(count);
	}
	
}



2017-09-14 21:27

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int N = scanner.nextInt();

long[] a = new long[N];

int number = 0;

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

if(i == 0){

a[0] = scanner.nextLong();

continue;

}

int c = i-1;

a[i] = scanner.nextLong();

while(c >=0){

String ai = String.valueOf(a[i]);

String ac = String.valueOf(a[c]);

System.out.println(a[i] + " " + a[c]);

System.out.println(a[c] + " " + a[i]);

if(Long.valueOf(ai + ac)%7 ==0){

// System.out.println(a[i] + " " + a[c]);

number++;

}

if(Long.valueOf(ac + ai)%7 ==0){

// System.out.println(a[i] + " " + a[c]);

number++;

}

c--;

}

}

System.out.println(number);

}

}

百分之70....

2017-09-14 21:27
coder_aHg5XoxQ 回复 coder_aHg5XoxQ ：

想知道错到哪里了 real尴尬
2017-09-14 21:27

你竟然用字符串连接然后parseInt。。。好吧。。。。我还是算出来的。。。扑街

2017-09-14 21:28
coder_I2TOCM8w 回复 coder_f0uRMttp ：

我Int就过了10%
2017-09-14 21:29
coder_aHg5XoxQ 回复 coder_f0uRMttp ：

求大神指导
2017-09-14 21:30
coder_I2TOCM8w 回复 coder_YDA6G9C9 ：

。。= =
2017-09-14 21:31

处理大数的时候用的同余数的性质，直接转换成余数的乘积和加和了 但是开始超时 后来先遍历一遍把能被7整除的全去掉了 但是时间不够了 最后只过了10% 另外 不知道 7，77的组合777算一次还是两次 怀疑这个也是特殊case

2017-09-14 21:33

不知道测试数据是不是有个100000的数组，让n能=100000就超时，不能就错误 = =

2017-09-14 21:35

本地测试用例都可以，大数也没问题。网页上就不行。。是因为不能使用Math么？？？？

package com.danny.mt;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        String str1= sc.next();
        int n = Integer.parseInt(str1);
        Scanner sc1 = new Scanner(System.in); 
        String str2= sc1.nextLine();
        String[] strarr = str2.split("\\s+");

        int count = 0;
        String str3 = ""; 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i!=j){
                    str3 = strarr[i]+strarr[j];
                    BigInteger b1= new BigInteger(str3);
                    BigInteger b2= new BigInteger("7");
                    BigInteger b3=b1.mod(b2);
                    if(b3.intValue()==0){
                        count++;
                   }
                }
            }		
        }
        System.out.print(count);
    }
}


2017-09-14 21:36

分两部分，能被7整除data1,不能被7整除data2,并用字典n保留data2中的余数值，即key为余数，value为个数。n中元素个数最多为9个。

对于data1，个数为len(data1)*(len(data)-1)/2

对于data2，遍历data2，其中对于每一个元素i，遍历字典n key，如果key拼接i整除7，结果+value


不知道思路对不对，反正没全通过



2017-09-14 21:37
coder_苏木离 回复 coder_f0uRMttp ：

这个绝对超时，，我和你这个差不多的，稍微优化了一下，还是超时，第二层循环里j不用从0开始，从i+1开始即可，里面前后比较两次；但是没卵用，看来n^2的复杂度怎么都超时。
2017-09-14 21:37
coder_苏木离 回复 coder_kLfwYYBG ：

看题意应该算两次，，他不是说有2*(n,2)种组合么，，
2017-09-14 21:39
coder_苏木离 回复 coder_BWZ6HJ9Z ：

你自己写几个大数没用，这个题大部分人都是超时，肯定是复杂度的问题，能找到一个fu’z复杂度低的，就能过。
2017-09-14 21:40
acmcoderzrQmtsqe 回复 coder_MBBXEB8V ：

还有date1 拼接date2的情况呢，而且时间复杂度是 m^2 + m*(n-M) 感觉应该也不会过， date1 的个数为 m！ 阶乘
2017-09-14 21:45
coder_苏木离 回复 coder_MBBXEB8V ：

没全通过，是什么原因？你跑完测试后，反馈的是什么错误？超时？超内存？还是啥？
2017-09-14 21:46
coder_FBGN8Y45 回复 coder_YNBDZGM4 ：

C++的同样版本只有10%
2017-09-14 22:58
coder_NHJPXP5H 回复 coder_aHg5XoxQ ：

while(in.hasNext()) { int n=in.nextInt(); int[] num=new int[n]; 你这里不是一直会重新生成数组吗
2017-09-14 23:06
coder_NHJPXP5H 回复 coder_E2P42YZY ：

怎么去重啊，讲讲大佬
2017-09-14 23:07 
#include <stdio.h>
int main()
{
    int n,l,i,j,o,p,q;
    int array[100];
    int num=0;
    int count1,count2,count3;
    int k=1;
	int m=1;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
		scanf("%d",&l);
		array[i]=l;
    }
    for(i=0;i<n-1;i++)
    {
    	count1=array[i];
        for(j=i+1;j<n;j++)
        {
        	count2=array[j];
            do{
            count2=count2/10;
            k++;
        	}while(count2>=10);
			for(p=0;p<k;p++)
			{
				m=m*10;
			}
			count3=count1*m+array[j];
			m=1;
			k=1;
        	if(count3%7==0)
        	{
        		num++;
        	}
			
        }
        for(o=i+1;o<n;o++)
        {
        	count2=array[o];
            do{
            count1=count1/10;
            k++;
        	}while(count1>=10);
			for(q=0;q<k;q++)
			{
				m=m*10;
			}
			count3=count2*m+count1;
			m=1;
			k=1;
        	if(count3%7==0)
        	{
        		num++;
        	}
		}
    }
 	printf("%d",num);  
    return 0;
}


2017-09-14 23:56

我也是这个思路，只能到70%

2017-09-15 09:35
coder_8KisduJn 回复 coder_I2TOCM8w ：

int明显不行，因为输入的数的范围就已经超过int类型了
2017-09-15 09:36
coder_8KisduJn 回复 coder_f0uRMttp ：

大家的方法好像都差不多，我也是这个方法
2017-09-15 09:37
coder_MHWHZGC5 回复 coder_FBGN8Y45 ：

这个题把c++的童鞋都坑了
2017-09-15 11:06
coder_2UH4GKHY 回复 coder_8KisduJn ：

我都用biginteger试了，也是通过70%，显示超时。
2017-09-16 14:42
添加回复
注册
回到顶部