第一题：字符串距离

题目：
给出两个相同长度的由字符 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

样例2：
aaabb
bab

5
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

1

样例2：
123456789

10

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);
        }
      }
  }
}

}