[数据结构与算法]第六次课For蓝桥杯

1. 二分查找

package test;

import java.util.Scanner;

public class DividSearch 
{
	//[begin,end)
	public static int f(int a[],int begin,int end,int x)
	{
		if(end-begin==1)
		{
			if(a[begin]>x) return begin;
			return end;
		}
		int mid=(begin+end)/2;
		if(x>=a[mid])//比中间的大，说明是右边
		{
			return f(a,mid,end,x);
		}else {
			return f(a,begin,mid,x);
		}
		
	}
	public static void main(String[] args)
	{
		int a[]= {1,4,8,16,17,22,23,663,1000};
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		if(a[a.length-1]<n)
		{
			System.out.println(-1);
		}else
		System.out.println(f(a,0,a.length,n));

	}

}

2. 最长公共子序列

for (int i = 1; i <= strlen(b); i++)
		for (int j = 1; j <= strlen(p); j++)
		{
			if (b[i - 1] == p[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}

3. 最大字段和（连续的段）

package test;

import java.util.Scanner;

public class MaxString 
{
	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		int m=0;
		int mid=-1,maxx=-10000;
		for(int i=0;i<n;i++)
		{
			m=cin.nextInt();
			if(mid>0)
			{
				mid+=m;
			}else {
				mid=m;
			}
			if(maxx<mid)
				maxx=mid;
				
		}
		System.out.println(maxx);
	}
	
}

4. 最长不下降子序列

package test;

public class MaxNoLow {

	public static void main(String[] args)
	{
		int a[]= {1,5,3,14,13,16,7,18};
		int len=0;
		int maxx=0;
		int b[]=new int[a.length];
		for(int i=1;i<a.length;i++)
		{
			len=1;
			for(int j=0;j<i;j++)
			{
				if(a[i]>a[j])
				{
					len=Integer.max(len,b[j]);
				}
			}
			
			b[i]=len+1;
			maxx=Integer.max(maxx,b[i]);
		}
		System.out.println(maxx);
	}

}

5.【大数乘法】-分治

package test;

import java.math.BigInteger;

public class MyBigInteger 
{

	public static String zero(int n)
	{
		String s="";
		for(int i=1;i<= n;i++)
		{
			s+="0";
		}
		return s;
	}
	public static String add(String a,String b)
	{
		if(a.length()<=8&&b.length()<=8)
		{
			return Integer.parseInt(a)+Integer.parseInt(b)+"";
		}
		//加法也进行分段来计算
		
		String ah="0";//高位记为0
		String al=a;
		if(a.length()>8)
		{
			ah=a.substring(0,a.length()-8);
			al=a.substring(a.length()-8);
		}
				
		String bh="0";
		String bl=b;
		if(b.length()>8)
		{
			bh=b.substring(0,b.length()-8);
			bl=b.substring(b.length()-8);
		}
		String t=add(al,bl);
		while(t.length()<8) t="0"+t;
		//说明有进位 进位一定是1
		//可以想象999+999 进位是1
		if(t.length()>8)
		{
			return add(add(ah,bh),"1")+t.substring(1);	
		}
		return add(ah,bh)+t;
		
	}
	public static String multip(String a,String b)
	{
		if(a.length()<=4&&b.length()<=4)
		{
			return ""+Integer.parseInt(a)*Integer.parseInt(b);
		}
		if(a.length()>4)
		{
			int k=a.length()/2;
			String a1=a.substring(0,k);
			String a2=a.substring(k);
			//把乘数分成两部分最后添零拼接在一起即可
			return add(multip(b,a1)+zero(a2.length()),multip(b,a2));					
		}
		return multip(b,a);
	}
	public static void main(String[] args) 
	{
		System.out.println(multip("1234567890987654321666","1234567890123456789555"));
		BigInteger b1=new BigInteger("1234567890987654321666");
		System.out.println(b1.multiply(new BigInteger("1234567890123456789555")));
	}

}