美团点评2018春招两道编程题

以你之姓@ 2022-05-29 12:30 235阅读 0赞

# 第一题：字符串距离 #

题目：  
给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符的数量。如串”aab”与串”aba”的距离为 2；串”ba”与串”aa”的距离为 1；串”baa”和串”baa”的距离为 0。下面给出两个字符串 S 与 T，其中 S 的长度不小于 T 的长度。我们用|S|代表 S 的长度，|T|代表 T 的长度，那么在 S 中一共有|S|-|T|+1 个与T长度相同的子串，现在你需要计算 T 串与这些|S|-|T|+1 个子串的距离的和。

输入描述：  
第一行包含一个字符串 S。第二行包含一个字符串 T。S 和 T 均由字符 a 和 b 组成，1 ≤ |T| ≤ |S| ≤105 。

输出描述：  
输出对应的答案。

样例1：  
aab  
aba

样例2：  
aaabb  
bab

import java.util.*;
    public class getStringDis{
    	
    
    	public static void main(String[]args)
    	{
           //System.out.println("Hello");
    		Scanner sin=new Scanner(System.in);
    		String s;   //母串
    		String t;   //子串
    		while(sin.hasNext())
    		{   	
    			s=sin.nextLine();
    			t=sin.nextLine();
    			if(t.length()<s.length()
    			  &&s.length()>0&&s.length()<105
    			  &&t.length()>0&&t.length()<105)
    			{
                   char[]chs=s.toCharArray();
                   char[]cht=t.toCharArray();
                   int sum=0; //输出两个字符串的距离
                   for(int i=0;i<=chs.length-cht.length;i++)
                   {
                   	   for(int j=0;j<cht.length;j++)
                   	   {
                   	   	   int k=i;
                           if(cht[j]!=chs[k++])
                           {
                           	 sum+=1;
                           }
                   	   }
                   }
                   System.out.println(sum);
    			}
    		}
        }
    }

//方法二:优化后的代码(时间复杂O(s.length))
    	public static int getStringDis(String s,String t)
    	{
                int m=0;  //统计模式串相邻的字符总长度
                int n=0;
                int sum=0; //记录放回的字符串长度
                int s_len=s.length();
                int t_len=t.length();
                char[]chs=s.toCharArray();
                char[]cht=t.toCharArray();
                
                //对模式串统计
                for(int i=0;i<t_len-1;i++)
                {
                	 if(cht[i]!=cht[i+1])
                	 {
                	 	  ++m;
                	 }
                }
                //对子、母串前t_len长度统计
                for(int j=0;j<t_len;j++)
                {
                	  if(chs[j]!=cht[j])
                	  {
                	  	  ++n;
                	  }
                }
                sum+=n;  //统计第一次匹配总共距离
                for(int k=t_len;k<s_len;k++)
                {
                    if(chs[k-t_len]!=cht[0])
                    {
                    	n-=1;
                    }
                    if(chs[k]!=cht[t_len-1])
                    {
                    	n=n+m+1;
                    }else{
                    	n=n+m;
                    }
                    n=n%(t_len+1); //防止统计越界
                    sum+=n;
    
                }
               return sum;
    
    	}

**第二题：数字字符**  
题目：  
在十进制表示中，任意一个正整数都可以用字符‘0’-‘9’表示出来。但是当‘0’-‘9’这些字符每种字符的数量有限时，可能有些正整数就无法表示出来了。比如你有两个‘1’，一个‘2’ ，那么你能表示出 11，12，121 等等，但是无法表示出 10，122，200 等数。  
　  
现在你手上拥有一些字符，它们都是‘0’-‘9’的字符。你可以选出其中一些字符然后将它们组合成一个数字，那么你所无法组成的最小的正整数是多少？

输入描述：  
第一行包含一个由字符’0’-‘9’组成的字符串，表示你可以使用的字符。1 ≤ 字符串长度 ≤ 1000

输出描述：  
输出你所无法组成的最小正整数。

样例1：  
55

样例2：  
123456789

import java.util.*;
    public class getMinInt{
    	
    	public static void main(String[]args)
    	{
          
    		Scanner sin=new Scanner(System.in);
    		String s;   //输入字符串
    		while(sin.hasNext())
    		{   	
    			s=sin.nextLine();
          int[]arr=new int[10];  //统计每个数字出现的频率
          int min=Integer.MAX_VALUE;
          int digit=-1;
    			if(s.length()>0&&s.length()<1001)
    			{
                char[]chs=s.toCharArray();
                for(int i=0;i<chs.length;i++)
                {
    
                     ++arr[chs[i]-'0'];
    			      }
                     
                for(int i=1;i<arr.length;i++)
                {
                   //寻找最小值
                    if(min>arr[i])
                    {
                       min=arr[i];
                       digit=i;
                    }
                      
                }
              //然后检查是否能够凑出n位数(1......n)
              //System.out.println(min);
                if(arr[0]+1<=min)
                {   String str="1";
                    for(int i=0;i<min;i++)
                    {
                        str+="0";
                    }
                    System.out.println(str);
                }else{
    
                    String str=digit+"";
                    for(int i=0;i<min;i++)
                    {
                        str+=digit+"";
                    }
                    System.out.println(str);
                }
              }
          }
    	}
      
    }