首页 > 编程语言 >七、常用算法

七、常用算法

时间：2024-09-12 12:23:18浏览次数：3  
标签：常用 String int length dest 算法 public charAt

文章目录

一、二分查找(非递归)

在这里插入图片描述

package com.gyh.algorithm;

import com.gyh.search.BinarySearch;

import java.util.ArrayList;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class BinarySearchNotRecursion {
    public static void main(String[] args) {
        int[] arr = {-1, 11, 11, 11, 34, 89};
        int index = BinarySearchNotRecursion.search(arr, 89);
        System.out.println(index);
    }

    public static int search(int[] nums, int value) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (value < nums[mid]) {
                right = mid - 1;
            } else if (value > nums[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

二、分治算法

2.1 分治算法介绍

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2.2 分治算法应用案例

在这里插入图片描述

在这里插入图片描述

package com.gyh.algorithm;

/**
 * @author Gao YongHao
 * @version 1.0
 * 汉诺塔
 */
public class Hanoi {
    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    public static void hanoiTower(int num, char a, char b, char c) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从" + a + "->" + c);
            return;
        }

        // 如果我们有 n>= 2 情况，我们总是可以看做是两个盘 1. 最下边的一个盘 2. 上面的所有盘
        // 1. 先把 最上面的所有盘 A -> B ，移动过程会使用到 C
        hanoiTower(num - 1, a, c, b);
        // 2. 在把 最下面的盘放入C
        System.out.println("第" + num + "个盘从" + a + "->" + c);
        // 3. 把 B 塔所有的盘放到 C 塔上，移动过程使用到 a 塔
        hanoiTower(num - 1, b, a, c);

    }
}

三、动态规划算法

3.1 引出

在这里插入图片描述

3.2 基本介绍

在这里插入图片描述

3.3 应用实例

在这里插入图片描述

在这里插入图片描述

package com.gyh.algorithm;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3};
        int[] val = {1500, 3000, 2000};
        String[] valStr = {"吉他", "音响", "电脑"};
        int m = 4; // 背包的容量
        int n = val.length; // 物品的数量

        // v[i][j] 表示在前 i 个物品中能有装入容量为 j 的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];
        // 用于记录方案方法
        String[][] items = new String[n + 1][m + 1];
        // 初始化第一行和第一列，这里在本程序中，可以不去处理，因为默认为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0; // 第一列设置为 0
            items[i][0] = "";
        }

        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0; // 第一列设置为 0
            items[0][i] = "";
        }

        // 动态规划
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                // 若当前物品的重量大于目前背包的容量
                // 则默认使用上一物品添加时在该背包容量情况下的价值
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                    items[i][j] = items[i - 1][j];
                } else {
                    // 若当前物品的重量小于等于目前背包的容量
                    // 判断添加当前物品后的最大价值与上一物品添加时的最大价值谁大
                    // 注意：若添加完当前物品后还有背包容量，则需再加上该容量下的最大价值
//                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);

                    // 只有在这里才可能有新的方案给出
                    if (v[i - 1][j] <= val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];

                        String con;
                        items[i][j] = valStr[i - 1] + ((con = items[i - 1][j - w[i - 1]]).equals("") ? con : "+" + con);
                    } else {
                        v[i][j] = v[i - 1][j];
                        items[i][j] = items[i - 1][j];
                    }

                }
            }
        }


        // 输出 v
//        for (int[] ints : v) {
//            for (int anInt : ints) {
//                System.out.print(anInt + "\t\t");
//            }
//            System.out.println();
//        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                System.out.print(v[i][j] + "," + items[i][j] + "\t\t");
            }
            System.out.println();
        }
    }


}

四、KMP算法

4.1 引出

在这里插入图片描述

4.2 暴力匹配法

在这里插入图片描述

在这里插入图片描述


package com.gyh.algorithm;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class ViolenceMatch {
    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "谷 尚硅谷";
        System.out.println(match(str1, str2));
    }

    public static int match(String origin, String sub) {
        char[] org = origin.toCharArray();
        char[] su = sub.toCharArray();

        int pos = 0; // 用于指示原串的匹配时的首位置
        int j = 0;

        while (pos < org.length && j < su.length) {
            if (org[pos] == su[j]) {
                pos++;
                j++;
            } else {
                pos = pos - j + 1; // 回溯到需要匹配的下一个位置
                j = 0;
            }
        }
        if (j == su.length) {
            return pos - j;
        }
        return -1;

    }
}

4.3 KMP算法

在这里插入图片描述

package com.gyh.algorithm;

import java.util.Arrays;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class KMP {
    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "谷 1尚硅谷";
        System.out.println(Arrays.toString(next(str2)));
        System.out.println(match(str1, str2, next(str2)));
    }

    public static int match(String str1, String str2, int[] next) {
        for (int i = 0, j = 0; i < str1.length(); i++) {
            // 需要处理 str1.charAt(i) != str2.charAt(j)，去调整 j 的大小
            // KMP 算法核心点
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }

            if (j == str2.length()) { // 找到了
                return i - j + 1;
            }
        }
        return -1;
    }

    // 获取到一个字符串（子串）的部分匹配值
    public static int[] next(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0; // 如果字符串的长度是 1 部分匹配值就是 0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            // 当 dest.charAt(i) != dest.charAt(j)，我们需要从next[j-1]获取新的j
            // 直到我们发现有 dest.charAt(i) == dest.charAt(j) 成立才退出
            // 这是kmp算法那的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            // 当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        return next;
    }
}

五、贪心算法

5.1 基本介绍

在这里插入图片描述

5.2 应用实例

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.algorithm;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        // 定义地名集合
        Set<String> places = new HashSet<>(Arrays.asList("北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"));
        // 设置广播台的覆盖范围
        HashMap<String, Set<String>> broadCast = new HashMap<>();
        broadCast.put("K1", new HashSet<>(Arrays.asList("北京", "上海", "天津")));
        broadCast.put("K2", new HashSet<>(Arrays.asList("广州", "北京", "深圳")));
        broadCast.put("K3", new HashSet<>(Arrays.asList("成都", "上海", "杭州")));
        broadCast.put("K4", new HashSet<>(Arrays.asList("上海", "天津")));
        broadCast.put("K5", new HashSet<>(Arrays.asList("杭州", "大连")));
        // 用于存储结果
        Set<String> result = new HashSet<>();

        // 用于存储各关闭的覆盖信息
        HashSet<String> tempSet = new HashSet<>();

        String maxBName;
        int max;
        while (!places.isEmpty()) {
            maxBName = null;
            max = -1;
            // 遍历剩余的电台，找出最优解
            for (Map.Entry<String, Set<String>> stringListEntry : broadCast.entrySet()) {
                // 清空临时的set集合
                tempSet.clear();
                // 将当前的广播范围加入至临时集合中
                tempSet.addAll(stringListEntry.getValue());
                // 计算当前的广播的最大未覆盖的范围大小(tempSet会保留交集的结果)
                tempSet.retainAll(places);

                // 记录本轮中最大范围电台的信息
                // 为空表示是第一次添加
                // 若大于已遍历的最大电台未覆盖值则改写信息
                int count;
                if ((count = tempSet.size()) > 0 && (maxBName == null || count > max)) {
                    maxBName = stringListEntry.getKey();
                    max = count;
                }
            }
            // 记录最大的电台信息，并将其在原始map中的信息删除
            if (maxBName != null) {
                result.add(maxBName);
                places.removeAll(broadCast.get(maxBName));
                broadCast.remove(maxBName);
            }

        }
        System.out.println(result);

    }

}

标签：常用,String,int,length,dest,算法,public,charAt
From： https://blog.csdn.net/weixin_44063529/article/details/142136912

相关文章

  • 苹果研究人员提出了一种新颖的AI算法来优化字节级表示以自动语音识别(ASR)，并将其与UTF
    端到端（E2E）神经网络已成为多语言自动语音识别（ASR）的灵活且准确的模型。然而，随着支持的语言数量增加，尤其是像中文、日语、韩语（CJK）这样大字符集的语言，输出层的大小显著增长。这种扩展对计算资源、内存使用和资产大小产生了负面影响。在多语言系统中，这一挑战尤为严重，因为输出通常包......
  • 算法 - 课程笔记
    调度问题插入排序分治法分治法是将原问题划分为多个规模较小的子问题，这些子问题可以独立求解，将子问题的解进行综合得到原问题的解。算法设计一般使用递归算法，算法分析一般使用递归表达式。归并排序归并排序，就是分组再合并，将一个数组等分为左右两个子数组，然后再使用......
  • 路径规划 | 基于A*算法的往返式全覆盖路径规划的改进算法（Matlab）
    目录效果一览基本介绍程序设计参考文献效果一览基本介绍基于A*算法的往返式全覆盖路径规划的改进算法matlab实现代码往返式全覆盖路径规划，通过建立二维栅格地图，设置障碍物，以及起始点根据定义往返式路径规划的定义的优先级运动规则从起始点开始进行全图遍历，利用A......
  • 强烈推荐PyCharm中常用的插件，增强效率，赶快收藏起来！！！
    一、pycharm插件安装方法和路径在上篇文章中介绍到的汉化pycharm的方法中就是通过汉化插件完成的，具体操作如下：打开设置 > 插件，在右侧的文本框中输入想要查看的插件名称，在下方就会罗列出已经安装的相关的插件。二、好用的几个插件1、汉化插件ChineseLanguagePack直......
  • HEXDUMP.EXE 是一个常用的工具，用于查看和显示二进制文件的内容，以十六进制格式呈现。它
    HEXDUMP.EXE是一种早期的计算机程序，用于显示文件的十六进制表示。其起源可以追溯到早期的计算机系统，特别是在UNIX操作系统中。最早的hexdump工具出现在UNIX系统中，它允许用户以十六进制和ASCII格式查看文件内容。这个工具在许多操作系统和编程环境中都得到了实现和扩展，以......
  • Git项目常用命令/Git
    Git一、配置简单配置：查看是否配置用户名和邮箱gitconfig--global--list配置邮箱和用户名gitconfig--globaluser.name"这里换上你的用户名"gitconfig--globaluser.email"这里换上你的邮箱"检查是否生成ssh文件夹ssh-keygen-trsa-C"<邮箱>"二......
  • 算法题：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第 4
    题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第43个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后5问第一个人，他说是10岁。请问第五个人多大？为了解决这个问题，我们可以使用两种不同的算法思路：递归和迭代。首先，我们......
  • 算法与数据结构——二分查找
    二分查找二分查找（binarysearch）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。Qustion：给定一个长度为n的数组nums，元素按从小到大的顺序排列且不重复。请查找并返回元素target在该数组中的索引。若数组不包含......
  • 57.C文件操作有关常用函数和模式整理
    为方便而有所整理数据文件分为文本文件二进制文件求速且生成文件较小则用二进制文件保存数据若要无须经过任何转换就可看到内容用文本文件保存数据FILE*gao=fopen("C:\\Users\\Desktop\\gao.txt","模式");fopen两个参数1个要打开文件的路径2打开的模式方式......
  • 算法备案的意义
        在数字化浪潮的推动下，算法已成为企业运营的核心驱动力。作为一家AI企业来讲，算法备案对于强化企业合规性、提升市场竞争力、防范法律与声誉风险、彰显技术实力以及优化用户体验的重要性。那么算法备案的意义具体是什么？一、企业稳健发展的基石    算法备......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99