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

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/78818527 常...
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/78818527

常用数据结构

数组、链表、堆、栈、队列、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--;
        }

    }


}
目录
相关文章
|
4天前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
11 3
|
1天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
|
2天前
|
运维 Java 程序员
新手进阶:用对if-else,让你的Java逻辑判断不再纠结!
【6月更文挑战第14天】本文介绍了如何有效使用Java中的if-else语句。从基础开始,解释了if-else用于根据条件执行不同代码路径的功能。接着,通过实践演示如何避免过度嵌套以提高代码可读性,利用逻辑运算符简化条件判断,以及在异常处理中运用if-else提升程序健壮性。通过这些最佳实践,旨在帮助开发者更好地掌握if-else,使其成为编程工具箱中的利器。
|
2天前
|
搜索推荐 算法 前端开发
计算机Java项目|基于协同过滤算法的体育商品推荐系统
计算机Java项目|基于协同过滤算法的体育商品推荐系统
|
2天前
|
缓存 安全 Java
全面解读ConcurrentHashMap:Java中的高效并发数据结构
全面解读ConcurrentHashMap:Java中的高效并发数据结构
7 2
|
2天前
|
算法 前端开发 Java
探讨Java中递归构建树形结构的算法
探讨Java中递归构建树形结构的算法
5 1
|
2天前
|
算法 Java 索引
12.12_黑马数据结构与算法笔记Java
12.12_黑马数据结构与算法笔记Java
12 1
|
2天前
|
存储 Java
Java 新手进阶:从变量到常量,一步步走向编程巅峰!
【6月更文挑战第14天】Java新手应掌握变量与常量,它们是编程基础。通过示例展示变量(如矩形的长度和宽度)用于存储可变数据,常量(如重力加速度)用于表示固定值。理解不同类型的变量,如字符串、整型和浮点型,并用`final`关键字定义常量。在银行账户管理程序案例中,变量跟踪账户信息,常量表示年利率。熟悉这些概念将提升编程技能。
|
3天前
|
算法 Java
Java中常用hash算法总结
Java中常用hash算法总结
4 0
|
6天前
|
分布式计算 算法 搜索推荐
Java中可以用的大数据推荐算法
在Java中实现大数据推荐算法,通常使用Apache Mahout、Weka、DL4J或Spark MLlib。本文简要介绍了三种推荐算法:基于内容的推荐、协同过滤推荐和深度学习推荐,以及它们的使用场景。提供了每种算法的伪代码或关键代码片段。基于内容的推荐适用于有用户历史行为和物品内容信息的场景,而协同过滤适用于大量用户行为数据的场景,深度学习推荐则用于处理复杂特征。在实现时,注意数据预处理、特征提取、用户画像构建和相似度计算。
14 1