{"id":78,"date":"2026-03-29T15:15:24","date_gmt":"2026-03-29T07:15:24","guid":{"rendered":"https:\/\/geocommunity.vip\/?p=78"},"modified":"2026-03-29T15:15:24","modified_gmt":"2026-03-29T07:15:24","slug":"%e8%87%b3%e5%b0%91%e6%9c%89-k-%e4%b8%aa%e9%87%8d%e5%a4%8d%e5%ad%97%e7%ac%a6%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e4%b8%b2-dfs","status":"publish","type":"post","link":"https:\/\/geocommunity.vip\/index.php\/2026\/03\/29\/%e8%87%b3%e5%b0%91%e6%9c%89-k-%e4%b8%aa%e9%87%8d%e5%a4%8d%e5%ad%97%e7%ac%a6%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e4%b8%b2-dfs\/","title":{"rendered":"\u81f3\u5c11\u6709 K \u4e2a\u91cd\u590d\u5b57\u7b26\u7684\u6700\u957f\u5b50\u4e32-DFS"},"content":{"rendered":"\n

1\u3001\u9898\u76ee\u63cf\u8ff0<\/h3>\n\n\n\n

\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\u00a0s<\/code>\u00a0\u548c\u4e00\u4e2a\u6574\u6570\u00a0k<\/code>\u00a0\uff0c\u8bf7\u4f60\u627e\u51fa\u00a0s<\/code>\u00a0\u4e2d\u7684\u6700\u957f\u5b50\u4e32\uff0c\u00a0\u8981\u6c42\u8be5\u5b50\u4e32\u4e2d\u7684\u6bcf\u4e00\u5b57\u7b26\u51fa\u73b0\u6b21\u6570\u90fd\u4e0d\u5c11\u4e8e\u00a0k<\/code>\u00a0\u3002\u8fd4\u56de\u8fd9\u4e00\u5b50\u4e32\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n

2\u3001\u89e3\u9898\u601d\u8def<\/h3>\n\n\n\n

\uff081\uff09\u5206\u6cbb\u601d\u60f3 \u5bf9\u4e8e\u6bcf\u4e00\u5c42 \u627e\u5230\u7b2c\u4e00\u4e2a\u574f\u7684\u5b57\u7b26 \u7136\u540e\u8fdb\u884c\u5206\u5272 \u5c06\u5206\u5272\u540e\u7684\u5b57\u7b26\u4e32\u8fdb\u884c\u9012\u5f52 \u6ee1\u8db3\u60c5\u51b5\u5219\u6309\u7167\u6808\u7684\u7ed3\u6784\u8fd4\u56de\u7b54\u6848 \uff08\u9012\u5f52\u6df1\u5ea6\u5927\uff09<\/p>\n\n\n\n

\uff082\uff09\u5206\u6cbb\u601d\u60f3 \u5bf9\u4e8e\u6bcf\u4e00\u5c42 \u627e\u5230\u6240\u6709\u574f\u7684\u5b57\u7b26 \u7136\u540e\u8fdb\u884c\u5206\u5272 \u5c06\u5206\u5272\u540e\u7684\u5b57\u7b26\u4e32\u8fdb\u884c\u9012\u5f52 \u6ee1\u8db3\u60c5\u51b5\u5219\u6309\u7167\u6808\u7684\u7ed3\u6784\u8fd4\u56de\u7b54\u6848 \uff08\u9012\u5f52\u6df1\u5ea6\u5c0f\uff09<\/p>\n\n\n\n

\u9488\u5bf9\u601d\u8def\u4e00\uff0c\u5148\u7528strtok\u51fd\u6570\u8fdb\u884c\u5206\u5272\uff0c\u8d85\u65f6\uff0819 \/ 38\uff09\u540e\uff0c\u6539\u4e3a\u624b\u52a8\u5206\u5272\uff0c\u4f46\u4ecd\u7136\u8d85\u65f6\uff0833 \/ 38\u00a0\uff09\u3002<\/p>\n\n\n\n

\u9488\u5bf9\u601d\u8def\u4e8c\uff1a\u901a\u8fc7 38 \/ 38\u00a0\u4e2a\u901a\u8fc7\u7684\u6d4b\u8bd5\u7528\u4f8b\u3002<\/p>\n\n\n\n

3\u3001\u7b97\u6cd5<\/h3>\n\n\n\n

\uff081\uff09\u601d\u8def\u4e00\uff0cstrtok\u51fd\u6570\u8fdb\u884c\u5206\u5272<\/p>\n\n\n\n

#include <string.h>\n#define MAX(a, b) (a > b ? a : b)\n\nint longestSubstring(char* s, int k) {\n    \/\/ 1\u3001\u5b58\u50a8\u6240\u6709\u5b57\u7b26\u51fa\u73b0\u7684\u6b21\u6570\n    int flag[26] = {0};\n    int n = strlen(s);\n    \/\/ \u5feb\u901f\u526a\u679d\n    if (n < k) return 0;\n    for (int i = 0; i < n; i++) {\n        flag[s[i] - 'a']++;\n    }\n    \/\/ 2\u3001\u67e5\u627e\u7b2c\u4e00\u4e2a\u574f\u7684\u5b57\u7b26\uff08\u56e0\u4e3a\u4e0d\u65ad\u9012\u5f52 \u80fd\u904d\u5386\u5230\u6240\u6709\u60c5\u51b5 \u6240\u4ee5\u67e5\u627e\u7b2c\u4e00\u4e2a\u574f\u7684\u5b57\u7b26\u5373\u53ef\uff09\n    for (int i = 0; i < n; i++) {\n        if (flag[s[i] - 'a'] < k && flag[s[i] - 'a'] > 0) {\n            \/\/ 3\u3001\u9012\u5f52\u5e76\u66f4\u65b0\u7b54\u6848\n            char split_c = s[i];\n            int c_max_len = 0;\n            char t_s[n + 1]; \/\/\uff08\u5305\u62ec\\0\uff09\n            strcpy(t_s, s); \/\/\uff08\u907f\u514d\u4fee\u6539s\uff09\n            char* c_s = strtok(t_s, (char[]){split_c, '\\0'}); \/\/ \uff08\u5206\u5272\u7684\u7b2c\u4e00\u6bb5\uff09\n            while (c_s != NULL) {\n                c_max_len = MAX(c_max_len, longestSubstring(c_s, k));\n                c_s = strtok(NULL, (char[]){split_c, '\\0'}); \/\/ \uff08\u5206\u5272\u7684\u540e\u9762\u51e0\u6bb5\uff09\n            }\n            return c_max_len;\n        }\n    }\n    return n;\n}<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790\uff1a<\/p>\n\n\n\n
\u7406\u8bba\u590d\u6742\u5ea6\uff1aO(26 * N)   26\u662f\u6700\u5927\u7684\u9012\u5f52\u6df1\u5ea6<\/p>\n\n\n\n
\u989d\u5916\uff1aA. \u9891\u7e41\u7684 strlen<\/code>\uff1aO(N)    B. \u6570\u7ec4\u5185\u5b58\u5206\u914d\u4e0e\u62f7\u8d1d\uff1aO(N)  C. strtok<\/code> \u7684\u526f\u4f5c\u7528<\/p>\n\n\n\n
\uff082\uff09\u601d\u8def\u4e00\uff0c\u624b\u52a8\u8fdb\u884c\u5206\u5272<\/p>\n\n\n\n
#include <string.h>\n#define MAX(a, b) (a > b ? a : b)\n\n\nint helper(char* s, int start, int end, int k) {\n    if (end - start + 1 < k) return 0;\n    \/\/ 1. \u7edf\u8ba1\u5f53\u524d\u533a\u95f4\u5185\u5b57\u7b26\u9891\u6b21\n    int flag[26] = {0};\n    for (int i = start; i <= end; i++) {\n        flag[s[i] - 'a']++;\n    }\n    \/\/ 2. \u5bfb\u627e\u7b2c\u4e00\u4e2a\u574f\u5b57\u7b26\n    for (int i = start; i <= end; i++) {\n        if (flag[s[i] - 'a'] > 0 && flag[s[i] - 'a'] < k) {\n            int max_len = 0;\n            int next_start = start;\n            \/\/ 3. \u539f\u5730\u5207\u5206\uff1a\u8df3\u8fc7\u574f\u5b57\u7b26\uff0c\u9012\u5f52\u5904\u7406\u6bcf\u4e00\u6bb5\n            for (int j = start; j <= end; j++) {\n                if (s[j] == s[i]) { \/\/ \u53d1\u73b0\u5206\u5272\u70b9\n                    max_len = MAX(max_len, helper(s, next_start, j - 1, k));\n                    next_start = j + 1;\n                }\n            }\n            \/\/ \u4e0d\u8981\u5fd8\u8bb0\u5904\u7406\u6700\u540e\u4e00\u6bb5\n            max_len = MAX(max_len, helper(s, next_start, end, k));\n            return max_len;\n        }\n    }\n    \/\/ \u5982\u679c\u6ca1\u6709\u574f\u5b57\u7b26\uff0c\u6574\u4e2a\u533a\u95f4\u90fd\u5408\u683c\n    return end - start + 1;\n}\nint longestSubstring(char* s, int k) {\n    return helper(s, 0, strlen(s) - 1, k);\n}<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790\uff1a<\/p>\n\n\n\n
\u7406\u8bba\u590d\u6742\u5ea6\uff1aO(26 * N)  26\u662f\u6700\u5927\u7684\u9012\u5f52\u6df1\u5ea6<\/p>\n\n\n\n
\u624b\u52a8\u5206\u5272\u7528\u5230\u7d22\u5f15\uff0c\u4ea7\u751f\u7684\u989d\u5916\u65f6\u95f4\u590d\u6742\u5ea6\u5f88\u5c11\uff0c\u4f46\u662f\u4ecd\u7136\u6bcf\u6b21\u53ea\u627e\u7b2c\u4e00\u4e2a\u5207\u5206\u70b9\uff0c\u9012\u5f52\u6df1\u5ea6\u4ecd\u7136\u8f83\u5927\u3002<\/p>\n\n\n\n
\uff083\uff09\u601d\u8def\u4e8c<\/p>\n\n\n\n
#include <string.h>\n#define MAX(a, b) (a > b ? a : b)\n\nint helper(char* s, int start, int end, int k) {\n    \/\/ \u526a\u679d\n    if (end - start + 1 < k) return 0;\n\n    int flag[26] = {0};\n    for (int i = start; i <= end; i++) {\n        flag[s[i] - 'a']++;\n    }\n\n    \/\/ \u9012\u5f52\u51fa\u53e3\n    int i = start;\n    while (i <= end && flag[s[i] - 'a'] >= k) {\n        i++;\n    }\n    if (i > end) return end - start + 1;\n\n    \/\/ \u4ee5\u533a\u95f4\u5185\u6240\u6709\u201c\u574f\u5b57\u7b26\u201d\u4e3a\u754c\uff0c\u62c6\u5206\u51fa\u591a\u4e2a\u5b50\u6bb5\n    int max_len = 0;\n    int curr_start = start;\n    while (curr_start <= end) {\n        \/\/ 1. \u627es[start:end+1]\u4e2d\u8be5\u5b50\u6bb5\u7684\u8d77\u70b9\n        while (curr_start <= end && flag[s[curr_start] - 'a'] < k) {\n            curr_start++;\n        }\n        if (curr_start > end) break;\n        \n        \/\/ 2. \u627es[start:end+1]\u4e2d\u8be5\u5b50\u6bb5\u7684\u7ec8\u70b9\n        int curr_end = curr_start;\n        while (curr_end <= end && flag[s[curr_end] - 'a'] >= k) {\n            curr_end++;\n        }\n        \n        \/\/ 3. \u9012\u5f52\u8fd9\u4e00\u6bb5\n        max_len = MAX(max_len, helper(s, curr_start, curr_end - 1, k));\n        \/\/ 4.\u8bbe\u7f6es[start:end+1]\u4e2d\u4e0b\u4e00\u5b57\u6bb5\u53ef\u80fd\u7684\u8d77\u70b9\n        curr_start = curr_end;\n    }\n\n    return max_len;\n}\n\nint longestSubstring(char* s, int k) {\n    return helper(s, 0, strlen(s) - 1, k);\n}<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790\uff1a<\/p>\n\n\n\n
\u7406\u8bba\u590d\u6742\u5ea6\uff1aO(26 * N) 26\u662f\u6700\u5927\u7684\u9012\u5f52\u6df1\u5ea6 \u4f46\u57fa\u672c\u4e0d\u4f1a\u5230\u8fbe26 \u901a\u5e38\u53ea\u67092-5\u5c42 \u56e0\u4e3a\u5728\u6bcf\u4e00\u5c42\u5206\u5272\u4e86\u6240\u6709\u4e0d\u6ee1\u8db3\u60c5\u51b5\u5b57\u7b26<\/p>\n","protected":false},"excerpt":{"rendered":"
1\u3001\u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\u00a0s\u00a0\u548c\u4e00\u4e2a\u6574\u6570\u00a0k\u00a0 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-78","post","type-post","status-publish","format-standard","hentry","category-7"],"_links":{"self":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/78","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/comments?post=78"}],"version-history":[{"count":2,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/78\/revisions"}],"predecessor-version":[{"id":80,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/78\/revisions\/80"}],"wp:attachment":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/media?parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/categories?post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/tags?post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}