\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c<\/h3>\n\u6709\u4e00\u4e2a\u6570\u7ec4\uff0c\u59821\uff0c \uff0d5\uff0c 8\uff0c 3\uff0c \uff0d4\uff0c 15\uff0c \uff0d8\uff0c\u67e5\u627e\u5176\u4e2d\u8fde\u7eed\u548c\u6700\u5927\u7684\u76f8\u90bb\u4e32\u7684\u503c\u3002\n\u5728\u672c\u4f8b\u4e2d\uff0c\u6700\u5927\u503c\u4e3a8 \uff0b 3 \uff0b \uff0d4 \uff0b 15 \uff1d 22\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[i]\u8868\u793a\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[i] = max{ dp[i-1] + arc[i] , arc[i] }\uff0c\u5373\uff0c\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\uff0c\u8981\u4e48\u662f\u7ee7\u7eed\u7d2f\u52a0\uff0c\u8981\u4e48\u5c31\u662f\u5143\u7d20\u672c\u8eab\uff08\u91cd\u65b0\u5f00\u59cb\u4e00\u8f6e\u7d2f\u52a0\uff09\u3002\u6700\u7ec8\u7684\u6700\u5927\u503c\u662fdp\u6570\u7ec4\u4e2d\u7684\u6700\u5927\u503c\u3002\uff08\u53ef\u4ee5\u7d2f\u52a0\u4e00\u4e2a\u8d1f\u6570\uff0c\u4f46\u4e0d\u80fd\u5728\u8d1f\u6570\u4e0a\u7d2f\u52a0\uff09<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1adp[0] = arc[0] \u3002<\/p>\nint max_successive_sub_serial_sum(int* numbers, int size)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[size];\ndp[0] = numbers[0];\nint max_sum = dp[0];\n\/\/\u63a8\u7b97\nfor(int i=1;i<size;i++)\n{\n dp[i] = std::max( dp[i-1] + numbers[i] , numbers[i] );\n max_sum = dp[i]>max_sum ? dp[i] : max_sum;\n}\n\ndelete[] dp;\nreturn max_sum;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u7ef4\u62a4\u524d\u540e\u4e24\u4e2a\u5e8f\u5217\u548c<\/p>\n
int max_successive_sub_serial_sum_space(int* numbers, int size)\n{ \n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint last_sum = numbers[0];\nint max_sum = last_sum;\n\/\/\u63a8\u7b97\nfor(int i=1;i<size;i++)\n{\n int cur_sum = std::max( last_sum + numbers[i] , numbers[i] );\n max_sum = cur_sum>max_sum ? cur_sum : max_sum;\n last_sum = cur_sum;\n}\n\nreturn max_sum;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u4e8c\u7ef4\u7f51\u683c\u4e0e\u8def\u5f84<\/h3>\n\u4e00\u4e2a m x n \u7684\u4e8c\u7ef4\u7f51\u683c\uff0c\u4ece\u5de6\u4e0a\u89d2\u79fb\u52a8\u5230\u53f3\u4e0b\u89d2\uff0c\u4e00\u5171\u591a\u5c11\u79cd\u8def\u5f84\uff0c\u6bcf\u6b21\u53ea\u80fd\u5411\u53f3\u6216\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[ i ][ j ] \u662f\u5230\u8fbe\u7b2c i \u884c\u7b2c j \u5217\u7684\u8def\u5f84\u603b\u6570\uff0ci \u548c j \u4ece0\u5f00\u59cb\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[ i ][ j ] = dp[ i – 1 ][ j ] + dp[ i ][ j – 1 ]\uff0c\u5373\u8fd9\u4e00\u70b9\u53ef\u4ee5\u7531\u4e0a\u9762\u7f51\u683c\u548c\u5de6\u4fa7\u7f51\u683c\u62b5\u8fbe\uff0c\u8def\u5f84\u603b\u6570\u4e3a\u4e24\u8def\u4e4b\u548c<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1adp[ 0 ][ 0 ] … dp[ 0 ][ n-1 ] = 1\uff0cdp[ 0 ] … dp[ 0 ][ m-1 ][ 0 ] = 1\uff0c\u6700\u5de6\u4fa7\u548c\u6700\u4e0a\u9762\u7684\u7f51\u683c\u90fd\u53ea\u6709\u4e00\u6761\u8def\u5f84\u3002<\/p>\nint unique_path(int rows, int cols)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint** dp = new int*[rows];\nfor(int i=0;i<rows;i++)\n{\n dp[i] = new int[cols];\n memset(dp[i],0,cols); \/\/memset\u662f\u9010\u5b57\u8282\u521d\u59cb\u5316\uff0c\u56e0\u6b64\u53ea\u67090\u548c-1\u662f\u6b63\u5e38\u521d\u59cb\u5316\n} \n\nfor(int i=0;i<cols;i++)\n dp[0][i]=1;\n\nfor(int i=0;i<rows;i++)\n dp[i][0]=1;\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[i][j] = dp[i-1][j] + dp[i][j-1];\n\/\/\u8f93\u51fa \nint sum = dp[rows-1][cols-1];\n\nfor(int i=0;i<rows;i++)\n delete[] dp[i];\ndelete[] dp;\n\nreturn sum;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u4fdd\u5b58\u4e00\u884c\u7684\u8bb0\u5f55\uff0c\u7136\u540e\u4e0d\u65ad\u8fed\u4ee3<\/p>\n
int unique_path_space(int rows, int cols)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[cols];\nfor(int i=0;i<cols;i++)\n dp[i] = 1;\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[j] = dp[j] + dp[j-1];\n\/\/\u8f93\u51fa \nint sum = dp[cols-1];\n\ndelete[] dp;\n\nreturn sum;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u4e8c\u7ef4\u7f51\u683c\u4e0e\u8def\u5f842 \u6700\u77ed\u8def\u5f84<\/h3>\n\u4e00\u4e2a m x n \u7684\u4e8c\u7ef4\u7f51\u683c\uff0c\u4ece\u5de6\u4e0a\u89d2\u79fb\u52a8\u5230\u53f3\u4e0b\u89d2\uff0c\u6c42\u6700\u77ed\u8def\u5f84\u957f\u5ea6\uff0c\u6bcf\u6b21\u53ea\u80fd\u5411\u53f3\u6216\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[ i ][ j ] \u4e3a\u5230\u8fbe\u7b2c i \u884c\u7b2c j \u5217\u7684\u6700\u77ed\u8def\u5f84\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[ i ][ j ] = min{ dp[ i – 1 ][ j ] + arc[ i ][ j ] , dp[ i ][ j-1 ] + arc[ i ][ j ] }\u3002<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1a
\ndp[ 0 ][ 0 ] = arc[ 0 ][ 0 ]
\ndp[ 0 ][ j ] = dp[ 0 ][ j – 1 ] + arc[ 0 ][ j ]
\ndp[ i ][ 0 ] = dp[ i – 1 ][ 0 ] + arc[ i ][ 0 ]<\/p>\nint unique_path_shortest(int** map, int rows, int cols )\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint** dp = new int*[rows];\nfor(int i=0;i<rows;i++)\n{\n dp[i] = new int[cols];\n memset(dp[i],0,cols); \n}\n\ndp[0][0] = map[0][0]; \nfor(int i=1;i<cols;i++)\n dp[0][i] = dp[0][i-1] + map[0][i];\nfor(int i=1;i<rows;i++)\n dp[i][0] = dp[i-1][0] + map[i][0];\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[i][j] = std::min(dp[i-1][j] + map[i][j] , dp[i][j-1] + map[i][j]);\n\/\/\u8f93\u51fa\nint sum_shortest = dp[rows-1][cols-1];\n\nfor(int i=0;i<rows;i++)\n delete[] dp[i];\ndelete[] dp;\n\nreturn sum_shortest;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u4fdd\u5b58\u4e00\u884c\u7684\u8bb0\u5f55\uff0c\u7136\u540e\u4e0d\u65ad\u8fed\u4ee3<\/p>\n
int unique_path_shortest_space(int** map, int rows, int cols )\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[cols];\ndp[0] = map[0][0]; \nfor(int i=1;i<cols;i++)\n dp[i] = dp[i-1] + map[0][i];\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n{\n dp[0] = dp[0] + map[i][0];\n for(int j=1;j<cols;j++)\n dp[j] = std::min(dp[j] + map[i][j] , dp[j-1] + map[i][j]);\n}\n\/\/\u8f93\u51fa\nint sum_shortest = dp[cols-1];\n\ndelete[] dp;\n\nreturn sum_shortest;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\uff08LIS\uff09<\/h3>\n
\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\uff08LIS\uff09<\/a><\/p>\n2\u3001\u6392\u5e8f<\/h2>\n
\n\n\n\u6392\u5e8f<\/th>\n \u63d2\u5165\u6392\u5e8f<\/th>\n \u5192\u6ce1\u6392\u5e8f<\/th>\n \u5f52\u5e76\u6392\u5e8f<\/th>\n \u5feb\u901f\u6392\u5e8f<\/th>\n<\/tr>\n<\/thead>\n \n\n\u57fa\u672c\u601d\u60f3<\/td>\n \u81ea\u7b2c\u4e8c\u4e2a\u8bb0\u5f55\u5f00\u59cb\uff0c\u6709\u5e8f\u524d\u63d2<\/td>\n \u76f8\u90bb\u5143\u7d20\u6bd4\u8f83\uff0c\u9006\u5e8f\u4ea4\u6362\uff0c\u9010\u904d\u628a\u6700\u5927\u503c\u79fb\u81f3\u6700\u540e<\/td>\n \u76f8\u90bb\u4e24\u4e2a\/\u591a\u4e2a\u987a\u5e8f\u8868\u5408\u5e76\uff0c\u521d\u59cb\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u4e00\u4e2a\u987a\u5e8f\u8868<\/td>\n \u4e24\u4fa7\u4f9d\u6b21\u626b\u63cf\uff0c\u5c06\u8f74\u503c\u79fb\u81f3\u6b63\u786e\u4f4d\u7f6e<\/td>\n<\/tr>\n \n\u65f6\u95f4\u590d\u6742\u5ea6<\/td>\n n~n^2<\/td>\n n~n^2<\/td>\n nlbn<\/td>\n nlbn~n^2<\/td>\n<\/tr>\n \n\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6<\/td>\n n^2<\/td>\n n^2<\/td>\n nlbn<\/td>\n nlbn<\/td>\n<\/tr>\n \n\u7a7a\u95f4\u590d\u6742\u5ea6<\/td>\n 1<\/td>\n 1<\/td>\n n<\/td>\n lbn~n<\/td>\n<\/tr>\n \n\u5e94\u7528\/\u4f18\u5316<\/td>\n \u9002\u7528\u4e8e\u5143\u7d20\u6570\u91cf\u5c11\uff0c\u4e14\u57fa\u672c\u6709\u5e8f\uff0c\u6539\u8fdb\uff1a\u5206\u5272\uff0c\u5206\u522b\u76f4\u63d2\uff0c\u57fa\u672c\u6709\u5e8f\u540e\u5168\u4f53\u76f4\u63d2<\/td>\n \u53cc\u5411\u8d77\u6ce1<\/td>\n \u76f8\u90bb-\u4e00\u8d9f-\u9012\u5f52<\/td>\n \u9012\u5f52\u6b21\u6570-\u7a7a\u95f4\u590d\u6742\u5ea6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\u5feb\u901f\u6392\u5e8f<\/h3>\n
\u5c06\u5f85\u6392\u6570\u7ec4\u4e0d\u65ad\u5206\u6210\u4e24\u90e8\u5206\uff0c\u5206\u522b\u6392\u5e8f<\/p>\n
int partition(int arr[], int start, int end)\n{\n int mid = arr[start];\n int i = start;\n int j = end;\n\n while(i<j){\n \/\/\u53f3\u4fa7\u626b\u63cf\uff0c\u5c06\u5c0f\u4e8e\u8f74\u503c\u7684\u5143\u7d20\u79fb\u5230\u5de6\u4fa7\n while(i<j && arr[j]>mid)\n j--;\n if(i<j){\n arr[i] = arr[j];\n i++;\n }\n\n \/\/\u5de6\u4fa7\u626b\u63cf\uff0c\u5c06\u5927\u4e8e\u8f74\u503c\u7684\u5143\u7d20\u79fb\u5230\u53f3\u4fa7\n while(i<j && arr[i]<mid)\n i++;\n if(i<j){\n arr[j] = arr[i];\n j--;\n }\n }\n arr[i] = mid;\n return i;\n}\n\nvoid quick_sort(int arr[], int start, int end)\n{\n int mid_index = partition(arr, start, end);\n if(start < mid_index)\n quick_sort(arr, start, mid_index-1);\n if(mid_index < end)\n quick_sort(arr, mid_index+1,end);\n}<\/code><\/pre>\n3\u3001\u67e5\u627e<\/h2>\n\u4e8c\u5206\u67e5\u627e<\/h3>\n
\u590d\u6742\u5ea6 lgn<\/p>\n
bool binary_search(int arr[], int length, int num)\n{\n int start = 0;\n int end = length-1;\n int mid = (start+end)\/2;\n\n while(start<=end)\n {\n if(arr[mid]==num)\n return true;\n else if(arr[mid]>num)\n end = mid - 1;\n else\n start = mid + 1;\n\n mid = (start+end)\/2;\n }\n\n return false;\n}<\/code><\/pre>\n\u4e8c\u53c9\u6392\u5e8f\u6811<\/h3>\n
\u590d\u6742\u5ea6 lgn~n<\/p>\n
myNode* searchSortBiTree(myNode* root, int k)\n{\n if(root == nullptr)\n return nullptr;\n else if(root->data == k)\n return root;\n else if(root->data > k)\n return searchSortBiTree(root->leftChild, k);\n else\n return searchSortBiTree(root->rightChild, k);\n}<\/code><\/pre>\n4\u3001\u4e8c\u53c9\u6811<\/h2>\nstruct myNode\n{\n int data;\n myNode* leftChild;\n myNode* rightChild;\n int flag;\n};<\/code><\/pre>\n\u6811\u7684\u6784\u9020\u4e0e\u91ca\u653e<\/h3>\n
\u6309\u5c42\u5e8f\u904d\u5386\u7684\u65b9\u5f0f\u6784\u9020\u3002<\/p>\n
myNode* createBiTree(int values[], int length)\n{\n queue<myNode*> nodes;\n int cnt = 0;\n\n myNode* n = new myNode;\n n->data = values[0];\n nodes.push(n);\n cnt++;\n\n while(cnt<length)\n {\n myNode* top = nodes.front();\n nodes.pop();\n\n myNode* left_n = new myNode;\n left_n->data = values[cnt];\n\n nodes.push(left_n);\n top->leftChild = left_n;\n cnt++;\n\n if(cnt==length)\n break;\n\n myNode* right_n = new myNode;\n right_n->data = values[cnt];\n nodes.push(right_n);\n top->rightChild = right_n;\n cnt++;\n }\n\n return n;\n}\n\nvoid releaseBiTree(myNode* n) \n{\n \/*\u6309\u7167\u540e\u5e8f\u904d\u5386\u7684\u987a\u5e8f\u91ca\u653e\u4e8c\u53c9\u6811*\/\n if(n != NULL) \n { \n releaseBiTree(n->leftChild); \/*\u91ca\u653e\u5de6\u5b50\u6811*\/\n releaseBiTree(n->rightChild); \/*\u91ca\u653e\u53f3\u5b50\u6811*\/\n delete n; \/*\u5220\u9664\u6839\u7ed3\u70b9*\/\n } \n}<\/code><\/pre>\n\u524d\u5e8f\u904d\u5386<\/h3>\n\/\/ \u975e\u9012\u5f52\uff1a\u6808\nvoid frontPrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n != nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n nodes.push(n);\n cout<<n->data<<\" \";\n n = n->leftChild;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid frontPrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n frontPrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n frontPrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n }\n}<\/code><\/pre>\n\u4e2d\u5e8f\u904d\u5386<\/h3>\n\/\/ \u975e\u9012\u5f52\uff1a\u6808\nvoid middlePrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n != nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n nodes.push(n);\n n = n->leftChild;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid middlePrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n middlePrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n middlePrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n }\n}<\/code><\/pre>\n\u540e\u5e8f\u904d\u5386<\/h3>\nvoid backPrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n!=nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n n->flag = 1;\n nodes.push(n);\n n = n->leftChild;\n }\n\n while(nodes.empty()!=1 && nodes.top()->flag==2)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n\n if(n==root)\n return;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n n->flag = 2;\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid backPrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n backPrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n backPrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n }\n}<\/code><\/pre>\n\u5c42\u5e8f\u904d\u5386<\/h3>\nvoid levelPrintBiTree(myNode* root)\n{\n queue<myNode*> nodes;\n myNode* n = root;\n nodes.push(n);\n\n while(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n if(n->leftChild != nullptr)\n nodes.push(n->leftChild);\n if(n->rightChild != nullptr)\n nodes.push(n->rightChild);\n }\n}<\/code><\/pre>\nZ\u5b57\u904d\u5386<\/h3>\nvoid ZPrintBiTree(myNode* root)\n{\n queue<myNode*> nodes_que;\n stack<myNode*> nodes_sta;\n int line = 1;\n int cnt = 0;\n\n queue<myNode*> nodes;\n myNode* n = root;\n nodes.push(n);\n\n while(nodes.empty()!=1)\n {\n \/\/\u5c42\u5e8f\u904d\u5386\n n = nodes.front();\n nodes.pop();\n if(n->leftChild != nullptr)\n nodes.push(n->leftChild);\n if(n->rightChild != nullptr)\n nodes.push(n->rightChild);\n\n \/\/Z\u5b57\u904d\u5386\n cnt++;\n if(line%2 == 1)\n {\n nodes_que.push(n);\n if(cnt==pow(2,line-1))\n {\n line++;\n cnt=0;\n while(nodes_que.empty()!=1)\n {\n cout<<nodes_que.front()->data<<\" \";\n nodes_que.pop();\n }\n }\n }\n else\n {\n nodes_sta.push(n);\n if(cnt==pow(2,line-1))\n {\n line++;\n cnt=0;\n while(nodes_sta.empty()!=1)\n {\n cout<<nodes_sta.top()->data<<\" \";\n nodes_sta.pop();\n }\n }\n } \n }\n \/\/\u6ca1\u6253\u5370\u7684\u6253\u5370\u5b8c\n while(nodes_que.empty()!=1)\n {\n cout<<nodes_que.front()->data<<\" \";\n nodes_que.pop();\n }\n while(nodes_sta.empty()!=1)\n {\n cout<<nodes_sta.top()->data<<\" \";\n nodes_sta.pop();\n }\n}<\/code><\/pre>\n\u91cd\u5efa\u4e8c\u53c9\u6811\uff1a\u524d\u5e8f+\u4e2d\u5e8f<\/h3>\nmyNode* createBiTreeByFrontMid(int* frontValues, int* midValues, int length)\n{\n if(length==0)\/\/\u53ea\u9488\u5bf9\u7b2c\u4e00\u6b21\u4f7f\u7528\n return nullptr;\n\n myNode* root = new myNode;\/\/\u786e\u5b9a\u8fd9\u4e00\u6bb5\u7684\u6839\u8282\u70b9\uff0c\u7136\u540e\u5212\u5206\u5de6\u53f3\u4e24\u5b50\u6811\n root->data = frontValues[0];\n root->leftChild = nullptr;\n root->rightChild = nullptr;\n\n int i;\n for(i=0;i<length && midValues[i]!=frontValues[0];i++)\n ;\n\n int leftLength = i;\n int rightLength = length-i-1;\n\n if(leftLength>0)\n root->leftChild = createBiTreeByFrontMid(&frontValues[1], &midValues[0], leftLength);\n if(rightLength>0)\n root->rightChild = createBiTreeByFrontMid(&frontValues[leftLength+1], &midValues[leftLength+1], rightLength);\n\n return root;\n}<\/code><\/pre>\n\u91cd\u5efa\u4e8c\u53c9\u6811\uff1a\u4e2d\u5e8f+\u540e\u5e8f<\/h3>\nmyNode* createBiTreeByBackMid(int* backValues, int* midValues, int length)\n{\n if(length==0)\/\/\u53ea\u9488\u5bf9\u7b2c\u4e00\u6b21\u4f7f\u7528\n return nullptr;\n\n myNode* root = new myNode;\/\/\u786e\u5b9a\u8fd9\u4e00\u6bb5\u7684\u6839\u8282\u70b9\uff0c\u7136\u540e\u5212\u5206\u5de6\u53f3\u4e24\u5b50\u6811\n root->data = backValues[length-1];\n root->leftChild = nullptr;\n root->rightChild = nullptr;\n\n int i;\n for(i=0;i<length && midValues[i]!=backValues[length-1];i++)\n ;\n\n int leftLength = i;\n int rightLength = length-i-1;\n\n if(leftLength>0)\n root->leftChild = createBiTreeByBackMid(&backValues[0], &midValues[0], leftLength);\n if(rightLength>0)\n root->rightChild = createBiTreeByBackMid(&backValues[leftLength], &midValues[leftLength+1], rightLength);\n\n return root;\n}<\/code><\/pre>\n\u4e8c\u53c9\u6392\u5e8f\u6811<\/h3>\n
\u4e8c\u53c9\u6392\u5e8f\u6811\uff1a\u7a7a\u6811\u6216\u975e\u7a7a\u6811\uff0c\u975e\u7a7a\u6811\u6ee1\u8db3\u5de6\u5b50\u6811\u6240\u6709\u8282\u70b9\u5c0f\u4e8e\u6839\u8282\u70b9\uff0c\u53f3\u5b50\u6811\u6240\u6709\u8282\u70b9\u5927\u4e8e\u6839\u8282\u70b9\uff0c\u5de6\u53f3\u5b50\u6811\u53c8\u662f\u4e8c\u53c9\u6392\u5e8f\u6811\u3002<\/p>\n
\u63d2\u5165<\/h4>\nvoid insertSortBiTree(myNode* &root, myNode* newNode)\n{\n if(root==nullptr)\n root = newNode;\n else if(root->data > newNode->data)\n insertSortBiTree(root->leftChild, newNode);\n else\n insertSortBiTree(root->rightChild, newNode);\n}<\/code><\/pre>\n\u6784\u9020<\/h4>\nmyNode* createSortBiTree(int data[], int n)\n{\n myNode* root = nullptr;\n myNode* newNode;\n for(int i=0;i<n;i++)\n {\n newNode = new myNode;\n newNode->data = data[i];\n newNode->leftChild = nullptr;\n newNode->rightChild = nullptr;\n insertSortBiTree(root, newNode);\n }\n return root;\n}<\/code><\/pre>\n5\u3001\u961f\u5217\u4e0e\u6808<\/h2>\n\u4e24\u4e2a\u961f\u5217\u5b9e\u73b0\u6808<\/h3>\nclass myStack\n{\n private:\n queue<int> que1;\n queue<int> que2;\n\n public:\n myStack();\n ~myStack(){};\n\n void push(int);\n void pop();\n int top();\n};\n\nmyStack::myStack(){}\nvoid myStack::push(int data)\/\/\u5728\u975e\u7a7a\u7684\u961f\u5217\u672b\u5c3e\u6dfb\u52a0\u65b0\u5143\u7d20\n{\n if(que1.empty())\n que2.push(data);\n else\n que1.push(data);\n}\n\nvoid myStack::pop()\/\/\u5c06\u975e\u7a7a\u961f\u5217\u5143\u7d20\u8f6c\u79fb\u5230\u7a7a\u961f\u5217\uff0c\u7559\u6700\u540e\u4e00\u4e2a\u5f39\u51fa\n{\n if(que1.empty() && que2.empty())\n return ;\n\n if(que1.empty())\n {\n while(que2.size()!=1)\n {\n que1.push(que2.front());\n que2.pop();\n }\n que2.pop();\n }\n else\n {\n while(que1.size()!=1)\n {\n que2.push(que1.front());\n que1.pop();\n }\n que1.pop();\n } \n}\n\nint myStack::top()\/\/\u5c06\u975e\u7a7a\u961f\u5217\u5143\u7d20\u8f6c\u79fb\u5230\u7a7a\u961f\u5217\uff0c\u6700\u540e\u4e00\u4e2a\u8f93\u51fa\n{\n if(que1.empty() && que2.empty())\n return -1;\n\n int out;\n if(que1.empty())\n {\n while(que2.size()!=1)\n {\n que1.push(que2.front());\n que2.pop();\n }\n out = que2.front();\n que1.push(out);\n que2.pop();\n }\n else\n {\n while(que1.size()!=1)\n {\n que2.push(que1.front());\n que1.pop();\n }\n out = que1.front();\n que2.push(out);\n que1.pop();\n }\n return out;\n}<\/code><\/pre>\n\u4e24\u4e2a\u6808\u5b9e\u73b0\u961f\u5217<\/h3>\nclass myQueue\n{\n private:\n stack<int> sta1;\/\/\u5b58\n stack<int> sta2;\/\/\u53d6\n\n public:\n myQueue();\n ~myQueue(){};\n\n void push(int);\n void pop();\n int front();\n};\n\nmyQueue::myQueue(){}\nvoid myQueue::push(int data)\n{\n sta1.push(data);\n}\n\nvoid myQueue::pop()\n{\n if(sta1.empty())\n return ;\n\n while(sta1.size()!=1)\n { \n sta2.push(sta1.top());\n sta1.pop();\n }\n\n sta1.pop(); \n\n while(sta2.size()!=0) \n {\n sta1.push(sta2.top());\n sta2.pop();\n } \n}\nint myQueue::front()\n{\n if(sta1.empty())\n return -1;\n\n while(sta1.size()!=1)\n { \n sta2.push(sta1.top());\n sta1.pop();\n }\n\n int out = sta1.top();\n sta2.push(out);\n sta1.pop(); \n\n while(sta2.size()!=0) \n {\n sta1.push(sta2.top());\n sta2.pop();\n } \n\n return out;\n}<\/code><\/pre>\n\u5faa\u73af\u961f\u5217*<\/h3>\n
\u76f8\u5bf9\u4e8e\u76f4\u7ebf\u961f\u5217\u6765\u8bb2\uff0c\u76f4\u7ebf\u961f\u5217\u5728\u5143\u7d20\u51fa\u961f\u540e\uff0c\u5934\u6307\u9488\u5411\u540e\u79fb\u52a8\uff0c\u5bfc\u81f4\u5220\u9664\u5143\u7d20\u540e\u7684\u7a7a\u95f4\u65e0\u6cd5\u5728\u5229\u7528\uff0c\u5373\u4f7f\u5143\u7d20\u4e2a\u6570\u5c0f\u4e8e\u7a7a\u95f4\u5927\u5c0f\uff0c\u4f9d\u7136\u65e0\u6cd5\u518d\u8fdb\u884c\u63d2\u5165\uff0c\u5373\u6240\u8c13\u7684\u201c\u5047\u4e0a\u6ea2\u201d\u3002\u5f53\u53d8\u6210\u5faa\u73af\u961f\u5217\u4e4b\u540e\uff0c\u5220\u9664\u5143\u7d20\u540e\u7684\u7a7a\u95f4\u4ecd\u7136\u53ef\u4ee5\u5229\u7528\uff0c\u6700\u5927\u9650\u5ea6\u7684\u5229\u7528\u7a7a\u95f4\u3002<\/p>\n
6\u3001\u56fe<\/h2>\n\u6df1\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\nvoid DFS_recursion(int curVertex, int vertexNum, vector<int>* arc, vector<int>* visited)\n{\n (*visited)[curVertex] = 1; \/\/\u6807\u8bb0\u8be5\u6b21\u904d\u5386\u7684\u9876\u70b9\n cout<<curVertex<<\" \";\n for(int i=0; i<vertexNum;i++) \/\/\u904d\u5386\u8be5\u9876\u70b9\u8fde\u63a5\u7684\u5176\u4ed6\u9876\u70b9\n if((*visited)[i]==0 && (*arc)[curVertex*vertexNum+i]==1)\n DFS_recursion(i, vertexNum, arc, visited); \n}\n\nvoid DFS(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u6240\u6709\u9876\u70b9\u672a\u88ab\u904d\u5386\n vector<int> visited; \n for(int i=0;i<vertexNum; i++)\n visited.push_back(0);\n\n\/\/\u6df1\u5ea6\u904d\u5386\n for(int i=0; i<vertexNum; i++)\/\/\u4ece\u7b2ci\u4e2a\u9876\u70b9\u5f00\u59cb\u7684\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n {\n if(visited[i]==0)\n DFS_recursion(i, vertexNum, arc, &visited);\n }\n}<\/code><\/pre>\n\u5e7f\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\nvoid BFS(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u6240\u6709\u9876\u70b9\u672a\u88ab\u904d\u5386\n vector<int> visited; \n for(int i=0;i<vertexNum; i++)\n visited.push_back(0);\n\n\/\/\u5e7f\u5ea6\u904d\u5386\n queue<int> q;\n for(int i=0;i<vertexNum; i++)\/\/\u4ece\u7b2ci\u4e2a\u9876\u70b9\u5f00\u59cb\u7684\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n {\n if(visited[i]==0)\n {\n q.push(i);\n visited[i]=1;\n\n while(q.empty()!=1)\n {\n int v = q.front();\n q.pop();\n cout<<v<<\" \";\n\n for(int j=0; j<vertexNum; j++)\n if(visited[j]==0 && (*arc)[v*vertexNum+j]==1)\n {\n q.push(j);\n visited[j]=1;\n }\n }\n }\n }\n}<\/code><\/pre>\n\u6700\u5c0f\u751f\u6210\u6811<\/h3>\n
n\u4e2a\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\uff0c\u76ee\u6807\u4f7f\u5f97\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02\u4e92\u901a\uff0c\u4e0d\u540c\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\u4ee3\u4ef7\u4e0d\u540c\uff0c\u6c42\u4ee3\u4ef7\u6700\u5c0f\u7684\u94fa\u8bbe\u65b9\u6cd5\u3002<\/p>\n
Prim<\/h4>\n
\u5411\u6700\u5c0f\u751f\u6210\u6811\u6dfb\u52a0\u70b9\u3002<\/p>\n
void Prim(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u5019\u9009\u6700\u77ed\u8fb9\u96c6\n vector<int> connectCost; \/\/\u5019\u9009\u6700\u77ed\u8fb9\u96c6\uff1a\u5019\u9009\u9876\u70b9\u5230\u6b63\u5f0f\u9876\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7 \u4ee3\u4ef7\u4e3a0\uff0c\u5373\u9009\u4e3a\u6b63\u5f0f\u9876\u70b9\n vector<int> connectVertex; \/\/\u5019\u9009\u6700\u77ed\u8fb9\u96c6\uff1a\u6700\u5c0f\u4ee3\u4ef7\u5bf9\u5e94\u7684\u6b63\u5f0f\u9876\u70b9 \u627e\u5185\u63a8\uff1f\n\n for(int i=0;i<vertexNum;i++)\n {\n connectCost.push_back((*arc)[0*vertexNum + i]); \/\/\u9ed8\u8ba4\u5230\u81ea\u8eab\u7684\u4ee3\u4ef7\u4e3a0\uff0c\u56e0\u6b640\u53f7\u9876\u70b9\u521d\u59cb\u5316\u5373\u9009\u4e3a\u6b63\u5f0f\u9876\u70b9\n connectVertex.push_back(0);\n }\n\n\/\/\u6700\u5c0f\u751f\u6210\u6811\uff1a\u6bcf\u6b21\u52a0\u5165\u4e00\u4e2a\u6b63\u5f0f\u9876\u70b9\uff0c\u5e76\u66f4\u65b0\u5019\u9009\u6700\u77ed\u8fb9\u96c6\n for(int m=1;m<vertexNum;m++)\n {\n \/\/\u904d\u5386\u6700\u77ed\u8fb9\u96c6\uff0c\u627e\u5230\u6700\u6700\u77ed\u7684\u4e00\u4e2a\n int k=0;\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0)\n {\n k=i; break;\n }\n\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0 && connectCost[i]<connectCost[k])\n k=i;\n\n if(connectCost[k]==0)\/\/\u627e\u4e00\u5708\u53d1\u73b0\u5747\u5df2\u6dfb\u52a0\u5230\u6b63\u5f0f\u9876\u70b9\u4e2d\uff0c\u5219\u9000\u51fa\n return ;\n\n cout<<\"(\"<<connectVertex[k]<<\"->\"<<k<<\")-cost-\"<<connectCost[k]<<\" \";\n \/\/\u628a\u7b2ck\u4e2a\u9876\u70b9\u52a0\u5165\u6b63\u5f0f\u9876\u70b9\u4e2d\n connectCost[k]=0; \n \/\/\u770b\u770b\u5269\u4e0b\u7684\u5019\u9009\u8282\u70b9\u662f\u4e0d\u662f\u5230k\u7684\u4ee3\u4ef7\u66f4\u5c0f\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0 && connectCost[i]>(*arc)[k*vertexNum + i])\n {\n connectCost[i] = (*arc)[k*vertexNum + i]; \n connectVertex[i] = k;\n }\n } \n}<\/code><\/pre>\nKruscal<\/h4>\n
\u5411\u6700\u5c0f\u751f\u6210\u6811\u6dfb\u52a0\u8fb9\u3002<\/p>\n
struct Edge\n{\n int vertexA;\n int vertexB;\n int cost;\n};\nbool cmp(const Edge &a,const Edge &b)\n{\n return (a.cost) < (b.cost);\n}\nint find_parent(int v, vector<int> &parents)\n{\n return parents[v]==v ? v : find_parent(parents[v], parents);\/\/\u9012\u5f52\u627e\u5230\u9876\u5c42\u53cc\u4eb2\n}\nvoid Kruscal(int vertexNum, vector<int>* arc)\n{\n\/\/\u6570\u636e\u51c6\u5907\n vector<Edge> edges;\n for(int i=0;i<vertexNum;i++)\n for(int j=i+1;j<vertexNum;j++)\n if((*arc)[i*vertexNum + j] < 100)\n {\n Edge edge;\n edge.vertexA = i;\n edge.vertexB = j;\n edge.cost = (*arc)[i*vertexNum + j];\n edges.push_back(edge);\n }\n\/\/Kruscal\n \/\/\u8fb9\u96c6\u6570\u7ec4\u521d\u59cb\u5316:\u5347\u5e8f\u6392\u5217\n sort(edges.begin(),edges.end(),cmp);\n\n \/\/\u9876\u5c42\u53cc\u4eb2\u521d\u59cb\u5316\uff1a\u7528\u4e8e\u5224\u65ad\u67d0\u4e00\u8fb9\u7684\u4e24\u9876\u70b9\u662f\u5426\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n vector<int> parents;\n for(int i=0;i<vertexNum;i++)\n parents.push_back(i);\/\/\u521d\u59cb\u5316\u6bcf\u4e2a\u9876\u70b9\u81ea\u6210\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\uff0c\u5176\u53cc\u4eb2\u4e3a\u81ea\u8eab\n\n \/\/\u6700\u5c0f\u751f\u6210\u6811\uff1a\u6bcf\u6b21\u6dfb\u52a0\u4e00\u6761\u8fb9\n for(int i=0;i<edges.size();i++)\n {\n \/\/\u62ff\u51fa\u4e00\u6761\u8fb9\uff0c\u5224\u65ad\u662f\u5426\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf:\u5224\u65ad\u9876\u5c42\u53cc\u4eb2\u662f\u5426\u76f8\u540c\n Edge e = edges[i];\n if(find_parent(e.vertexA, parents) != find_parent(e.vertexB, parents))\n {\n parents[find_parent(e.vertexB, parents)]=find_parent(e.vertexA, parents);\n cout<<\"(\"<<e.vertexA<<\"->\"<<e.vertexB<<\")-cost-\"<<e.cost<<\" \";\n }\n }\n}<\/code><\/pre>\n7\u3001\u5e77\u67e5\u96c6<\/h2>\n\n\u9898\u76ee\u80cc\u666f
\n\u82e5\u67d0\u4e2a\u5bb6\u65cf\u4eba\u5458\u8fc7\u4e8e\u5e9e\u5927\uff0c\u8981\u5224\u65ad\u4e24\u4e2a\u662f\u5426\u662f\u4eb2\u621a\uff0c\u786e\u5b9e\u8fd8\u5f88\u4e0d\u5bb9\u6613\uff0c\u73b0\u5728\u7ed9\u51fa\u67d0\u4e2a\u4eb2\u621a\u5173\u7cfb\u56fe\uff0c\u6c42\u4efb\u610f\u7ed9\u51fa\u7684\u4e24\u4e2a\u4eba\u662f\u5426\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u9898\u76ee\u63cf\u8ff0
\n\u89c4\u5b9a\uff1ax\u548cy\u662f\u4eb2\u621a\uff0cy\u548cz\u662f\u4eb2\u621a\uff0c\u90a3\u4e48x\u548cz\u4e5f\u662f\u4eb2\u621a\u3002\u5982\u679cx,y\u662f\u4eb2\u621a\uff0c\u90a3\u4e48x\u7684\u4eb2\u621a\u90fd\u662fy\u7684\u4eb2\u621a\uff0cy\u7684\u4eb2\u621a\u4e5f\u90fd\u662fx\u7684\u4eb2\u621a\u3002
\n\u8f93\u5165\u683c\u5f0f
\n\u7b2c\u4e00\u884c\uff1a\u4e09\u4e2a\u6574\u6570n,m,p\uff0c\uff08n<=5000,m<=5000,p<=5000\uff09\uff0c\u5206\u522b\u8868\u793a\u6709n\u4e2a\u4eba\uff0cm\u4e2a\u4eb2\u621a\u5173\u7cfb\uff0c\u8be2\u95eep\u5bf9\u4eb2\u621a\u5173\u7cfb\u3002
\n\u4ee5\u4e0bm\u884c\uff1a\u6bcf\u884c\u4e24\u4e2a\u6570Mi\uff0cMj\uff0c1<=Mi\uff0cMj<=N\uff0c\u8868\u793aMi\u548cMj\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u63a5\u4e0b\u6765p\u884c\uff1a\u6bcf\u884c\u4e24\u4e2a\u6570Pi\uff0cPj\uff0c\u8be2\u95eePi\u548cPj\u662f\u5426\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u8f93\u51fa\u683c\u5f0f
\nP\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u2019Yes\u2019\u6216\u2019No\u2019\u3002\u8868\u793a\u7b2ci\u4e2a\u8be2\u95ee\u7684\u7b54\u6848\u4e3a\u201c\u5177\u6709\u201d\u6216\u201c\u4e0d\u5177\u6709\u201d\u4eb2\u621a\u5173\u7cfb\u3002<\/p>\n<\/blockquote>\n
\n- \u5e77\u67e5\u96c6\u7684\u4e24\u79cd\u64cd\u4f5c\uff1a\u67e5\u8be2\u662f\u5426\u5728\u540c\u4e00\u96c6\u5408\uff0c\u5408\u5e76\u4e0d\u540c\u96c6\u5408<\/li>\n
- \u5e77\u67e5\u96c6\u7684\u601d\u60f3\uff1a\u6bcf\u4e2a\u96c6\u5408\u786e\u5b9a\u4e00\u4e2a\u4ee3\u8868\u5143\u7d20\uff0c\u5f62\u6210\u4e00\u4e2a\u6811\u72b6\u7ed3\u6784\uff0c\u4ee3\u8868\u5143\u7d20\u4e3a\u6839\u8282\u70b9\uff0c\u5176\u4ed6\u5143\u7d20\u4e3a\u5b50\u8282\u70b9\u3002\u96c6\u5408\u7684\u5408\u5e76\u5c31\u662f\u4e00\u4e2a\u96c6\u5408\u7684\u6839\u8282\u70b9\u6210\u4e3a\u53e6\u4e00\u4e2a\u96c6\u5408\u7684\u5b50\u8282\u70b9\u3002\u96c6\u5408\u7684\u67e5\u8be2\u5c31\u662f\u4e0d\u65ad\u627e\u7236\u8282\u70b9\uff0c\u76f4\u5230\u627e\u5230\u6839\u8282\u70b9\uff0c\u5224\u65ad\u6839\u8282\u70b9\u662f\u5426\u76f8\u540c\u3002<\/li>\n
- \u5e77\u67e5\u96c6\u5e94\u7528\uff1a\u6700\u5c0f\u751f\u6210\u6811\u7684Kruscal\u65b9\u6cd5\u3002<\/li>\n
- \u5e77\u67e5\u96c6\u7684\u521d\u59cb\u5316\uff0c\u5408\u5e76\u548c\u67e5\u8be2\n
int parent[NMAX]\nvoid init(int n) \/\/\u521d\u59cb\u5316\u4e3a\u672c\u8eab\n{\nfor(int i=0;i<n;i++)\n parent[i]=i;\n}\nint find(int i)\n{\nreturn parent[i]==i ? i : find(parent[i]); \/\/\u4e0d\u65ad\u5411\u4e0a\u67e5\u8be2\u7236\u8282\u70b9\uff0c\u76f4\u5230\u6240\u5c5e\u7ed3\u5408\u7684\u6839\u8282\u70b9\n}\nint merge(int i, int j)\n{\nparent[find(i)] = find(j);\/\/\u628ai\u6240\u5c5e\u96c6\u5408\u7684\u6839\u8282\u70b9\uff0c\u53d8\u6210j\u6240\u5c5e\u96c6\u5408\u6839\u8282\u70b9\u7684\u5b50\u8282\u70b9\n}<\/code><\/pre>\n<\/li>\n- \u538b\u7f29\uff1a\u67e5\u8be2\u8fc7\u7a0b\u4e2d\u5c06\u5176\u7236\u8282\u70b9\u6362\u6210\u6839\u8282\u70b9\uff0c\u51cf\u5c11\u9012\u5f52\u6b21\u6570\uff0c\u56e0\u4e3a\u53ea\u5728\u67e5\u8be2\u65f6\u538b\u7f29\uff0c\u56e0\u6b64\u672a\u5fc5\u6bcf\u4e2a\u96c6\u5408\u9664\u4e86\u6839\u8282\u70b9\uff0c\u5168\u662f\u53f6\u5b50\u8282\u70b9\n
int find(int i)\n{\nreturn parent[i]==i ? i : ( parent[i] = find(parent[i]) ); \/\/\u67e5\u8be2\u8fc7\u7a0b\u4e2d\u5c06\u5176\u7236\u8282\u70b9\u6362\u6210\u6839\u8282\u70b9\n}<\/code><\/pre>\n<\/li>\n- \u6309\u79e9\u5408\u5e76\uff1a\u628a\u7b80\u5355\u6811\u5408\u5e76\u5230\u590d\u6742\u6811
\n\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0(1) : \u5e76\u67e5\u96c6<\/a><\/li>\n<\/ol>\n8\u3001\u5b57\u7b26\u4e32<\/h2>\n\u6709\u6548\u5b57\u7b26\u4e32<\/h3>\n
![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"http:\/\/47.103.123.166\/wp-content\/uploads\/2021\/11\/post-179-619a422d80f46.png\")
\n\u4e00\u4e2a\u770b\u7740\u4e0d\u9519\u7684\u7b54\u6848<\/p>\n
bool checkValidString(String s) {\n int low = 0; \/\/ \u8868\u793a*\u53f7\u90fd\u4f5c\u4e3a\u53f3\u62ec\u53f7\u65f6\uff0c\u5de6\u62ec\u53f7\u7684\u6570\u91cf\n int hight = 0; \/\/ \u8868\u793a*\u90fd\u4f5c\u4e3a\u5de6\u62ec\u53f7\u65f6\uff0c\u5de6\u62ec\u53f7\u7684\u6570\u91cf\n \/\/ \u5982\u679chight < 0 \u8bf4\u660e*\u90fd\u4f5c\u4e3a\u5de6\u62ec\u53f7\u4e86\uff0c\u8fd8\u662f\u4e0d\u591f\u62b5\u6d88\u4e0d\u4e86\u53f3\u62ec\u53f7\n \/\/ \u5982\u679clow > 0 \u8bf4\u660e*\u53f7\u90fd\u4f5c\u4e3a\u53f3\u62ec\u53f7\u4e86\uff0c\u8fd8\u662f\u62b5\u6d88\u4e0d\u4e86\u62ec\u53f7\u7684\u503c\n for (int i=0; i<s.length();i++){\n char tmp = s.charAt(i);\n if (tmp == '(') {\n low++;\n hight++;\n } \n else if (tmp == ')') {\n if (low > 0) {\n low--;\n }\n hight--;\n } else if (tmp == '*') {\n if (low > 0) {\n low--;\n }\n hight++;\n }\n\n if (hight < 0) {\n return false;\n }\n }\n return low == 0;\n}<\/code><\/pre>\n9\u3001\u6570\u7ec4<\/h2>\n\u5dee\u5206\u6570\u7ec4 \u524d\u7f00\u548c<\/h3>\n
![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"http:\/\/47.103.123.166\/wp-content\/uploads\/2021\/11\/post-179-619a422de05a9.png\")
<\/p>\n
class Solution {\npublic:\n vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {\n\n vector<int> data;\n for(int i=0; i<n;i++)\n data.push_back(0);\n\n for(auto i : bookings)\n {\n data[i[0]-1]+=i[2];\n if(i[1]<n)\n data[i[1]]-=i[2];\n }\n\n for(int i=1; i<n;i++)\n data[i]+=data[i-1];\n\n return data;\n }\n};<\/code><\/pre>\n\u6d4b\u8bd5<\/h2>\n\u4ee3\u7801<\/h3>\nint main()\n{\n\/\/\u52a8\u6001\u89c4\u5212\n int a[]{1,-5,8,3,-4,15,-8};\n std::cout<<\"max_successive_sub_serial_sum: \"<<max_successive_sub_serial_sum(a,7)<<std::endl;\n std::cout<<\"max_successive_sub_serial_sum_space: \"<<max_successive_sub_serial_sum_space(a,7)<<std::endl;\n\n std::cout<<\"unique_path: \"<<unique_path(3,7)<<std::endl;\n std::cout<<\"unique_path_space: \"<<unique_path_space(3,7)<<std::endl;\n\n int rows=3, cols=3;\n int** map = new int*[rows];\n for(int i=0;i<rows;i++)\n {\n map[i] = new int[cols];\n for(int j=0;j<cols;j++)\n map[i][j]=j;\n }\n std::cout<<\"unique_path_shortest: \"<<unique_path_shortest(map, rows, cols)<<std::endl;\n std::cout<<\"unique_path_shortest_space: \"<<unique_path_shortest_space(map, rows, cols)<<std::endl;\n\/\/\u6392\u5e8f \n int arr[8]{8,7,6,5,4,4,2,1};\n quick_sort(arr,0,7);\n std:cout<<\"quick_sort: \";\n for(int i=0;i<8;i++)\n std::cout<<arr[i]<<\" \";\n std::cout<<std::endl;\n\/\/\u67e5\u627e \n int arr1[9]{8,7,6,5,4,4,2,1,11};\n std::cout<<\"binary_search: \"<<binary_search(arr, 8,5)<<std::endl;\n std::cout<<\"binary_search: \"<<binary_search(arr1, 9,3)<<std::endl;\n\n\/\/\u4e8c\u53c9\u6811\n int arr2[9]{8,7,6,5,4,4,2,1,11};\n myNode* root = createBiTree(arr2, 9);\n cout<<\"frontPrintBiTree: \";\n frontPrintBiTree(root);\n cout<<endl<<\"middlePrintBiTree: \";\n middlePrintBiTree(root);\n cout<<endl<<\"backPrintBiTree: \";\n backPrintBiTree(root);\n cout<<endl<<\"frontPrintBiTree_recursion: \";\n frontPrintBiTree_recursion(root);\n cout<<endl<<\"middlePrintBiTree_recursion: \";\n middlePrintBiTree_recursion(root);\n cout<<endl<<\"backPrintBiTree_recursion: \";\n backPrintBiTree_recursion(root);\n cout<<endl<<\"levelPrintBiTree: \";\n levelPrintBiTree(root);\n cout<<endl<<\"ZPrintBiTree: \";\n ZPrintBiTree(root);\n releaseBiTree(root);\n\n int arr2_front[9]{8,7,5,1,11,4,6,4,2};\n int arr2_mid[9]{1,5,11,7,4,8,4,6,2};\n int arr2_back[9]{1,11,5,4,7,4,2,6,8};\n myNode* root1 = createBiTreeByFrontMid(arr2_front, arr2_mid, 9);\n cout<<endl<<\"createBiTreeByFrontMid backPrintBiTree: \";\n backPrintBiTree(root1);\n releaseBiTree(root1);\n myNode* root2 = createBiTreeByBackMid(arr2_back, arr2_mid, 9);\n cout<<endl<<\"createBiTreeByBackMid frontPrintBiTree: \";\n frontPrintBiTree(root2);\n releaseBiTree(root2);\n cout<<endl;\n\n\/\/\u961f\u5217\u4e0e\u6808\n myStack s;\n s.push(1);\n s.push(2);\n s.push(3);\n s.push(4);\n s.push(5);\n cout<<\"s.top():\"<<s.top()<<endl;\n s.pop();\n cout<<\"s.top() after pop():\"<<s.top()<<endl;\n\n myQueue q;\n q.push(1);\n q.push(2);\n q.push(3);\n q.push(4);\n q.push(5);\n cout<<\"q.front():\"<<q.front()<<endl;\n q.pop();\n cout<<\"q.front() after pop():\"<<q.front()<<endl;\n\n\/\/\u56fe\n int vertexNum = 10;\n \/\/0 1 2 3 4 5 6 7 8 9 \u65e0\u5411\u56fe \u4e24\u4e2a\u8fde\u901a\u5206\u91cf \n int arc_a[10][10]={0,0,1,0,1, 1,0,0,0,0, \n 0,0,0,1,0, 0,0,0,0,0,\n 1,0,0,0,0, 0,0,0,0,0,\n 0,1,0,0,0, 0,0,0,0,0,\n 1,0,0,0,0, 0,0,0,1,0,\n\n 1,0,0,0,0, 0,1,1,0,0,\n 0,0,0,0,0, 1,0,0,0,0,\n 0,0,0,0,0, 1,0,0,0,0,\n 0,0,0,0,1, 0,0,0,0,1,\n 0,0,0,0,0, 0,0,0,1,0}; \n\n vector<int> arc;\n for(int i=0;i<vertexNum;i++)\n for(int j=0;j<vertexNum;j++)\n arc.push_back(arc_a[i][j]);\n cout<<\"DFS: \";\n DFS(vertexNum, &arc); \n cout<<endl<<\"BFS: \";\n BFS(vertexNum, &arc); \n cout<<endl;\n\n vertexNum = 6;\n \/\/0 1 2 3 4 5 6 7 8 9 \u65e0\u5411\u8fde\u901a\u56fe\n int arc_b[6][6]={0, 4, 100, 100, 5, 2, \n 4, 0, 2, 100, 100, 1,\n 100, 2, 0, 10, 100, 3,\n 100, 100, 10, 0, 1, 4,\n 5, 100, 100, 1, 0, 8,\n 2, 1, 3, 4, 8, 0}; \n arc.clear();\n for(int i=0;i<vertexNum;i++)\n for(int j=0;j<vertexNum;j++)\n arc.push_back(arc_b[i][j]);\n cout<<\"Prim:\";\n Prim(vertexNum, &arc);\n cout<<endl<<\"Kruscal:\";\n Kruscal(vertexNum, &arc);\n cout<<endl;\n\n\/\/\u4e8c\u53c9\u6392\u5e8f\u6811\n int sortBiTree[]{80,40,70,90,100,15,81,77,89,96,1};\n myNode* sortRoot = createSortBiTree(sortBiTree, 11);\n cout<<\"createSortBiTree frontPrintBiTree: \";\n frontPrintBiTree(sortRoot);\n cout<<endl;\n myNode* getNode = searchSortBiTree(sortRoot, 96);\n cout<<\"searchSortBiTree 96:\"<<(getNode!=nullptr)<<endl;\n getNode = searchSortBiTree(sortRoot, 77);\n cout<<\"searchSortBiTree 77:\"<<(getNode!=nullptr)<<endl;\n getNode = searchSortBiTree(sortRoot, 2);\n cout<<\"searchSortBiTree 2:\"<<(getNode!=nullptr)<<endl;\n releaseBiTree(sortRoot); \n return 0;\n}<\/code><\/pre>\n\u8f93\u51fa<\/h3>\nmax_successive_sub_serial_sum: 22\nmax_successive_sub_serial_sum_space: 22\nunique_path: 28\nunique_path_space: 28\nunique_path_shortest: 3\nunique_path_shortest_space: 3\nquick_sort: 1 2 4 4 5 6 7 8 \nbinary_search: 1\nbinary_search: 0\nfrontPrintBiTree: 8 7 5 1 11 4 6 4 2 \nmiddlePrintBiTree: 1 5 11 7 4 8 4 6 2 \nbackPrintBiTree: 1 11 5 4 7 4 2 6 8 \nfrontPrintBiTree_recursion: 8 7 5 1 11 4 6 4 2 \nmiddlePrintBiTree_recursion: 1 5 11 7 4 8 4 6 2 \nbackPrintBiTree_recursion: 1 11 5 4 7 4 2 6 8 \nlevelPrintBiTree: 8 7 6 5 4 4 2 1 11 \nZPrintBiTree: 8 6 7 5 4 4 2 11 1 \ncreateBiTreeByFrontMid backPrintBiTree: 1 11 5 4 7 4 2 6 8 \ncreateBiTreeByBackMid frontPrintBiTree: 8 7 5 1 11 4 6 4 2 \ns.top():5\ns.top() after pop():4\nq.front():1\nq.front() after pop():2\nDFS: 0 2 4 8 9 5 6 7 1 3 \nBFS: 0 2 4 5 8 6 7 9 1 3 \nPrim:(0->5)-cost-2 (5->1)-cost-1 (1->2)-cost-2 (5->3)-cost-4 (3->4)-cost-1 \nKruscal:(1->5)-cost-1 (3->4)-cost-1 (0->5)-cost-2 (1->2)-cost-2 (3->5)-cost-4\ncreateSortBiTree frontPrintBiTree: 80 40 15 1 70 77 90 81 89 100 96 \nsearchSortBiTree 96:1\nsearchSortBiTree 77:1\nsearchSortBiTree 2:0<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"1\u3001\u52a8\u6001\u89c4\u5212 DP\u95ee\u9898\u4e09\u6b65\u8d70 \u5b9a\u4e49\u4e00\u4e2a\u52a8\u6001\u89c4\u5212\u6570\u7ec4\uff0c\u660e\u786e\u6570\u7ec4\u5143\u7d20\uff0c\u76ee\u7684\u662f\u4fdd\u5b58\u8ba1\u7b97\u7684\u5386\u53f2\u8bb0\u5f55\uff0c\u8282\u7701\u91cd\u590d\u8ba1\u7b97\u65f6\u95f4 \u786e\u5b9a\u6570\u7ec4\u95f4\u7684\u5173\u7cfb \u627e\u51fa\u521d\u59cb\u503c \u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c \u6709\u4e00\u4e2a\u6570\u7ec4\uff0c\u59821\uff0c \uff0d5\uff0c 8\uff0c 3\uff0c \uff0d4\uff0c 15\uff0c \uff0d8\uff0c\u67e5\u627e\u5176\u4e2d\u8fde\u7eed\u548c\u6700\u5927\u7684\u76f8\u90bb\u4e32\u7684\u503c\u3002 \u5728\u672c\u4f8b\u4e2d\uff0c\u6700\u5927\u503c\u4e3a8 \uff0b 3 \uff0b \uff0d4 \uff0b 15 \uff1d 22\u3002 \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20\uff1adp[i]\u8868\u793a\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\u3002 \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb\uff1adp[i] = max{ dp[i-1] + arc[i] , arc[i] }\uff0c\u5373\uff0c\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\uff0c\u8981\u4e48\u662f\u7ee7\u7eed\u7d2f\u52a0\uff0c\u8981\u4e48\u5c31\u662f\u5143\u7d20\u672c\u8eab\uff08\u91cd\u65b0\u5f00\u59cb\u4e00\u8f6e\u7d2f\u52a0\uff09\u3002\u6700\u7ec8\u7684\u6700\u5927\u503c\u662fdp\u6570\u7ec4\u4e2d\u7684\u6700\u5927\u503c\u3002\uff08\u53ef\u4ee5\u7d2f\u52a0\u4e00\u4e2a\u8d1f\u6570\uff0c\u4f46\u4e0d\u80fd\u5728\u8d1f\u6570\u4e0a\u7d2f\u52a0\uff09 \u521d\u59cb\u503c\uff1adp[0] = arc[0] \u3002 int max_successive_sub_serial_sum(int* numbers, int size) { \/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316 int* dp = new int[size]; dp[0] = numbers[0]; int max_sum = dp[0]; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179"}],"collection":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=179"}],"version-history":[{"count":2,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179\/revisions"}],"predecessor-version":[{"id":202,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179\/revisions\/202"}],"wp:attachment":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u6709\u4e00\u4e2a\u6570\u7ec4\uff0c\u59821\uff0c \uff0d5\uff0c 8\uff0c 3\uff0c \uff0d4\uff0c 15\uff0c \uff0d8\uff0c\u67e5\u627e\u5176\u4e2d\u8fde\u7eed\u548c\u6700\u5927\u7684\u76f8\u90bb\u4e32\u7684\u503c\u3002\n\u5728\u672c\u4f8b\u4e2d\uff0c\u6700\u5927\u503c\u4e3a8 \uff0b 3 \uff0b \uff0d4 \uff0b 15 \uff1d 22\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[i]\u8868\u793a\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[i] = max{ dp[i-1] + arc[i] , arc[i] }\uff0c\u5373\uff0c\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\uff0c\u8981\u4e48\u662f\u7ee7\u7eed\u7d2f\u52a0\uff0c\u8981\u4e48\u5c31\u662f\u5143\u7d20\u672c\u8eab\uff08\u91cd\u65b0\u5f00\u59cb\u4e00\u8f6e\u7d2f\u52a0\uff09\u3002\u6700\u7ec8\u7684\u6700\u5927\u503c\u662fdp\u6570\u7ec4\u4e2d\u7684\u6700\u5927\u503c\u3002\uff08\u53ef\u4ee5\u7d2f\u52a0\u4e00\u4e2a\u8d1f\u6570\uff0c\u4f46\u4e0d\u80fd\u5728\u8d1f\u6570\u4e0a\u7d2f\u52a0\uff09<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1adp[0] = arc[0] \u3002<\/p>\nint max_successive_sub_serial_sum(int* numbers, int size)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[size];\ndp[0] = numbers[0];\nint max_sum = dp[0];\n\/\/\u63a8\u7b97\nfor(int i=1;i<size;i++)\n{\n dp[i] = std::max( dp[i-1] + numbers[i] , numbers[i] );\n max_sum = dp[i]>max_sum ? dp[i] : max_sum;\n}\n\ndelete[] dp;\nreturn max_sum;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u7ef4\u62a4\u524d\u540e\u4e24\u4e2a\u5e8f\u5217\u548c<\/p>\n
int max_successive_sub_serial_sum_space(int* numbers, int size)\n{ \n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint last_sum = numbers[0];\nint max_sum = last_sum;\n\/\/\u63a8\u7b97\nfor(int i=1;i<size;i++)\n{\n int cur_sum = std::max( last_sum + numbers[i] , numbers[i] );\n max_sum = cur_sum>max_sum ? cur_sum : max_sum;\n last_sum = cur_sum;\n}\n\nreturn max_sum;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u4e8c\u7ef4\u7f51\u683c\u4e0e\u8def\u5f84<\/h3>\n\u4e00\u4e2a m x n \u7684\u4e8c\u7ef4\u7f51\u683c\uff0c\u4ece\u5de6\u4e0a\u89d2\u79fb\u52a8\u5230\u53f3\u4e0b\u89d2\uff0c\u4e00\u5171\u591a\u5c11\u79cd\u8def\u5f84\uff0c\u6bcf\u6b21\u53ea\u80fd\u5411\u53f3\u6216\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[ i ][ j ] \u662f\u5230\u8fbe\u7b2c i \u884c\u7b2c j \u5217\u7684\u8def\u5f84\u603b\u6570\uff0ci \u548c j \u4ece0\u5f00\u59cb\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[ i ][ j ] = dp[ i – 1 ][ j ] + dp[ i ][ j – 1 ]\uff0c\u5373\u8fd9\u4e00\u70b9\u53ef\u4ee5\u7531\u4e0a\u9762\u7f51\u683c\u548c\u5de6\u4fa7\u7f51\u683c\u62b5\u8fbe\uff0c\u8def\u5f84\u603b\u6570\u4e3a\u4e24\u8def\u4e4b\u548c<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1adp[ 0 ][ 0 ] … dp[ 0 ][ n-1 ] = 1\uff0cdp[ 0 ] … dp[ 0 ][ m-1 ][ 0 ] = 1\uff0c\u6700\u5de6\u4fa7\u548c\u6700\u4e0a\u9762\u7684\u7f51\u683c\u90fd\u53ea\u6709\u4e00\u6761\u8def\u5f84\u3002<\/p>\nint unique_path(int rows, int cols)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint** dp = new int*[rows];\nfor(int i=0;i<rows;i++)\n{\n dp[i] = new int[cols];\n memset(dp[i],0,cols); \/\/memset\u662f\u9010\u5b57\u8282\u521d\u59cb\u5316\uff0c\u56e0\u6b64\u53ea\u67090\u548c-1\u662f\u6b63\u5e38\u521d\u59cb\u5316\n} \n\nfor(int i=0;i<cols;i++)\n dp[0][i]=1;\n\nfor(int i=0;i<rows;i++)\n dp[i][0]=1;\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[i][j] = dp[i-1][j] + dp[i][j-1];\n\/\/\u8f93\u51fa \nint sum = dp[rows-1][cols-1];\n\nfor(int i=0;i<rows;i++)\n delete[] dp[i];\ndelete[] dp;\n\nreturn sum;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u4fdd\u5b58\u4e00\u884c\u7684\u8bb0\u5f55\uff0c\u7136\u540e\u4e0d\u65ad\u8fed\u4ee3<\/p>\n
int unique_path_space(int rows, int cols)\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[cols];\nfor(int i=0;i<cols;i++)\n dp[i] = 1;\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[j] = dp[j] + dp[j-1];\n\/\/\u8f93\u51fa \nint sum = dp[cols-1];\n\ndelete[] dp;\n\nreturn sum;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u4e8c\u7ef4\u7f51\u683c\u4e0e\u8def\u5f842 \u6700\u77ed\u8def\u5f84<\/h3>\n\u4e00\u4e2a m x n \u7684\u4e8c\u7ef4\u7f51\u683c\uff0c\u4ece\u5de6\u4e0a\u89d2\u79fb\u52a8\u5230\u53f3\u4e0b\u89d2\uff0c\u6c42\u6700\u77ed\u8def\u5f84\u957f\u5ea6\uff0c\u6bcf\u6b21\u53ea\u80fd\u5411\u53f3\u6216\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u3002<\/code><\/pre>\n\n- \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20<\/strong>\uff1adp[ i ][ j ] \u4e3a\u5230\u8fbe\u7b2c i \u884c\u7b2c j \u5217\u7684\u6700\u77ed\u8def\u5f84\u3002<\/li>\n
- \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb<\/strong>\uff1adp[ i ][ j ] = min{ dp[ i – 1 ][ j ] + arc[ i ][ j ] , dp[ i ][ j-1 ] + arc[ i ][ j ] }\u3002<\/li>\n
- \n
\u521d\u59cb\u503c<\/strong>\uff1a
\ndp[ 0 ][ 0 ] = arc[ 0 ][ 0 ]
\ndp[ 0 ][ j ] = dp[ 0 ][ j – 1 ] + arc[ 0 ][ j ]
\ndp[ i ][ 0 ] = dp[ i – 1 ][ 0 ] + arc[ i ][ 0 ]<\/p>\nint unique_path_shortest(int** map, int rows, int cols )\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint** dp = new int*[rows];\nfor(int i=0;i<rows;i++)\n{\n dp[i] = new int[cols];\n memset(dp[i],0,cols); \n}\n\ndp[0][0] = map[0][0]; \nfor(int i=1;i<cols;i++)\n dp[0][i] = dp[0][i-1] + map[0][i];\nfor(int i=1;i<rows;i++)\n dp[i][0] = dp[i-1][0] + map[i][0];\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n for(int j=1;j<cols;j++)\n dp[i][j] = std::min(dp[i-1][j] + map[i][j] , dp[i][j-1] + map[i][j]);\n\/\/\u8f93\u51fa\nint sum_shortest = dp[rows-1][cols-1];\n\nfor(int i=0;i<rows;i++)\n delete[] dp[i];\ndelete[] dp;\n\nreturn sum_shortest;\n}<\/code><\/pre>\n<\/li>\n- \n
\u4f18\u5316\u7a7a\u95f4\u590d\u6742\u5ea6\uff1a\u53ea\u4fdd\u5b58\u4e00\u884c\u7684\u8bb0\u5f55\uff0c\u7136\u540e\u4e0d\u65ad\u8fed\u4ee3<\/p>\n
int unique_path_shortest_space(int** map, int rows, int cols )\n{\n\/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316\nint* dp = new int[cols];\ndp[0] = map[0][0]; \nfor(int i=1;i<cols;i++)\n dp[i] = dp[i-1] + map[0][i];\n\/\/\u63a8\u7b97\nfor(int i=1;i<rows;i++)\n{\n dp[0] = dp[0] + map[i][0];\n for(int j=1;j<cols;j++)\n dp[j] = std::min(dp[j] + map[i][j] , dp[j-1] + map[i][j]);\n}\n\/\/\u8f93\u51fa\nint sum_shortest = dp[cols-1];\n\ndelete[] dp;\n\nreturn sum_shortest;\n}<\/code><\/pre>\n<\/li>\n<\/ol>\n\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\uff08LIS\uff09<\/h3>\n
\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\uff08LIS\uff09<\/a><\/p>\n2\u3001\u6392\u5e8f<\/h2>\n
\n\n\n\u6392\u5e8f<\/th>\n \u63d2\u5165\u6392\u5e8f<\/th>\n \u5192\u6ce1\u6392\u5e8f<\/th>\n \u5f52\u5e76\u6392\u5e8f<\/th>\n \u5feb\u901f\u6392\u5e8f<\/th>\n<\/tr>\n<\/thead>\n \n\n\u57fa\u672c\u601d\u60f3<\/td>\n \u81ea\u7b2c\u4e8c\u4e2a\u8bb0\u5f55\u5f00\u59cb\uff0c\u6709\u5e8f\u524d\u63d2<\/td>\n \u76f8\u90bb\u5143\u7d20\u6bd4\u8f83\uff0c\u9006\u5e8f\u4ea4\u6362\uff0c\u9010\u904d\u628a\u6700\u5927\u503c\u79fb\u81f3\u6700\u540e<\/td>\n \u76f8\u90bb\u4e24\u4e2a\/\u591a\u4e2a\u987a\u5e8f\u8868\u5408\u5e76\uff0c\u521d\u59cb\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u4e00\u4e2a\u987a\u5e8f\u8868<\/td>\n \u4e24\u4fa7\u4f9d\u6b21\u626b\u63cf\uff0c\u5c06\u8f74\u503c\u79fb\u81f3\u6b63\u786e\u4f4d\u7f6e<\/td>\n<\/tr>\n \n\u65f6\u95f4\u590d\u6742\u5ea6<\/td>\n n~n^2<\/td>\n n~n^2<\/td>\n nlbn<\/td>\n nlbn~n^2<\/td>\n<\/tr>\n \n\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6<\/td>\n n^2<\/td>\n n^2<\/td>\n nlbn<\/td>\n nlbn<\/td>\n<\/tr>\n \n\u7a7a\u95f4\u590d\u6742\u5ea6<\/td>\n 1<\/td>\n 1<\/td>\n n<\/td>\n lbn~n<\/td>\n<\/tr>\n \n\u5e94\u7528\/\u4f18\u5316<\/td>\n \u9002\u7528\u4e8e\u5143\u7d20\u6570\u91cf\u5c11\uff0c\u4e14\u57fa\u672c\u6709\u5e8f\uff0c\u6539\u8fdb\uff1a\u5206\u5272\uff0c\u5206\u522b\u76f4\u63d2\uff0c\u57fa\u672c\u6709\u5e8f\u540e\u5168\u4f53\u76f4\u63d2<\/td>\n \u53cc\u5411\u8d77\u6ce1<\/td>\n \u76f8\u90bb-\u4e00\u8d9f-\u9012\u5f52<\/td>\n \u9012\u5f52\u6b21\u6570-\u7a7a\u95f4\u590d\u6742\u5ea6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\u5feb\u901f\u6392\u5e8f<\/h3>\n
\u5c06\u5f85\u6392\u6570\u7ec4\u4e0d\u65ad\u5206\u6210\u4e24\u90e8\u5206\uff0c\u5206\u522b\u6392\u5e8f<\/p>\n
int partition(int arr[], int start, int end)\n{\n int mid = arr[start];\n int i = start;\n int j = end;\n\n while(i<j){\n \/\/\u53f3\u4fa7\u626b\u63cf\uff0c\u5c06\u5c0f\u4e8e\u8f74\u503c\u7684\u5143\u7d20\u79fb\u5230\u5de6\u4fa7\n while(i<j && arr[j]>mid)\n j--;\n if(i<j){\n arr[i] = arr[j];\n i++;\n }\n\n \/\/\u5de6\u4fa7\u626b\u63cf\uff0c\u5c06\u5927\u4e8e\u8f74\u503c\u7684\u5143\u7d20\u79fb\u5230\u53f3\u4fa7\n while(i<j && arr[i]<mid)\n i++;\n if(i<j){\n arr[j] = arr[i];\n j--;\n }\n }\n arr[i] = mid;\n return i;\n}\n\nvoid quick_sort(int arr[], int start, int end)\n{\n int mid_index = partition(arr, start, end);\n if(start < mid_index)\n quick_sort(arr, start, mid_index-1);\n if(mid_index < end)\n quick_sort(arr, mid_index+1,end);\n}<\/code><\/pre>\n3\u3001\u67e5\u627e<\/h2>\n\u4e8c\u5206\u67e5\u627e<\/h3>\n
\u590d\u6742\u5ea6 lgn<\/p>\n
bool binary_search(int arr[], int length, int num)\n{\n int start = 0;\n int end = length-1;\n int mid = (start+end)\/2;\n\n while(start<=end)\n {\n if(arr[mid]==num)\n return true;\n else if(arr[mid]>num)\n end = mid - 1;\n else\n start = mid + 1;\n\n mid = (start+end)\/2;\n }\n\n return false;\n}<\/code><\/pre>\n\u4e8c\u53c9\u6392\u5e8f\u6811<\/h3>\n
\u590d\u6742\u5ea6 lgn~n<\/p>\n
myNode* searchSortBiTree(myNode* root, int k)\n{\n if(root == nullptr)\n return nullptr;\n else if(root->data == k)\n return root;\n else if(root->data > k)\n return searchSortBiTree(root->leftChild, k);\n else\n return searchSortBiTree(root->rightChild, k);\n}<\/code><\/pre>\n4\u3001\u4e8c\u53c9\u6811<\/h2>\nstruct myNode\n{\n int data;\n myNode* leftChild;\n myNode* rightChild;\n int flag;\n};<\/code><\/pre>\n\u6811\u7684\u6784\u9020\u4e0e\u91ca\u653e<\/h3>\n
\u6309\u5c42\u5e8f\u904d\u5386\u7684\u65b9\u5f0f\u6784\u9020\u3002<\/p>\n
myNode* createBiTree(int values[], int length)\n{\n queue<myNode*> nodes;\n int cnt = 0;\n\n myNode* n = new myNode;\n n->data = values[0];\n nodes.push(n);\n cnt++;\n\n while(cnt<length)\n {\n myNode* top = nodes.front();\n nodes.pop();\n\n myNode* left_n = new myNode;\n left_n->data = values[cnt];\n\n nodes.push(left_n);\n top->leftChild = left_n;\n cnt++;\n\n if(cnt==length)\n break;\n\n myNode* right_n = new myNode;\n right_n->data = values[cnt];\n nodes.push(right_n);\n top->rightChild = right_n;\n cnt++;\n }\n\n return n;\n}\n\nvoid releaseBiTree(myNode* n) \n{\n \/*\u6309\u7167\u540e\u5e8f\u904d\u5386\u7684\u987a\u5e8f\u91ca\u653e\u4e8c\u53c9\u6811*\/\n if(n != NULL) \n { \n releaseBiTree(n->leftChild); \/*\u91ca\u653e\u5de6\u5b50\u6811*\/\n releaseBiTree(n->rightChild); \/*\u91ca\u653e\u53f3\u5b50\u6811*\/\n delete n; \/*\u5220\u9664\u6839\u7ed3\u70b9*\/\n } \n}<\/code><\/pre>\n\u524d\u5e8f\u904d\u5386<\/h3>\n\/\/ \u975e\u9012\u5f52\uff1a\u6808\nvoid frontPrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n != nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n nodes.push(n);\n cout<<n->data<<\" \";\n n = n->leftChild;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid frontPrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n frontPrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n frontPrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n }\n}<\/code><\/pre>\n\u4e2d\u5e8f\u904d\u5386<\/h3>\n\/\/ \u975e\u9012\u5f52\uff1a\u6808\nvoid middlePrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n != nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n nodes.push(n);\n n = n->leftChild;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid middlePrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n middlePrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n middlePrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n }\n}<\/code><\/pre>\n\u540e\u5e8f\u904d\u5386<\/h3>\nvoid backPrintBiTree(myNode* root)\n{\n stack<myNode*> nodes;\n myNode* n = root;\n\n while(n!=nullptr || nodes.empty()!=1)\n {\n while(n != nullptr)\n {\n n->flag = 1;\n nodes.push(n);\n n = n->leftChild;\n }\n\n while(nodes.empty()!=1 && nodes.top()->flag==2)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n\n if(n==root)\n return;\n }\n\n if(nodes.empty()!=1)\n {\n n = nodes.top();\n n->flag = 2;\n n = n->rightChild;\n }\n }\n}\n\n\/\/ \u9012\u5f52\nvoid backPrintBiTree_recursion(myNode* root) \n{\n if(root == NULL) \/*\u9012\u5f52\u8c03\u7528\u7684\u8fb9\u754c\u6761\u4ef6*\/\n return;\n else \n { \n backPrintBiTree_recursion(root->leftChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u5de6\u5b50\u6811*\/\n backPrintBiTree_recursion(root->rightChild); \/*\u524d\u5e8f\u9012\u5f52\u904d\u5386\u53f3\u5b50\u6811*\/\n cout<<root->data<<\" \"; \/*\u8bbf\u95ee\u6839\u7ed3\u70b9*\/\n }\n}<\/code><\/pre>\n\u5c42\u5e8f\u904d\u5386<\/h3>\nvoid levelPrintBiTree(myNode* root)\n{\n queue<myNode*> nodes;\n myNode* n = root;\n nodes.push(n);\n\n while(nodes.empty()!=1)\n {\n n = nodes.top();\n nodes.pop();\n cout<<n->data<<\" \";\n if(n->leftChild != nullptr)\n nodes.push(n->leftChild);\n if(n->rightChild != nullptr)\n nodes.push(n->rightChild);\n }\n}<\/code><\/pre>\nZ\u5b57\u904d\u5386<\/h3>\nvoid ZPrintBiTree(myNode* root)\n{\n queue<myNode*> nodes_que;\n stack<myNode*> nodes_sta;\n int line = 1;\n int cnt = 0;\n\n queue<myNode*> nodes;\n myNode* n = root;\n nodes.push(n);\n\n while(nodes.empty()!=1)\n {\n \/\/\u5c42\u5e8f\u904d\u5386\n n = nodes.front();\n nodes.pop();\n if(n->leftChild != nullptr)\n nodes.push(n->leftChild);\n if(n->rightChild != nullptr)\n nodes.push(n->rightChild);\n\n \/\/Z\u5b57\u904d\u5386\n cnt++;\n if(line%2 == 1)\n {\n nodes_que.push(n);\n if(cnt==pow(2,line-1))\n {\n line++;\n cnt=0;\n while(nodes_que.empty()!=1)\n {\n cout<<nodes_que.front()->data<<\" \";\n nodes_que.pop();\n }\n }\n }\n else\n {\n nodes_sta.push(n);\n if(cnt==pow(2,line-1))\n {\n line++;\n cnt=0;\n while(nodes_sta.empty()!=1)\n {\n cout<<nodes_sta.top()->data<<\" \";\n nodes_sta.pop();\n }\n }\n } \n }\n \/\/\u6ca1\u6253\u5370\u7684\u6253\u5370\u5b8c\n while(nodes_que.empty()!=1)\n {\n cout<<nodes_que.front()->data<<\" \";\n nodes_que.pop();\n }\n while(nodes_sta.empty()!=1)\n {\n cout<<nodes_sta.top()->data<<\" \";\n nodes_sta.pop();\n }\n}<\/code><\/pre>\n\u91cd\u5efa\u4e8c\u53c9\u6811\uff1a\u524d\u5e8f+\u4e2d\u5e8f<\/h3>\nmyNode* createBiTreeByFrontMid(int* frontValues, int* midValues, int length)\n{\n if(length==0)\/\/\u53ea\u9488\u5bf9\u7b2c\u4e00\u6b21\u4f7f\u7528\n return nullptr;\n\n myNode* root = new myNode;\/\/\u786e\u5b9a\u8fd9\u4e00\u6bb5\u7684\u6839\u8282\u70b9\uff0c\u7136\u540e\u5212\u5206\u5de6\u53f3\u4e24\u5b50\u6811\n root->data = frontValues[0];\n root->leftChild = nullptr;\n root->rightChild = nullptr;\n\n int i;\n for(i=0;i<length && midValues[i]!=frontValues[0];i++)\n ;\n\n int leftLength = i;\n int rightLength = length-i-1;\n\n if(leftLength>0)\n root->leftChild = createBiTreeByFrontMid(&frontValues[1], &midValues[0], leftLength);\n if(rightLength>0)\n root->rightChild = createBiTreeByFrontMid(&frontValues[leftLength+1], &midValues[leftLength+1], rightLength);\n\n return root;\n}<\/code><\/pre>\n\u91cd\u5efa\u4e8c\u53c9\u6811\uff1a\u4e2d\u5e8f+\u540e\u5e8f<\/h3>\nmyNode* createBiTreeByBackMid(int* backValues, int* midValues, int length)\n{\n if(length==0)\/\/\u53ea\u9488\u5bf9\u7b2c\u4e00\u6b21\u4f7f\u7528\n return nullptr;\n\n myNode* root = new myNode;\/\/\u786e\u5b9a\u8fd9\u4e00\u6bb5\u7684\u6839\u8282\u70b9\uff0c\u7136\u540e\u5212\u5206\u5de6\u53f3\u4e24\u5b50\u6811\n root->data = backValues[length-1];\n root->leftChild = nullptr;\n root->rightChild = nullptr;\n\n int i;\n for(i=0;i<length && midValues[i]!=backValues[length-1];i++)\n ;\n\n int leftLength = i;\n int rightLength = length-i-1;\n\n if(leftLength>0)\n root->leftChild = createBiTreeByBackMid(&backValues[0], &midValues[0], leftLength);\n if(rightLength>0)\n root->rightChild = createBiTreeByBackMid(&backValues[leftLength], &midValues[leftLength+1], rightLength);\n\n return root;\n}<\/code><\/pre>\n\u4e8c\u53c9\u6392\u5e8f\u6811<\/h3>\n
\u4e8c\u53c9\u6392\u5e8f\u6811\uff1a\u7a7a\u6811\u6216\u975e\u7a7a\u6811\uff0c\u975e\u7a7a\u6811\u6ee1\u8db3\u5de6\u5b50\u6811\u6240\u6709\u8282\u70b9\u5c0f\u4e8e\u6839\u8282\u70b9\uff0c\u53f3\u5b50\u6811\u6240\u6709\u8282\u70b9\u5927\u4e8e\u6839\u8282\u70b9\uff0c\u5de6\u53f3\u5b50\u6811\u53c8\u662f\u4e8c\u53c9\u6392\u5e8f\u6811\u3002<\/p>\n
\u63d2\u5165<\/h4>\nvoid insertSortBiTree(myNode* &root, myNode* newNode)\n{\n if(root==nullptr)\n root = newNode;\n else if(root->data > newNode->data)\n insertSortBiTree(root->leftChild, newNode);\n else\n insertSortBiTree(root->rightChild, newNode);\n}<\/code><\/pre>\n\u6784\u9020<\/h4>\nmyNode* createSortBiTree(int data[], int n)\n{\n myNode* root = nullptr;\n myNode* newNode;\n for(int i=0;i<n;i++)\n {\n newNode = new myNode;\n newNode->data = data[i];\n newNode->leftChild = nullptr;\n newNode->rightChild = nullptr;\n insertSortBiTree(root, newNode);\n }\n return root;\n}<\/code><\/pre>\n5\u3001\u961f\u5217\u4e0e\u6808<\/h2>\n\u4e24\u4e2a\u961f\u5217\u5b9e\u73b0\u6808<\/h3>\nclass myStack\n{\n private:\n queue<int> que1;\n queue<int> que2;\n\n public:\n myStack();\n ~myStack(){};\n\n void push(int);\n void pop();\n int top();\n};\n\nmyStack::myStack(){}\nvoid myStack::push(int data)\/\/\u5728\u975e\u7a7a\u7684\u961f\u5217\u672b\u5c3e\u6dfb\u52a0\u65b0\u5143\u7d20\n{\n if(que1.empty())\n que2.push(data);\n else\n que1.push(data);\n}\n\nvoid myStack::pop()\/\/\u5c06\u975e\u7a7a\u961f\u5217\u5143\u7d20\u8f6c\u79fb\u5230\u7a7a\u961f\u5217\uff0c\u7559\u6700\u540e\u4e00\u4e2a\u5f39\u51fa\n{\n if(que1.empty() && que2.empty())\n return ;\n\n if(que1.empty())\n {\n while(que2.size()!=1)\n {\n que1.push(que2.front());\n que2.pop();\n }\n que2.pop();\n }\n else\n {\n while(que1.size()!=1)\n {\n que2.push(que1.front());\n que1.pop();\n }\n que1.pop();\n } \n}\n\nint myStack::top()\/\/\u5c06\u975e\u7a7a\u961f\u5217\u5143\u7d20\u8f6c\u79fb\u5230\u7a7a\u961f\u5217\uff0c\u6700\u540e\u4e00\u4e2a\u8f93\u51fa\n{\n if(que1.empty() && que2.empty())\n return -1;\n\n int out;\n if(que1.empty())\n {\n while(que2.size()!=1)\n {\n que1.push(que2.front());\n que2.pop();\n }\n out = que2.front();\n que1.push(out);\n que2.pop();\n }\n else\n {\n while(que1.size()!=1)\n {\n que2.push(que1.front());\n que1.pop();\n }\n out = que1.front();\n que2.push(out);\n que1.pop();\n }\n return out;\n}<\/code><\/pre>\n\u4e24\u4e2a\u6808\u5b9e\u73b0\u961f\u5217<\/h3>\nclass myQueue\n{\n private:\n stack<int> sta1;\/\/\u5b58\n stack<int> sta2;\/\/\u53d6\n\n public:\n myQueue();\n ~myQueue(){};\n\n void push(int);\n void pop();\n int front();\n};\n\nmyQueue::myQueue(){}\nvoid myQueue::push(int data)\n{\n sta1.push(data);\n}\n\nvoid myQueue::pop()\n{\n if(sta1.empty())\n return ;\n\n while(sta1.size()!=1)\n { \n sta2.push(sta1.top());\n sta1.pop();\n }\n\n sta1.pop(); \n\n while(sta2.size()!=0) \n {\n sta1.push(sta2.top());\n sta2.pop();\n } \n}\nint myQueue::front()\n{\n if(sta1.empty())\n return -1;\n\n while(sta1.size()!=1)\n { \n sta2.push(sta1.top());\n sta1.pop();\n }\n\n int out = sta1.top();\n sta2.push(out);\n sta1.pop(); \n\n while(sta2.size()!=0) \n {\n sta1.push(sta2.top());\n sta2.pop();\n } \n\n return out;\n}<\/code><\/pre>\n\u5faa\u73af\u961f\u5217*<\/h3>\n
\u76f8\u5bf9\u4e8e\u76f4\u7ebf\u961f\u5217\u6765\u8bb2\uff0c\u76f4\u7ebf\u961f\u5217\u5728\u5143\u7d20\u51fa\u961f\u540e\uff0c\u5934\u6307\u9488\u5411\u540e\u79fb\u52a8\uff0c\u5bfc\u81f4\u5220\u9664\u5143\u7d20\u540e\u7684\u7a7a\u95f4\u65e0\u6cd5\u5728\u5229\u7528\uff0c\u5373\u4f7f\u5143\u7d20\u4e2a\u6570\u5c0f\u4e8e\u7a7a\u95f4\u5927\u5c0f\uff0c\u4f9d\u7136\u65e0\u6cd5\u518d\u8fdb\u884c\u63d2\u5165\uff0c\u5373\u6240\u8c13\u7684\u201c\u5047\u4e0a\u6ea2\u201d\u3002\u5f53\u53d8\u6210\u5faa\u73af\u961f\u5217\u4e4b\u540e\uff0c\u5220\u9664\u5143\u7d20\u540e\u7684\u7a7a\u95f4\u4ecd\u7136\u53ef\u4ee5\u5229\u7528\uff0c\u6700\u5927\u9650\u5ea6\u7684\u5229\u7528\u7a7a\u95f4\u3002<\/p>\n
6\u3001\u56fe<\/h2>\n\u6df1\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\nvoid DFS_recursion(int curVertex, int vertexNum, vector<int>* arc, vector<int>* visited)\n{\n (*visited)[curVertex] = 1; \/\/\u6807\u8bb0\u8be5\u6b21\u904d\u5386\u7684\u9876\u70b9\n cout<<curVertex<<\" \";\n for(int i=0; i<vertexNum;i++) \/\/\u904d\u5386\u8be5\u9876\u70b9\u8fde\u63a5\u7684\u5176\u4ed6\u9876\u70b9\n if((*visited)[i]==0 && (*arc)[curVertex*vertexNum+i]==1)\n DFS_recursion(i, vertexNum, arc, visited); \n}\n\nvoid DFS(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u6240\u6709\u9876\u70b9\u672a\u88ab\u904d\u5386\n vector<int> visited; \n for(int i=0;i<vertexNum; i++)\n visited.push_back(0);\n\n\/\/\u6df1\u5ea6\u904d\u5386\n for(int i=0; i<vertexNum; i++)\/\/\u4ece\u7b2ci\u4e2a\u9876\u70b9\u5f00\u59cb\u7684\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n {\n if(visited[i]==0)\n DFS_recursion(i, vertexNum, arc, &visited);\n }\n}<\/code><\/pre>\n\u5e7f\u5ea6\u4f18\u5148\u904d\u5386<\/h3>\nvoid BFS(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u6240\u6709\u9876\u70b9\u672a\u88ab\u904d\u5386\n vector<int> visited; \n for(int i=0;i<vertexNum; i++)\n visited.push_back(0);\n\n\/\/\u5e7f\u5ea6\u904d\u5386\n queue<int> q;\n for(int i=0;i<vertexNum; i++)\/\/\u4ece\u7b2ci\u4e2a\u9876\u70b9\u5f00\u59cb\u7684\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n {\n if(visited[i]==0)\n {\n q.push(i);\n visited[i]=1;\n\n while(q.empty()!=1)\n {\n int v = q.front();\n q.pop();\n cout<<v<<\" \";\n\n for(int j=0; j<vertexNum; j++)\n if(visited[j]==0 && (*arc)[v*vertexNum+j]==1)\n {\n q.push(j);\n visited[j]=1;\n }\n }\n }\n }\n}<\/code><\/pre>\n\u6700\u5c0f\u751f\u6210\u6811<\/h3>\n
n\u4e2a\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\uff0c\u76ee\u6807\u4f7f\u5f97\u4efb\u610f\u4e24\u4e2a\u57ce\u5e02\u4e92\u901a\uff0c\u4e0d\u540c\u57ce\u5e02\u4e4b\u95f4\u94fa\u8bbe\u7535\u7f06\u4ee3\u4ef7\u4e0d\u540c\uff0c\u6c42\u4ee3\u4ef7\u6700\u5c0f\u7684\u94fa\u8bbe\u65b9\u6cd5\u3002<\/p>\n
Prim<\/h4>\n
\u5411\u6700\u5c0f\u751f\u6210\u6811\u6dfb\u52a0\u70b9\u3002<\/p>\n
void Prim(int vertexNum, vector<int>* arc)\n{\n\/\/\u521d\u59cb\u5316\u5019\u9009\u6700\u77ed\u8fb9\u96c6\n vector<int> connectCost; \/\/\u5019\u9009\u6700\u77ed\u8fb9\u96c6\uff1a\u5019\u9009\u9876\u70b9\u5230\u6b63\u5f0f\u9876\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7 \u4ee3\u4ef7\u4e3a0\uff0c\u5373\u9009\u4e3a\u6b63\u5f0f\u9876\u70b9\n vector<int> connectVertex; \/\/\u5019\u9009\u6700\u77ed\u8fb9\u96c6\uff1a\u6700\u5c0f\u4ee3\u4ef7\u5bf9\u5e94\u7684\u6b63\u5f0f\u9876\u70b9 \u627e\u5185\u63a8\uff1f\n\n for(int i=0;i<vertexNum;i++)\n {\n connectCost.push_back((*arc)[0*vertexNum + i]); \/\/\u9ed8\u8ba4\u5230\u81ea\u8eab\u7684\u4ee3\u4ef7\u4e3a0\uff0c\u56e0\u6b640\u53f7\u9876\u70b9\u521d\u59cb\u5316\u5373\u9009\u4e3a\u6b63\u5f0f\u9876\u70b9\n connectVertex.push_back(0);\n }\n\n\/\/\u6700\u5c0f\u751f\u6210\u6811\uff1a\u6bcf\u6b21\u52a0\u5165\u4e00\u4e2a\u6b63\u5f0f\u9876\u70b9\uff0c\u5e76\u66f4\u65b0\u5019\u9009\u6700\u77ed\u8fb9\u96c6\n for(int m=1;m<vertexNum;m++)\n {\n \/\/\u904d\u5386\u6700\u77ed\u8fb9\u96c6\uff0c\u627e\u5230\u6700\u6700\u77ed\u7684\u4e00\u4e2a\n int k=0;\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0)\n {\n k=i; break;\n }\n\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0 && connectCost[i]<connectCost[k])\n k=i;\n\n if(connectCost[k]==0)\/\/\u627e\u4e00\u5708\u53d1\u73b0\u5747\u5df2\u6dfb\u52a0\u5230\u6b63\u5f0f\u9876\u70b9\u4e2d\uff0c\u5219\u9000\u51fa\n return ;\n\n cout<<\"(\"<<connectVertex[k]<<\"->\"<<k<<\")-cost-\"<<connectCost[k]<<\" \";\n \/\/\u628a\u7b2ck\u4e2a\u9876\u70b9\u52a0\u5165\u6b63\u5f0f\u9876\u70b9\u4e2d\n connectCost[k]=0; \n \/\/\u770b\u770b\u5269\u4e0b\u7684\u5019\u9009\u8282\u70b9\u662f\u4e0d\u662f\u5230k\u7684\u4ee3\u4ef7\u66f4\u5c0f\n for(int i=0;i<vertexNum;i++)\n if(connectCost[i]!=0 && connectCost[i]>(*arc)[k*vertexNum + i])\n {\n connectCost[i] = (*arc)[k*vertexNum + i]; \n connectVertex[i] = k;\n }\n } \n}<\/code><\/pre>\nKruscal<\/h4>\n
\u5411\u6700\u5c0f\u751f\u6210\u6811\u6dfb\u52a0\u8fb9\u3002<\/p>\n
struct Edge\n{\n int vertexA;\n int vertexB;\n int cost;\n};\nbool cmp(const Edge &a,const Edge &b)\n{\n return (a.cost) < (b.cost);\n}\nint find_parent(int v, vector<int> &parents)\n{\n return parents[v]==v ? v : find_parent(parents[v], parents);\/\/\u9012\u5f52\u627e\u5230\u9876\u5c42\u53cc\u4eb2\n}\nvoid Kruscal(int vertexNum, vector<int>* arc)\n{\n\/\/\u6570\u636e\u51c6\u5907\n vector<Edge> edges;\n for(int i=0;i<vertexNum;i++)\n for(int j=i+1;j<vertexNum;j++)\n if((*arc)[i*vertexNum + j] < 100)\n {\n Edge edge;\n edge.vertexA = i;\n edge.vertexB = j;\n edge.cost = (*arc)[i*vertexNum + j];\n edges.push_back(edge);\n }\n\/\/Kruscal\n \/\/\u8fb9\u96c6\u6570\u7ec4\u521d\u59cb\u5316:\u5347\u5e8f\u6392\u5217\n sort(edges.begin(),edges.end(),cmp);\n\n \/\/\u9876\u5c42\u53cc\u4eb2\u521d\u59cb\u5316\uff1a\u7528\u4e8e\u5224\u65ad\u67d0\u4e00\u8fb9\u7684\u4e24\u9876\u70b9\u662f\u5426\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n vector<int> parents;\n for(int i=0;i<vertexNum;i++)\n parents.push_back(i);\/\/\u521d\u59cb\u5316\u6bcf\u4e2a\u9876\u70b9\u81ea\u6210\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\uff0c\u5176\u53cc\u4eb2\u4e3a\u81ea\u8eab\n\n \/\/\u6700\u5c0f\u751f\u6210\u6811\uff1a\u6bcf\u6b21\u6dfb\u52a0\u4e00\u6761\u8fb9\n for(int i=0;i<edges.size();i++)\n {\n \/\/\u62ff\u51fa\u4e00\u6761\u8fb9\uff0c\u5224\u65ad\u662f\u5426\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf:\u5224\u65ad\u9876\u5c42\u53cc\u4eb2\u662f\u5426\u76f8\u540c\n Edge e = edges[i];\n if(find_parent(e.vertexA, parents) != find_parent(e.vertexB, parents))\n {\n parents[find_parent(e.vertexB, parents)]=find_parent(e.vertexA, parents);\n cout<<\"(\"<<e.vertexA<<\"->\"<<e.vertexB<<\")-cost-\"<<e.cost<<\" \";\n }\n }\n}<\/code><\/pre>\n7\u3001\u5e77\u67e5\u96c6<\/h2>\n\n\u9898\u76ee\u80cc\u666f
\n\u82e5\u67d0\u4e2a\u5bb6\u65cf\u4eba\u5458\u8fc7\u4e8e\u5e9e\u5927\uff0c\u8981\u5224\u65ad\u4e24\u4e2a\u662f\u5426\u662f\u4eb2\u621a\uff0c\u786e\u5b9e\u8fd8\u5f88\u4e0d\u5bb9\u6613\uff0c\u73b0\u5728\u7ed9\u51fa\u67d0\u4e2a\u4eb2\u621a\u5173\u7cfb\u56fe\uff0c\u6c42\u4efb\u610f\u7ed9\u51fa\u7684\u4e24\u4e2a\u4eba\u662f\u5426\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u9898\u76ee\u63cf\u8ff0
\n\u89c4\u5b9a\uff1ax\u548cy\u662f\u4eb2\u621a\uff0cy\u548cz\u662f\u4eb2\u621a\uff0c\u90a3\u4e48x\u548cz\u4e5f\u662f\u4eb2\u621a\u3002\u5982\u679cx,y\u662f\u4eb2\u621a\uff0c\u90a3\u4e48x\u7684\u4eb2\u621a\u90fd\u662fy\u7684\u4eb2\u621a\uff0cy\u7684\u4eb2\u621a\u4e5f\u90fd\u662fx\u7684\u4eb2\u621a\u3002
\n\u8f93\u5165\u683c\u5f0f
\n\u7b2c\u4e00\u884c\uff1a\u4e09\u4e2a\u6574\u6570n,m,p\uff0c\uff08n<=5000,m<=5000,p<=5000\uff09\uff0c\u5206\u522b\u8868\u793a\u6709n\u4e2a\u4eba\uff0cm\u4e2a\u4eb2\u621a\u5173\u7cfb\uff0c\u8be2\u95eep\u5bf9\u4eb2\u621a\u5173\u7cfb\u3002
\n\u4ee5\u4e0bm\u884c\uff1a\u6bcf\u884c\u4e24\u4e2a\u6570Mi\uff0cMj\uff0c1<=Mi\uff0cMj<=N\uff0c\u8868\u793aMi\u548cMj\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u63a5\u4e0b\u6765p\u884c\uff1a\u6bcf\u884c\u4e24\u4e2a\u6570Pi\uff0cPj\uff0c\u8be2\u95eePi\u548cPj\u662f\u5426\u5177\u6709\u4eb2\u621a\u5173\u7cfb\u3002
\n\u8f93\u51fa\u683c\u5f0f
\nP\u884c\uff0c\u6bcf\u884c\u4e00\u4e2a\u2019Yes\u2019\u6216\u2019No\u2019\u3002\u8868\u793a\u7b2ci\u4e2a\u8be2\u95ee\u7684\u7b54\u6848\u4e3a\u201c\u5177\u6709\u201d\u6216\u201c\u4e0d\u5177\u6709\u201d\u4eb2\u621a\u5173\u7cfb\u3002<\/p>\n<\/blockquote>\n
\n- \u5e77\u67e5\u96c6\u7684\u4e24\u79cd\u64cd\u4f5c\uff1a\u67e5\u8be2\u662f\u5426\u5728\u540c\u4e00\u96c6\u5408\uff0c\u5408\u5e76\u4e0d\u540c\u96c6\u5408<\/li>\n
- \u5e77\u67e5\u96c6\u7684\u601d\u60f3\uff1a\u6bcf\u4e2a\u96c6\u5408\u786e\u5b9a\u4e00\u4e2a\u4ee3\u8868\u5143\u7d20\uff0c\u5f62\u6210\u4e00\u4e2a\u6811\u72b6\u7ed3\u6784\uff0c\u4ee3\u8868\u5143\u7d20\u4e3a\u6839\u8282\u70b9\uff0c\u5176\u4ed6\u5143\u7d20\u4e3a\u5b50\u8282\u70b9\u3002\u96c6\u5408\u7684\u5408\u5e76\u5c31\u662f\u4e00\u4e2a\u96c6\u5408\u7684\u6839\u8282\u70b9\u6210\u4e3a\u53e6\u4e00\u4e2a\u96c6\u5408\u7684\u5b50\u8282\u70b9\u3002\u96c6\u5408\u7684\u67e5\u8be2\u5c31\u662f\u4e0d\u65ad\u627e\u7236\u8282\u70b9\uff0c\u76f4\u5230\u627e\u5230\u6839\u8282\u70b9\uff0c\u5224\u65ad\u6839\u8282\u70b9\u662f\u5426\u76f8\u540c\u3002<\/li>\n
- \u5e77\u67e5\u96c6\u5e94\u7528\uff1a\u6700\u5c0f\u751f\u6210\u6811\u7684Kruscal\u65b9\u6cd5\u3002<\/li>\n
- \u5e77\u67e5\u96c6\u7684\u521d\u59cb\u5316\uff0c\u5408\u5e76\u548c\u67e5\u8be2\n
int parent[NMAX]\nvoid init(int n) \/\/\u521d\u59cb\u5316\u4e3a\u672c\u8eab\n{\nfor(int i=0;i<n;i++)\n parent[i]=i;\n}\nint find(int i)\n{\nreturn parent[i]==i ? i : find(parent[i]); \/\/\u4e0d\u65ad\u5411\u4e0a\u67e5\u8be2\u7236\u8282\u70b9\uff0c\u76f4\u5230\u6240\u5c5e\u7ed3\u5408\u7684\u6839\u8282\u70b9\n}\nint merge(int i, int j)\n{\nparent[find(i)] = find(j);\/\/\u628ai\u6240\u5c5e\u96c6\u5408\u7684\u6839\u8282\u70b9\uff0c\u53d8\u6210j\u6240\u5c5e\u96c6\u5408\u6839\u8282\u70b9\u7684\u5b50\u8282\u70b9\n}<\/code><\/pre>\n<\/li>\n- \u538b\u7f29\uff1a\u67e5\u8be2\u8fc7\u7a0b\u4e2d\u5c06\u5176\u7236\u8282\u70b9\u6362\u6210\u6839\u8282\u70b9\uff0c\u51cf\u5c11\u9012\u5f52\u6b21\u6570\uff0c\u56e0\u4e3a\u53ea\u5728\u67e5\u8be2\u65f6\u538b\u7f29\uff0c\u56e0\u6b64\u672a\u5fc5\u6bcf\u4e2a\u96c6\u5408\u9664\u4e86\u6839\u8282\u70b9\uff0c\u5168\u662f\u53f6\u5b50\u8282\u70b9\n
int find(int i)\n{\nreturn parent[i]==i ? i : ( parent[i] = find(parent[i]) ); \/\/\u67e5\u8be2\u8fc7\u7a0b\u4e2d\u5c06\u5176\u7236\u8282\u70b9\u6362\u6210\u6839\u8282\u70b9\n}<\/code><\/pre>\n<\/li>\n- \u6309\u79e9\u5408\u5e76\uff1a\u628a\u7b80\u5355\u6811\u5408\u5e76\u5230\u590d\u6742\u6811
\n\u7b97\u6cd5\u5b66\u4e60\u7b14\u8bb0(1) : \u5e76\u67e5\u96c6<\/a><\/li>\n<\/ol>\n8\u3001\u5b57\u7b26\u4e32<\/h2>\n\u6709\u6548\u5b57\u7b26\u4e32<\/h3>\n
\n\u4e00\u4e2a\u770b\u7740\u4e0d\u9519\u7684\u7b54\u6848<\/p>\n
bool checkValidString(String s) {\n int low = 0; \/\/ \u8868\u793a*\u53f7\u90fd\u4f5c\u4e3a\u53f3\u62ec\u53f7\u65f6\uff0c\u5de6\u62ec\u53f7\u7684\u6570\u91cf\n int hight = 0; \/\/ \u8868\u793a*\u90fd\u4f5c\u4e3a\u5de6\u62ec\u53f7\u65f6\uff0c\u5de6\u62ec\u53f7\u7684\u6570\u91cf\n \/\/ \u5982\u679chight < 0 \u8bf4\u660e*\u90fd\u4f5c\u4e3a\u5de6\u62ec\u53f7\u4e86\uff0c\u8fd8\u662f\u4e0d\u591f\u62b5\u6d88\u4e0d\u4e86\u53f3\u62ec\u53f7\n \/\/ \u5982\u679clow > 0 \u8bf4\u660e*\u53f7\u90fd\u4f5c\u4e3a\u53f3\u62ec\u53f7\u4e86\uff0c\u8fd8\u662f\u62b5\u6d88\u4e0d\u4e86\u62ec\u53f7\u7684\u503c\n for (int i=0; i<s.length();i++){\n char tmp = s.charAt(i);\n if (tmp == '(') {\n low++;\n hight++;\n } \n else if (tmp == ')') {\n if (low > 0) {\n low--;\n }\n hight--;\n } else if (tmp == '*') {\n if (low > 0) {\n low--;\n }\n hight++;\n }\n\n if (hight < 0) {\n return false;\n }\n }\n return low == 0;\n}<\/code><\/pre>\n9\u3001\u6570\u7ec4<\/h2>\n\u5dee\u5206\u6570\u7ec4 \u524d\u7f00\u548c<\/h3>\n
<\/p>\n
class Solution {\npublic:\n vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {\n\n vector<int> data;\n for(int i=0; i<n;i++)\n data.push_back(0);\n\n for(auto i : bookings)\n {\n data[i[0]-1]+=i[2];\n if(i[1]<n)\n data[i[1]]-=i[2];\n }\n\n for(int i=1; i<n;i++)\n data[i]+=data[i-1];\n\n return data;\n }\n};<\/code><\/pre>\n\u6d4b\u8bd5<\/h2>\n\u4ee3\u7801<\/h3>\nint main()\n{\n\/\/\u52a8\u6001\u89c4\u5212\n int a[]{1,-5,8,3,-4,15,-8};\n std::cout<<\"max_successive_sub_serial_sum: \"<<max_successive_sub_serial_sum(a,7)<<std::endl;\n std::cout<<\"max_successive_sub_serial_sum_space: \"<<max_successive_sub_serial_sum_space(a,7)<<std::endl;\n\n std::cout<<\"unique_path: \"<<unique_path(3,7)<<std::endl;\n std::cout<<\"unique_path_space: \"<<unique_path_space(3,7)<<std::endl;\n\n int rows=3, cols=3;\n int** map = new int*[rows];\n for(int i=0;i<rows;i++)\n {\n map[i] = new int[cols];\n for(int j=0;j<cols;j++)\n map[i][j]=j;\n }\n std::cout<<\"unique_path_shortest: \"<<unique_path_shortest(map, rows, cols)<<std::endl;\n std::cout<<\"unique_path_shortest_space: \"<<unique_path_shortest_space(map, rows, cols)<<std::endl;\n\/\/\u6392\u5e8f \n int arr[8]{8,7,6,5,4,4,2,1};\n quick_sort(arr,0,7);\n std:cout<<\"quick_sort: \";\n for(int i=0;i<8;i++)\n std::cout<<arr[i]<<\" \";\n std::cout<<std::endl;\n\/\/\u67e5\u627e \n int arr1[9]{8,7,6,5,4,4,2,1,11};\n std::cout<<\"binary_search: \"<<binary_search(arr, 8,5)<<std::endl;\n std::cout<<\"binary_search: \"<<binary_search(arr1, 9,3)<<std::endl;\n\n\/\/\u4e8c\u53c9\u6811\n int arr2[9]{8,7,6,5,4,4,2,1,11};\n myNode* root = createBiTree(arr2, 9);\n cout<<\"frontPrintBiTree: \";\n frontPrintBiTree(root);\n cout<<endl<<\"middlePrintBiTree: \";\n middlePrintBiTree(root);\n cout<<endl<<\"backPrintBiTree: \";\n backPrintBiTree(root);\n cout<<endl<<\"frontPrintBiTree_recursion: \";\n frontPrintBiTree_recursion(root);\n cout<<endl<<\"middlePrintBiTree_recursion: \";\n middlePrintBiTree_recursion(root);\n cout<<endl<<\"backPrintBiTree_recursion: \";\n backPrintBiTree_recursion(root);\n cout<<endl<<\"levelPrintBiTree: \";\n levelPrintBiTree(root);\n cout<<endl<<\"ZPrintBiTree: \";\n ZPrintBiTree(root);\n releaseBiTree(root);\n\n int arr2_front[9]{8,7,5,1,11,4,6,4,2};\n int arr2_mid[9]{1,5,11,7,4,8,4,6,2};\n int arr2_back[9]{1,11,5,4,7,4,2,6,8};\n myNode* root1 = createBiTreeByFrontMid(arr2_front, arr2_mid, 9);\n cout<<endl<<\"createBiTreeByFrontMid backPrintBiTree: \";\n backPrintBiTree(root1);\n releaseBiTree(root1);\n myNode* root2 = createBiTreeByBackMid(arr2_back, arr2_mid, 9);\n cout<<endl<<\"createBiTreeByBackMid frontPrintBiTree: \";\n frontPrintBiTree(root2);\n releaseBiTree(root2);\n cout<<endl;\n\n\/\/\u961f\u5217\u4e0e\u6808\n myStack s;\n s.push(1);\n s.push(2);\n s.push(3);\n s.push(4);\n s.push(5);\n cout<<\"s.top():\"<<s.top()<<endl;\n s.pop();\n cout<<\"s.top() after pop():\"<<s.top()<<endl;\n\n myQueue q;\n q.push(1);\n q.push(2);\n q.push(3);\n q.push(4);\n q.push(5);\n cout<<\"q.front():\"<<q.front()<<endl;\n q.pop();\n cout<<\"q.front() after pop():\"<<q.front()<<endl;\n\n\/\/\u56fe\n int vertexNum = 10;\n \/\/0 1 2 3 4 5 6 7 8 9 \u65e0\u5411\u56fe \u4e24\u4e2a\u8fde\u901a\u5206\u91cf \n int arc_a[10][10]={0,0,1,0,1, 1,0,0,0,0, \n 0,0,0,1,0, 0,0,0,0,0,\n 1,0,0,0,0, 0,0,0,0,0,\n 0,1,0,0,0, 0,0,0,0,0,\n 1,0,0,0,0, 0,0,0,1,0,\n\n 1,0,0,0,0, 0,1,1,0,0,\n 0,0,0,0,0, 1,0,0,0,0,\n 0,0,0,0,0, 1,0,0,0,0,\n 0,0,0,0,1, 0,0,0,0,1,\n 0,0,0,0,0, 0,0,0,1,0}; \n\n vector<int> arc;\n for(int i=0;i<vertexNum;i++)\n for(int j=0;j<vertexNum;j++)\n arc.push_back(arc_a[i][j]);\n cout<<\"DFS: \";\n DFS(vertexNum, &arc); \n cout<<endl<<\"BFS: \";\n BFS(vertexNum, &arc); \n cout<<endl;\n\n vertexNum = 6;\n \/\/0 1 2 3 4 5 6 7 8 9 \u65e0\u5411\u8fde\u901a\u56fe\n int arc_b[6][6]={0, 4, 100, 100, 5, 2, \n 4, 0, 2, 100, 100, 1,\n 100, 2, 0, 10, 100, 3,\n 100, 100, 10, 0, 1, 4,\n 5, 100, 100, 1, 0, 8,\n 2, 1, 3, 4, 8, 0}; \n arc.clear();\n for(int i=0;i<vertexNum;i++)\n for(int j=0;j<vertexNum;j++)\n arc.push_back(arc_b[i][j]);\n cout<<\"Prim:\";\n Prim(vertexNum, &arc);\n cout<<endl<<\"Kruscal:\";\n Kruscal(vertexNum, &arc);\n cout<<endl;\n\n\/\/\u4e8c\u53c9\u6392\u5e8f\u6811\n int sortBiTree[]{80,40,70,90,100,15,81,77,89,96,1};\n myNode* sortRoot = createSortBiTree(sortBiTree, 11);\n cout<<\"createSortBiTree frontPrintBiTree: \";\n frontPrintBiTree(sortRoot);\n cout<<endl;\n myNode* getNode = searchSortBiTree(sortRoot, 96);\n cout<<\"searchSortBiTree 96:\"<<(getNode!=nullptr)<<endl;\n getNode = searchSortBiTree(sortRoot, 77);\n cout<<\"searchSortBiTree 77:\"<<(getNode!=nullptr)<<endl;\n getNode = searchSortBiTree(sortRoot, 2);\n cout<<\"searchSortBiTree 2:\"<<(getNode!=nullptr)<<endl;\n releaseBiTree(sortRoot); \n return 0;\n}<\/code><\/pre>\n\u8f93\u51fa<\/h3>\nmax_successive_sub_serial_sum: 22\nmax_successive_sub_serial_sum_space: 22\nunique_path: 28\nunique_path_space: 28\nunique_path_shortest: 3\nunique_path_shortest_space: 3\nquick_sort: 1 2 4 4 5 6 7 8 \nbinary_search: 1\nbinary_search: 0\nfrontPrintBiTree: 8 7 5 1 11 4 6 4 2 \nmiddlePrintBiTree: 1 5 11 7 4 8 4 6 2 \nbackPrintBiTree: 1 11 5 4 7 4 2 6 8 \nfrontPrintBiTree_recursion: 8 7 5 1 11 4 6 4 2 \nmiddlePrintBiTree_recursion: 1 5 11 7 4 8 4 6 2 \nbackPrintBiTree_recursion: 1 11 5 4 7 4 2 6 8 \nlevelPrintBiTree: 8 7 6 5 4 4 2 1 11 \nZPrintBiTree: 8 6 7 5 4 4 2 11 1 \ncreateBiTreeByFrontMid backPrintBiTree: 1 11 5 4 7 4 2 6 8 \ncreateBiTreeByBackMid frontPrintBiTree: 8 7 5 1 11 4 6 4 2 \ns.top():5\ns.top() after pop():4\nq.front():1\nq.front() after pop():2\nDFS: 0 2 4 8 9 5 6 7 1 3 \nBFS: 0 2 4 5 8 6 7 9 1 3 \nPrim:(0->5)-cost-2 (5->1)-cost-1 (1->2)-cost-2 (5->3)-cost-4 (3->4)-cost-1 \nKruscal:(1->5)-cost-1 (3->4)-cost-1 (0->5)-cost-2 (1->2)-cost-2 (3->5)-cost-4\ncreateSortBiTree frontPrintBiTree: 80 40 15 1 70 77 90 81 89 100 96 \nsearchSortBiTree 96:1\nsearchSortBiTree 77:1\nsearchSortBiTree 2:0<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"1\u3001\u52a8\u6001\u89c4\u5212 DP\u95ee\u9898\u4e09\u6b65\u8d70 \u5b9a\u4e49\u4e00\u4e2a\u52a8\u6001\u89c4\u5212\u6570\u7ec4\uff0c\u660e\u786e\u6570\u7ec4\u5143\u7d20\uff0c\u76ee\u7684\u662f\u4fdd\u5b58\u8ba1\u7b97\u7684\u5386\u53f2\u8bb0\u5f55\uff0c\u8282\u7701\u91cd\u590d\u8ba1\u7b97\u65f6\u95f4 \u786e\u5b9a\u6570\u7ec4\u95f4\u7684\u5173\u7cfb \u627e\u51fa\u521d\u59cb\u503c \u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c \u6709\u4e00\u4e2a\u6570\u7ec4\uff0c\u59821\uff0c \uff0d5\uff0c 8\uff0c 3\uff0c \uff0d4\uff0c 15\uff0c \uff0d8\uff0c\u67e5\u627e\u5176\u4e2d\u8fde\u7eed\u548c\u6700\u5927\u7684\u76f8\u90bb\u4e32\u7684\u503c\u3002 \u5728\u672c\u4f8b\u4e2d\uff0c\u6700\u5927\u503c\u4e3a8 \uff0b 3 \uff0b \uff0d4 \uff0b 15 \uff1d 22\u3002 \u5b9a\u4e49\u52a8\u6001\u89c4\u5212\u6570\u7ec4\u5143\u7d20\uff1adp[i]\u8868\u793a\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\u3002 \u6570\u7ec4\u5143\u7d20\u95f4\u7684\u5173\u7cfb\uff1adp[i] = max{ dp[i-1] + arc[i] , arc[i] }\uff0c\u5373\uff0c\u5230\u7b2ci\u4e2a\u5143\u7d20\u7684\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u548c\uff0c\u8981\u4e48\u662f\u7ee7\u7eed\u7d2f\u52a0\uff0c\u8981\u4e48\u5c31\u662f\u5143\u7d20\u672c\u8eab\uff08\u91cd\u65b0\u5f00\u59cb\u4e00\u8f6e\u7d2f\u52a0\uff09\u3002\u6700\u7ec8\u7684\u6700\u5927\u503c\u662fdp\u6570\u7ec4\u4e2d\u7684\u6700\u5927\u503c\u3002\uff08\u53ef\u4ee5\u7d2f\u52a0\u4e00\u4e2a\u8d1f\u6570\uff0c\u4f46\u4e0d\u80fd\u5728\u8d1f\u6570\u4e0a\u7d2f\u52a0\uff09 \u521d\u59cb\u503c\uff1adp[0] = arc[0] \u3002 int max_successive_sub_serial_sum(int* numbers, int size) { \/\/\u5b9a\u4e49\u4e0e\u521d\u59cb\u5316 int* dp = new int[size]; dp[0] = numbers[0]; int max_sum = dp[0]; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179"}],"collection":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=179"}],"version-history":[{"count":2,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179\/revisions"}],"predecessor-version":[{"id":202,"href":"http:\/\/47.103.123.166\/index.php?rest_route=\/wp\/v2\/posts\/179\/revisions\/202"}],"wp:attachment":[{"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/47.103.123.166\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}