算法(五)

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.LinkedList;

public class HomeWork {

    private static LinkedList<Integer> list = new LinkedList<Integer>();

    /**
     * 求解思路： 1.首先判断，如果n>m,则n中大于m的数不可能参与组合，此时置n=m； 2.将最大的数n加入且n==m，则满足条件，输出；
     * 3.将n分两种情况求解：n没有加入，取n=n-1,m=m,递归； 4.n加入，取n=n-1,m=m-n,递归。 5.结束。
     * 
     * @param sum
     * @param n
     */
    static void findSum(int sum, int n) {
        if (n < 1 || sum < 1)
            return;
        if (sum > n) {
            list.add(n);
            findSum(sum - n, n - 1);// n加入，取n=n-1,m=m-n
            list.pop();
            findSum(sum, n - 1); // n没有加入，取n=n-1,m=m
        } else {
            n = sum;
            // System.out.print(sum); // sum < n ,直接输出n就可以满足了
            for (int i = 0; i < list.size(); i++)
                System.out.print("  " + list.get(i));
            System.out.println();
        }
    }

    /**
     * 数兔子(斐波那契) 默认是两只小兔子 第一个月不生------1 第二个月生一对----2 第三个月生一对----3
     * 
     * @param i
     * @return
     */
    static int rabbit(int i) {
        if (i == 2)
            return 1;
        else if (i == 3)
            return 2;
        else
            return rabbit(i - 1) + rabbit(i - 2);
    }

    public static void main(String[] args) throws ParseException {
        // 1.
        findSum(10, 8);
        System.out.println("----------------");
        // 2.
        System.out.println("一个月兔子指数增长总结：");
        for (int j = 2; j < 32; j++) {
            System.out.print(rabbit(j) + "\t");
            if (j % 5 == 1)
                System.out.println();
        }
        System.out.println("\n----------------");
        // 3.
        String string = "13314741143";
        String regex = "^1[345678][0-9]{9}$";
        System.out.println("是否匹配:" + string.matches(regex));
        System.out.println("----------------");
        // 4.
        String string2 = "adfgre";
        String regex1 = "^[a-zA-Z]\\w{5,15}$";
        System.out.println("是否匹配:" + string2.matches(regex1));
        // 5.
        String str = "我草你妈哈哈背景天胡景涛哪肉涯剪短发欲望";
        String strs = str.replaceAll("[肉]|[欲]", "*");
        String strss = strs.replaceAll("胡景涛|草你妈", "***");
        System.out.println(strss);
        // 6.//^(([1-9]{1}\\d*)|([0]{1}))(\\.(\\d){0,2})?$
        String string3 = "$10234685445.023642";
        // (?=(?:\\d{3})+\\b)
        String string3s = string3.replaceAll("\\w{2,4}$", "");
        String string3ss = string3s.replaceAll("[\\w]{3}", "$0,");
        System.out.println(string3ss);
        // \\$(0{1}|([1-9]\\d{0,2}(,\\d{3})*))(\\.\\d{2})?
        // 7.
        // 计算两个时间的差
        // 2017:09:04 00:00:00 - 2017:10:01 00:00:00 差多少天
        //
        SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = dateFormat2.parse("1992-02-13 00:00:00");

        Date date2 = dateFormat2.parse("1992-02-18 00:00:00");

        // 获取时间距离1970年1月1日 0的毫秒数
        long time1 = date1.getTime();
        long time2 = date2.getTime();

        long day = (time2 - time1) / 1000 / 60 / 60 / 24;
        System.out.println("1992-02-13 00:00:00 到 1992-02-18 00:00:00相差:" + day + "天");
    }

}

    // 台阶问题
    // 一次走一节或2阶,n阶台阶有多少种走法
    int StepWen(int num) {
        if (num == 1) {
            return 1;
        }
        if (num == 2) {
            return 2;
        }
        return StepWen(num - 1) + StepWen(num - 2);
    }

    static void func(int m, int n, ArrayList<Integer> arr) {
        if (m == 0) {// 该输出喽
            // 回溯
            System.out.println(arr);
            return;
        }
        if (m <= 0 || n < 0) {// 没有意义,当然不用比
            return;
        }
        // 不包含n的情况
        func(m, n - 1, new ArrayList<>(arr));//import java.util.ArrayList;记得导包
        // 包含n的情况
        arr.add(n);
        func(m - n, n - 1, new ArrayList<>(arr));
    }

    public static void main(String[] args) {
        int m = 13;
        int n = 9;

        func(m, n, new ArrayList<>());

    }