三道经典算法题解析与优化实践

1. 三道经典算法题解析与优化思路

最近在刷算法题时遇到了三道非常有意思的题目，涉及数字串处理、公式求解和累加式输出。这三道题看似简单，但都蕴含着值得深入探讨的算法思想和优化技巧。下面我将详细解析每道题的解题思路、代码实现以及可能的优化方向。

1.1 T19：数字串处理问题

这道题要求我们找出数字串中连续出现次数最多的数字及其出现次数。题目描述是：给定一个数字序列，找出其中连续出现次数最多的数字及其出现次数。

1.1.1 基础解法分析

原始代码的思路非常清晰：

1. 使用temp_num记录当前正在统计的数字
2. 使用temp_count记录当前数字的连续出现次数
3. 使用max_num和max_count记录全局最大值

cpp复制#include <iostream>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int num;
        int max_num=0;
        int max_count=0;
        int temp_num=0;
        int temp_count=0;
        
        for(int i=0;i<n;i++){
            cin>>num;
            if(i==0){
                temp_num=num;
                temp_count=1;
                max_num=num;
                max_count=1;
            }
            else{
                if(num ==temp_num){
                    temp_count++;
                    if(temp_count>max_count){
                        max_count=temp_count;
                        max_num=temp_num;
                    }
                }
                else{
                    temp_num=num;
                    temp_count=1;
                }
            }
        }
        cout<<max_num<<" "<<max_count<<endl;
    }
    return 0;
}

注意：这段代码在处理第一个数字时有特殊处理，这其实可以通过初始化变量来避免，使代码更简洁。

1.1.2 代码优化建议

1. 初始化优化：可以将temp_num初始化为第一个数字，减少特殊判断
2. 变量命名：可以使用更具描述性的变量名，如current_num代替temp_num
3. 边界情况：考虑输入为空的情况（虽然题目保证n>0）

优化后的代码可能如下：

cpp复制#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n && n > 0) {
        int current_num, current_count = 0;
        int max_num = 0, max_count = 0;
        
        for (int i = 0; i < n; ++i) {
            int num;
            cin >> num;
            
            if (num == current_num) {
                ++current_count;
            } else {
                current_num = num;
                current_count = 1;
            }
            
            if (current_count > max_count) {
                max_count = current_count;
                max_num = current_num;
            }
        }
        
        cout << max_num << " " << max_count << endl;
    }
    return 0;
}

1.1.3 算法复杂度分析

时间复杂度：O(n)，只需要一次遍历
空间复杂度：O(1)，只使用了固定数量的变量

1.2 T20：公式求解问题

这道题要求解方程a² + x² = b² + y²，其中x和y都在1到100之间。题目会给出多组a和b的值，每组以0 0结束。

1.2.1 暴力解法（法一）

最直观的方法是双重循环遍历所有可能的x和y：

cpp复制#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    int i = 0; // 记录当前是第几组输出
    
    while (cin >> a >> b) {
        if (a == 0 && b == 0) break;
        
        if (i > 0) cout << endl; // 组间空行
        
        int a2 = a * a;
        int b2 = b * b;
        
        for (int x = 1; x <= 100; x++) {
            for (int y = 1; y <= 100; y++) {
                if (a2 + x * x == b2 + y * y) {
                    cout << x << " " << y << endl;
                }
            }
        }
        i++;
    }
    return 0;
}

这种解法简单直接，但效率不高，时间复杂度为O(n²)，其中n=100。

1.2.2 优化解法（法二）

我们可以通过数学变形来优化：

a² + x² = b² + y²
=> y² = a² - b² + x²
=> y = sqrt(a² - b² + x²)

这样只需要遍历x，然后计算y是否满足条件：

cpp复制#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    int i = 0;
    
    while (cin >> a >> b) {
        if (a == 0 && b == 0) break;
        
        if (i > 0) cout << endl;
        
        int a2 = a * a;
        int b2 = b * b;
        
        for (int x = 1; x <= 100; x++) {
            int y2 = a2 + x * x - b2;
            if (y2 <= 0) continue;
            
            int y = (int)sqrt(y2);
            if (y * y == y2 && y >= 1 && y <= 100) {
                cout << x << " " << y << endl;
            }
        }
        i++;
    }
    return 0;
}

这种优化将时间复杂度降到了O(n)，效率提升明显。

1.2.3 进一步优化思路

1. 预处理平方数：可以预先计算1-100的平方数存入数组，避免重复计算
2. 数学性质利用：观察方程可以发现有对称性，可能可以进一步减少计算量
3. 输出优化：如果输出很多，可以考虑先缓存结果再统一输出

1.3 T21：累加式输出问题

这道题要求按照特定格式输出累加式。例如输入5，输出：
1+2+3+4+5+4+3+2+1

1.3.1 基础解法

原始代码的思路是先正序输出1到n，数字间用+连接，然后逆序输出n-1到1，前面都加+：

cpp复制#include <iostream>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cout<<i;
            if(i<n) cout<<"+";
        }
        for(int i=n-1;i>=1;i--){
            cout<<"+"<<i; 
        }
        cout<<endl; 
    }
    return 0;
}

1.3.2 代码优化建议

1. 减少循环次数：可以合并两个循环
2. 使用字符串拼接：可以先将结果构建成字符串再输出
3. 考虑使用递归：这个问题也可以用递归思路解决

优化后的代码示例：

cpp复制#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        string result;
        for (int i = 1; i <= n; ++i) {
            result += to_string(i);
            if (i < n) result += "+";
        }
        for (int i = n - 1; i >= 1; --i) {
            result += "+" + to_string(i);
        }
        cout << result << endl;
    }
    return 0;
}

1.3.3 其他实现方式

递归解法示例：

cpp复制#include <iostream>
using namespace std;

void printPattern(int n, int current = 1, bool ascending = true) {
    cout << current;
    
    if (ascending && current < n) {
        cout << "+";
        printPattern(n, current + 1, true);
    } 
    else if (current > 1) {
        cout << "+";
        printPattern(n, current - 1, false);
    }
}

int main() {
    int n;
    while (cin >> n) {
        printPattern(n);
        cout << endl;
    }
    return 0;
}

2. 算法题解常见问题与调试技巧

2.1 常见错误类型

1. 边界条件处理不当：如空输入、单个元素等情况
2. 循环条件错误：特别是涉及多个循环时
3. 变量初始化问题：未正确初始化导致结果错误
4. 输出格式问题：如多余的空格、换行等

2.2 调试技巧

1. 小规模测试：先用小数据测试，确保基本逻辑正确
2. 打印中间变量：在关键步骤打印变量值，观察程序状态
3. 逐步调试：使用调试器一步步执行，观察变量变化
4. 边界测试：专门测试边界情况，如最小/最大输入值

2.3 性能优化思路

1. 数学公式简化：如T20中的方程变形
2. 预处理数据：预先计算可能用到的值
3. 减少重复计算：将重复计算结果保存起来
4. 选择合适的数据结构：根据问题特点选择最优结构

3. 从这三道题中学到的编程思维

3.1 问题分解能力

这三道题都展示了如何将复杂问题分解为简单步骤：

1. T19：将连续数字统计分解为当前数字记录和最大值更新
2. T20：将方程求解分解为遍历和验证
3. T21：将模式输出分解为升序和降序两部分

3.2 算法优化思维

从T20的两种解法可以看出算法优化的重要性：

1. 暴力解法简单但效率低
2. 数学优化后性能大幅提升
3. 在编程中要不断思考是否有更优解

3.3 代码整洁与可读性

好的代码应该：

1. 变量命名清晰
2. 结构合理
3. 适当注释
4. 处理边界情况

3.4 调试与测试方法

通过这三道题的实践，我总结了以下调试经验：

1. 先确保小数据正确
2. 再测试边界情况
3. 最后考虑性能优化
4. 保持代码可读性比过早优化更重要

在实际编程中，我习惯先写出可工作的代码，然后再考虑优化。同时，良好的代码风格和适当的注释对于后续维护非常重要，特别是当代码需要修改或扩展时。