首页 > 代码库 > 蓝桥杯-递归常用的几种套路

蓝桥杯-递归常用的几种套路

求最大公共子序列的大小

public class 最大公共子序列 {
    public static void main(String[] args) {
        int k=f("abc","adfefexcgfd");
        System.out.println(k);
    }

    private static int f(String s1, String s2) {
        
        if(s1.length()==0||s2.length()==0) return 0;
        
        if(s1.charAt(0)==s2.charAt(0))
            return f(s1.substring(1),s2.substring(1))+1;
        else
            return Math.max(f(s1.substring(1),s2),f(s1,s2.substring(1)));
    }
}

字母数组或数字的全排列

/*
A B C 
A C B 
B A C 
B C A 
C B A 
C A B 
 */
public class 全排列 {
    public static void main(String[] args) {
        
        char[] data="http://www.mamicode.com/123456789".toCharArray();
        f(data,0);
    }

    private static void f(char[] data, int k) {
        
        if (k==data.length) {
            for (int i = 0; i < data.length; i++) {
                System.out.print(data[i]+" ");
            }
            System.out.println();
        }
        
        for (int j = k; j < data.length; j++) {
            { char t=data[k];data[k]=data[j];data[j]=t; }//试探
            f(data,k+1);//递归
            { char t=data[k];data[k]=data[j];data[j]=t; }//回溯
        }
    }
}

超大的数字和小数的四舍五入(e,zheigehediguimeiguanxi)

import java.math.BigDecimal;
import java.math.BigInteger;

public class 大数和分数 {
    public static void main(String[] args) {
        
        //大的数
        BigInteger bi=BigInteger.valueOf(1);
        BigInteger sum=BigInteger.valueOf(0);
        for (int i = 0; i < 64; i++) {
            sum=sum.add(bi);
            bi=bi.multiply(BigInteger.valueOf(2));
        }
        System.out.println(sum);
        
        //小数的四舍五入
        double d=1234.546556;
        BigDecimal bd=new BigDecimal(d);
        double d1=bd.setScale(2,BigDecimal.ROUND_HALF_UP).doubleValue();
        System.out.println(d1);
    }
}

 

蓝桥杯-递归常用的几种套路