第16章 算法与数据库编程实战

16.1 基础算法问题精解

面试题188 斐波那契数列的多种实现方法

斐波那契数列是经典的递归问题，其定义如下：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。在实际编程中，我们需要考虑不同实现方式的性能差异。

递归实现是最直观的方法，但存在重复计算问题，时间复杂度为O(2^n)：

#include <iostream>
using namespace std;

class FibonacciCalculator 
{
public:
    long long fibonacciRecursive(int n) 
    {
        if (n <= 0) 
        {
            return 0;
        }
        if (n == 1) 
        {
            return 1;
        }
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
};

int main() 
{
    FibonacciCalculator calculator;
    int n = 10;
    cout << "斐波那契数列第" << n << "项（递归）：" 
         << calculator.fibonacciRecursive(n) << endl;
    return 0;
}

迭代实现通过保存中间结果避免重复计算，时间复杂度降为O(n)：

#include <iostream>
#include <vector>
using namespace std;

class FibonacciCalculator 
{
public:
    long long fibonacciIterative(int n) 
    {
        if (n <= 0) 
        {
            return 0;
        }
        if (n == 1) 
        {
            return 1;
        }
        
        long long prev = 0;
        long long curr = 1;
        for (int i = 2; i <= n; i++) 
        {
            long long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
    
    vector<long long> generateSequence(int count) 
    {
        vector<long long> sequence;
        if (count <= 0) 
        {
            return sequence;
        }
        
        sequence.push_back(0);
        if (count == 1) 
        {
            return sequence;
        }
        
        sequence.push_back(1);
        for (int i = 2; i < count; i++) 
        {
            long long next = sequence[i-1] + sequence[i-2];
            sequence.push_back(next);
        }
        return sequence;
    }
};

int main() 
{
    FibonacciCalculator calculator;
    int n = 10;
    
    cout << "斐波那契数列第" << n << "项（迭代）：" 
         << calculator.fibonacciIterative(n) << endl;
    
    vector<long long> sequence = calculator.generateSequence(n);
    cout << "前" << n << "项斐波那契数列：";
    for (long long num : sequence) 
    {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

矩阵快速幂实现将时间复杂度进一步优化到O(log n)，适用于大数计算：

#include <iostream>
#include <vector>
using namespace std;

class MatrixFibonacci 
{
private:
    // 2x2矩阵乘法
    vector<vector<long long>> matrixMultiply(
        const vector<vector<long long>>& A, 
        const vector<vector<long long>>& B) 
    {
        vector<vector<long long>> result(2, vector<long long>(2, 0));
        for (int i = 0; i < 2; i++) 
        {
            for (int j = 0; j < 2; j++) 
            {
                for (int k = 0; k < 2; k++) 
                {
                    result[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        return result;
    }
    
    // 矩阵快速幂
    vector<vector<long long>> matrixPower(int n) 
    {
        vector<vector<long long>> base = {{1, 1}, {1, 0}};
        vector<vector<long long>> result = {{1, 0}, {0, 1}}; // 单位矩阵
        
        while (n > 0) 
        {
            if (n % 2 == 1) 
            {
                result = matrixMultiply(result, base);
            }
            base = matrixMultiply(base, base);
            n /= 2;
        }
        return result;
    }
    
public:
    long long fibonacciMatrix(int n) 
    {
        if (n <= 0) 
        {
            return 0;
        }
        vector<vector<long long>> result = matrixPower(n - 1);
        return result[0][0];
    }
};

int main() 
{
    MatrixFibonacci calculator;
    int n = 10;
    cout << "斐波那契数列第" << n << "项（矩阵快速幂）：" 
         << calculator.fibonacciMatrix(n) << endl;
    return 0;
}

面试题189 杨辉三角的构建与应用

杨辉三角是二项式系数在三角形中的几何排列，每个数等于它上方两数之和。

理论基础：

• 第n行有n个元素
• 每行第一个和最后一个元素为1
• 其他元素满足：triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

#include <iostream>
#include <vector>
using namespace std;

class PascalTriangle 
{
public:
    vector<vector<int>> generateTriangle(int numRows) 
    {
        vector<vector<int>> triangle;
        if (numRows <= 0) 
        {
            return triangle;
        }
        
        // 第一行
        triangle.push_back({1});
        if (numRows == 1) 
        {
            return triangle;
        }
        
        for (int i = 1; i < numRows; i++) 
        {
            vector<int> row;
            row.push_back(1); // 每行第一个元素
            
            for (int j = 1; j < i; j++) 
            {
                int value = triangle[i-1][j-1] + triangle[i-1][j];
                row.push_back(value);
            }
            
            row.push_back(1); // 每行最后一个元素
            triangle.push_back(row);
        }
        
        return triangle;
    }
    
    void printTriangle(const vector<vector<int>>& triangle) 
    {
        int numRows = triangle.size();
        for (int i = 0; i < numRows; i++) 
        {
            // 打印前导空格实现居中效果
            for (int space = 0; space < numRows - i - 1; space++) 
            {
                cout << "  ";
            }
            
            for (int j = 0; j <= i; j++) 
            {
                cout << triangle[i][j] << "   ";
            }
            cout << endl;
        }
    }
    
    // 获取特定位置的二项式系数 C(n, k)
    int getBinomialCoefficient(int n, int k) 
    {
        if (k < 0 || k > n) 
        {
            return 0;
        }
        if (k == 0 || k == n) 
        {
            return 1;
        }
        
        // 使用组合公式 C(n, k) = n! / (k! * (n-k)!)
        // 为避免溢出，使用迭代计算
        long long result = 1;
        if (k > n - k) 
        {
            k = n - k; // 利用对称性
        }
        
        for (int i = 0; i < k; i++) 
        {
            result = result * (n - i) / (i + 1);
        }
        
        return result;
    }
};

int main() 
{
    PascalTriangle pascal;
    int numRows = 6;
    
    vector<vector<int>> triangle = pascal.generateTriangle(numRows);
    cout << "杨辉三角（" << numRows << "行）：" << endl;
    pascal.printTriangle(triangle);
    
    int n = 5, k = 2;
    cout << "二项式系数 C(" << n << ", " << k << ") = " 
         << pascal.getBinomialCoefficient(n, k) << endl;
    
    return 0;
}

面试题190 整数十进制转二进制的多种算法

十进制转二进制是基础的数字系统转换问题，有多种实现方法。

除二取余法是最常用的方法：

#include <iostream>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;

class DecimalToBinaryConverter 
{
public:
    // 方法1：使用除二取余法
    string decimalToBinaryBasic(int decimal) 
    {
        if (decimal == 0) 
        {
            return "0";
        }
        
        string binary;
        bool isNegative = false;
        
        // 处理负数（使用补码表示）
        if (decimal < 0) 
        {
            isNegative = true;
            decimal = -decimal;
        }
        
        while (decimal > 0) 
        {
            binary += (decimal % 2) ? '1' : '0';
            decimal /= 2;
        }
        
        reverse(binary.begin(), binary.end());
        
        if (isNegative) 
        {
            // 简单处理：添加负号，实际应用中应使用补码
            binary = "-" + binary;
        }
        
        return binary;
    }
    
    // 方法2：使用位运算（更高效）
    string decimalToBinaryBitwise(int decimal) 
    {
        if (decimal == 0) 
        {
            return "0";
        }
        
        const int BITS = 32; // 32位整数
        string binary;
        
        for (int i = BITS - 1; i >= 0; i--) 
        {
            int bit = (decimal >> i) & 1;
            binary += (bit ? '1' : '0');
        }
        
        // 去除前导零
        size_t pos = binary.find('1');
        if (pos != string::npos) 
        {
            binary = binary.substr(pos);
        } 
        else 
        {
            binary = "0";
        }
        
        return binary;
    }
    
    // 方法3：使用标准库bitset
    string decimalToBinaryBitset(int decimal) 
    {
        bitset<32> bits(decimal);
        string binary = bits.to_string();
        
        // 去除前导零
        size_t pos = binary.find('1');
        if (pos != string::npos) 
        {
            binary = binary.substr(pos);
        } 
        else 
        {
            binary = "0";
        }
        
        return binary;
    }
    
    // 二进制转十进制
    int binaryToDecimal(const string& binary) 
    {
        int decimal = 0;
        int length = binary.length();
        
        for (int i = 0; i < length; i++) 
        {
            if (binary[i] == '1') 
            {
                decimal = decimal * 2 + 1;
            } 
            else if (binary[i] == '0') 
            {
                decimal = decimal * 2;
            } 
            else 
            {
                throw invalid_argument("无效的二进制字符串");
            }
        }
        
        return decimal;
    }
};

int main() 
{
    DecimalToBinaryConverter converter;
    int decimal = 42;
    
    cout << "十进制数 " << decimal << " 的二进制表示：" << endl;
    cout << "除二取余法: " << converter.decimalToBinaryBasic(decimal) << endl;
    cout << "位运算法: " << converter.decimalToBinaryBitwise(decimal) << endl;
    cout << "bitset法: " << converter.decimalToBinaryBitset(decimal) << endl;
    
    string binary = "101010";
    cout << "二进制数 " << binary << " 的十进制表示: " 
         << converter.binaryToDecimal(binary) << endl;
    
    return 0;
}

面试题191 素数判定与生成算法

素数（质数）是大于1且只能被1和自身整除的自然数，在密码学等领域有重要应用。

基础素数判定：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class PrimeNumber 
{
public:
    // 基础素数判定（试除法）
    bool isPrimeBasic(int n) 
    {
        if (n <= 1) 
        {
            return false;
        }
        if (n == 2) 
        {
            return true;
        }
        if (n % 2 == 0) 
        {
            return false;
        }
        
        // 检查从3到sqrt(n)的奇数
        for (int i = 3; i * i <= n; i += 2) 
        {
            if (n % i == 0) 
            {
                return false;
            }
        }
        
        return true;
    }
    
    // 埃拉托斯特尼筛法生成素数表
    vector<int> generatePrimesSieve(int limit) 
    {
        vector<bool> isPrime(limit + 1, true);
        vector<int> primes;
        
        if (limit < 2) 
        {
            return primes;
        }
        
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= limit; i++) 
        {
            if (isPrime[i]) 
            {
                for (int j = i * i; j <= limit; j += i) 
                {
                    isPrime[j] = false;
                }
            }
        }
        
        for (int i = 2; i <= limit; i++) 
        {
            if (isPrime[i]) 
            {
                primes.push_back(i);
            }
        }
        
        return primes;
    }
    
    // 优化版筛法（奇数筛）
    vector<int> generatePrimesOptimized(int limit) 
    {
        if (limit < 2) 
        {
            return {};
        }
        
        vector<bool> isPrime(limit + 1, true);
        vector<int> primes = {2};
        
        // 只处理奇数
        for (int i = 3; i <= limit; i += 2) 
        {
            if (isPrime[i]) 
            {
                primes.push_back(i);
                if ((long long)i * i <= limit) 
                {
                    for (int j = i * i; j <= limit; j += 2 * i) 
                    {
                        isPrime[j] = false;
                    }
                }
            }
        }
        
        return primes;
    }
    
    // 分解质因数
    vector<pair<int, int>> primeFactorization(int n) 
    {
        vector<pair<int, int>> factors;
        
        if (n <= 1) 
        {
            return factors;
        }
        
        // 处理2的因子
        int count = 0;
        while (n % 2 == 0) 
        {
            count++;
            n /= 2;
        }
        if (count > 0) 
        {
            factors.push_back({2, count});
        }
        
        // 处理奇数因子
        for (int i = 3; i * i <= n; i += 2) 
        {
            count = 0;
            while (n % i == 0) 
            {
                count++;
                n /= i;
            }
            if (count > 0) 
            {
                factors.push_back({i, count});
            }
        }
        
        // 处理剩余的质数
        if (n > 1) 
        {
            factors.push_back({n, 1});
        }
        
        return factors;
    }
};

int main() 
{
    PrimeNumber prime;
    int testNumber = 97;
    
    cout << testNumber << " 是素数吗？ " 
         << (prime.isPrimeBasic(testNumber) ? "是" : "否") << endl;
    
    int limit = 100;
    vector<int> primes = prime.generatePrimesSieve(limit);
    cout << "小于等于 " << limit << " 的素数：" << endl;
    for (int i = 0; i < primes.size(); i++) 
    {
        cout << primes[i];
        if (i < primes.size() - 1) 
        {
            cout << ", ";
        }
        if ((i + 1) % 10 == 0) 
        {
            cout << endl;
        }
    }
    cout << endl;
    
    int factorNumber = 84;
    vector<pair<int, int>> factors = prime.primeFactorization(factorNumber);
    cout << factorNumber << " 的质因数分解：";
    for (size_t i = 0; i < factors.size(); i++) 
    {
        cout << factors[i].first;
        if (factors[i].second > 1) 
        {
            cout << "^" << factors[i].second;
        }
        if (i < factors.size() - 1) 
        {
            cout << " × ";
        }
    }
    cout << endl;
    
    return 0;
}

面试题192 字符串与整数的相互转换

字符串与整数的转换是常见的编程任务，需要处理边界条件和错误情况。

#include <iostream>
#include <string>
#include <climits>
#include <stdexcept>
using namespace std;

class StringIntConverter 
{
public:
    // 字符串转整数（支持负数）
    int stringToInt(const string& str) 
    {
        if (str.empty()) 
        {
            throw invalid_argument("空字符串");
        }
        
        int index = 0;
        int sign = 1;
        int result = 0;
        
        // 跳过前导空格
        while (index < str.length() && str[index] == ' ') 
        {
            index++;
        }
        
        // 处理符号
        if (index < str.length() && (str[index] == '+' || str[index] == '-')) 
        {
            sign = (str[index] == '-') ? -1 : 1;
            index++;
        }
        
        // 转换数字
        while (index < str.length() && isdigit(str[index])) 
        {
            int digit = str[index] - '0';
            
            // 检查溢出
            if (result > INT_MAX / 10 || 
                (result == INT_MAX / 10 && digit > INT_MAX % 10)) 
            {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return sign * result;
    }
    
    // 整数转字符串
    string intToString(int num) 
    {
        if (num == 0) 
        {
            return "0";
        }
        
        string result;
        bool isNegative = false;
        
        // 处理负数
        if (num < 0) 
        {
            isNegative = true;
            // 注意：INT_MIN取反会溢出，需要特殊处理
            if (num == INT_MIN) 
            {
                return "-2147483648";
            }
            num = -num;
        }
        
        // 逐位转换
        while (num > 0) 
        {
            char digit = '0' + (num % 10);
            result = digit + result;
            num /= 10;
        }
        
        if (isNegative) 
        {
            result = "-" + result;
        }
        
        return result;
    }
    
    // 增强版：支持不同进制（2-36）
    string intToStringWithBase(int num, int base = 10) 
    {
        if (base < 2 || base > 36) 
        {
            throw invalid_argument("进制必须在2-36之间");
        }
        
        if (num == 0) 
        {
            return "0";
        }
        
        const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string result;
        bool isNegative = false;
        
        if (num < 0 && base == 10) 
        {
            isNegative = true;
            num = -num;
        }
        
        unsigned int unum = num; // 使用无符号数避免负数问题
        
        while (unum > 0) 
        {
            result = DIGITS[unum % base] + result;
            unum /= base;
        }
        
        if (isNegative) 
        {
            result = "-" + result;
        }
        
        return result;
    }
};

int main() 
{
    StringIntConverter converter;
    
    // 测试字符串转整数
    vector<string> testStrings = {"42", "   -123", "4193 with words", "0", "-2147483648"};
    
    for (const string& str : testStrings) 
    {
        try 
        {
            int result = converter.stringToInt(str);
            cout << "字符串 \"" << str << "\" 转换为整数: " << result << endl;
        } 
        catch (const exception& e) 
        {
            cout << "字符串 \"" << str << "\" 转换错误: " << e.what() << endl;
        }
    }
    
    // 测试整数转字符串
    vector<int> testInts = {42, -123, 0, INT_MAX, INT_MIN};
    
    for (int num : testInts) 
    {
        string result = converter.intToString(num);
        cout << "整数 " << num << " 转换为字符串: \"" << result << "\"" << endl;
    }
    
    // 测试不同进制
    int number = 255;
    cout << "数字 " << number << " 在不同进制下的表示：" << endl;
    for (int base = 2; base <= 16; base++) 
    {
        string result = converter.intToStringWithBase(number, base);
        cout << "基数 " << base << ": " << result << endl;
    }
    
    return 0;
}

16.2 数据库操作实践

面试题193 选课系统设计与实现

选课系统是典型的多表关系数据库应用，涉及学生、课程和选课记录等实体。

数据库设计：

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <memory>
using namespace std;

// 简单的内存数据库模拟
class InMemoryDatabase 
{
private:
    map<int, string> students;
    map<int, pair<string, int>> courses; // 课程ID -> (课程名, 容量)
    map<pair<int, int>, string> enrollments; // (学生ID, 课程ID) -> 成绩
    
    int nextStudentId = 1;
    int nextCourseId = 1;
    
public:
    // 学生管理
    int addStudent(const string& name) 
    {
        students[nextStudentId] = name;
        return nextStudentId++;
    }
    
    string getStudentName(int studentId) 
    {
        auto it = students.find(studentId);
        return (it != students.end()) ? it->second : "未知学生";
    }
    
    // 课程管理
    int addCourse(const string& name, int capacity) 
    {
        courses[nextCourseId] = {name, capacity};
        return nextCourseId++;
    }
    
    string getCourseName(int courseId) 
    {
        auto it = courses.find(courseId);
        return (it != courses.end()) ? it->second.first : "未知课程";
    }
    
    int getCourseCapacity(int courseId) 
    {
        auto it = courses.find(courseId);
        return (it != courses.end()) ? it->second.second : 0;
    }
    
    // 选课功能
    bool enrollStudent(int studentId, int courseId) 
    {
        // 检查学生和课程是否存在
        if (students.find(studentId) == students.end() || 
            courses.find(courseId) == courses.end()) 
        {
            return false;
        }
        
        // 检查是否已经选过该课程
        if (enrollments.find({studentId, courseId}) != enrollments.end()) 
        {
            return false;
        }
        
        // 检查课程容量
        int currentEnrollment = 0;
        for (const auto& enrollment : enrollments) 
        {
            if (enrollment.first.second == courseId) 
            {
                currentEnrollment++;
            }
        }
        
        if (currentEnrollment >= getCourseCapacity(courseId)) 
        {
            return false;
        }
        
        // 成功选课
        enrollments[{studentId, courseId}] = ""; // 初始成绩为空
        return true;
    }
    
    // 成绩管理
    bool setGrade(int studentId, int courseId, const string& grade) 
    {
        auto key = make_pair(studentId, courseId);
        if (enrollments.find(key) != enrollments.end()) 
        {
            enrollments[key] = grade;
            return true;
        }
        return false;
    }
    
    string getGrade(int studentId, int courseId) 
    {
        auto key = make_pair(studentId, courseId);
        auto it = enrollments.find(key);
        return (it != enrollments.end()) ? it->second : "未选课";
    }
    
    // 查询功能
    vector<int> getStudentCourses(int studentId) 
    {
        vector<int> result;
        for (const auto& enrollment : enrollments) 
        {
            if (enrollment.first.first == studentId) 
            {
                result.push_back(enrollment.first.second);
            }
        }
        return result;
    }
    
    vector<int> getCourseStudents(int courseId) 
    {
        vector<int> result;
        for (const auto& enrollment : enrollments) 
        {
            if (enrollment.first.second == courseId) 
            {
                result.push_back(enrollment.first.first);
            }
        }
        return result;
    }
    
    // 统计功能
    void printDatabaseStatus() 
    {
        cout << "=== 数据库状态 ===" << endl;
        cout << "学生总数: " << students.size() << endl;
        cout << "课程总数: " << courses.size() << endl;
        cout << "选课记录总数: " << enrollments.size() << endl;
        
        for (const auto& course : courses) 
        {
            int enrollmentCount = getCourseStudents(course.first).size();
            cout << "课程 '" << course.second.first << "' 选课人数: " 
                 << enrollmentCount << "/" << course.second.second << endl;
        }
        cout << "=================" << endl;
    }
};

// 选课系统业务逻辑层
class CourseSelectionSystem 
{
private:
    unique_ptr<InMemoryDatabase> database;
    
public:
    CourseSelectionSystem() : database(make_unique<InMemoryDatabase>()) {}
    
    // 初始化测试数据
    void initializeTestData() 
    {
        // 添加学生
        int student1 = database->addStudent("张三");
        int student2 = database->addStudent("李四");
        int student3 = database->addStudent("王五");
        
        // 添加课程
        int course1 = database->addCourse("高等数学", 2);
        int course2 = database->addCourse("程序设计", 3);
        int course3 = database->addCourse("数据结构", 2);
        
        cout << "测试数据初始化完成" << endl;
    }
    
    // 学生选课
    void studentEnrollCourse(int studentId, int courseId) 
    {
        if (database->enrollStudent(studentId, courseId)) 
        {
            cout << database->getStudentName(studentId) << " 成功选课: " 
                 << database->getCourseName(courseId) << endl;
        } 
        else 
        {
            cout << database->getStudentName(studentId) << " 选课失败: " 
                 << database->getCourseName(courseId) << endl;
        }
    }
    
    // 教师录入成绩
    void teacherInputGrade(int studentId, int courseId, const string& grade) 
    {
        if (database->setGrade(studentId, courseId, grade)) 
        {
            cout << "成功为 " << database->getStudentName(studentId) 
                 << " 的课程 '" << database->getCourseName(courseId) 
                 << "' 录入成绩: " << grade << endl;
        } 
        else 
        {
            cout << "成绩录入失败" << endl;
        }
    }
    
    // 查询学生选课情况
    void queryStudentCourses(int studentId) 
    {
        cout << database->getStudentName(studentId) << " 的选课情况:" << endl;
        vector<int> courses = database->getStudentCourses(studentId);
        
        if (courses.empty()) 
        {
            cout << "  未选任何课程" << endl;
        } 
        else 
        {
            for (int courseId : courses) 
            {
                string grade = database->getGrade(studentId, courseId);
                cout << "  课程: " << database->getCourseName(courseId) 
                     << ", 成绩: " << (grade.empty() ? "未出成绩" : grade) << endl;
            }
        }
    }
    
    // 查询课程选课学生
    void queryCourseStudents(int courseId) 
    {
        cout << "课程 '" << database->getCourseName(courseId) << "' 的选课学生:" << endl;
        vector<int> students = database->getCourseStudents(courseId);
        
        if (students.empty()) 
        {
            cout << "  暂无学生选课" << endl;
        } 
        else 
        {
            for (int studentId : students) 
            {
                string grade = database->getGrade(studentId, courseId);
                cout << "  学生: " << database->getStudentName(studentId) 
                     << ", 成绩: " << (grade.empty() ? "未出成绩" : grade) << endl;
            }
        }
    }
    
    void printSystemStatus() 
    {
        database->printDatabaseStatus();
    }
};

int main() 
{
    CourseSelectionSystem system;
    
    // 初始化测试数据
    system.initializeTestData();
    cout << endl;
    
    // 模拟选课过程
    cout << "=== 选课过程模拟 ===" << endl;
    system.studentEnrollCourse(1, 1); // 张三选高等数学
    system.studentEnrollCourse(1, 2); // 张三选程序设计
    system.studentEnrollCourse(2, 1); // 李四选高等数学
    system.studentEnrollCourse(2, 2); // 李四选程序设计
    system.studentEnrollCourse(3, 1); // 王五选高等数学（应该失败，容量已满）
    system.studentEnrollCourse(3, 2); // 王五选程序设计
    system.studentEnrollCourse(3, 3); // 王五选数据结构
    cout << endl;
    
    // 模拟成绩录入
    cout << "=== 成绩录入模拟 ===" << endl;
    system.teacherInputGrade(1, 1, "A");
    system.teacherInputGrade(1, 2, "B+");
    system.teacherInputGrade(2, 1, "B");
    system.teacherInputGrade(2, 2, "A-");
    system.teacherInputGrade(3, 2, "C+");
    system.teacherInputGrade(3, 3, "A");
    cout << endl;
    
    // 查询功能演示
    cout << "=== 查询功能演示 ===" << endl;
    system.queryStudentCourses(1);
    cout << endl;
    system.queryStudentCourses(2);
    cout << endl;
    system.queryStudentCourses(3);
    cout << endl;
    
    system.queryCourseStudents(1);
    cout << endl;
    system.queryCourseStudents(2);
    cout << endl;
    
    // 系统状态
    system.printSystemStatus();
    
    return 0;
}

第17章 算法思维拓展与面试技巧

17.1 经典算法问题深入解析

面试题194 八皇后问题的回溯解法

八皇后问题要求在8×8棋盘上放置8个皇后，使得它们互不攻击（即任意两个皇后都不在同一行、同一列或同一对角线上）。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class EightQueensSolver 
{
private:
    vector<vector<string>> solutions;
    
    bool isValid(const vector<string>& board, int row, int col, int n) 
    {
        // 检查同一列
        for (int i = 0; i < row; i++) 
        {
            if (board[i][col] == 'Q') 
            {
                return false;
            }
        }
        
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) 
        {
            if (board[i][j] == 'Q') 
            {
                return false;
            }
        }
        
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) 
        {
            if (board[i][j] == 'Q') 
            {
                return false;
            }
        }
        
        return true;
    }
    
    void backtrack(vector<string>& board, int row, int n) 
    {
        if (row == n) 
        {
            solutions.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) 
        {
            if (isValid(board, row, col, n)) 
            {
                board[row][col] = 'Q';
                backtrack(board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int n) 
    {
        solutions.clear();
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0, n);
        return solutions;
    }
    
    void printSolutions(int n = 8) 
    {
        auto allSolutions = solveNQueens(n);
        cout << n << "皇后问题共有 " << allSolutions.size() << " 种解法" << endl;
        
        // 打印前3种解法（如果存在）
        int count = min(3, (int)allSolutions.size());
        for (int i = 0; i < count; i++) 
        {
            cout << "解法 " << (i + 1) << ":" << endl;
            for (const string& row : allSolutions[i]) 
            {
                for (char cell : row) 
                {
                    cout << cell << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
    }
};

int main() 
{
    EightQueensSolver solver;
    solver.printSolutions(8);
    return 0;
}

面试题195 最大矩形面积问题

给定一个由0和1组成的二维矩阵，找出只包含1的最大矩形，并返回其面积。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class MaxRectangleFinder 
{
public:
    int maximalRectangle(vector<vector<char>>& matrix) 
    {
        if (matrix.empty() || matrix[0].empty()) 
        {
            return 0;
        }
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> heights(cols + 1, 0); // 多加一列用于处理边界
        int maxArea = 0;
        
        for (int i = 0; i < rows; i++) 
        {
            // 更新高度数组
            for (int j = 0; j < cols; j++) 
            {
                if (matrix[i][j] == '1') 
                {
                    heights[j] += 1;
                } 
                else 
                {
                    heights[j] = 0;
                }
            }
            
            // 计算当前行的最大矩形面积
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int>& heights) 
    {
        stack<int> st;
        int maxArea = 0;
        int n = heights.size();
        
        for (int i = 0; i < n; i++) 
        {
            while (!st.empty() && heights[i] < heights[st.top()]) 
            {
                int height = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

int main() 
{
    MaxRectangleFinder finder;
    
    vector<vector<char>> matrix = {
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'}
    };
    
    int maxArea = finder.maximalRectangle(matrix);
    cout << "最大矩形面积为: " << maxArea << endl;
    
    // 可视化矩阵
    cout << "输入矩阵:" << endl;
    for (const auto& row : matrix) 
    {
        for (char cell : row) 
        {
            cout << cell << " ";
        }
        cout << endl;
    }
    
    return 0;
}

面试题196 汉诺塔问题的递归解法

汉诺塔问题是经典的递归问题，涉及将盘子从一个柱子移动到另一个柱子，遵守移动规则。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class HanoiTowerSolver 
{
private:
    int moveCount;
    
    void moveDisk(int n, char from, char to, char aux) 
    {
        if (n == 1) 
        {
            cout << "将盘 1 从 " << from << " 移动到 " << to << endl;
            moveCount++;
            return;
        }
        
        moveDisk(n - 1, from, aux, to);
        cout << "将盘 " << n << " 从 " << from << " 移动到 " << to << endl;
        moveCount++;
        moveDisk(n - 1, aux, to, from);
    }
    
public:
    HanoiTowerSolver() : moveCount(0) {}
    
    void solveHanoi(int n) 
    {
        if (n <= 0) 
        {
            cout << "盘子数量必须大于0" << endl;
            return;
        }
        
        cout << "解决 " << n << " 个盘子的汉诺塔问题:" << endl;
        moveCount = 0;
        moveDisk(n, 'A', 'C', 'B');
        cout << "总移动次数: " << moveCount << " (理论最小值: " << ( (1 << n) - 1 ) << ")" << endl;
    }
    
    // 迭代解法（使用栈模拟）
    void solveHanoiIterative(int n) 
    {
        if (n <= 0) 
        {
            return;
        }
        
        struct Move 
        {
            int n;
            char from, to, aux;
            bool expanded;
        };
        
        stack<Move> st;
        st.push({n, 'A', 'C', 'B', false});
        moveCount = 0;
        
        cout << "迭代解法 - " << n << " 个盘子:" << endl;
        
        while (!st.empty()) 
        {
            Move current = st.top();
            st.pop();
            
            if (current.n == 1) 
            {
                cout << "将盘 1 从 " << current.from << " 移动到 " << current.to << endl;
                moveCount++;
            } 
            else 
            {
                if (!current.expanded) 
                {
                    // 第一次处理这个状态，展开为子问题
                    st.push({current.n, current.from, current.to, current.aux, true});
                    st.push({current.n - 1, current.from, current.aux, current.to, false});
                } 
                else 
                {
                    // 已经展开过，现在执行移动
                    cout << "将盘 " << current.n << " 从 " << current.from << " 移动到 " << current.to << endl;
                    moveCount++;
                    st.push({current.n - 1, current.aux, current.to, current.from, false});
                }
            }
        }
        
        cout << "总移动次数: " << moveCount << endl;
    }
};

int main() 
{
    HanoiTowerSolver solver;
    
    cout << "=== 递归解法 ===" << endl;
    solver.solveHanoi(3);
    
    cout << endl << "=== 迭代解法 ===" << endl;
    solver.solveHanoiIterative(3);
    
    return 0;
}

面试题197 逻辑推理问题：新娘和新郎

这是经典逻辑推理问题，需要根据条件推断正确配对。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MarriageProblemSolver 
{
public:
    void solveMarriageProblem() 
    {
        // 三对新郎新娘：A,B,C 和 X,Y,Z
        vector<char> grooms = {'A', 'B', 'C'};
        vector<char> brides = {'X', 'Y', 'Z'};
        
        // 生成所有可能的配对
        vector<vector<pair<char, char>>> allPairings;
        vector<char> temp = brides;
        
        do 
        {
            vector<pair<char, char>> pairing;
            for (size_t i = 0; i < grooms.size(); i++) 
            {
                pairing.push_back({grooms[i], temp[i]});
            }
            allPairings.push_back(pairing);
        } 
        while (next_permutation(temp.begin(), temp.end()));
        
        // 应用条件过滤
        vector<vector<pair<char, char>>> validSolutions;
        
        for (const auto& pairing : allPairings) 
        {
            if (satisfiesConditions(pairing)) 
            {
                validSolutions.push_back(pairing);
            }
        }
        
        // 输出结果
        cout << "新娘新郎配对问题解决方案:" << endl;
        if (validSolutions.empty()) 
        {
            cout << "无解" << endl;
        } 
        else 
        {
            for (size_t i = 0; i < validSolutions.size(); i++) 
            {
                cout << "解决方案 " << (i + 1) << ":" << endl;
                for (const auto& couple : validSolutions[i]) 
                {
                    cout << "  新郎 " << couple.first << " 娶新娘 " << couple.second << endl;
                }
            }
        }
    }
    
private:
    bool satisfiesConditions(const vector<pair<char, char>>& pairing) 
    {
        // 条件1：A不与X结婚
        for (const auto& couple : pairing) 
        {
            if (couple.first == 'A' && couple.second == 'X') 
            {
                return false;
            }
        }
        
        // 条件2：X不与C结婚
        for (const auto& couple : pairing) 
        {
            if (couple.first == 'C' && couple.second == 'X') 
            {
                return false;
            }
        }
        
        // 条件3：C不与Z结婚
        for (const auto& couple : pairing) 
        {
            if (couple.first == 'C' && couple.second == 'Z') 
            {
                return false;
            }
        }
        
        return true;
    }
};

int main() 
{
    MarriageProblemSolver solver;
    solver.solveMarriageProblem();
    return 0;
}

面试题198 大数乘法算法实现

处理超出基本数据类型范围的大数乘法。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class BigNumberMultiplier 
{
public:
    string multiply(string num1, string num2) 
    {
        if (num1 == "0" || num2 == "0") 
        {
            return "0";
        }
        
        int m = num1.size();
        int n = num2.size();
        vector<int> result(m + n, 0);
        
        // 从低位到高位逐位相乘
        for (int i = m - 1; i >= 0; i--) 
        {
            for (int j = n - 1; j >= 0; j--) 
            {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + result[i + j + 1];
                
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        
        // 转换为字符串
        string product;
        for (int num : result) 
        {
            if (!(product.empty() && num == 0)) 
            {
                product += to_string(num);
            }
        }
        
        return product.empty() ? "0" : product;
    }
    
    // 使用Karatsuba算法（分治法）
    string karatsubaMultiply(string num1, string num2) 
    {
        // 确保字符串长度相等且为2的幂（简化实现）
        int n = max(num1.size(), num2.size());
        while (num1.size() < n) num1 = "0" + num1;
        while (num2.size() < n) num2 = "0" + num2;
        
        if (n == 0) 
        {
            return "0";
        }
        if (n == 1) 
        {
            return to_string((num1[0] - '0') * (num2[0] - '0'));
        }
        
        int half = n / 2;
        
        string a = num1.substr(0, half);
        string b = num1.substr(half);
        string c = num2.substr(0, half);
        string d = num2.substr(half);
        
        string ac = karatsubaMultiply(a, c);
        string bd = karatsubaMultiply(b, d);
        string abcd = karatsubaMultiply(addStrings(a, b), addStrings(c, d));
        
        string adbc = subtractStrings(subtractStrings(abcd, ac), bd);
        
        // 结果 = ac * 10^(2*half) + adbc * 10^half + bd
        for (int i = 0; i < 2 * half; i++) 
        {
            ac += "0";
        }
        for (int i = 0; i < half; i++) 
        {
            adbc += "0";
        }
        
        return addStrings(addStrings(ac, adbc), bd);
    }
    
private:
    string addStrings(string num1, string num2) 
    {
        string result;
        int carry = 0;
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        
        while (i >= 0 || j >= 0 || carry > 0) 
        {
            int sum = carry;
            if (i >= 0) 
            {
                sum += num1[i--] - '0';
            }
            if (j >= 0) 
            {
                sum += num2[j--] - '0';
            }
            result += to_string(sum % 10);
            carry = sum / 10;
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
    
    string subtractStrings(string num1, string num2) 
    {
        // 简化实现，假设num1 >= num2
        string result;
        int borrow = 0;
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        
        while (i >= 0) 
        {
            int digit1 = num1[i--] - '0' - borrow;
            int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
            
            if (digit1 < digit2) 
            {
                digit1 += 10;
                borrow = 1;
            } 
            else 
            {
                borrow = 0;
            }
            
            result += to_string(digit1 - digit2);
        }
        
        reverse(result.begin(), result.end());
        
        // 去除前导零
        size_t pos = result.find_first_not_of('0');
        return (pos != string::npos) ? result.substr(pos) : "0";
    }
};

int main() 
{
    BigNumberMultiplier multiplier;
    
    string num1 = "123456789";
    string num2 = "987654321";
    
    cout << "大数乘法测试:" << endl;
    cout << num1 << " × " << num2 << " = " << endl;
    
    string result1 = multiplier.multiply(num1, num2);
    cout << "标准算法: " << result1 << endl;
    
    // 验证结果
    cout << "验证: " << endl;
    cout << "123456789 × 987654321 = 121932631112635269" << endl;
    
    // 更大数的测试
    string bigNum1 = "12345678901234567890";
    string bigNum2 = "98765432109876543210";
    
    string result2 = multiplier.multiply(bigNum1, bigNum2);
    cout << bigNum1 << " × " << bigNum2 << " = " << endl;
    cout << result2 << endl;
    
    return 0;
}

17.2 面试经验与技巧分享

17.2.1 技术面试准备策略

技术面试的成功不仅取决于技术能力，还与准备策略和面试技巧密切相关。以下是一些有效的准备方法：

算法与数据结构复习：

• 重点掌握数组、链表、栈、队列、哈希表、树、图等基础数据结构
• 熟练运用排序、搜索、动态规划、回溯、分治等算法思想
• 每天坚持解决2-3道LeetCode中等难度问题

系统设计准备：

• 理解常见系统设计模式：MVC、微服务、事件驱动等
• 掌握数据库设计原则和优化技巧
• 学习分布式系统基础概念：负载均衡、缓存、消息队列等

// 面试中常见的白板编码示例：实现LRU缓存
#include <iostream>
#include <unordered_map>
using namespace std;

struct LRUNode 
{
    int key;
    int value;
    LRUNode* prev;
    LRUNode* next;
    
    LRUNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache 
{
private:
    int capacity;
    unordered_map<int, LRUNode*> cache;
    LRUNode* head;
    LRUNode* tail;
    
    void addToHead(LRUNode* node) 
    {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(LRUNode* node) 
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void moveToHead(LRUNode* node) 
    {
        removeNode(node);
        addToHead(node);
    }
    
    LRUNode* removeTail() 
    {
        LRUNode* node = tail->prev;
        removeNode(node);
        return node;
    }
    
public:
    LRUCache(int capacity) 
    {
        this->capacity = capacity;
        head = new LRUNode(-1, -1);
        tail = new LRUNode(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) 
    {
        if (cache.find(key) == cache.end()) 
        {
            return -1;
        }
        
        LRUNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) 
    {
        if (cache.find(key) != cache.end()) 
        {
            LRUNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        } 
        else 
        {
            LRUNode* newNode = new LRUNode(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            
            if (cache.size() > capacity) 
            {
                LRUNode* tailNode = removeTail();
                cache.erase(tailNode->key);
                delete tailNode;
            }
        }
    }
};

// 使用示例
int main() 
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << "get(1): " << cache.get(1) << endl; // 返回 1
    cache.put(3, 3); // 该操作会使得密钥 2 作废
    cout << "get(2): " << cache.get(2) << endl; // 返回 -1 (未找到)
    cache.put(4, 4); // 该操作会使得密钥 1 作废
    cout << "get(1): " << cache.get(1) << endl; // 返回 -1 (未找到)
    cout << "get(3): " << cache.get(3) << endl; // 返回 3
    cout << "get(4): " << cache.get(4) << endl; // 返回 4
    
    return 0;
}

17.2.2 面试后的反思与提升

每次面试后都应该进行系统性的反思：

技术层面的反思：

• 哪些问题回答得不够完善？
• 是否存在知识盲区需要补充？
• 编码过程中出现了哪些错误？

沟通表达的反思：

• 问题理解是否准确？
• 思路表达是否清晰？
• 是否与面试官进行了有效互动？

// 面试常见问题：二叉树相关操作
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTreeProcessor 
{
public:
    // 前序遍历（递归）
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        preorderHelper(root, result);
        return result;
    }
    
    // 前序遍历（迭代）
    vector<int> preorderIterative(TreeNode* root) 
    {
        vector<int> result;
        if (!root) 
        {
            return result;
        }
        
        stack<TreeNode*> st;
        st.push(root);
        
        while (!st.empty()) 
        {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            
            if (node->right) 
            {
                st.push(node->right);
            }
            if (node->left) 
            {
                st.push(node->left);
            }
        }
        
        return result;
    }
    
    // 层次遍历
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> result;
        if (!root) 
        {
            return result;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) 
        {
            int levelSize = q.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < levelSize; i++) 
            {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                
                if (node->left) 
                {
                    q.push(node->left);
                }
                if (node->right) 
                {
                    q.push(node->right);
                }
            }
            
            result.push_back(currentLevel);
        }
        
        return result;
    }
    
    // 判断是否为二叉搜索树
    bool isValidBST(TreeNode* root) 
    {
        return isValidBSTHelper(root, nullptr, nullptr);
    }
    
private:
    void preorderHelper(TreeNode* node, vector<int>& result) 
    {
        if (!node) 
        {
            return;
        }
        result.push_back(node->val);
        preorderHelper(node->left, result);
        preorderHelper(node->right, result);
    }
    
    bool isValidBSTHelper(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) 
    {
        if (!node) 
        {
            return true;
        }
        
        if ((minNode && node->val <= minNode->val) || 
            (maxNode && node->val >= maxNode->val)) 
        {
            return false;
        }
        
        return isValidBSTHelper(node->left, minNode, node) && 
               isValidBSTHelper(node->right, node, maxNode);
    }
};

// 构建测试二叉树
TreeNode* buildTestTree() 
{
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

int main() 
{
    BinaryTreeProcessor processor;
    TreeNode* root = buildTestTree();
    
    cout << "前序遍历（递归）: ";
    vector<int> preorder = processor.preorderTraversal(root);
    for (int val : preorder) 
    {
        cout << val << " ";
    }
    cout << endl;
    
    cout << "前序遍历（迭代）: ";
    vector<int> preorderIter = processor.preorderIterative(root);
    for (int val : preorderIter) 
    {
        cout << val << " ";
    }
    cout << endl;
    
    cout << "层次遍历: " << endl;
    vector<vector<int>> levels = processor.levelOrder(root);
    for (size_t i = 0; i < levels.size(); i++) 
    {
        cout << "第 " << i << " 层: ";
        for (int val : levels[i]) 
        {
            cout << val << " ";
        }
        cout << endl;
    }
    
    // 测试二叉搜索树验证
    TreeNode* bstRoot = new TreeNode(2);
    bstRoot->left = new TreeNode(1);
    bstRoot->right = new TreeNode(3);
    
    cout << "是否为二叉搜索树: " << (processor.isValidBST(bstRoot) ? "是" : "否") << endl;
    
    return 0;
}

17.3 群体面试策略与技巧

群体面试（如群面、小组讨论）考察候选人的团队协作和沟通能力：

有效参与策略：

• 提前了解面试形式和评价标准
• 平衡发言频率，既不过于沉默也不过于强势
• 展现建设性意见和团队合作精神

角色定位建议：

• 根据自身特点选择适合的角色：领导者、记录者、时间管理者等
• 关注团队目标而非个人表现
• 学会倾听和整合他人观点

通过系统的技术准备和面试技巧训练，结合实际的编码实践，候选人可以显著提升面试表现和通过率。重要的是保持持续学习的态度，从每次面试经历中吸取经验，不断完善自己的技术体系和沟通能力。