华为机试经典算法题整理与实战解析

最长公共子序列：dp[i][j] 表示 str1[0...i] 和 str2[0...j] 的最长公共子序列长度。

• 当 str1[i] == str2[j] 时，dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 最优解为 dp[len1-1][len2-1]

4. 数学与模拟问题

约瑟夫环问题（每隔两个数删掉一个数）和牛顿迭代法求立方根也是常考点。例如求 y 的立方根，设 f(x)=x³-y，根据牛顿迭代公式 xₙ₊₁=xₙ-f(xₙ)/f'(xₙ)，可推导出 x = (2*x + y/x/x)/3。

扑克牌大小比较则涉及自定义排序规则，注意大小王（JOKER/joker）的特殊性。

5. 实用代码片段

统计二进制中 1 的个数

通过取模运算逐位检查，适合处理位运算相关题目。

#include <iostream>

int main() {
    int num;
    while (std::cin >> num) {
        int count = 0;
        while (num > 0) {
            if (num % 2 == 1) {
                count++;
            }
            num /= 2;
        }
        std::cout << count << std::endl;
    }
    return 0;
}

字符串字典序排序

利用 vector 存储并调用 sort 进行排序，注意输入循环的处理。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    int n;
    while (std::cin >> n) {
        std::vector<std::string> vec;
        for (int i = 0; i < n; ++i) {
            std::string s;
            std::cin >> s;
            vec.push_back(s);
        }
        std::sort(vec.begin(), vec.end());
        for (const auto& s : vec) {
            std::cout << s << std::endl;
        }
    }
    return 0;
}

掌握这些基础算法模型，配合对边界条件的仔细检查，能有效提升机试通过率。