首页 > 编程语言 >解密编程的八大法宝（四）（附二分查找、分治法和图论算法（深度和广度优先搜索、最短路径、最小生成树）详解）

解密编程的八大法宝（四）（附二分查找、分治法和图论算法（深度和广度优先搜索、最短路径、最小生成树）详解）

时间：2024-08-02 10:26:42浏览次数：16  
标签：图论 int 解密 mid 查找 算法 详解 array left

算法题中常见的几大解题方法有以下几种：：

  1. 暴力枚举法（Brute Force）：这是最基本的解题方法，直接尝试所有可能的组合或排列来找到答案。这种方法适用于问题规模较小的情况，但在大多数情况下效率不高。

  2. 贪心算法（Greedy Algorithm）：贪心算法在每一步都选择当前看起来最优的解，希望最终能得到全局最优解。这种方法适用于一些特定类型的问题，如背包问题、最小生成树等。

  3. 分治法（Divide and Conquer）：将问题分解为更小的子问题，递归解决这些子问题，然后将结果合并以得到原问题的解。经典的例子包括快速排序和归并排序。

  4. 动态规划（Dynamic Programming）：动态规划通过将问题分解为相互重叠的子问题，并使用记忆化技术来避免重复计算，来解决问题。这种方法适用于有重叠子问题和最优子结构性质的问题。

  5. 回溯法（Backtracking）：回溯法是一种试错的算法，通过不断尝试和撤销来搜索所有可能的解。这种方法适用于需要探索所有可能解的组合问题。

  6. 二分查找（Binary Search）：二分查找是一种在有序数组中查找特定元素的高效算法。每次比较中间元素，根据大小关系缩小查找范围。

  7. 图论算法：图论算法用于解决图相关的问题，包括最短路径、最小生成树、拓扑排序等。常见的图论算法有Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。

  8. 字符串匹配算法：字符串匹配算法用于在一个文本中查找一个模式串的出现位置。经典的算法有KMP算法、Boyer-Moore算法和Rabin-Karp算法等。

本文主要详细介绍一下二分查找、分治法和图论算法：

1、二分查找法的详细概念

二分查找法（Binary Search）是一种高效的查找算法，适用于在有序数组或列表中查找特定元素。其核心思想是通过不断将查找范围减半，从而快速缩小目标元素的查找范围。二分查找的时间复杂度为O(log n)，远优于线性查找的O(n)。

二分查找法的基本步骤如下：

  1. 初始化边界：定义查找范围的左边界（left）和右边界（right）。
  2. 计算中间点：计算当前查找范围的中间点（mid）。
  3. 比较中间点元素：将中间点元素与目标元素进行比较：
    • 如果中间点元素等于目标元素，则查找成功，返回中间点的索引。
    • 如果中间点元素小于目标元素，则将左边界移动到中间点的右侧，即 left = mid + 1。
    • 如果中间点元素大于目标元素，则将右边界移动到中间点的左侧，即 right = mid - 1。
  4. 重复步骤2和3：在新的查找范围内重复上述步骤，直到找到目标元素或查找范围为空。

二分查找法的实现

以下是二分查找法的标准实现：

1. 迭代版本
public class BinarySearch {
    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 表示未找到目标元素
    }
}
2. 递归版本
public class BinarySearch {
    public int binarySearch(int[] nums, int target) {
        return binarySearchHelper(nums, target, 0, nums.length - 1);
    }

    private int binarySearchHelper(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1; // 表示未找到目标元素
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearchHelper(nums, target, mid + 1, right);
        } else {
            return binarySearchHelper(nums, target, left, mid - 1);
        }
    }
}

二分查找法的应用场景

二分查找法适用于以下几类问题：

  1. 有序数组查找：在有序数组中查找特定元素的位置。
  2. 查找上下界：查找有序数组中某个元素的最左或最右位置。
  3. 峰值元素查找：在数组中查找局部峰值元素。
  4. 旋转有序数组查找：在旋转后的有序数组中查找特定元素。

应用示例

示例1：查找有序数组的最左位置

问题描述：给定一个有序数组和一个目标值，返回目标值在数组中的最左位置。如果目标值不在数组中，返回-1。

public class BinarySearch {
    public int findLeftmostPosition(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < nums.length && nums[left] == target) {
            return left;
        }
        return -1; // 表示未找到目标元素
    }
}
示例2：查找旋转有序数组中的元素

问题描述：给定一个旋转后的有序数组和一个目标值，返回目标值在数组中的位置。如果目标值不在数组中，返回-1。

public class BinarySearch {
    public int searchInRotatedArray(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // 表示未找到目标元素
    }
}

二分查找法的优势和劣势

优势：

  1. 高效：时间复杂度为O(log n)，适用于大规模数据的查找问题。
  2. 简单：实现逻辑清晰，代码简洁。

劣势：

  1. 适用范围有限：仅适用于有序数组或列表的查找问题。
  2. 不适合动态数据：对于频繁插入和删除操作的动态数据结构，二分查找效率较低。

二分查找法的变种

  1. 查找第一个等于目标值的位置。
  2. 查找最后一个等于目标值的位置。
  3. 查找第一个大于等于目标值的位置。
  4. 查找最后一个小于等于目标值的位置。

这些变种可以通过对二分查找的边界条件进行调整来实现，具体实现方法类似于标准二分查找，但需要根据具体需求进行适当修改。

总结

二分查找法是一种高效的查找算法，广泛应用于各种查找问题。通过不断缩小查找范围，二分查找能够在对数时间内找到目标元素或确定其不存在。掌握二分查找法及其变种，能够帮助你在解决查找问题时更加高效和准确。

分治法的详细概念

分治法（Divide and Conquer）是一种算法设计范式，通过将一个复杂问题分解为多个规模较小的子问题，递归解决这些子问题，然后将子问题的解合并得到原问题的解。分治法的核心思想是将问题分解（Divide）、递归解决（Conquer）和合并（Combine）。

分治法的基本步骤可以概括为以下三步：

  1. 分解（Divide）：将原问题分解为若干个规模较小且相互独立的子问题。
  2. 解决（Conquer）：递归地解决这些子问题。当子问题的规模足够小时，直接解决。
  3. 合并（Combine）：将子问题的解合并成原问题的解。

分治法的应用场景

分治法广泛应用于各种算法设计中，特别是在解决具有重复子结构的问题时表现出色。常见的应用场景包括：

  1. 排序算法：如归并排序（Merge Sort）、快速排序（Quick Sort）。
  2. 搜索算法：如二分查找（Binary Search）。
  3. 大整数乘法：如Karatsuba算法。
  4. 矩阵乘法：如Strassen算法。
  5. 最近点对问题：通过分治法求解平面上最近的两个点。

分治法的示例

示例1：归并排序

归并排序是一种典型的分治法应用，通过将数组分成两半，递归排序每一半，然后合并两个有序数组。

public class MergeSort {
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }

    private void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = array[left + i];
        for (int i = 0; i < n2; i++) R[i] = array[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k++] = L[i++];
            } else {
                array[k++] = R[j++];
            }
        }
        while (i < n1) array[k++] = L[i++];
        while (j < n2) array[k++] = R[j++];
    }

    public static void main(String[] args) {
        MergeSort ms = new MergeSort();
        int[] array = {12, 11, 13, 5, 6, 7};
        ms.mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array)); // 输出: [5, 6, 7, 11, 12, 13]
    }
}
示例2：快速排序

快速排序通过选择一个基准元素，将数组分成两部分，一部分小于基准元素，另一部分大于基准元素，然后递归排序这两部分。

public class QuickSort {
    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    private int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        QuickSort qs = new QuickSort();
        int[] array = {10, 7, 8, 9, 1, 5};
        qs.quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array)); // 输出: [1, 5, 7, 8, 9, 10]
    }
}
示例3：二分查找

二分查找在一个有序数组中查找目标值，通过每次将查找范围减半，快速找到目标值。

public class BinarySearch {
    public int binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int[] array = {2, 3, 4, 10, 40};
        int result = bs.binarySearch(array, 10);
        System.out.println(result); // 输出: 3
    }
}

分治法的优缺点

优点：

  1. 易于理解和实现：分治法将复杂问题分解为较小的子问题，递归解决，逻辑清晰。
  2. 高效：对于许多问题，分治法能显著减少时间复杂度，如快速排序和归并排序。
  3. 并行计算：分治法的子问题相互独立，适合并行计算。

缺点：

  1. 递归开销：递归调用会带来额外的函数调用开销，可能导致栈溢出。
  2. 问题分解困难：对于某些问题，找到合适的分解方法和合并策略可能比较困难。

分治法的优化

在实际应用中，可以通过以下方法优化分治法：

  1. 尾递归优化：将递归转换为迭代，减少函数调用开销。
  2. 记忆化搜索：对于重复计算的子问题，使用记忆化技术存储中间结果。
  3. 动态规划：对于具有重叠子问题和最优子结构的问题，可以使用动态规划替代分治法，提高效率。

总结

分治法是一种强大的算法设计范式，广泛应用于各种复杂问题的求解。通过将问题分解为较小的子问题，递归解决这些子问题，并合并子问题的解，分治法能够显著提高算法效率。掌握分治法的基本思想和常见应用，能够帮助你在实际应用中更高效地解决各种复杂问题。

3、二分法和分治法对比

二分法（Binary Search）可以被看作是分治法（Divide and Conquer）的一种特例。二分法的核心思想与分治法一致，即将问题分解为较小的子问题，递归或迭代解决这些子问题。

分治法的基本步骤
  1. 分解（Divide）：将原问题分解为若干个规模较小且相互独立的子问题。
  2. 解决（Conquer）：递归地解决这些子问题。当子问题的规模足够小时，直接解决。
  3. 合并（Combine）：将子问题的解合并成原问题的解。
二分法的基本步骤
  1. 分解（Divide）：将查找范围分成两半。
  2. 解决（Conquer）：比较中间元素与目标值，如果相等则找到目标值；否则根据比较结果选择一半继续查找。
  3. 合并（Combine）：二分法不需要显式的合并步骤，因为它直接在递归或迭代过程中得出结果。
对比

虽然二分法是分治法的一种特例，但它们在应用场景和具体实现上有所不同：

  • 分治法：用于解决广泛的复杂问题，包括排序、矩阵乘法、大整数乘法等。一般需要明确的分解和合并步骤。
  • 二分法：专用于在有序数组或列表中查找目标值。分解步骤简单且不需要显式的合并步骤。

4、图论算法

图论算法是一类用于处理和分析图（Graph）结构的算法。图是由节点（也称为顶点）和连接这些节点的边组成的结构，广泛应用于计算机科学、网络科学、物流规划、社交网络分析等领域。图论算法涉及如何有效地表示、遍历、搜索和优化图结构。

图的基本概念

  1. 节点（顶点，Vertex）：图中的基本单位，表示对象。
  2. 边（Edge）：连接两个节点的线，表示节点之间的关系。
  3. 无向图（Undirected Graph）：边没有方向，表示双向关系。
  4. 有向图（Directed Graph）：边有方向，表示单向关系。
  5. 加权图（Weighted Graph）：边带有权重，表示节点之间的距离或代价。
  6. 邻接矩阵（Adjacency Matrix）：用一个二维矩阵表示图，矩阵元素表示节点之间是否有边及其权重。
  7. 邻接表（Adjacency List）：用一个数组或链表表示图，每个节点对应一个列表，列表中存储与该节点相连的节点和边的权重。

常见的图论算法

1. 图遍历算法

  • 深度优先搜索（DFS, Depth-First Search）：
    深度优先搜索是一种遍历或搜索图的算法，沿着图的深度遍历尽可能远的节点，然后回溯。

    public class DFS {
    public void depthFirstSearch(Graph graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        dfsHelper(graph, start, visited);
    }

    private void dfsHelper(Graph graph, int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
        for (int neighbor : graph.getNeighbors(v)) {
            if (!visited[neighbor]) {
                dfsHelper(graph, neighbor, visited);
            }
        }
    }
}

  • 广度优先搜索（BFS, Breadth-First Search）：
    广度优先搜索是一种遍历或搜索图的算法，从起始节点开始，逐层遍历邻近节点。

    public class BFS {
    public void breadthFirstSearch(Graph graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            for (int neighbor : graph.getNeighbors(v)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}
2. 最短路径算法

  • Dijkstra 算法：
    用于查找加权图中单源最短路径，不能处理负权边。

    public class Dijkstra {
    public int[] dijkstra(Graph graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }
            if (dist[u] == Integer.MAX_VALUE) break;
            visited[u] = true;

            for (int v : graph.getNeighbors(u)) {
                if (!visited[v] && dist[u] + graph.getWeight(u, v) < dist[v]) {
                    dist[v] = dist[u] + graph.getWeight(u, v);
                }
            }
        }
        return dist;
    }
}

  • Bellman-Ford 算法：
    用于查找加权图中单源最短路径，可以处理负权边。

    public class BellmanFord {
    public int[] bellmanFord(Graph graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int u = 0; u < n; u++) {
                for (int v : graph.getNeighbors(u)) {
                    if (dist[u] != Integer.MAX_VALUE && dist[u] + graph.getWeight(u, v) < dist[v]) {
                        dist[v] = dist[u] + graph.getWeight(u, v);
                    }
                }
            }
        }

        for (int u = 0; u < n; u++) {
            for (int v : graph.getNeighbors(u)) {
                if (dist[u] != Integer.MAX_VALUE && dist[u] + graph.getWeight(u, v) < dist[v]) {
                    throw new IllegalArgumentException("Graph contains a negative-weight cycle");
                }
            }
        }
        return dist;
    }
}
3. 最小生成树算法

  • Kruskal 算法：
    用于查找加权无向图的最小生成树，基于贪心策略和并查集。

    public class Kruskal {
    public List<Edge> kruskal(Graph graph) {
        List<Edge> result = new ArrayList<>();
        Collections.sort(graph.getEdges(), Comparator.comparingInt(Edge::getWeight));
        UnionFind uf = new UnionFind(graph.size());

        for (Edge edge : graph.getEdges()) {
            if (uf.find(edge.getU()) != uf.find(edge.getV())) {
                result.add(edge);
                uf.union(edge.getU(), edge.getV());
            }
        }
        return result;
    }
}

  • Prim 算法：
    用于查找加权无向图的最小生成树，基于贪心策略。

    public class Prim {
    public List<Edge> prim(Graph graph, int start) {
        List<Edge> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.size()];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
        visit(graph, start, visited, pq);

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int u = edge.getU();
            int v = edge.getV();
            if (visited[u] && visited[v]) continue;
            result.add(edge);
            if (!visited[u]) visit(graph, u, visited, pq);
            if (!visited[v]) visit(graph, v, visited, pq);
        }
        return result;
    }

    private void visit(Graph graph, int u, boolean[] visited, PriorityQueue<Edge> pq) {
        visited[u] = true;
        for (Edge edge : graph.getEdges(u)) {
            if (!visited[edge.getV()]) {
                pq.add(edge);
            }
        }
    }
}

图论算法的应用场景

  1. 网络流量优化：如最大流问题、最小割问题。
  2. 路径规划：如导航系统中的最短路径算法。
  3. 社交网络分析：如社区检测、影响力最大化问题。
  4. 计算生物学：如基因序列比对、蛋白质相互作用网络分析。
  5. 物流和运输：如车辆路径优化、供应链管理。

总结

图论算法是处理图结构的关键工具，涉及图的表示、遍历、搜索和优化等多方面。掌握常见的图论算法，如深度优先搜索、广度优先搜索、最短路径算法和最小生成树算法，可以帮助你解决各种复杂的图相关问题。在实际应用中，选择合适的算法和数据结构，可以显著提高问题求解的效率和效果。

标签：图论,int,解密,mid,查找,算法,详解,array,left
From： https://blog.csdn.net/weixin_55745942/article/details/140865120

相关文章

  • 数据结构C语言---文件的加密和解密
    本篇的主要目的是利用所学的数据结构的知识对一个任意文件进行加密和解密。在文件加密过程中，常用的数据结构包括哈希表、树结构（如二叉搜索树、哈夫曼树）、堆、链表等。选择合适的数据结构取决于加密算法的需求和特性。选择合适的加密算法和数据结构对保障数据安全至关重要。常......
  • SQL命令详解
    countCOUNT()函数COUNT()函数进行计数。可利用COUNT()确定表中行的数目或符合特定条件的行的数目。COUNT()函数有两种使用方式：使用COUNT(*)对表中行的数目进行计数，不管表列中包含的是空值（NULL）还是非空值。使用COUNT(column)对特定列中具有值的行进行计数，忽略NULL值。下面......
  • 24-7-31String类,StringBuffer类,StringBuilder类的详解与比较
    24-7-31String类,StringBuffer类,StringBuilder类的详解与比较文章目录24-7-31String类,StringBuffer类,StringBuilder类的详解与比较StringString的结构String的方法String对象的两种创建方法String的其他方法String练习StringExercise01StringExercise02StringExer......
  • grep命令详解：文本搜索的利器
    grep命令详解：文本搜索的利器大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！grep是一个强大的命令行工具，用于在文件中搜索特定的文本模式。它是Unix和类Unix系统中最常用的工具之一，广泛应用于系统管理、日志分析、代码查找等场景。本文将详细介绍grep命令......
  • Jenkins 配置即代码（Configuration as Code）详解
    1、概述在《Centos7下安装配置最新版本Jenkins(2.452.3)》这篇博文中讲解了如何安装Jenkins，虽然在安装Jenkins时安装了一些必备的推荐插件，但在企业环境中使用Jenkins之前，我们仍需完成一系列手动配置工作，如配置SystemConfiguration、Security。SystemConfiguration是确保......
  • 文件系统类型详解及选择指南
    文件系统类型详解及选择指南大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！文件系统是操作系统管理存储设备的一种方式，负责文件的存储、读取和管理。不同的文件系统有不同的特性和适用场景。了解这些文件系统类型有助于我们根据需求选择最合适的文件系统......
  • Java多线程编程详解：从基础到高级
    Java多线程编程详解：从基础到高级大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！Java的多线程编程允许程序同时执行多个任务，提高了应用的性能和响应能力。本文将从基础到高级，全面介绍Java中的多线程编程，包括线程的创建、线程池、同步机制及并发工具的使用......
  • Java堆栈详解：内存管理与优化
    Java堆栈详解：内存管理与优化大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！Java的内存管理系统由堆（Heap）和栈（Stack）两部分组成，这些部分负责管理Java程序运行时的数据。理解Java堆栈的内存管理以及如何优化这些资源对于开发高效的Java应用至关重要。本文将......
  • Mojo模块和包的概念详解
    Mojo提供了一个打包系统，可让您将代码库组织和编译库为可导入文件。本文介绍了关于如何将您的代码组织成模块和包的必要概念。并向您展示了如何使用命令行创建打包mojo的二进制包文件。Mojomodules了解Mojo软件包，首先需要了解Mojo模块。Mojo模块是一个Mojo源文件，其......
  • Kotlin 运算符详解：算术、赋值、比较与逻辑运算符全解析
    Kotlin运算符运算符用于对变量和值执行操作。值称为操作数，而操作符定义了要在两个操作数之间执行的操作：操作数运算符操作数100+50在下面的示例中，数字100和50是操作数，+号是运算符：示例varx=100+50虽然+运算符通常用于将两个值相加，如上例所示，但它也可以用......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99