【软件设计师备考 专题 】算法探索:排序、查找、数值计算和字符串处理(二)

简介: 【软件设计师备考 专题 】算法探索:排序、查找、数值计算和字符串处理

【软件设计师备考 专题 】算法探索:排序、查找、数值计算和字符串处理(一)https://developer.aliyun.com/article/1467572


4. 字符串处理方法

4.1 字符串匹配

字符串匹配是指在一个文本串中查找一个模式串的过程。常用的字符串匹配算法有暴力匹配、KMP算法、Boyer-Moore算法等。

4.1.1 暴力匹配

暴力匹配算法,也称为朴素匹配算法,是最简单直观的字符串匹配算法。它的原理是从文本串的每个位置开始,逐个字符与模式串进行比较,直到找到匹配或者遍历完整个文本串。

// 暴力匹配算法示例代码
int bruteForce(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == m) {
            return i; // 匹配成功,返回匹配的起始位置
        }
    }
    return -1; // 匹配失败,返回-1
}

暴力匹配算法的时间复杂度为O(n * m),其中n为文本串的长度,m为模式串的长度。

4.1.2 KMP算法

KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,它利用模式串的特点,在匹配过程中避免不必要的回溯。

// KMP算法示例代码
void getNext(string pattern, int next[]) {
    int m = pattern.length();
    next[0] = -1;
    int i = 0, j = -1;
    while (i < m - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}
int kmp(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    int* next = new int[m];
    getNext(pattern, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    delete[] next;
    if (j == m) {
        return i - j; // 匹配成功,返回匹配的起始位置
    } else {
        return -1; // 匹配失败,返回-1
    }
}

KMP算法的时间复杂度为O(n + m),其中n为文本串的长度,m为模式串的长度。

4.1.3 Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法,它利用模式串的特点和右移规则,在匹配过程中跳过尽可能多的字符。

// Boyer-Moore算法示例代码
void buildBadCharTable(string pattern, int badCharTable[]) {
    int m = pattern.length();
    for (int i = 0; i < 256; i++) {
        badCharTable[i] = m;
    }
    for (int i = 0; i < m - 1; i++) {
        badCharTable[pattern[i]] = m - 1 - i;
    }
}
int boyerMoore(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    int* badCharTable = new int[256];
    buildBadCharTable(pattern, badCharTable);
    int i = m - 1, j = m - 1;
    while (i < n) {
        if (text[i] == pattern[j]) {
            if (j == 0) {
                delete[] badCharTable;
                return i; // 匹配成功,返回匹配的起始位置
            }
            i--;
            j--;
        } else {
            i += badCharTable[text[i]];
            j = m - 1;
        }
    }
    delete[] badCharTable;
    return -1; // 匹配失败,返回-1
}

Boyer-Moore算法的时间复杂度为O(n + m),其中n为文本串的长度,m为模式串的长度。

4.2 字符串编辑距离

字符串编辑距离是指通过一系列的插入、删除和替换操作,将一个字符串转换成另一个字符串所需的最少操作次数。常用的字符串编辑距离算法有Levenshtein距离、Damerau-Levenshtein距离等。

4.2.1 Levenshtein距离

Levenshtein距离,也称为编辑距离,是衡量两个字符串相似程度的指标。它定义为将一个字符串转换成另一个字符串所需的最少编辑操作次数,允许的操作包括插入、删除和替换。

// Levenshtein距离算法示例代码
int levenshteinDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[m][n];
}

Levenshtein距离的时间复杂度为O(m * n),其中m和n分别为两个字符串的长度。

4.2.2 Damerau-Levenshtein距离

Damerau-Levenshtein距离是Levenshtein距离的一种扩展,除了插入、删除和替换操作外,还允许相邻字符的交换操作。

// Damerau-Levenshtein距离算法示例代码
int damerauLevenshteinDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
            if (i > 1 && j > 1 && word1[i - 1] == word2[j - 2] && word1[i - 2] == word2[j - 1]) {
                dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1);
            }
        }
    }
    return dp[m][n];
}

Damerau-Levenshtein距离的时间复杂度为O(m * n),其中m和n分别为两个字符串的长度。

4.3 字符串压缩与解压缩

字符串压缩是指通过对字符串中重复出现的字符进行编码,减少字符串的存储空间。常用的字符串压缩算法有Run-Length Encoding(RLE)算法、Huffman编码等。

4.3.1 Run-Length Encoding(RLE)算法

Run-Length Encoding(RLE)算法是一种简单的无损压缩算法,它通过将连续出现的相同字符替换为字符和出现次数的组合来进行压缩。

// RLE算法示例代码
string compressRLE(string text) {
    int n = text.length();
    if (n <= 1) {
        return text;
    }
    string compressed;
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (text[i] == text[i - 1]) {
            count++;
        } else {
            compressed += text[i - 1] + to_string(count);
            count = 1;
        }
    }
    compressed += text[n - 1] + to_string(count);
    return compressed;
}

4.3.2 Huffman编码

Huffman编码是一种变长编码方法,它通过根据字符出现的频率构建哈夫曼树,并根据哈夫曼树生成每个字符的编码。

// Huffman编码示例代码
struct TreeNode {
    char val;
    int freq;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c, int f) : val(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->freq > b->freq;
    }
};
void buildHuffmanTree(string text, unordered_map<char, int>& freqMap, priority_queue<TreeNode*, vector<TreeNode*>, Compare>& pq) {
    for (char c : text) {
        freqMap[c]++;
    }
    for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
        TreeNode* node = new TreeNode(it->first, it->second);
        pq.push(node);
    }
    while (pq.size() > 1) {
        TreeNode* left = pq.top();
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* parent = new TreeNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
}
void generateHuffmanCode(TreeNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        codeMap[root->val] = code;
    }
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}
string compressHuffman(string text) {
    unordered_map<char, int> freqMap;
    priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq;
    buildHuffmanTree(text, freqMap, pq);
    unordered_map<char, string> codeMap;
    generateHuffmanCode(pq.top(), "", codeMap);
    string compressed;
    for (char c : text) {
        compressed += codeMap[c];
    }
    return compressed;
}

字符串解压缩与压缩相反,根据压缩后的字符串和相应的编码表进行解码即可。

以上是字符串处理方法的一些常用算法和示例代码,通过学习这些算法,可以更好地理解和应用字符串处理技术。在实际的软件设计师考试中,掌握这些知识点将有助于解答相关问题和完成相应的编程任务。


第五章:其他常用算法

5.1 贪心算法

5.1.1 原理及步骤

贪心算法是一种通过每一步的局部最优选择来达到全局最优的算法。其基本思想是在每一步选择中都做出当前状态下最优的选择,而不考虑之后的结果。贪心算法一般可以分为以下步骤:

  1. 定义问题的解空间和解空间的度量准则。
  2. 利用贪心的策略进行选择,即每一步都选择当前最优解。
  3. 判断当前选择是否满足问题的约束条件,如果满足,则进入下一步;如果不满足,则回溯到上一步重新选择。
  4. 重复步骤2和3,直到达到问题的终止条件。

5.1.2 时间复杂度和空间复杂度

贪心算法的时间复杂度一般较低,通常为O(nlogn)或O(n),其中n为问题的规模。空间复杂度则取决于具体的算法实现。

5.1.3 应用场景和优化方法

贪心算法常用于求解最优化问题,例如霍夫曼编码、最小生成树、任务调度等。在实际应用中,需要注意贪心策略是否能够得到全局最优解,有时候需要进行优化方法的改进。

以下是一个示例代码,展示了贪心算法在任务调度问题中的应用:

#include <iostream>
#include <vector>
#include <algorithm>
// 定义任务结构体
struct Task {
    int start;
    int end;
};
// 比较函数,按照任务结束时间进行排序
bool compare(Task t1, Task t2) {
    return t1.end < t2.end;
}
// 贪心算法求解任务调度问题
std::vector<Task> scheduleTasks(std::vector<Task>& tasks) {
    std::vector<Task> result;
    
    // 按照任务结束时间进行排序
    std::sort(tasks.begin(), tasks.end(), compare);
    
    // 选择第一个任务
    result.push_back(tasks[0]);
    int lastEnd = tasks[0].end;
    
    // 依次选择后续任务
    for (int i = 1; i < tasks.size(); i++) {
        if (tasks[i].start >= lastEnd) {
            result.push_back(tasks[i]);
            lastEnd = tasks[i].end;
        }
    }
    
    return result;
}
int main() {
    std::vector<Task> tasks = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9},
                               {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
    
    std::vector<Task> result = scheduleTasks(tasks);
    
    std::cout << "最优任务调度结果:" << std::endl;
    for (auto task : result) {
        std::cout << "开始时间:" << task.start << ",结束时间:" << task.end << std::endl;
    }
    
    return 0;
}


【软件设计师备考 专题 】算法探索:排序、查找、数值计算和字符串处理(三)https://developer.aliyun.com/article/1467574

目录
相关文章
|
29天前
|
算法 C++
【洛谷 P1223】排队接水(贪心算法+结构体排序)
该问题要求安排$n$个人的排队顺序以最小化平均等待时间。每个人接水需时$T_i$,解决方案是让接水时间短的人优先。给定$n\leq1000$和$t_i\leq10^6$,代码示例使用C++实现,通过排序使时间从小到大排列,然后计算平均等待时间。样例输入为10个人的时间数组,输出为优化后的排队顺序及平均等待时间(291.90)。
20 0
|
8天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
33 4
|
1月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
24天前
|
算法 Java 调度
Java数据结构与算法:拓扑排序
Java数据结构与算法:拓扑排序
|
24天前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
18 0
|
29天前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
29天前
|
人工智能 算法 BI
【洛谷 P1803】凌乱的yyy _ 线段覆盖 题解(贪心算法+结构体排序)
**线段覆盖问题**: YYY 想在 NOIP 前参加最多比赛。给定 $n$ 场比赛的开始和结束时间,每场比赛必须连续且不能冲突。输入包含每场比赛的时间段,输出最多可参加的比赛数。$20\%$ 数据 $n\leq10$,$50\%$ 数据 $n\leq10^3$,$100\%$ 数据 $n\leq10^6$。解决方案:按结束时间排序比赛,若当前比赛开始时间晚于上一个结束时间,则计数加一。样例输入:3 场比赛,输出:2。AC C++ 代码实现了此算法。
16 0
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
1月前
|
算法 搜索推荐 数据可视化
【漫画算法】指挥官的排序战术:快速排序算法解密
【漫画算法】指挥官的排序战术:快速排序算法解密