知识复习。。。。。。

郑雨飞130

44人浏览 · 2026-08-21 16:52:28

郑雨飞130 · 2026-08-21 16:52:28 发布

1.替换空格，把字符串空格替换为%20

void replaceSpace(char* s, char* result)
{
    int i = 0;
    int j = 0;

    while (s[i] != '\0') {

        if (s[i] == ' ') {
            result[j++] = '%';
            result[j++] = '2';
            result[j++] = '0';
        } else {
            result[j++] = s[i];
        }

        i++;
    }

    result[j] = '\0';
}

2.判断回文字符串，不调用库函数

int isPalindrome(char s[])
{
    // 先自己计算字符串长度
    int len = 0;

    while (s[len] != '\0') {
        len++;
    }

    // 双指针
    int left = 0;
    int right = len - 1;

    while (left < right) {

        // 两边字符不一样，不是回文
        if (s[left] != s[right]) {
            return 0;
        }

        left++;
        right--;
    }

    // 全部相同，是回文
    return 1;
}

3.无重复字符最长子串长度

int lengthOfLongestSubstring(char* s)
{
    int maxLen = 0;

    // 字符集假设为 ASCII
    int count[256] = {0};

    int left = 0;
    int right = 0;

    while (s[right] != '\0') {

        // 当前字符出现次数 +1
        count[(unsigned char)s[right]]++;

        // 如果出现重复字符
        while (count[(unsigned char)s[right]] > 1) {
            count[(unsigned char)s[left]]--;
            left++;
        }

        // 当前窗口长度
        int len = right - left + 1;

        if (len > maxLen) {
            maxLen = len;
        }

        right++;
    }

    return maxLen;
}

4.字符串相加，两个数字字符串做加法，不能转 int

char* addStrings(char* num1, char* num2)
{
    int len1 = strlen(num1);
    int len2 = strlen(num2);

    int maxLen = len1 > len2 ? len1 : len2;

    // 最多 maxLen + 1 位
    char* result = malloc(maxLen + 2);

    int i = len1 - 1;
    int j = len2 - 1;
    int k = maxLen;
    int carry = 0;

    result[k + 1] = '\0';

    while (i >= 0 || j >= 0 || carry) {

        int a = 0;
        int b = 0;

        if (i >= 0) {
            a = num1[i] - '0';
            i--;
        }

        if (j >= 0) {
            b = num2[j] - '0';
            j--;
        }

        int sum = a + b + carry;

        result[k] = (sum % 10) + '0';

        carry = sum / 10;

        k--;
    }

    // 如果最高位没有进位
    // k 可能停在 maxLen - 1
    return result + k + 1;
}

int value(char c)
{
    switch (c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
    }

    return 0;
}

int romanToInt(char* s)
{
    int ans = 0;

    for (int i = 0; s[i] != '\0'; i++) {

        int cur = value(s[i]);
        int next = value(s[i + 1]);

        // 当前数字比后面小，减
        if (cur < next) {
            ans -= cur;
        }
        // 否则加
        else {
            ans += cur;
        }
    }

    return ans;
}

6.KMP，求子串第一次在主串出现下标

void getNext(char* needle, int* next)
{
    int j = 0;

    next[0] = 0;

    for (int i = 1; needle[i] != '\0'; i++) {

        // 不匹配，j 往前跳
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];
        }

        // 匹配成功
        if (needle[i] == needle[j]) {
            j++;
        }

        next[i] = j;
    }
}

// KMP 查找子串第一次出现的位置
int strStr(char* haystack, char* needle)
{
    if (needle[0] == '\0') {
        return 0;
    }

    int n = strlen(needle);

    int* next = malloc(sizeof(int) * n);

    // 构造 next 数组
    getNext(needle, next);

    int j = 0;

    for (int i = 0; haystack[i] != '\0'; i++) {

        // 不匹配，j 根据 next 数组跳转
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }

        // 匹配
        if (haystack[i] == needle[j]) {
            j++;
        }

        // 子串全部匹配
        if (j == n) {
            free(next);

            // 当前 i 是子串最后一个字符
            // 所以起始位置是：
            return i - n + 1;
        }
    }

    free(next);

    return -1;
}

7.词频统计，统计单词在字符串数组出现次数

void getNext(char* needle, int* next)
{
    int j = 0;

    next[0] = 0;

    for (int i = 1; needle[i] != '\0'; i++) {

        // 不匹配，j 往前跳
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];
        }

        // 匹配成功
        if (needle[i] == needle[j]) {
            j++;
        }

        next[i] = j;
    }
}

// KMP 查找子串第一次出现的位置
int strStr(char* haystack, char* needle)
{
    if (needle[0] == '\0') {
        return 0;
    }

    int n = strlen(needle);

    int* next = malloc(sizeof(int) * n);

    // 构造 next 数组
    getNext(needle, next);

    int j = 0;

    for (int i = 0; haystack[i] != '\0'; i++) {

        // 不匹配，j 根据 next 数组跳转
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }

        // 匹配
        if (haystack[i] == needle[j]) {
            j++;
        }

        // 子串全部匹配
        if (j == n) {
            free(next);

            // 当前 i 是子串最后一个字符
            // 所以起始位置是：
            return i - n + 1;
        }
    }

    free(next);

    return -1;
}

8.字符串，把所有数字 * 2 输出（a12d3→a24d6）

int main()
{
    char s[] = "a12d3";

    int i = 0;

    while (s[i] != '\0') {

        // 判断是不是数字
        if (s[i] >= '0' && s[i] <= '9') {

            int num = 0;

            // 连续读取整个数字
            while (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + (s[i] - '0');
                i++;
            }

            // 数字乘 2
            num *= 2;

            printf("%d", num);

        } else {

            // 普通字符直接输出
            printf("%c", s[i]);

            i++;
        }
    }

    return 0;
}

9.最长公共子序列 LCS

int LCS(char *s1, char *s2)
{
    int n = strlen(s1);
    int m = strlen(s2);

    // dp[0][j] dp[i][0] 已经是0，全局数组默认0
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }
    return dp[n][m];
}