语源科技BlogJava-kevin

String类型简单解析

夏日清风 — Fri, 21 Nov 2008 10:50:00 GMT

摘要: String存储操作简单分析阅读全文

夏日清风 2008-11-21 18:50 发表评论

基于字典序排列生成

夏日清风 — Tue, 01 Jul 2008 01:14:00 GMT

摘要: java 字典序排列生成算法阅读全文

夏日清风 2008-07-01 09:14 发表评论

多边形游戏问题

夏日清风 — Mon, 30 Jun 2008 09:32:00 GMT

摘要: /**//* 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：（1）选择一条边E以及由E连接着的两个顶点V1和V2；（2）用一个新的顶点取代边E... 阅读全文

夏日清风 2008-06-30 17:32 发表评论

哈夫曼树

夏日清风 — Sat, 28 Jun 2008 10:38:00 GMT

摘要: Huffman树实现阅读全文

夏日清风 2008-06-28 18:38 发表评论

石子合并问题

夏日清风 — Sat, 28 Jun 2008 10:24:00 GMT

摘要: 石子合并，动态规划阅读全文

夏日清风 2008-06-28 18:24 发表评论

编辑距离

夏日清风 — Thu, 26 Jun 2008 02:53:00 GMT

/*问题描述：设S1和S2是两个字符串。要用最少的字符操作将字符串S1转换为字符串S2。这里的字符串操作包括：

(1)删除一个字符

(2)插入一个字符

(3)将一个字符改成为另一个字符。

将字符串S1转换为字符串S2的所用的最少的字符串操作数称作字符串S1到S2的最短距离，记为 d(S1, S2).

算法设计：给定字符串S1和S2，计算它们的最短编辑距离d(S1, S2)。
*/
/*算法思想：
  用数组b[i][j]记录s1[1..i]和s2[1..j]之间的编辑长度。
  递归公式
   b[i][j]=min(b[i-1]][j],b[i][j-1],b[i][j]+(s1[i]==s2[i]?0:1));
*/
public class EditDistance
{
public int  editDistance(String s,String aim)
{
     int sLength=s.length()+1;
     int aLength=aim.length()+1;
     int[][] b=new int[aLength][sLength];
     for(int i=1;i<sLength;i++)
     {
         b[0][i]=i;
     }
     for(int k=1;k<aLength;k++)
     {
          b[k][0]=k;
     }
     for(int j=1;j<sLength;j++)
     {
         for(int i=1;i<aLength;i++)
         {
         int x=b[i-1][j]+1;
             int y=b[i][j-1]+1;
             int z=b[i-1][j-1]+((s.charAt(i-1)==aim.charAt(j-1))?0:1);
             b[i][j]=min(x,y,z);
              }
     }

     return b[aLength-1][sLength-1];
     }
     public int min(int x,int y,int z)
     {
         int temp;
         if(x<y)
         {
             temp=x;
         }
         else temp=y;
         if(z<temp) temp=z;
         return temp;
     }
     public static void main(String []args)
     {
         String s="hhdeihhh";
         System.out.println(s.length());
         String aim="hheepppk";
         System.out.println(aim.length());
         EditDistance ed=new EditDistance();
         System.out.println(ed.editDistance(s,aim));
     }

}

夏日清风 2008-06-26 10:53 发表评论

数组换位的两种方法

夏日清风 — Mon, 09 Jun 2008 13:04:00 GMT

/*
问题描述:
设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数．试设计一个算法将子数组
a[0:k]与a[k+1:n-1]换位．要求算法在最坏情况下耗时O(n), 且只用到O(1)的辅助空间．
*/
/*求解思想：
  算法的时间复杂度很容易保证，想弄出O(n*n)的算法都会很困难，关键是要保证只用到O(1)的辅助空间。
  可以用递归分治的算法思想。
*/
public class ChangePosition
{
  public void swap(int a[],int begin,int second,int size)
  {
      int tmp=0;
      for(int i=0;i<size;i++)
      {
          tmp=a[i+begin];
          a[i+begin]=a[i+second];
          a[i+second]=tmp;
      }
  }
  public void change(int a[],int begin,int k,int nlen)
  {
      int first=k+1;

      int second=nlen-first;

      if(second<=0||first<0)
      {
             return  ;
      }
      else
      {
          if(first<=second)
          {

               swap(a,begin,first+begin,first);
               change(a,begin+first,first-1,nlen-first);
          }
          else
          {

              swap(a,begin,begin+first,second);
              change(a,begin+second,first-1-second,nlen-second);
      }
      }
  }
  public void print(int[]a,int size)
  {
       for(int i=0;i<size;i++)
       {
           System.out.print(a[i]+" ");
       }
       System.out.println();
  }
  /*
    第二种方法的思想是我们把一个数组的两个部分分别逆序，然后将整个数组再次逆序，
    逆序两次以后就可以得到该问题的解，如果可以想到的话问题就很简单了!
  */
  public void reverse(int[]a,int begin,int end)
  {
      int n=(begin+end)/2;
      int tmp=0;
      for(int i=begin;i<=n;i++)
      {
          tmp=a[i];
          a[i]=a[end];
          a[end]=tmp;
          end--;
      }
  }


  public static void main(String[] args)
  {
      int[] a={0,1,2,3,4,5,6,7,8,9};
      ChangePosition cp=new ChangePosition();
      cp.change(a,0,1,10);
      cp.print(a,10);
      int[] b={0,1,2,3,4,5,6,7,8,9};
    cp.reverse(b,0,2);
    cp.reverse(b,3,9);
    cp.reverse(b,0,9);
    cp.print(b,10);
  }

}

夏日清风 2008-06-09 21:04 发表评论

整数划分

夏日清风 — Wed, 04 Jun 2008 14:52:00 GMT

import java.util.*;
public class SplitNum
{
  public SplitNum()
  {
  }
  public int split(int n,int m)
   {

      if(n <1||m<1)   return 0;
      if(n ==1||m == 1) return 1;
      if(n<m)return   split(n, n);
      if(n==m) return (split(n, m-1)+1);
      if(n>m)  return (split(n, m-1)+split((n - m),m));
      else
      {
          return 0;
      }
   }

public  static  void   main(String []args)
{
      SplitNum sn=new      SplitNum();
      Scanner in=new Scanner(System.in);
    System.out.print("input the num:");
    int n=in.nextInt();
    int p=sn.split(n,n);
    System.out.println(n+"的划分个数:"+p);
}
}

夏日清风 2008-06-04 22:52 发表评论