{"id":5414,"date":"2024-09-16T08:01:03","date_gmt":"2024-09-16T00:01:03","guid":{"rendered":""},"modified":"2024-09-16T08:01:03","modified_gmt":"2024-09-16T00:01:03","slug":"\u7b97\u6cd5\u9898\u6ed1\u52a8\u7a97\u53e3_LeetCode\u5237\u9898\u624b\u518c","status":"publish","type":"post","link":"https:\/\/mushiming.com\/5414.html","title":{"rendered":"\u7b97\u6cd5\u9898\u6ed1\u52a8\u7a97\u53e3_LeetCode\u5237\u9898\u624b\u518c"},"content":{"rendered":"

\u6ed1\u52a8\u7a97\u53e3\u4e09\u6b65\u8d70\uff1a<\/h3>\n

\u7b2c\u4e00\u6b65<\/strong>\u786e\u5b9a\u5c3e\u6307\u9488++\u7684\u6761\u4ef6\uff0c\u5f80\u53f3\u6269\u5f20\uff1b\u7b2c\u4e8c\u6b65<\/strong>\u786e\u5b9a\u5934\u6307\u9488++\u7684\u6761\u4ef6\uff0c\u5f80\u53f3\u6536\u7f29\uff0c\u7b2c\u4e09\u6b65<\/strong>\u66f4\u65b0\u6240\u6c42\u76ee\u6807\u503c\uff08\u4e00\u822c\u90fd\u662f\u6781\u503c\uff09<\/p>\n

\u6ed1\u52a8\u7a97\u53e3\u4f2a\u4ee3\u7801<\/strong>\uff1a<\/p>\n

start = 0 end = 0 \/\/\u521d\u59cb\u5316 while\uff08\u6269\u5f20\u6761\u4ef6\uff09 { while\uff08\u6536\u7f29\u6761\u4ef6\uff09 { FindTarget\uff08\uff09\/\/\u6536\u7f29\u65f6\u4e00\u822c\u6c42\u6781\u5c0f\u503c start++\/\/\u6536\u7f29\uff0c\u6709\u53ef\u80fd\u662f++\uff0c\u4e5f\u6709\u53ef\u80fd\u662f\u8df3\u8dc3\u5f0f\u79fb\u52a8 } FindTarget\uff08\uff09\/\/\u6269\u5f20\u65f6\u4e00\u822c\u6c42\u6781\u5927\u503c end++\/\/\u6269\u5f20\uff0c\u4e00\u822c\u90fd\u662f++ } if\uff08\u4e00\u6b21\u90fd\u6ca1\u8fdb\u5165\u8fc7\u6536\u7f29\u6761\u4ef6\uff09 { \u7279\u6b8a\u5904\u7406\u4e00\u4e0b }<\/code><\/pre>\n
\u76ee\u524d\u6765\u770b\uff0c\u6ed1\u52a8\u7a97\u53e3\u4e3b\u8981\u6709\u4e24\u79cd\u9898\u578b\uff0c\u4e00\u79cd\u662f\u627e\u6700\u957f\/\u6700\u77ed\u5b50\u6570\u7ec4\uff0c\u8fd9\u79cd\u4f7f\u7528\u4e0a\u8ff0\u7684\u4e09\u6b65\u8d70\u7b56\u7565\u3002\u53e6\u4e00\u79cd\u662f\u56fa\u5b9a\u957f\u5ea6\u7684\u7a97\u53e3\u5185\u7684\u6781\u503c\uff0c\u6b64\u65f6\u9700\u8981\u501f\u52a9\u5355\u8c03\u961f\u5217<\/span><\/strong><\/p>\n<\/p>\n
\u9898\u76ee\u4e00\uff1a209. \u957f\u5ea6\u6700\u5c0f\u7684\u5b50\u6570\u7ec4<\/h4>\n
\u7ed9\u5b9a\u4e00\u4e2a\u542b\u6709 n \u4e2a\u6b63\u6574\u6570\u7684\u6570\u7ec4\u548c\u4e00\u4e2a\u6b63\u6574\u6570 target \u3002<\/p>\n
\u627e\u51fa\u8be5\u6570\u7ec4\u4e2d\u6ee1\u8db3\u5176\u548c \u2265 target \u7684\u957f\u5ea6\u6700\u5c0f\u7684 \u8fde\u7eed\u5b50\u6570\u7ec4 [numsl, numsl+1, ..., numsr-1, numsr] \uff0c\u5e76\u8fd4\u56de\u5176\u957f\u5ea6\u3002\u5982\u679c\u4e0d\u5b58\u5728\u7b26\u5408\u6761\u4ef6\u7684\u5b50\u6570\u7ec4\uff0c\u8fd4\u56de 0 \u3002<\/p>\n<\/p>\n
\u793a\u4f8b 1\uff1a<\/p>\n
\u8f93\u5165\uff1atarget = 7, nums = [2,3,1,2,4,3]
 \u8f93\u51fa\uff1a2
 \u89e3\u91ca\uff1a\u5b50\u6570\u7ec4 [4,3] \u662f\u8be5\u6761\u4ef6\u4e0b\u7684\u957f\u5ea6\u6700\u5c0f\u7684\u5b50\u6570\u7ec4\u3002<\/p>\n<\/p>\n
\u601d\u8def\uff1a<\/p>\n
for\uff08\u904d\u5386\u6574\u4e2a\u5b57\u7b26\u4e32\uff09 { for\uff08\u548c\u503c\u5927\u4e8etarget\uff09 { \u8ba1\u7b97\u4e00\u6b21\u6700\u77ed\u957f\u5ea6 \u5934\u6307\u9488\u53f3\u79fb\u6536\u7f29 } \u5c3e\u6307\u9488\u53f3\u79fb\u6269\u5f20 } \u6ca1\u6536\u7f29\u8fc7\u9700\u8981\u7279\u6b8a\u5904\u7406<\/code><\/pre>\n
\u4ee3\u7801\uff1a<\/p>\n
int minSubArrayLen(int target, int* nums, int numsSize) { int start = 0, end = 0; int sum = 0, minlen = INT_MAX, tmp = 0; while (end < numsSize) { sum += nums[end]; while (sum >= target) { tmp = end - start + 1; if (minlen > tmp) { minlen = tmp; } sum -= nums[start]; start++; } end++; } return minlen == INT_MAX ? 0 : minlen; }<\/code><\/pre>\n<\/p>\n
\u9898\u76ee\u4e8c\uff1a3. \u65e0\u91cd\u590d\u5b57\u7b26\u7684\u6700\u957f\u5b50\u4e32<\/h4>\n
\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32 s \uff0c\u8bf7\u4f60\u627e\u51fa\u5176\u4e2d\u4e0d\u542b\u6709\u91cd\u590d\u5b57\u7b26\u7684 \u6700\u957f\u5b50\u4e32 \u7684\u957f\u5ea6\u3002<\/p>\n<\/p>\n
\u793a\u4f8b 1:<\/p>\n
\u8f93\u5165: s = \"abcabcbb\"
 \u8f93\u51fa: 3 
 \u89e3\u91ca: \u56e0\u4e3a\u65e0\u91cd\u590d\u5b57\u7b26\u7684\u6700\u957f\u5b50\u4e32\u662f \"abc\"\uff0c\u6240\u4ee5\u5176\u957f\u5ea6\u4e3a 3\u3002<\/p>\n<\/p>\n
\u601d\u8def\uff1a<\/p>\n
for\uff08\u904d\u5386\u5b57\u7b26\u4e32\uff09 { for\uff08\u51fa\u73b0\u4e86\u91cd\u590d\u5b57\u7b26\uff09 { \u5934\u6307\u9488\u53f3\u79fb\u5167\u7f29\uff0c\u53f3\u79fb\u5230\u91cd\u590d\u5b57\u7b26\u540e\u9762\u4e00\u4f4d\u7684\u5730\u65b9\uff0c\u4fdd\u8bc1\u65b0\u7684\u4e32\u53e3\u5185\u6ca1\u6709\u91cd\u590d\u5b57\u7b26 } \u5c3e\u6307\u9488\u53f3\u79fb\u6269\u5f20 \u6bcf\u6b21\u6269\u5f20\u8ba1\u7b97\u4e00\u6b21\u6700\u5927\u8ddd\u79bb }<\/code><\/pre>\n<\/p>\n
\u4ee3\u7801\uff1a<\/p>\n
int lengthOfLongestSubstring(char * s){ int start = 0, end = 0, len = 0, output = 0; int chs[128] = {0}; if (0 == strlen(s) || NULL == s) { return 0; } for (end = 0; s[end] != '\\0'; end++) { \/\/\u96be\u70b91\uff1achs[s[end]]\u5185\u4fdd\u5b58\u7684\u662f\u76ee\u6807\u5b57\u7b26\u6700\u8fd1\u4e00\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\uff0c\u65b9\u4fbf\u5934\u6307\u9488\u53f3\u79fb\u627e\u4f4d\u7f6e if (chs[s[end]] > start) { \/\/\u96be\u70b91\u76f8\u5173\u5904\u7406 start = chs[s[end]]; \/\/\u76ee\u6807\u662f\u6c42\u6700\u957f\u8ddd\u79bb\uff0c\u5b83\u66f4\u53ef\u80fd\u51fa\u73b0\u5728\u6269\u5f20\u7684\u8fc7\u7a0b\u4e2d \/\/\u672c\u9898\u6536\u7f29\u65f6\u8ba1\u7b97\u548c\u6269\u5f20\u65f6\u8ba1\u7b97\u5b8c\u5168\u91cd\u590d\uff0c\u5219\u53ef\u4ee5\u7701\u7565 \/\/len = end - start + 1; \/\/output = output < len ? len : output; } \/\/\u96be\u70b91\u76f8\u5173\u5904\u7406 chs[s[end]] = end + 1; len = end - start + 1; output = output < len ? len : output; } return output; }<\/code><\/pre>\n<\/p>\n
\u9898\u76ee\u4e09\uff1a76. \u6700\u5c0f\u8986\u76d6\u5b50\u4e32<\/h4>\n
\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s \u3001\u4e00\u4e2a\u5b57\u7b26\u4e32 t \u3002\u8fd4\u56de s \u4e2d\u6db5\u76d6 t \u6240\u6709\u5b57\u7b26\u7684\u6700\u5c0f\u5b50\u4e32\u3002\u5982\u679c s \u4e2d\u4e0d\u5b58\u5728\u6db5\u76d6 t \u6240\u6709\u5b57\u7b26\u7684\u5b50\u4e32\uff0c\u5219\u8fd4\u56de\u7a7a\u5b57\u7b26\u4e32 \"\" \u3002
  <\/p>\n
\u793a\u4f8b 1\uff1a<\/p>\n
\u8f93\u5165\uff1as = \"ADOBECODEBANC\", t = \"ABC\"
 \u8f93\u51fa\uff1a\"BANC\"<\/p>\n<\/p>\n
\u601d\u8def\uff1a<\/p>\n
for\uff08\u904d\u5386\u6574\u4e2a\u5b57\u7b26\u4e32\uff09 { for\uff08s\u4e2d\u51fa\u73b0\u4e86t\u4e2d\u7684\u6240\u6709\u5143\u7d20\uff09 { \u8ba1\u7b97\u6700\u5c0f\u8986\u76d6\u957f\u5ea6 \u5934\u6307\u9488\u53f3\u79fb\u6536\u7f29 } \u5c3e\u6307\u9488\u53f3\u79fb\u6269\u5f20 }<\/code><\/pre>\n<\/p>\n
\u4ee3\u7801\uff1a<\/p>\n
char * minWindow(char * s, char * t){ int start = 0, end = 0; int slen = strlen(s); int tlen = strlen(t); int chst[128] = {0}; int minlen = INT_MAX, minlenindex; int tmplen; \/\/\u7edf\u8ba1t\u4e2d\u6240\u6709\u5b57\u7b26\u51fa\u73b0\u7684\u6b21\u6570 for (end = 0; end < tlen; end++) { chst[t[end]]++; } end = 0; while (end < slen) { if (chst[s[end]] > 0) { \/\/\u6b64\u65f6tlen\u7684\u5927\u5c0f\u4ee3\u8868s\u5df2\u7ecf\u51fa\u73b0\u4e86(strlen(t) - tlen)\u4e2at\u4e2d\u7684\u5143\u7d20 tlen--; } \/\/chst[i]\u4e3a\u6b63\uff0c\u4ee3\u8868s\u4e2d\u8fd8\u9700\u51fa\u73b0chst[i]\u6b21\u5b57\u7b26i\uff0c\u624d\u4f1a\u4f7fs\u4e0et\u4e2d\u51fa\u73b0i\u7684\u6b21\u6570\u76f8\u540c \/\/chst[i]\u4e3a\u8d1f\uff0c\u4ee3\u8868\u5b57\u7b26i\u53ea\u5728s\u4e2d\u51fa\u73b0 chst[s[end]]--; \/\/\u96be\u70b9\uff1atlen==0 \u65f6\u4ee3\u8868s\u4e2d\u5df2\u7ecf\u51fa\u73b0\u4e86t\u4e2d\u6240\u6709\u7684\u5143\u7d20\uff08\u5305\u62ec\u91cd\u590d\u7684\u5143\u7d20\uff09 \/\/\u540c\u65f6\uff0c\u4e5f\u4f5c\u4e3a\u5934\u6307\u9488\u6536\u7f29\u7684\u6761\u4ef6 while (0 == tlen) { \/\/\u66f4\u65b0\u6700\u5c0f\u8986\u76d6\u8ddd\u79bb tmplen = end - start + 1; if (minlen > tmplen) { minlen = tmplen; minlenindex = start; } chst[s[start]]++; if (chst[s[start]] > 0) { \/\/\u4ee3\u8868\u6536\u7f29\u540e\u7684\u7a97\u53e3\u4e0d\u6ee1\u8db3\u6761\u4ef6\u4e86\uff0c\u9700\u8981\u6269\u5f20 tlen++; } start++; } end++; } \/\/\u6536\u7f29\u8fc7\u81f3\u5c11\u4e00\u6b21 if(minlen != INT_MAX) { char* t = (char*)malloc(sizeof(char)*(minlen+1)); *t = '\\0'; strncat(t, s+minlenindex, minlen); return t; } \/\/\u4e00\u6b21\u90fd\u6ca1\u6536\u7f29\u8fc7 return \"\"; }<\/code><\/pre>\n<\/p>\n
\u9898\u76ee\u56db\uff1a239. \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c<\/h4>\n
\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 nums\uff0c\u6709\u4e00\u4e2a\u5927\u5c0f\u4e3a k \u7684\u6ed1\u52a8\u7a97\u53e3\u4ece\u6570\u7ec4\u7684\u6700\u5de6\u4fa7\u79fb\u52a8\u5230\u6570\u7ec4\u7684\u6700\u53f3\u4fa7\u3002\u4f60\u53ea\u53ef\u4ee5\u770b\u5230\u5728\u6ed1\u52a8\u7a97\u53e3\u5185\u7684 k \u4e2a\u6570\u5b57\u3002\u6ed1\u52a8\u7a97\u53e3\u6bcf\u6b21\u53ea\u5411\u53f3\u79fb\u52a8\u4e00\u4f4d\u3002<\/p>\n
\u8fd4\u56de \u6ed1\u52a8\u7a97\u53e3\u4e2d\u7684\u6700\u5927\u503c \u3002<\/p>\n<\/p>\n
\u793a\u4f8b 1\uff1a<\/p>\n
\u8f93\u5165\uff1anums = [1,3,-1,-3,5,3,6,7], k = 3
 \u8f93\u51fa\uff1a[3,3,5,5,6,7]<\/p>\n<\/p>\n
\u601d\u8def\uff1a\u6ed1\u52a8\u7a97\u53e3\u627e\u6781\u503c\uff0c\u91c7\u7528\u5355\u8c03\u961f\u5217\u601d\u60f3<\/p>\n
\/\/\u7531\u4e8e\u7a97\u53e3\u957f\u5ea6\u88ab\u56fa\u5b9a\u4e86\uff0c\u6240\u4ee5\u6ca1\u6709\u52a8\u6001\u7684\u6536\u7f29\u6269\u5f20\u8fc7\u7a0b for\uff08\u7ef4\u62a4\u6ed1\u52a8\u7a97\u53e3\u7684\u79fb\u52a8\uff0c\u76f4\u5230\u904d\u5386\u7ed3\u675f\uff09 { \u7ef4\u62a4\u4e00\u4e2a\u5355\u8c03\u961f\u5217\uff0c\u4fdd\u8bc1\u961f\u5934\u6307\u9488\u6307\u5411\u7684\u5143\u7d20\u4e00\u5b9a\u662f\u7a97\u53e3\u5185\u7684\u6700\u5927\u503c\uff0c\u4e14\u6574\u4e2a\u961f\u5217\u4fdd\u6301\u4ece\u5de6\u5230\u53f3\u5355\u8c03\u9012\u51cf \u5bf9\u4e8e\u6bcf\u4e00\u6b21\u7a97\u53e3\u5411\u524d\u79fb\u52a8\uff0c\u5bf9\u5e94\u5220\u9664\u4e00\u4e2a\u65e7\u5143\u7d20,\u589e\u52a0\u4e00\u4e2a\u65b0\u7684\u5143\u7d20(\u5fc5\u987b\u5148\u5224\u65ad\u51fa\u961f\uff0c\u518d\u5224\u65ad\u5165\u961f) \u6bcf\u79fb\u52a8\u4e00\u6b21\u5c31\u628a\u961f\u5934\u5143\u7d20\u8f93\u51fa\u4e00\u6b21 } \/\/\u96be\u70b91\uff1a\u5224\u65ad\u51fa\u961f\u7684\u5143\u7d20\u662f\u4e0d\u662f\u961f\u5934\u5143\u7d20 \/\/\u96be\u70b92\uff1a\u961f\u5934\u5143\u7d20\u51fa\u961f\u540e\u5982\u4f55\u4f7f\u961f\u5934\u6307\u9488\u6307\u5411\u65b0\u7684\u961f\u5934 \/\/\u96be\u70b93\uff1a\u5165\u961f\u7684\u5143\u7d20\u627e\u5230\u4f4d\u7f6e\u540e\u76f4\u63a5\u8986\u76d6\u65e7\u5143\u7d20\uff0c\u53ef\u4ee5\u7701\u7565\u6570\u7ec4\u63d2\u5165\u65b0\u5143\u7d20\u7684\u8fc7\u7a0b<\/code><\/pre>\n<\/p>\n
\u4ee3\u7801\uff1a<\/p>\n
typedef struct Queue { int head; int tail; int * data; }MyQueue; int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) { int* output = malloc(sizeof(int) * numsSize); MyQueue q; int i, j = 0; q.head = 0; q.tail = 0; q.data = malloc(sizeof(int) * numsSize); *returnSize = 0; for (i = 0; i < numsSize; i++) { \/\/data\u5185\u5b58\u7684\u662f\u6570\u7ec4\u4e0b\u6807\uff0c\u800c\u975e\u6570\u7ec4\u5143\u7d20\uff0c\u76ee\u7684\u662f\u65b9\u4fbf\u961f\u5934\u5143\u7d20\u51fa\u961f\u540e\uff0c\u961f\u5934\u6307\u9488head\u5bb9\u6613\u627e\u5230\u4e0b\u4e00\u4e2a\u961f\u5934 \/\/data[head]\u5904\u4e8e\u7a97\u53e3\u5916\u4e86\uff08\u88ab\u51fa\u961f\u4e86\uff09\uff0c\u66f4\u65b0\u961f\u5934\u6307\u9488 if (q.data[q.head] <= i - k && q.head < q.tail) { q.head++; \/\/ \u51fa\u961f\u540e\u7684\u4e0b\u4e00\u4e2a\u5143\u7d20\u5c31\u662f\u6700\u5927\u7684 } \/\/\u7ed9\u65b0\u5165\u961f\u7684\u5143\u7d20\u627e\u5728\u5355\u8c03\u961f\u5217\u4e2d\u7684\u4f4d\u7f6e\uff08\u5728\u961f\u5c3e\u6307\u9488\u6307\u5411\u7684\u4f4d\u7f6e\u76f4\u63a5\u8986\u76d6\uff09 for (j = q.tail; j > q.head; j--) { if (nums[q.data[j - 1]] < nums[i]) { q.tail--; } \/\/\u8fd9\u91cc\u7528for\u5faa\u73af\u4f1a\u8d85\u65f6\u7684\u539f\u56e0 \/\/1. \u591a\u7ed9j\u8fdb\u884c\u4e86++\u64cd\u4f5c \/\/2. \u5982\u679c\u4e0d\u52a0beark\uff0c\u6bcf\u6b21\u4f1a\u8fdb\u884c\u591a\u4f59\u7684\u5faa\u73af else { break; } } #if 0 if (q.tail > q.head) { while (q.tail > q.head && nums[q.data[q.tail - 1]] < nums[i]) { q.tail--; } } #endif q.data[q.tail++] = i; \/\/\u524dk\u4e2a\u5143\u7d20\u4e0d\u8f93\u51fa\uff08\u7b49\u5f85\u7a97\u53e3\u6210\u578b\uff09 if (i >= k - 1) { output[(*returnSize)++] = nums[q.data[q.head]]; } } return output; }<\/code><\/pre><\/p>\n","protected":false},"excerpt":{"rendered":"\u7b97\u6cd5\u9898\u6ed1\u52a8\u7a97\u53e3_LeetCode\u5237\u9898\u624b\u518c\u6ed1\u52a8\u7a97\u53e3\u4e09\u6b65\u8d70\uff1a\u7b2c\u4e00\u6b65\u786e\u5b9a\u5c3e\u6307\u9488++\u7684\u6761\u4ef6\uff0c\u5f80\u53f3\u6269\u5f20\uff1b\u7b2c\u4e8c\u6b65\u786e\u5b9a\u5934\u6307\u9488++\u7684\u6761\u4ef6\uff0c\u5f80\u53f3\u6536\u7f29...","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/5414"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=5414"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/5414\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=5414"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=5414"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=5414"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}