java进阶 - 常用数据结构以及算法思想

常用数据结构

数组、链表、堆、栈、队列、Hash表、二叉树等

算法思想

算法时间复杂度和空间复杂度的分析计算
算法思想：递推、递归、穷举、贪心、分治、动态规划、迭代、分枝界限

以下是部分代码

package com.cn.learn;

import com.cn.entity.Goods;
import org.junit.Test;

import java.util.*;

/**
 * 描述:算法学习
 *
 * @outhor hjx
 * @create 2017-12-05 11:09
 */
public class LearnArithmeticTest{

    private static int count = 0;
    /**
     * 递推的经典算法
     * 1.兔子数列demo
     * 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci[1]  ）
     * 以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上
     * 斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
     * 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用
     *
     * 2.Hanoi塔
     *设hn为n个盘子从a柱移到c柱所需移动的盘次。
     * 显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，
     * 故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去;
     * 然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。
     * 以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，
     * 然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。
     *　∴hn=2hn-1+1 边界条件：h1=1
     * and so on;
     */
    @Test
    public void learn1(){
        int n = 3;
        System.out.println("经历了多少个月:"+n);
        System.out.println(calc(n));
        System.out.println("罗盘:"+n);
        System.out.println(hanoi(n));
    }

    public static int calc(int month){
        if (month == 1 || month == 2){
            return 1;
        }else{
            return calc(month-1) + calc(month-2);
        }
    }

    public static int hanoi(int n){
        if (n == 1){
            return 1;
        }else{
            return 2*hanoi(n-1)+1;
        }
    }

    /**
     * 递归算法
     * hanoi 算移动
     *
     */
    @Test
    public void learn2(){

        move(4,"A","B","C");
        System.out.println("移动次数 :"+count);
    }

    /**
     *  算移动次数以及如何移动
     * @param n     总数
     * @param p1    1
     * @param p2    2
     * @param p3    3
     */
    public void move(int n,String p1,String p2,String p3){

        if (n == 1){
            System.out.println("从 "+p1+" ----> "+p3);
            count += 1;
        }else{
            move(n-1,p1,p3,p2);
            System.out.println("从 "+p1+" ----> "+p3);
            count += 1;
            move(n-1,p2,p1,p3);
        }

    }

    /**
     * 穷举法
     * 例子 鸡兔同笼
     */
    @Test
    public void learn3(){
        calc03(21,94);
    }
    /**
     * 例子 鸡兔同笼
     * @param head 头的个数
     * @param foot 腿的个数
     *
     */
    public void calc03 (int head,int foot){
        int chicken,rabbit;
        boolean flag = false;
        for(chicken = 0;chicken<=head;chicken++){
            rabbit = head - chicken;
            if(chicken*2+rabbit*4 == foot){
                flag = true;
                System.out.println(String.format("鸡有"+chicken+"只，兔子有"+rabbit+"只"));
            }
        }
        if (flag == false){
            System.out.println(head + "个头的数量和"+foot+"个腿的数量不对！");
        }

    }

    /**
     * 贪心算法
     * 例子 经典的背包问题(不包括0-1背包问题)
     */
    @Test
    public void learn04(){
        List<Goods> list = new ArrayList<Goods>();
        Goods goods1 = new Goods(1,5,20);
        Goods goods2 = new Goods(2,2,10);
        Goods goods3 = new Goods(3,3,10);
        Goods goods4 = new Goods(4,2,4);
        Goods goods5 = new Goods(5,7,100);
        Goods goods6 = new Goods(6,2,5);
        list.add(goods1);
        list.add(goods2);
        list.add(goods3);
        list.add(goods4);
        list.add(goods5);
        list.add(goods6);
        Collections.sort(list);

    }

    /**
     * 位运算
     * 都是基础
     * 由位运算操作符衍生而来的有：
     * &= 按位与赋值
     * |=  按位或赋值
     * ^= 按位非赋值
     * >>= 右移赋值
     * >>>= 无符号右移赋值
     * <<= 赋值左移
     */
    @Test
    public void dynamic(){
        /**
         * 左移   运行结果是20
         */
        System.out.println(5<<2);
        /**
         * 右移   运行结果是1
         */
        System.out.println(5>>2);
        /**
         * 无符号右移
         * 结果是536870911 高位补0所以变成正的
         */
        System.out.println(-5>>>3);
        /**
         * 与 &   运行结果是1
         */
        System.out.println(5&3);
        /**
         * 或 | 运行结果 7
         */
        System.out.println(5|3);
        /**
         * 非 ~ 结果为-6
         */
        System.out.println(~5);
        /**
         * 异或 ^ 结果为6
         */
        System.out.println(5^3);

        System.out.println(8>>2);
    }

    /**
     * 动态规划(问题建模)
     * 1.最优子结构
     * 2.边界
     * 3.状态转移方程
     *  简单的动态规划问题
     *  问题1:有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
     *  问题2:有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。
     *  每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     *  400金/5人 500金/5人 200金/3人 300金/4人 350金/3人
     */
    @Test
    public void learndynamic(){
        //问题1
        System.out.println(calcDynamic01(10));
    }
    /**
     * 问题1:有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
     * n为楼梯的高度
     * 问题建模:
     * 1.最优子结构
     *  F(10) = F(9)+F(8)
     * 2.边界（当楼梯为1或者2时可以直接得出结论）
     *  F(1) = 1
     *  F(2) = 2
     * 3.状态转移方程
     *  F（n） = F(n-1)+ F(n-2)
     * @param n
     */
    public int calcDynamic01(int n){

        if (n < 1){ return 0;}
        if (n == 1){ return 1;}
        if (n == 2){ return 2;}
        int a = 1;
        int b = 2;
        int temp = 0 ;
        for(int i=3;i<=n;i++){
            temp = a+b;
            a = b;
            b =temp;
        }
        return  temp;
    }

    /**
     * 有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。
     * 每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     * 400金/5人 500金/5人 200金/3人 300金/4人 350金/3人
     * 问题建模：
     * 1.最优子结构
     * 四金矿 10工人 或者 四金矿 10-3工人
     * F(5,10) = MAX(F(4,10),F(4,10-P(4))+G(4))
     * 2.边界
     * 当N=1,W>=P[0]时，F(N.W) = G[0]
     * 当N=1,W<P[0]时，F(N.W) = 0
     * 3.状态转移方程
     * F(n,w) = F(n-1,w) (n>1, w<p[n-1]) ----> F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])
     *
     * @param n 金矿数量
     * @param w 工人数
     * @param g 黄金量
     * @param p 金矿用工量
     * @return 最大值
     */
    public int calcGold(int n,int w,int[] g,int[] p){
        int[] preResult = new int[p.length];
        int[] results = new int[p.length];
        for(int i=0;i<=n;i++){
            if (i<p[0]){
                preResult[i] = 0;
            }else{
                preResult[i] = g[0];
            }
        }
        // 外层循环 金矿数量 内层循环 工人数量
        for (int i=0;i<n;i++){
            for (int j=0;j<=w;j++){
                if (j<p[i]){
                    results[j] = preResult[j];
                }else{
                    results[j] = Math.max(preResult[j],preResult[j-p[i]]+g[i]);
                }
            }
            preResult = results;
        }
        return results[n];
    }

    /**
     * 动态规划
     * 核心理解
     * 1.最优子结构
     * 总价值 tab(i+1) = max( tab(i) + v(i+1) , tab(i) ) 寻找最优解子结构
     * 重量   j(i+1) = j(i) + w(i+1)
     * 2.边界
     * 3.状态转移方程
     * total[i][j] = max(total[i-1][j-weight[i]]+value[i],total[i-1][j]) ({i,j|0< i <=n,0<= j <=packMax})
     * 0-1 背包问题
     */
    @Test
    public void pack(){
        //物品重量
        int[] weight = {5,2,3,2,7,2};
        //物品价值
        int[] val = {20,10,10,4,100,5};
        //背包容量
        int m = 15;
        //物品个数
        int n = val.length;
        //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值
        int[][] f = new int[n+1][m+1];
        int[][] path = new int[n+1][m+1];
        //初始化第一列和第一行
        for(int i=0;i<f.length;i++){
            f[i][0] = 0;
        }
        for(int i=0;i<f[0].length;i++){
            f[0][i] = 0;
        }
        /**
         * 通过公式迭代计算
         */
        for(int i=1;i<f.length;i++){
            for(int j=1;j<f[0].length;j++){
                if(weight[i-1]>j){
                    f[i][j] = f[i-1][j];
                }else{
                    if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){
                        f[i][j] = f[i-1][j-weight[i-1]]+val[i-1];
                        path[i][j] = 1;
                    }else{
                        f[i][j] = f[i-1][j];
                    }
                }
            }
        }
        for(int i=0;i<f.length;i++){

            for(int j=0;j<f[0].length;j++){
                System.out.print(f[i][j]+" ");
            }
            System.out.println();
        }
        int i=f.length-1;
        int j=f[0].length-1;
        while(i>0&&j>0){
            if(path[i][j] == 1){
                System.out.print("第"+i+"个物品装入 ");
                j -= weight[i-1];
            }
            i--;
        }

    }


}