数据结构与算法(3)

数据结构与算法(3)

算法笔记3

一、图

public class Graph {
    /**
     * 顶点的list集合
     */
    private ArrayList<String> vertexList;
    /**
     * 顶点对应的邻接矩阵
     */
    private int [][] adjacencyMatrix;
    /**
     * 边的个数!
     */
    private int edgeCount;

    /**
     * 顶点个数
     */
    private int vertexCount;
    public Graph(int vertexCount) {
        this.vertexCount =vertexCount;
        vertexList = new ArrayList<>(vertexCount);
        adjacencyMatrix = new int[vertexCount][vertexCount];
        edgeCount  = 0;
    }
    /**
     * 添加节点
     */
    public void addVertex(String vertex){
        if (vertexList.size() == vertexCount){
            System.out.println("顶点数已满");
            return;
        }
        vertexList.add(vertex);

    }

    /**
     * 通过字符顶点,获取在临界矩阵中的数字顶点
     * @param vertex
     * @return
     */
    public int getIntByVertex(String vertex){
        int num = 0;
        for (String s : vertexList) {
            if (s == vertex){
                break;
            }
            num++;
        }
        return num;
    }

    /**
     * 添加边
     */
    public void addEdge(String vertex1,String vertex2,int weight){
        int vertexNum1 = getIntByVertex(vertex1);
        int vertexNum2 = getIntByVertex(vertex2);
        adjacencyMatrix[vertexNum1][vertexNum2] = weight;
        adjacencyMatrix[vertexNum2][vertexNum1] = weight;
        edgeCount++;
    }

    /**
     * 展示
     */
    public void showGraph(){
        for (int[] rows : adjacencyMatrix) {
            for (int vertex : rows) {
                System.out.printf(vertex+" ");
            }
            System.out.println("");

        }
    }
    /**
     * 获取邻接节点
     * @return
     */
    public String getAdjacentNode(String s){
        int intByVertex = getIntByVertex(s);
        for (int i = 0; i < vertexCount; i++){
            //如果有边,并且末节点为访问过
            if (adjacencyMatrix[intByVertex][i] != 0&& isVisit[i] == false){
                return getStrByInt(i);
            }
        }
        return null;
    }
}

1.1深度优先


/**
 * DFS搜索
 */
public void DFSSearch(){
    Stack<String> stack = new Stack<>();
    //1.将第一个元素压入栈,并将访问情况至为true
    //访问情况
    isVisit[0] = true;
    //搜索到元素,打印操作
    System.out.printf(vertexList.get(0));
    //压入栈
    stack.push(vertexList.get(0));
    //循环
    while (stack.isEmpty() != true){
        //获取栈顶元素的邻接节点
        String adjacentNode = getAdjacentNode(stack.peek());
        if (adjacentNode == null){
            stack.pop();
        }
        else {
            //访问情况
            isVisit[getIntByVertex(adjacentNode)] = true;
            //搜索到元素,打印操作
            System.out.printf(adjacentNode);
            //压入栈
            stack.push(adjacentNode);

        }
    }
    //还原
    for (int i = 0; i < vertexCount; i++) {
        isVisit[i] = false;
    }
}

1.2广度优先

/**
 * 广度优先搜索
 */
public void BFSSearch(){
    ArrayQueue<String> queue = new ArrayQueue<String>(edgeCount);
    //1.将第一个元素压入栈,并将访问情况至为true
    //访问情况
    isVisit[0] = true;
    //搜索到元素,打印操作
    System.out.printf(vertexList.get(0));
    //压入栈
    queue.add(vertexList.get(0));
    String next;
    while (queue.isEmpty() != true){
        //对头出队列
        String s = queue.remove(0);

        while (( next = getAdjacentNode(s)) != null){
            isVisit[getIntByVertex(next)] = true;
            System.out.printf(next);
            queue.add(next);
        }
    }
    //还原
    for (int i = 0; i < vertexCount; i++) {
        isVisit[i] = false;
    }
}

二、算法

2.1非递归二分查找

/**
 * 非递归二分查找
 * @param arr 查找数组
 * @param target 目标元素
 * @return 目标元素下标
 */
public static int binarySearchNoRecursion(int [] arr, int target){
    int left = 0;
    int right = arr.length - 1;
    int mid = 0;
    //当左边界小于右边界时,一直查找
    while (left <= right){
        //中值
        mid = (left+right) / 2;
        //找到
        if (arr[mid] == target){
            return mid;
        }
        //中值大于目标值
        if (arr[mid] > target){
            //向左寻找
            right = mid - 1;

        }
        else
        {
            //向右
            left = mid + 1;

        }
    }
    //没找到
    return -1;
}

2.2分治算法(汉罗塔问题)

/**
 * 分治算法模仿 汉罗塔问题
 * @param num 罗盘数
 * @param a 第一个柱子
 * @param b 第二个柱子
 * @param c 第三个柱子
 */
public static void divideAndConquer(int num, String a,String b, String c){
    if (num == 1){
        System.out.println("第1个盘从" +a+ "->" +c);
    }
    //此时盘数大于1,将盘看做两个盘:
    //第一个盘为上面所有盘, 第二个盘为最下面的盘
    /*
    分为三步:
    1.把上面所有盘从a->b
    2.把最下面的盘从a->c
    3.把b的盘移到c
     */
    else {
        //1.把上面所有盘从a->b
        divideAndConquer(num-1,a,c,b);
        //2.把最下面的盘从a->c
        System.out.println("第"+num+"个盘从"+a+"->"+c);
        //3.把b的盘移到c
        divideAndConquer(num-1,b,a,c);
    }

}

2.3动态规划

<span>数据结构与算法(3)</span>
问:背包总称重4,物品不重复的前提,如何保证背包装的价格最高

/**
 * @Author: 郜宇博
 * @Date: 2021/8/11 15:31
 * 动态规划问题
 */

public class DynamicProgramming {
    public static void main(String[] args) {
        int []weight = {1,4,3};
        int []value = {1500,3000,2000};
        int knapsackWeight = 4;

        knapsackProblem(weight,value,knapsackWeight);
    }
    public static void knapsackProblem(int[] weight,int[] value, int knapsackWeight){
        //物品数量
        int G,S,L = 0;
        //用于存储各重量背包价值
        int [][] knapsackValue = new int[weight.length+1][knapsackWeight+1];
        int [][] path = new int[weight.length+1][knapsackWeight+1];
        //第一行和第一列设为0
        for (int i =0; i < knapsackValue.length; i++){
            knapsackValue[i][0] = 0;
        }
        for (int i =0; i < knapsackValue[0].length; i++){
            knapsackValue[0][i] = 0;
        }
        //动态规划
        for (int i = 1; i < knapsackValue.length; i++){
            for (int j = 1; j < knapsackValue[i].length; j++){
                if (weight[i-1]>j){
                    //物品大于背包重量
                    knapsackValue[i][j] = knapsackValue[i-1][j];
                }
                else {
                    //如果放入背包
                    if ((value[i-1]+knapsackValue[i-1][j-weight[i-1]]) > knapsackValue[i-1][j]){
                        knapsackValue[i][j] = value[i-1]+knapsackValue[i-1][j-weight[i-1]];
                        //是否到达最后一个点
                        path[i][j] = 1;
                    }
                    //如果不放入背包
                    else {
                        knapsackValue[i][j] = knapsackValue[i-1][j];
                    }
                }
            }
        }

        //展示
        for (int[] ints : knapsackValue) {
            for (int anInt : ints) {
                System.out.printf(anInt+" ");
            }
            System.out.println("");
        }
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i>0&&j>0){
            if (path[i][j] == 1){
                System.out.println("第"+i+"个商品放到背包");
                j = j- weight[i-1];
            }
            i--;
        }


    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115182.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 毕业设计去做基于决策树的网页敏感词过滤系统设计「建议收藏」

    毕业设计去做基于决策树的网页敏感词过滤系统设计「建议收藏」找了两个分开的程序,但是老师说不可以这样,要求用户输入网页文件路径,系统自动识别处理出文本信息,文本信息再通过决策树分类,通过得到的类别再去匹配这个类别的敏感词库,把敏感词找出来。。。。现在感觉只能弄好每个功能,再去画GUI把他们当函数调用了,但是我应该分成哪些功能模块呀,没做过系统,真的难受,每个功能模块的语言是不是必须要统一,Java好还是Python好?有大佬指点一下吗?别喷为什么我现在在忙…

  • QCustomPlot运用

    QCustomPlot运用日常记录学习QCustomPlot的配置和编码过程。1.结构QCustomPlot类的命名规则是QCP加xxx。类的组织有很强的区分性,就如图Qt中的模块分类。  Class Name QCPPlotTitle 图表标题 QCPAxis 坐标轴、上下左右四个坐标轴 …

    2022年10月17日
  • DHCP Option 82详细讲解[通俗易懂]

    DHCP Option 82详细讲解[通俗易懂]option82是dhcp报文中的中继代理信息选项(relayagentinformationoption)。当dhcpclient发送请求报文到dhcpserver时,若需要经过dhcp中继,则由dhcp中继将option82添加到请求报文中。option82包含很多sub-option,本文中的option82只支持sub-option1、sub-option2和sub-

    2022年10月16日
  • 微信H5分享到朋友圈,转发朋友功能随记[通俗易懂]

    微信H5分享到朋友圈,转发朋友功能随记[通俗易懂]最近刚做了一个微信公众号H5项目,里面包含一个分享到朋友圈和分享给好友的功能。配置白名单以及公众号js安全域名这些就不赘述了,接下来简单介绍下实现这个功能的几个前端步骤因为是微信网页开发,项目里如果有用到一些分享,音频,视频的功能就必须接入它的SDK工具包,详情可以到官方文档里看一下第一步绑定域名先登录微信公众平台进入“公众号设置”的“功能设置”里填写“JS接口安全域名”。备注:登录后可在“开发者中心”查看对应的接口权限。第二步引入JS文件在需要调用JS接口的页面引入如下JS文件,(支持ht

  • PyYAML中文文档「建议收藏」

    PyYAML中文文档「建议收藏」PyYAML文档PyYAML现在维护在https://github.com/yaml/pyyaml。此页面仅用于历史目的。英文文档链接:http://pyyaml.org/wiki/PyYAMLDocumentation安装下载源码包PyYAML-3.12.tar.gz并解压缩。转到目录PyYAML-3.12并运行$pythonsetup….

  • 面试基础知识整理

    面试基础知识整理写在前面:3月伊始便经历了几次笔面试,深深感到自己知识储备的不足,痛下决心,在期末考试前一周,着手整理基础知识,希望可以对接下来的笔面试以及秋招有所帮助。本系列文章涉及数据结构及算法均使用Java语言描述。本文系基础知识整理,文章内容多来源于各经典书籍。本系列文章不定期更新,希望我可以有毅力完成这一工作。1.数据结构数组链表栈队列数图堆2.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号