![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155467.gif\")
<\/div><\/p>\n#include<iostream>\nusing namespace std;\nvoid Select_Sort(int arr*,int n)\n{\n for(int i = 0;i < n;i++){\n int min = i;\n for(int j = i;j < n;j++){\n if(arr[min] > arr[j]){\n min = j;\n }\n }\n if(min != i){\n swap(arr[i],arr[min]);\n }\n }\n\n}<\/code><\/pre>\npackage class01;\nimport java.util.Arrays;\npublic class Code01_SelectionSort{\n public static void selectionSort(int[] arr){\n if(arr == null||arr.length < 2){\n return 0;\n }\n for(int i = 0,i < arr.length - 1; i++){\n int minIndex = i;\n for(int j = i+1,j<arr.length,j++){\n minIndex = arr[j] < arr[minIndex] ? j : minIndex;\/\/\u6b64\u65f6\u51fa\u7528\u5230\u4e86\u4e09\u76ee\u8fd0\u7b97\u7b26[\u5e03\u5c14\u8868\u8fbe\u5f0f ? \u53d6\u771f\u65f6\u53d6\u503c : \u53d6\u5047\u65f6\u53d6\u503c]\n }\n swap(arr, i, minIndex);\n }\n }\n public static void swap(int[] arr,int i,int j){\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n }\n}<\/code><\/pre>\n\u5192\u6ce1\u6392\u5e8f<\/h4>\n
\u5148\u5bf9\u4ece0\u5230n-1\u9879\u8fdb\u884c\u76f8\u90bb\u4e24\u9879\u7684\u5927\u5c0f\u6392\u5e8f\uff0c\u518d\u5bf9\u4ece0\u5230n-2\u9879\u8fdb\u884c\u76f8\u90bb\u5927\u5c0f\u6392\u5e8f\uff0c\u4ee5\u6b64\u7c7b\u63a8\uff0c\u6700\u7ec8\u6392\u5e8f\u5b8c\u6210\u3002<\/p>\n
![\"img\"](\"data:image\/svg+xml;base64,PCEtLUFyZ29uTG9hZGluZy0tPgo8c3ZnIHdpZHRoPSIxIiBoZWlnaHQ9IjEiIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgc3Ryb2tlPSIjZmZmZmZmMDAiPjxnPjwvZz4KPC9zdmc+\")
<\/div><\/p>\npublic class Bubble_Sort{\n public static void bubbleSort(int[] arr){\n if(arr == null || arr.length == 1) return 0;\n for(int i = 0;i < arr.length - 1;i++){\n boolean isSorted = ture;\n for(int j = 0;j < arr.length - 1 - i;j++){\n if(arr[j] > arr[j + 1]){\n int temp = arr[j]; \n arr[j] = arr[j + 1];\n arr[j + 1] = temp;\n isSorted = false;\n }\n }\n if(isSorted) return; \n System.out.print("\u7b2c"+(i+1)+"\u8d9f\uff1a")\uff1b\n print(arr);\n }\n }\n}<\/code><\/pre>\npackage class01;\nimport java.util.Arrays;\npublic class Code02_BubbleSort{\n public static void bubbleSort(int[] arr){\n if(arr = null||arr.length < 2){\n return;\n }\n for(int n = arr.length - 1,n > 0,n--){\n for(int i = 0,i < e,i++){\n if(arr[i] > arr[i+1]){\n swap(arr,i,i + 1);\n } \n }\n }\n }\n public static void swap(int[] arr,int i,int j){\n arr[i]=arr[i]^arr[j];\n arr[j]=arr[i]^arr[j];\n arr[i]=arr[i]^arr[j];\n }\n}<\/code><\/pre>\n^ \u5f02\u6216\u8fd0\u7b97<\/code>\uff08\u4e0d\u540c\u4e3a1\uff0c\u76f8\u540c\u4e3a0\uff09<\/p>\n\u76f8\u5173\u6027\u8d28\uff1a<\/p>\n
0 ^ N = N\n\nN ^ N = N\n\n\u6ee1\u8db3\u4ea4\u6362\u5f8b\u548c\u7ed3\u5408\u7387\n\n\u4e00\u7fa4\u6570\u5f02\u6216\u5148\u540e\u987a\u5e8f\u4e0d\u5f71\u54cd\u7ed3\u679c\n\n\u6ce8\u610f\uff1a\u4ea6\u6216\u8fd0\u7b97\u4e2d\u7684\u4e24\u4e2a\u6570\u5b57\u4f4d\u7f6e\u4e0d\u80fd\u6307\u5411\u540c\u4e00\u7247\u5185\u5b58\u533a\u57df<\/code><\/pre>\n\u7b97\u6cd5\u9898<\/code><\/p>\n\/\/\u6570\u7ec4\u5185\u67d0\u4e2a\u6570\u51fa\u73b0\u4e86\u5947\u6570\u6b21\uff0c\u5176\u4ed6\u6570\u5b57\u51fa\u73b0\u4e86\u5076\u6570\u6b21\uff0c\u6c42\u8be5\u51fa\u73b0\u4e86\u57fa\u6570\u6b21\u7684\u6570\npublic static void print0ddTimesNum1(int[] arr){\n int eor = 0;\n for(int cur : arr){\n eor ^= cur;\n }\n System.out.println(eor); \n}<\/code><\/pre>\n\u6570\u7ec4\u5185\u67d0\u4e24\u4e2a\u6570\u51fa\u73b0\u4e86\u5947\u6570\u6b21\uff0c\u5176\u4ed6\u6570\u5b57\u51fa\u73b0\u5076\u6570\u6b21\uff0c\u6c42\u8fd9\u4e24\u4e2a\u6570<\/p>\n
public static void print0ddTimesNum2(int[] arr){\n int eor = 0;\n for(int i = 1,i < arr.length;i++){\n eor ^arr[i];\n }\n int rightone = eor & (~eor + 1);\n int onlyOne = 0; \/\/onlyOne\u5c31\u662feor'\n for (int cur : arr){\n if((cur & rightOne) == 0){\n onlyOne ^= cur;\n }\n }\n System.out.println(onlyOne + " " +(eor ^ onlyOne));\n}<\/code><\/pre>\n\u4e24\u4e2a\u5947\u6570\u6b21\u6570\uff0c\u5148\u5f02\u6216\u8fd0\u7b97\u83b7\u5f97\u7b2c\u4e00\u4e2a\u5947\u6570\u6b21\u6570\uff0c\u518d eor ^ eor ' \u5373\u53ef\u5f97\u5230\u7b2c\u4e8c\u4e2a\u5947\u6570\u6b21\u6570<\/code><\/p>\n\u63d2\u5165\u6392\u5e8f<\/h4>\n
\u5148\u770b 0\\~0\u4e0a\u662f\u5426\u6709\u5e8f\uff0c\u518d\u770b 0\\~1\u4e0a\u662f\u5426\u6709\u5e8f\uff0c\u6709\u5e8f\u5219\u4e0d\u53d8\uff0c\u65e0\u5e8f\u5219\u6392\u5e8f\u4ee5\u6b64\u7c7b\u63a8\u5230\u6700\u540e 0\\~n\u3002\u8be5\u7b97\u6cd5\u4e0e\u6240\u7ed9\u6570\u636e\u7684\u4e0d\u540c\u590d\u6742\u5ea6\u4e5f\u4e0d\u540c\u3002<\/p>\n
\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO($N^2$)\uff0c\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(1)\u3002<\/p>\n
<\/div><\/p>\npublic class Code03_InsertionSort{\n public static void insortionSort(int[] arr){\n if(arr == null||arr.length < 2){\n return;\n }\n for(int i = 1;i < arr.length;i++){\n for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j--){\n swap(arr,j,j+1);\n }\n }\n }\n public static void swap(int[] arr,int i,int j){\n arr[i] = arr[i] ^ arr[j];\n arr[j] = arr[i] ^ arr[j];\n arr[i] = arr[i] ^ arr[j];\n }\n}<\/code><\/pre>\n\u4e8c\u5206\u6cd5\u67e5\u627e<\/h4>\n
\u4e8c\u5206\u6cd5\u8981\u5728\u5df2\u7ecf\u6392\u597d\u5e8f\u7684\u6570\u7ec4\u4e2d\u8fdb\u884c\u67e5\u627e\uff0c\u5148\u548c\u4e2d\u95f4\u6570\u6bd4\u8f83\u518d\u4e0e\u4e0b\u4e00\u6bb5\u7684\u4e2d\u95f4\u6570\u6bd4\u8f83\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$log_2N$\u3002<\/p>\n
\u4e8c\u5206\u6cd5\u8fd8\u53ef\u4ee5\u627e\u5927\u4e8e\u7b49\u4e8e\u67d0\u6570\u6700\u5de6\u4fa7\u7684\u6570\u5b57\u548c\u5c0f\u4e8e\u7b49\u4e8e\u67d0\u6570\u6700\u53f3\u4fa7\u7684\u4f4d\u7f6e\u90fd\u53ef\u4ee5\u3002<\/p>\n
\u7b97\u6cd5\u9898<\/code><\/p>\n\u5728\u4e00\u4e2a\u6570\u7ec4arr\u4e2d\uff0carr\u65e0\u5e8f\uff0c\u4e14\u4efb\u610f\u4e24\u4e2a\u76f8\u90bb\u7684\u6570\u4e0d\u76f8\u7b49\uff0c\u5b9a\u4e49\u5c40\u90e8\u6700\u5c0f\uff0c\u53ea\u6c42\u4e00\u4e2a\u5c40\u90e8\u6700\u5c0f\uff0c\u95ee\u662f\u5426\u5b58\u5728\u4e00\u4e2a\u7b97\u6cd5\u590d\u6742\u5ea6\u53ef\u4ee5\u5c0f\u4e8eO(n)\u3002<\/p>\n
\u89e3\u6cd5<\/code>\uff1a<\/p>\n\u82e5 0\\~1\u4e2d\u4e0eN-2\\~N-1\u4e2d\u8d8b\u52bf\u4e0d\u540c\u5219\u518d\u6570\u7ec4\u4e2d\u5fc5\u5b9a\u5b58\u5728\u5c40\u90e8\u6700\u5c0f\uff0c\u4e8c\u5206\u6cd5\u6c42\u4e2d\u95f4\u4e24\u4e2a\u6570\u7684\u5927\u5c0f\u5173\u7cfb\uff0c\u548c\u54ea\u8fb9\u76f8\u540c\u5c31\u5f80\u53cd\u65b9\u5411\u7ee7\u7eed\u4e8c\u5206\u3002<\/p>\n
<\/div><\/p>\n\u5e0c\u5c14\u6392\u5e8f<\/h4>\n
\u5e0c\u5c14\u6392\u5e8f\uff0c\u901a\u8fc7\u589e\u91cf(gap)\u5c06\u5143\u7d20\u4e24\u4e24\u5206\u7ec4\uff0c\u5bf9\u6bcf\u7ec4\u4f7f\u7528\u76f4\u63a5\u63d2\u5165\u6392\u5e8f\u7b97\u6cd5\u6392\u5e8f\uff1b\u589e\u91cf(gap)\u9010\u6e10\u51cf\u5c11\uff0c\u5f53\u589e\u91cf(gap)\u51cf\u81f31\u65f6\uff0c\u6574\u4e2a\u6570\u636e\u6070\u88ab\u5206\u6210\u4e00\u7ec4\uff0c\u6700\u540e\u8fdb\u884c\u4e00\u6b21\u63d2\u5165\u6392\u5e8f\uff0c\u6574\u4e2a\u6570\u7ec4\u5c31\u6709\u5e8f\u4e86\u3002<\/p>\n
<\/div><\/p>\n<\/div><\/p>\n<\/div><\/p>\n\u7b2c\u4e00\u6b21:gap = 9\/2 = 4\uff0c\u6bcf\u4e2a\u5143\u7d20\u548c\u540e\u9762\u7684\u5143\u7d20\u4e4b\u95f4\u95f4\u96944\uff0c\u5143\u7d20\u88ab\u5206\u62104\u7ec4\u3002\u5176\u4e2d\u5143\u7d207, 5, 6\u5206\u6210\u4e00\u7ec4\uff0c\u5143\u7d203,4\u5206\u6210\u4e00\u7ec4\uff0c\u5143\u7d201, 2\u5206\u6210\u4e00\u7ec4\uff0c\u5143\u7d209,8\u5206\u6210\u4e00\u7ec4\uff0c\u6548\u679c\u5982\u4e0b\u56fe\uff1a<\/p>\n
<\/div><\/p>\n\u7b2c\u4e8c\u6b21:gap = 4\/2 = 2\uff0c\u6bcf\u4e2a\u5143\u7d20\u548c\u540e\u9762\u7684\u5143\u7d20\u4e4b\u95f4\u95f4\u96942\uff0c\u5143\u7d20\u88ab\u5206\u62102\u7ec4\u3002<\/p>\n
<\/div><\/p>\n\u7b2c\u4e09\u6b21:gap = 2\/2 = 1\uff0c\u6bcf\u4e2a\u5143\u7d20\u548c\u540e\u9762\u7684\u5143\u7d20\u4e4b\u95f4\u95f4\u96941\uff0c\u5143\u7d20\u88ab\u5206\u62101\u7ec4\u3002<\/p>\n
<\/div><\/p>\npublic class ShellSortTest2 {\n public static void main(String[] args) {\n int[] arr = new int[] {7, 3, 1, 9, 5, 4, 2, 8, 6};\n shellSort(arr);\n }\n\n public static void shellSort(int[] arr) {\n \/\/ \u589e\u91cfgap,\u901a\u8fc7gap\u6765\u5212\u5206\u51fa\u4e0d\u540c\u7684\u5b50\u5e8f\u5217,gap\u4e0d\u65ad\u51cf\u5c11,\u5212\u5206\u7684\u5b50\u5e8f\u5217\u66f4\u591a\n for (int gap = arr.length \/ 2; gap > 0; gap \/= 2) { \/\/ \u5faa\u73af\u5f97\u5230\u4e0d\u540c\u7684gap\uff0cgap = 4, 2, 1\n System.out.println("gap: " + gap);\n\n for (int i = gap; i < arr.length; i++) { \/\/ \u6bcf\u7ec4\u4f7f\u7528\u63d2\u5165\u6392\u5e8f\n for (int j = i; j-gap >= 0; j -= gap) {\n if (arr[j-gap] > arr[j]) {\n swap(arr, j-gap, j);\n System.out.print("\\t\u4ea4\u6362: " + arr[j-gap] + "\u548c" + arr[j]);\n System.out.println(Arrays.toString(arr));\n }\n }\n }\n }\n }\n\n public static void swap(int[] arr, int start, int end) {\n int temp = arr[start];\n arr[start] = arr[end];\n arr[end] = temp;\n }\n}<\/code><\/pre>\n\u6267\u884c\u6548\u679c\uff1a<\/p>\n
gap: 4\n \u4ea4\u6362: 5\u548c7[5, 3, 1, 9, 7, 4, 2, 8, 6]\n \u4ea4\u6362: 8\u548c9[5, 3, 1, 8, 7, 4, 2, 9, 6]\n \u4ea4\u6362: 6\u548c7[5, 3, 1, 8, 6, 4, 2, 9, 7]\ngap: 2\n \u4ea4\u6362: 1\u548c5[1, 3, 5, 8, 6, 4, 2, 9, 7]\n \u4ea4\u6362: 4\u548c8[1, 3, 5, 4, 6, 8, 2, 9, 7]\n \u4ea4\u6362: 2\u548c6[1, 3, 5, 4, 2, 8, 6, 9, 7]\n \u4ea4\u6362: 2\u548c5[1, 3, 2, 4, 5, 8, 6, 9, 7]\ngap: 1\n \u4ea4\u6362: 2\u548c3[1, 2, 3, 4, 5, 8, 6, 9, 7]\n \u4ea4\u6362: 6\u548c8[1, 2, 3, 4, 5, 6, 8, 9, 7]\n \u4ea4\u6362: 7\u548c9[1, 2, 3, 4, 5, 6, 8, 7, 9]\n \u4ea4\u6362: 7\u548c8[1, 2, 3, 4, 5, 6, 7, 8, 9]<\/code><\/pre>\n\u603b\u7ed3<\/strong><\/h5>\n\u5e0c\u5c14\u6392\u5e8f\uff0c\u662f\u76f4\u63a5\u63d2\u5165\u6392\u5e8f\u7b97\u6cd5\u7684\u4e00\u79cd\u66f4\u9ad8\u6548\u7684\u6539\u8fdb\u7248\u672c\u3002\u901a\u8fc7\u589e\u91cf(gap)\u5c06\u5143\u7d20\u8fdb\u884c\u5206\u7ec4\uff0c\u5bf9\u6bcf\u7ec4\u4f7f\u7528\u76f4\u63a5\u63d2\u5165\u6392\u5e8f\u7b97\u6cd5\u6392\u5e8f\uff1b\u589e\u91cf(gap)\u9010\u6e10\u51cf\u5c11\uff0c\u5f53\u589e\u91cf(gap)\u51cf\u81f31\u65f6\uff0c\u6574\u4e2a\u6570\u636e\u6070\u88ab\u5206\u6210\u4e00\u7ec4\uff0c\u6700\u540e\u8fdb\u884c\u4e00\u6b21\u63d2\u5165\u6392\u5e8f\u3002<\/p>\n
\u5bf9\u6570\u5668<\/h4>\n
1\u3001\u751f\u6210\u968f\u673a\u6837\u672c\u4ea7\u751f\u5668\u3002<\/p>\n
2\u3001\u5c06\u4e24\u4e2a\u65b9\u6cd5\u540c\u65f6\u8f93\u5165\u6570\u636e\uff0c\u6bd4\u8f83\u4e24\u4e2a\u65b9\u6cd5\u7684\u65b9\u6cd5\u3002<\/p>\n
public static void comparator(int[] arr){\n Arrays.sort(arr);\n}<\/code><\/pre>\njava\u751f\u6210\u968f\u673a\u6570\u7684\u51fd\u6570<\/p>\n
\/\/\u81ea\u5df1\u6253\u7684\npublic static int[] generateRandomArray(int maxSize,int maxValue){\n \/\/(int)(Math.random() * N) \u2014\u2014>[0 ~ N-1]\u6240\u6709\u7684\u6574\u6570\uff0c\u7b49\u6982\u7387\u8fd4\u56de\u4e00\u4e2a\n int[] arr = new int[(int)((maxSize + 1) * Math.random())];\n for (int i = 0;i < arr.length;i++){\n arr[i] = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random());\n }\n return arr;\n}\n\/\/\u7f51\u4e0a\u7684\n\/\/\u968f\u673a\u6570\u7ec4\u7684\u751f\u6210\n\/\/Math.random() [0,1) double\n\/\/Math.random() *A ->[0,A) double A->int\npublic static int []generateRandomArray(int maxSize,int maxValue)\n{ \n int []arr=new int[(int)(maxSize+1)*Math.random())];\n for(int i=0;i<arr.length;i++)\n {\n arr[i]=(int)((maxValue+1)*Math.random())-(int)(maxValue*Math.random)\n }\n return arr;\n\n}\n\/\/\u590d\u5236 \u8fd4\u56de\u6570\u7ec4\npublic static int[] copyArray(int[] arr)\n{\n if(arr==null)\n {\n return null;\n }\n int []res=new int[arr.length];\n for(int i=0;i<arr.length;i++)\n {\n res[i]=arr[i];\n }\n return res;\n}<\/code><\/pre>\n\u6d4b\u8bd5\u5668\u6848\u4f8b<\/p>\n
\/\/for test\nstatic void main()\n{ \n int testTime=2000;\/\/\u6d4b\u8bd5\u6b21\u6570 \n int maxSize=100;\/\/\u6570\u7ec4\u5927\u5c0f \n int maxValue=100;\/\/\u6570\u7ec4\u503c\u5927\u5c0f \n boolean succeed=true;\/\/\u521d\u59cb\u503c \u4e0d\u6210\u529f \n for(int i=0;i<testTime;i++) \n { \n int []arr1=generateRandomArray(maxSize,maxValue);\/\/\u4ea7\u751f\u968f\u673a\u6570\u7ec4 \n int []arr2=copyArray(arr1); \/\/\u62f7\u8d1d\u751f\u6210\u65b0\u6570\u7ec4 \n selectionSort(arr1); \/\/\u88ab\u6d4b\u9ed1\u76d2\u51fd\u6570 \n comparator(arr2); \/\/\u7edd\u5bf9\u6b63\u786e\u51fd\u6570 \n if(!isEqual(arr1,arr2)) \/\/\u5bf9\u6bd4\u7ed3\u679c \n { \n succeed=false; \/\/\u53ea\u8981\u6709\u4e00\u6b21\u5931\u8d25\u5c31\u6253\u5370 \n printArray(arr1); \n printArray(arr2); \n break; \n } \n } \n}<\/code><\/pre>\n2.\u8ba4\u8bc6O(NlogN)\u7684\u6392\u5e8f<\/h2>\n
\u53d6\u4e2d\u70b9\u7684\u65b9\u6cd5\uff1a
\n$$
\nmid = \\frac{L+R}{2}
\n$$
\n\u4f46\u662f\u8fd9\u79cd\u65b9\u6cd5\u4e0d\u4e00\u5b9a\u51c6\u786e\uff0c\u5982\u679c\u5728\u6570\u7ec4\u4e2dR\u8db3\u591f\u7684\u5927\uff0c\u53ef\u80fd\u4f1a\u9020\u6210\u6ea2\u51fa\uff0c\u4ece\u800cmid\u53d6\u8d1f\u6570\u3002<\/p>\n
\u6545\u91c7\u7528\u4ee5\u4e0b\u65b9\u6cd5\uff1a
\n$$
\nmid = L + \\frac{R-L}{2}
\n$$
\n\u540c\u65f6\u4e3a\u4e86\u63d0\u9ad8\u8fd0\u7b97\u6548\u7387\u5f15\u5165\u4f4d\u8fd0\u7b97\u7b26>><\/code>
\n$$
\nmid = L + ((R-L)>>1)
\n$$<\/p>\n\u4f4d\u8fd0\u7b97\u7b26 >> or <<\n\u5c06\u5de6\u8fb9\u7684\u6570\u8f6c\u6362\u6210\u4e8c\u8fdb\u5236\u6570\uff0c\u518d\u6839\u636e\u7b26\u53f7\u65b9\u5411\u5411\u5de6\u6216\u5411\u53f3\u79fb\u52a8\u4e00\u5b9a\u4f4d\u6570\uff0c\u8fd9\u4e2a\u4f4d\u6570\u6307\u7684\u662f\u7b26\u53f7\u53f3\u8fb9\u7684\u503c\u3002<\/code><\/pre>\n\u9012\u5f52\u6cd5\u6c42\u6700\u5927\u503c<\/h3>\npublic class Code08_GetMax{\n public static int getMax(int[] arr){\n return process(arr, 0, arr.length - 1);\n }\n public static int process(int[] arr, int L, int R){\n if(L == R){\n return arr[L];\n }\n int mid = L + ((R - L) >> 1);\n int leftMax = process(arr, L, mid);\n int rightMax = process(arr, mid + 1, R);\n return Math.max(leftMax, rightMax);\n }\n}<\/code><\/pre>\nmaster\u516c\u5f0f\u2014\u2014\u89e3\u9012\u5f52\u7a0b\u5e8f\u590d\u6742\u5ea6\u7684\u65b9\u6cd5<\/h3>\n
$$
\nmaster\\;\u516c\u5f0f\uff1aT(N) = a \\times T(\\frac{N}{b}) +O(N^d)\\
\n\u5173\u4e8e\\,master\\,\u516c\u5f0f\u6709\u4ee5\u4e0b\u7ed3\u8bba\uff1a\\
\n\u82e5\\;log_ba<d,\u5219\u8be5\u9012\u5f52\u590d\u6742\u5ea6\u4e3a\\;O(N^d)\\
\n\u82e5\\;log_ba>d,\u5219\u8be5\u9012\u5f52\u590d\u6742\u5ea6\u4e3a\\;O(N^{log_ba})\\
\n\u82e5\\;log_ba=d,\u5219\u8be5\u9012\u5f52\u590d\u6742\u5ea6\u4e3a\\;O(N^d \\times logN)
\n$$<\/p>\n
<\/div>
\n<\/div><\/p>\n\u5f52\u5e76\u6392\u5e8f<\/h3>\n
\u5de6\u8fb9\u6392\u597d\u5e8f\uff0c\u53f3\u8fb9\u6392\u597d\u5e8f\u8ba9\u6574\u4f53\u6709\u5e8f\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u7531 master \u516c\u5f0f\u6c42\u51fa\uff0c\u4e3a$O(N\\times logN)$\uff0c\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a$O(N)$\u3002<\/p>\n
\u5728\u989d\u5916\u4e00\u4e2a\u7a7a\u95f4\u5185\uff0c\u5de6\u53f3\u4f9d\u6b21\u76f8\u540c\u5e8f\u53f7\u7684\u6570\u5b57\u6bd4\u8f83\uff0c\u8c01\u5c0f\u5148\u62f7\u8d1d\u8c01\u5230\u65b0\u7a7a\u95f4\u5185\u3002\u6700\u7ec8\u518d\u62f7\u8d1d\u56de\u539f\u6570\u7ec4\u3002<\/p>\n
<\/div><\/p>\n\/\/\u5f52\u5e76\u6392\u5e8f\u4ee3\u7801\u5b9e\u73b0\nimport java.util.Arrays;\npublic class Code01_MergeSort{\n public static void mergeSort(int[] arr){\n if(arr = null || arr.length < 2){\n return;\n }\n process(arr, 0, arr.length - 1);\n }\n public static void process(int[] arr, int L, int R){\n if(L == R){\n return;\n }\n int mid = L + ((R - L) >> 1);\n process(arr, L, mid);\n process(arr, mid + 1, R);\n merge(arr, L, mid, R);\n }\n public static void merge(int[] arr, int L, int M, int R){\n int[] help = new int[R - L + 1];\n int i =0;\n int p1 = L;\n int p2 = M + 1;\n while(p1 <= M && p2 <= R){\n help[i++] = arr[p1] <=arr[p2] ? arr[p1] :arr[p2];\n }\n while(p1 <= M){\n help[i++] = arr[p1++];\n }\n while(p2 <= R){\n help[i++] = arr[p2++];\n }\n for (i = 0; i < help.length; i++){\n arr[L + i] = help[i++];\n }\n }\n}<\/code><\/pre>\n<\/div>
\n<\/div><\/p>\n\u4e4b\u524d\u7684\u6392\u5e8f\u5728\u6bd4\u8f83\u4ee5\u540e\u4e22\u5f03\u4e86\u5927\u91cf\u7684\u6bd4\u8f83\u6570\u636e\u3002<\/p>\n
<\/div> <\/p>\n\u7b28\u65b9\u6cd5\u662f\u66b4\u529b\u6c42\u89e3\uff0c\u8f83\u597d\u7684\u7b97\u6cd5\u662f\u8fd0\u7528\u5f52\u5e76\u6392\u5e8f\u8fdb\u884c\u8ba1\u7b97\u3002\u5982\u56fe\uff1a<\/p>\n
<\/div>
\n<\/div>
\n<\/div><\/p>\n\/\/\u5b9e\u73b0\u4ee3\u7801\nclass test \n{ public static int smallSum(int[] arr) {\n if (arr == null || arr.length < 2) {\n return 0;\n }\n return mergeSort(arr, 0, arr.length - 1);\n}\n\n public static int mergeSort(int[] arr, int l, int r) {\n if (l == r) {\n return 0;\n }\n int mid = l + ((r - l) >> 1);\n return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);\n }\n\n public static int merge(int[] arr, int l, int m, int r) {\n int[] help = new int[r - l + 1];\n int i = 0;\n int p1 = l;\n int p2 = m + 1;\n int res = 0;\n while (p1 <= m && p2 <= r) {\n res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;\n help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];\n }\n while (p1 <= m) {\n help[i++] = arr[p1++];\n }\n while (p2 <= r) {\n help[i++] = arr[p2++];\n }\n for (i = 0; i < help.length; i++) {\n arr[l + i] = help[i];\n }\n return res;\n }\n public static void main (String[] args) throws java.lang.Exception\n {\n int[] arr = { 1,2,3};\n System.out.println(smallSum(arr));\n }\n}<\/code><\/pre>\n<\/div><\/p>\n\u95ee\u9898\u4e00\uff1a\u5206\u4e24\u6b65\uff1a<\/p>\n
[i] <= num , [i] \u548c<=\u8fb9\u754c\u7684\u4e0b\u4e00\u4e2a\u6570\u5b57\u4ea4\u6362\uff0c\u5c0f\u4e8e\u533a\u57df\u53f3\u79fb,i++;\n[i] > num , i++ <\/code><\/pre>\n\u95ee\u9898\u4e00\u884d\u751f\uff1a\u589e\u52a0\u7b49\u4e8e\u533a\u57df<\/p>\n
<\/div><\/p>\n\u5feb\u901f\u6392\u5217<\/h3>\n
\u9009\u62e9\u6700\u540e\u4e00\u4e2a\u6570\uff0c\u5c06\u6570\u7ec4\u5212\u5206\u6210\u4e24\u90e8\u5206\uff0c\u518d\u5206\u522b\u5bf9\u4e24\u90e8\u5206\u7684\u6700\u540e\u4e00\u4e2a\u6570\u91cd\u590d\u8fdb\u884c\u4e0a\u8ff0\u6b65\u9aa4\u3002\u5feb\u901f\u6392\u5e8f\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6700\u5dee\u4e3aO(N)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u6700\u5dee\u4e3aO(N)\uff0c\u6309\u7167\u6982\u7387\u76f8\u5173\u77e5\u8bc6\uff0c\u5f97\u51fa\u5feb\u901f\u6392\u5e8f\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(NlogN)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(logN)\u3002<\/p>\n
<\/div><\/p>\n\u5feb\u901f\u6392\u5e8f\u4f7f\u7528\u5206\u6cbb\u6cd5\uff08Divide and conquer\uff09\u7b56\u7565\u6765\u628a\u4e00\u4e2a\u5e8f\u5217\uff08list\uff09\u5206\u4e3a\u4e24\u4e2a\u5b50\u5e8f\u5217\uff08sub-lists\uff09\u3002\n\u2460 \u4ece\u6570\u5217\u4e2d\u6311\u51fa\u4e00\u4e2a\u5143\u7d20\uff0c\u79f0\u4e3a \u201c\u57fa\u51c6\u201d\uff08pivot\uff09\uff0c\n\u2461 \u91cd\u65b0\u6392\u5e8f\u6570\u5217\uff0c\u6240\u6709\u5143\u7d20\u6bd4\u57fa\u51c6\u503c\u5c0f\u7684\u6446\u653e\u5728\u57fa\u51c6\u524d\u9762\uff0c\u6240\u6709\u5143\u7d20\u6bd4\u57fa\u51c6\u503c\u5927\u7684\u6446\u5728\u57fa\u51c6\u7684\u540e\u9762\uff08\u76f8\u540c\u7684\u6570\u53ef\u4ee5\u5230\u4efb\u4e00\u8fb9\uff09\u3002\u5728\u8fd9\u4e2a\u5206\u533a\u9000\u51fa\u4e4b\u540e\uff0c\u8be5\u57fa\u51c6\u5c31\u5904\u4e8e\u6570\u5217\u7684 \u4e2d\u95f4\u4f4d\u7f6e\u3002\u8fd9\u4e2a\u79f0\u4e3a\u5206\u533a\uff08partition\uff09\u64cd\u4f5c\u3002\n\u2462 \u9012\u5f52\u5730\uff08recursive\uff09\u628a\u5c0f\u4e8e\u57fa\u51c6\u503c\u5143\u7d20\u7684\u5b50\u6570\u5217\u548c\u5927\u4e8e\u57fa\u51c6\u503c\u5143\u7d20\u7684\u5b50\u6570\u5217\u6392\u5e8f\u3002\n\u9012\u5f52\u5230\u6700\u5e95\u90e8\u65f6\uff0c\u6570\u5217\u7684\u5927\u5c0f\u662f\u96f6\u6216\u4e00\uff0c\u4e5f\u5c31\u662f\u5df2\u7ecf\u6392\u5e8f\u597d\u4e86\u3002\u8fd9\u4e2a\u7b97\u6cd5\u4e00\u5b9a\u4f1a\u7ed3\u675f\uff0c\u56e0\u4e3a\u5728\u6bcf\u6b21\u7684\u8fed\u4ee3\uff08iteration\uff09\u4e2d\uff0c\u5b83\u81f3\u5c11\u4f1a\u628a\u4e00\u4e2a\u5143\u7d20\u6446\u5230\u5b83\u6700\u540e\u7684\u4f4d\u7f6e\u53bb\u3002<\/code><\/pre>\n<\/div><\/p>\n\u5212\u5206\u503c\u53d6\u7684\u597d\u7684\u8bdd\uff0c\u6570\u636e\u7ed3\u6784\u65f6\u95f4\u590d\u6742\u5ea6\u53ef\u4ee5\u8fbe\u5230 NlogN\u3002<\/p>\n
<\/div><\/p>\n\u5c06\u5212\u5206\u503c\u770b\u6210\u7b49\u6982\u7387\u597d\u574f\uff0c\u518d\u5bf9\u4e0d\u540c\u60c5\u51b5\u4e0b\u7684master\u516c\u5f0f\u6c42\u6570\u5b66\u671f\u671b\uff0c\u53ef\u5f97\u6570\u5b66\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(NlogN)\u3002<\/p>\n
\/\/\u5feb\u901f\u6392\u5e8f\u76f8\u5173\u4ee3\u7801\npublic static void quickSort(int[] arr){\n if(arr == null || arr.length<2){\n return;\n }\n quickSort(arr,0,arr.length-1);\n}\npublic static void quickSort(int[] arr,int l,int r){\n if(l < r){\n swap(arr, l+(int)(Math.random()*(r-l+1)),r);\/\/\u968f\u673a\u62bd\u53d6\u6570\u503c\n int[] p = partition(arr,l,r);\/\/\u5c06\u7b49\u4e8ex\u90e8\u5206\u7b5b\u51fa\uff0c\u5b58\u653e\u81f3\u6570\u7ec4\u4e4b\u4e2d\u3002\n quickSort(arr,l,p[0]-1);\/\/\u5c0f\u4e8e\u90e8\u5206\u5feb\u901f\u6392\u5e8f\n quickSort(arr,p[1]+2,r);\/\/\u5927\u4e8e\u90e8\u5206\u5feb\u901f\u6392\u5e8f\n }\n}\npublic static int[] partition(int[] arr,int l,int r){\n int less = l-1;\n int more = r;\n \/\/\u5c06r\u5f53\u4f5c\u8be5\u6570\u503c\uff0c\u5c06r-1\u4e2a\u6570\u503c\u8fdb\u884c\u6bd4\u8f83\uff0c\u6700\u540e\u518d\u5c06more\u548cr\u8fdb\u884c\u8f6c\u6362\u3002\n while(l<more){\n if(arr[l]<arr[r]){\n swap(arr,++less,l++);\n }else if(arr[l]>arr[r]){\n swap(arr,--more,l);\n }else{\n l++\n }\n }\n swap(arr,more,r);\n return new int[] { less+1,more};\n}\npublic static void swap(int[] arr,int i,int j){\n int tmp = arr[i];\n arr[i] = arr[j];\n arr[j] = tmp;\n}<\/code><\/pre>\n\u5806<\/h3>\n
\u5728\u903b\u8f91\u4e0a\u662f\u5b8c\u5168\u4e8c\u53c9\u6811<\/p>\n
<\/div><\/p>\n\u5806\u6392\u5e8f<\/h3>\n
<\/div><\/p>\n\u8ba9\u7528\u6237\u8f93\u5165\u7684\u6570\u5b57\u53d8\u6210\u5927\u6839\u5806\u3002<\/p>\n
heapinsert \n(1).\u987a\u5e8f\u63d2\u5165\u3002\n(2).\u5c06\u6570\u5b57\u548c\u7236\u4f4d\u7f6e\u7684\u6839\u8282\u70b9\u6bd4\u8f83\uff0c\u6bd4\u6839\u8282\u70b9\u5927\u5219\u8ddf\u6362\u4f4d\u7f6e\uff0c\u4e0d\u5927\u5219\u987a\u5e8f\u6392\u5217\u3002\n(3).\u548c\u66f4\u9ad8\u7684\u6839\u8282\u70b9\u6bd4\u8f83\uff0c\u66f4\u6362\u3002<\/code><\/pre>\n\u5982\u679c\u8981\u5220\u9664\u5927\u6839\u5806\u7684\u6839\u8282\u70b9\u600e\u4e48\u5904\u7406\uff1f<\/p>\n
heapify\n\u5c06\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u653e\u5230\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\uff0cheapsize - 1\uff1b\n\u5c06\u8be5\u6570\u5b57\u4e0e\u5de6\u5b50\u6811\uff0c\u53f3\u5b50\u6811\u6839\u8282\u70b9\u6bd4\u8f83\uff0c\u4ea4\u6362\uff1b\n\u91cd\u590d\u4e0a\u4e2a\u6b65\u9aa4\u3002<\/code><\/pre>\n\/\/heapinsert\u76f8\u5173\u4ee3\u7801\npublic static void heapInsert(int [] arr, int index){\n while(arr[index] > arr[(index - 1)\/2]){\n swap(arr, index, (index - 1) \/2);\n index = (index - 1) \/2; \n }\n}\npublic static void heapify(int[] arr, int index, int heapSize){\n int left = index * 2 + 1;\n while (left < heapSize){\n int largest = left + 1 < heapSize && arr[left > 1] > arr[left] ? left + 1 : left;\n \/\/\u4e0a\u8ff0\u5f0f\u5b50\u7406\u89e3\uff1a\u5148\u5bf9(left + 1 < heapSize)(arr[left > 1] > arr[left])\u5206\u522b\u8fdb\u884c\u5224\u65ad\uff0c\u518d\u8fdb\u884c\u903b\u8f91\u4e0e&&\u8fd0\u7b97\uff0c\u6b63\u786e\u53d6\u5de6\uff0c\u4e0d\u6b63\u786e\u53d6\u53f3\uff0c\u6700\u540e\u8d4b\u503c\u3002\n largest = arr[largest] > arr[index] ? largest : index;\n if(largest == index){\n break;\n }\n swap(arr, largest, index);\n index = largest;\n left = index * 2 + 1\uff1b\n }\n}\npublic static void swap(intp[] arr, int i, int j){\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n}<\/code><\/pre>\n\/\/\u5806\u6392\u5e8fcode\npublic static void Code02_HeapSort{\n public static void heapSort(int [] arr){\n if(arr = null || arr.length < 2){\n return;\n }\n\/\/ for(int i = 0, i < arr.length, i++){\n\/\/ heapInsert(arr, i);\n\/\/ }\n for(int i = arr.length - 1;i >= 0;i--){\n heapify(arr, i, arr.length);\n }\/\/\u8be5\u65b9\u6cd5\u6bd4\u4e0a\u9762\u7684\u6ce8\u91ca\u5185\u5bb9\u7565\u5feb\uff0c\u4f46\u4e0d\u5f71\u54cd\u6574\u4f53\u7684\u590d\u6742\u5ea6\u3002\n int heapSize = arr.length;\n swap(arr, 0, --heapSize);\n while(heapSize > 0){\n heapify(arr, 0, heapSize);\n swap(arr, 0, --heapSize);\n }\n }\n}<\/code><\/pre>\n\u5806\u6392\u5e8f\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(NlogN)\uff0c\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(1)\u3002<\/p>\n
\u5982\u679c\u76f4\u63a5\u7ed9n\u4e2a\u6570\u7684\u6570\u7ec4\uff0c\u4ece\u53f3\u81f3\u5de6\uff0c\u4ece\u4e0b\u5f80\u4e0aheapify\u3002<\/p>\n
<\/div>
\n<\/div>
\n<\/div> <\/p>\n\u5176\u590d\u6742\u5ea6\u4e3aO(logk)\u3002<\/p>\n
\u4f18\u5148\u961f\u5217<\/h4>\n#include<iostream>\n#include<queue>\nusing namespace std;\nint main()\n{\n priority_queue<int>heap;\n heap.push(10);\n heap.push(8);\n heap.push(9);\n heap.push(12);\n heap.push(3);\n\n while(heap.size()>0)\n {\n cout<<heap.top()<<" ";\n heap.pop();\n }\n return 0;\n}\n<\/code><\/pre>\nimport java.util.PriorityQueue;\npublic class04_SortArrayDistanceLessK{\n public void sortedArrayDistanceLessK(int [] arr, int k){\n \/\/\u9ed8\u8ba4\u5c0f\u6839\u5806\uff0c\u7cfb\u7edf\u4f18\u5148\u6392\u5e8f\u3002\n PriorityQueue<Integer> heap = new PriorityQueue<>();\n int index = 0;\n for(; index <= Math.min(arr.length,k);index++){\n heap.add(arr[index]);\n }\n int i = 0;\n for(;index <= arr.length; index++){\n heap.add(arr[index]);\n arr[i] = heap.poll();\n }\n while(!heap.isEmpty()){\n arr[i++] = heap.poll();\n }\n }\n public static void main(String [] args){\n PriorityQueue<Integer> heap = new PriorityQueue<>();\n heap.add(8);\n heap.add(4);\n heap.add(4);\n heap.add(9);\n heap.add(10);\n heap.add(3);\n while(!heap.isEmpty()){\n System.out.println(heap.poll());\n }\/\/>>>3 4 4 8 9 10\n }\n}<\/code><\/pre>\n\u6bd4\u8f83\u5668<\/h3>\n
<\/div> <\/p>\n<\/div><\/p>\n3.\u6876\u6392\u5e8f\u4ee5\u53ca\u6392\u5e8f\u5185\u5bb9\u5927\u603b\u7ed3<\/h2>\n\u8ba1\u6570\u6392\u5e8f<\/h3>\n
\u8ba1\u6570\u6392\u5e8f\uff08Counting sort\uff09<\/strong>\u662f\u4e00\u79cd\u7a33\u5b9a\u7684\u7ebf\u6027\u65f6\u95f4\u6392\u5e8f\u7b97\u6cd5\u3002<\/p>\n1. \u57fa\u672c\u601d\u60f3<\/h4>\n
\u8ba1\u6570\u6392\u5e8f\u4f7f\u7528\u4e00\u4e2a\u989d\u5916\u7684\u6570\u7ec4C\uff0c\u5176\u4e2d\u7b2ci\u4e2a\u5143\u7d20\u662f\u5f85\u6392\u5e8f\u6570\u7ec4A\u4e2d\u503c\u7b49\u4e8ei\u7684\u5143\u7d20\u7684\u4e2a\u6570\u3002<\/p>\n
\u8ba1\u6570\u6392\u5e8f\u7684\u6838\u5fc3\u5728\u4e8e\u5c06\u8f93\u5165\u7684\u6570\u636e\u503c\u8f6c\u5316\u4e3a\u952e\u5b58\u50a8\u5728\u989d\u5916\u5f00\u8f9f\u7684\u6570\u7ec4\u7a7a\u95f4\u4e2d\u3002\u4f5c\u4e3a\u4e00\u79cd\u7ebf\u6027\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u6392\u5e8f\uff0c\u8ba1\u6570\u6392\u5e8f\u8981\u6c42\u8f93\u5165\u7684\u6570\u636e\u5fc5\u987b\u662f\u6709\u786e\u5b9a\u8303\u56f4\u7684\u6574\u6570\u3002<\/p>\n
\u7528\u6765\u8ba1\u6570\u7684\u6570\u7ec4C\u7684\u957f\u5ea6\u53d6\u51b3\u4e8e\u5f85\u6392\u5e8f\u6570\u7ec4\u4e2d\u6570\u636e\u7684\u8303\u56f4\uff08\u7b49\u4e8e\u5f85\u6392\u5e8f\u6570\u7ec4\u7684\u6700\u5927\u503c\u4e0e\u6700\u5c0f\u503c\u7684\u5dee\u52a0\u4e0a1\uff09\uff0c\u7136\u540e\u8fdb\u884c\u5206\u914d\u3001\u6536\u96c6\u5904\u7406\uff1a<\/p>\n
\n\u2460 \u5206\u914d<\/strong>\u3002\u626b\u63cf\u4e00\u904d\u539f\u59cb\u6570\u7ec4\uff0c\u4ee5\u5f53\u524d\u503c-minValue\u4f5c\u4e3a\u4e0b\u6807\uff0c\u5c06\u8be5\u4e0b\u6807\u7684\u8ba1\u6570\u5668\u589e1\u3002
\n\u2461 \u6536\u96c6<\/strong>\u3002\u626b\u63cf\u4e00\u904d\u8ba1\u6570\u5668\u6570\u7ec4\uff0c\u6309\u987a\u5e8f\u628a\u503c\u6536\u96c6\u8d77\u6765\u3002<\/p>\n<\/blockquote>\n2. \u5b9e\u73b0\u903b\u8f91<\/h4>\n\n\u2460 \u627e\u51fa\u5f85\u6392\u5e8f\u7684\u6570\u7ec4\u4e2d\u6700\u5927\u548c\u6700\u5c0f\u7684\u5143\u7d20
\n\u2461 \u7edf\u8ba1\u6570\u7ec4\u4e2d\u6bcf\u4e2a\u503c\u4e3ai\u7684\u5143\u7d20\u51fa\u73b0\u7684\u6b21\u6570\uff0c\u5b58\u5165\u6570\u7ec4C\u7684\u7b2ci\u9879
\n\u2462 \u5bf9\u6240\u6709\u7684\u8ba1\u6570\u7d2f\u52a0\uff08\u4eceC\u4e2d\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u5f00\u59cb\uff0c\u6bcf\u4e00\u9879\u548c\u524d\u4e00\u9879\u76f8\u52a0\uff09
\n\u2463 \u53cd\u5411\u586b\u5145\u76ee\u6807\u6570\u7ec4\uff1a\u5c06\u6bcf\u4e2a\u5143\u7d20i\u653e\u5728\u65b0\u6570\u7ec4\u7684\u7b2cC(i)\u9879\uff0c\u6bcf\u653e\u4e00\u4e2a\u5143\u7d20\u5c31\u5c06C(i)\u51cf\u53bb1<\/p>\n<\/blockquote>\n
3. \u52a8\u56fe\u6f14\u793a<\/h4>\n
<\/div><\/p>\n\u8ba1\u6570\u6392\u5e8f\u6f14\u793a<\/p>\n
\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5047\u8bbe\u6709\u65e0\u5e8f\u6570\u5217nums=[2, 1, 3, 1, 5], \u9996\u5148\u626b\u63cf\u4e00\u904d\u83b7\u53d6\u6700\u5c0f\u503c\u548c\u6700\u5927\u503c\uff0cmaxValue=5, minValue=1\uff0c\u4e8e\u662f\u5f00\u4e00\u4e2a\u957f\u5ea6\u4e3a5\u7684\u8ba1\u6570\u5668\u6570\u7ec4counter<\/p>\n
\n(1) \u5206\u914d<\/strong>
\n\u7edf\u8ba1\u6bcf\u4e2a\u5143\u7d20\u51fa\u73b0\u7684\u9891\u7387\uff0c\u5f97\u5230counter=[2, 1, 1, 0, 1]\uff0c\u4f8b\u5982counter[0]\u8868\u793a\u503c0+minValue=1\u51fa\u73b0\u4e862\u6b21\u3002
\n(2) \u6536\u96c6<\/strong>
\ncounter[0]=2\u8868\u793a1\u51fa\u73b0\u4e86\u4e24\u6b21\uff0c\u90a3\u5c31\u5411\u539f\u59cb\u6570\u7ec4\u5199\u5165\u4e24\u4e2a1\uff0ccounter[1]=1\u8868\u793a2\u51fa\u73b0\u4e861\u6b21\uff0c\u90a3\u5c31\u5411\u539f\u59cb\u6570\u7ec4\u5199\u5165\u4e00\u4e2a2\uff0c\u4f9d\u6b21\u7c7b\u63a8\uff0c\u6700\u7ec8\u539f\u59cb\u6570\u7ec4\u53d8\u4e3a[1,1,2,3,5]\uff0c\u6392\u5e8f\u597d\u4e86\u3002<\/p>\n<\/blockquote>\n4. \u590d\u6742\u5ea6\u5206\u6790<\/h4>\n\n\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n + k)
\n\u6700\u4f73\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n + k)
\n\u6700\u5dee\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n + k)
\n\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n + k)<\/p>\n<\/blockquote>\n
\u5f53\u8f93\u5165\u7684\u5143\u7d20\u662fn \u4e2a0\u5230k\u4e4b\u95f4\u7684\u6574\u6570\u65f6\uff0c\u5b83\u7684\u8fd0\u884c\u65f6\u95f4\u662f O(n + k)\u3002\u3002\u5728\u5b9e\u9645\u5de5\u4f5c\u4e2d\uff0c\u5f53k=O(n)\u65f6\uff0c\u6211\u4eec\u4e00\u822c\u4f1a\u91c7\u7528\u8ba1\u6570\u6392\u5e8f\uff0c\u8fd9\u65f6\u7684\u8fd0\u884c\u65f6\u95f4\u4e3aO(n)\u3002<\/p>\n
\u8ba1\u6570\u6392\u5e8f\u9700\u8981\u4e24\u4e2a\u989d\u5916\u7684\u6570\u7ec4\u7528\u6765\u5bf9\u5143\u7d20\u8fdb\u884c\u8ba1\u6570\u548c\u4fdd\u5b58\u6392\u5e8f\u7684\u8f93\u51fa\u7ed3\u679c\uff0c\u6240\u4ee5\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(k+n)\u3002<\/p>\n
\u8ba1\u6570\u6392\u5e8f\u7684\u4e00\u4e2a\u91cd\u8981\u6027\u8d28\u662f\u5b83\u662f\u7a33\u5b9a\u7684\uff1a\u5177\u6709\u76f8\u540c\u503c\u7684\u5143\u7d20\u5728\u8f93\u51fa\u6570\u7ec4\u4e2d\u7684\u76f8\u5bf9\u6b21\u5e8f\u4e0e\u5b83\u4eec\u5728\u8f93\u5165\u6570\u7ec4\u4e2d\u7684\u76f8\u5bf9\u6b21\u5e8f\u662f\u76f8\u540c\u7684\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5bf9\u4e24\u4e2a\u76f8\u540c\u7684\u6570\u6765\u8bf4\uff0c\u5728\u8f93\u5165\u6570\u7ec4\u4e2d\u5148\u51fa\u73b0\u7684\u6570\uff0c\u5728\u8f93\u51fa\u6570\u7ec4\u4e2d\u4e5f\u4f4d\u4e8e\u524d\u9762\u3002<\/p>\n
\u8ba1\u6570\u6392\u5e8f\u7684\u7a33\u5b9a\u6027\u5f88\u91cd\u8981\u7684\u4e00\u4e2a\u539f\u56e0\u662f\uff1a\u8ba1\u6570\u6392\u5e8f\u7ecf\u5e38\u4f1a\u88ab\u7528\u4e8e\u57fa\u6570\u6392\u5e8f\u7b97\u6cd5\u7684\u4e00\u4e2a\u5b50\u8fc7\u7a0b\u3002\u6211\u4eec\u5c06\u5728\u540e\u9762\u6587\u7ae0\u4e2d\u4ecb\u7ecd\uff0c\u4e3a\u4e86\u4f7f\u57fa\u6570\u6392\u5e8f\u80fd\u591f\u6b63\u786e\u8fd0\u884c\uff0c\u8ba1\u6570\u6392\u5e8f\u5fc5\u987b\u662f\u7a33\u5b9a\u7684\u3002<\/p>\n
5. \u4ee3\u7801\u5b9e\u73b0<\/h4>\n
C\u7248\u672c\uff1a<\/strong><\/p>\n\/\/ \u8ba1\u6570\u6392\u5e8f\uff08C\uff09\n#include <stdio.h>\n#include <stdlib.h>\n#include <time.h>\nvoid print_arr(int *arr, int n) {\n int i;\n printf("%d", arr[0]);\n for (i = 1; i < n; i++)\n printf(" %d", arr[i]);\n printf("\\n");\n}\nvoid counting_sort(int *ini_arr, int *sorted_arr, int n) {\n int *count_arr = (int *) malloc(sizeof(int) * 100);\n int i, j, k;\n for (k = 0; k < 100; k++)\n count_arr[k] = 0;\n for (i = 0; i < n; i++)\n count_arr[ini_arr[i]]++;\n for (k = 1; k < 100; k++)\n count_arr[k] += count_arr[k - 1];\n for (j = n; j > 0; j--)\n sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];\n free(count_arr);\n}\nint main(int argc, char **argv) {\n int n = 10;\n int i;\n int *arr = (int *) malloc(sizeof(int) * n);\n int *sorted_arr = (int *) malloc(sizeof(int) * n);\n srand(time(0));\n for (i = 0; i < n; i++)\n arr[i] = rand() % 100;\n printf("ini_array: ");\n print_arr(arr, n);\n counting_sort(arr, sorted_arr, n);\n printf("sorted_array: ");\n print_arr(sorted_arr, n);\n free(arr);\n free(sorted_arr);\n return 0;\n}<\/code><\/pre>\nJava\u7248\u672c\uff1a<\/strong><\/p>\n\/\/ \u8ba1\u6570\u6392\u5e8f(Java)\npublic class CountingSort {\n public static void main(String[] argv) {\n int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});\n Utils.print(A);\n }\n public static int[] countingSort(int[] A) {\n int[] B = new int[A.length];\n \/\/ \u5047\u8bbeA\u4e2d\u7684\u6570\u636ea'\u6709\uff0c0<=a' && a' < k\u5e76\u4e14k=100\n int k = 100;\n countingSort(A, B, k);\n return B;\n }\n private static void countingSort(int[] A, int[] B, int k) {\n int[] C = new int[k];\n \/\/ \u8ba1\u6570\n for (int j = 0; j < A.length; j++) {\n int a = A[j];\n C[a] += 1;\n }\n Utils.print(C);\n \/\/ \u6c42\u8ba1\u6570\u548c\n for (int i = 1; i < k; i++) {\n C[i] = C[i] + C[i - 1];\n }\n Utils.print(C);\n \/\/ \u6574\u7406\n for (int j = A.length - 1; j >= 0; j--) {\n int a = A[j];\n B[C[a] - 1] = a;\n C[a] -= 1;\n }\n }\n}<\/code><\/pre>\n6. \u4f18\u5316\u6539\u8fdb<\/h4>\n
\u573a\u666f\u5206\u6790\uff1a<\/strong>\u4e3e\u4e2a\u6781\u7aef\u7684\u4f8b\u5b50\uff1a\u5982\u679c\u6392\u5e8f\u7684\u6570\u7ec4\u6709200W\u4e2a\u5143\u7d20\uff0c\u4f46\u662f\u8fd9200W\u4e2a\u6570\u7684\u503c\u90fd\u57281000000-1000100\uff0c\u4e5f\u5c31\u8bf4\u6709100\u4e2a\u6570\uff0c\u603b\u5171\u91cd\u590d\u4e86200W\u6b21\uff0c\u73b0\u5728\u8981\u6392\u5e8f\uff0c\u600e\u4e48\u529e\uff1f<\/p>\n\u8fd9\u79cd\u60c5\u51b5\u6392\u5e8f\uff0c\u8ba1\u6570\u6392\u5e8f\u5e94\u8be5\u662f\u9996\u9009\u3002\u4f46\u662f\u8fd9\u65f6\u5019n\u7684\u503c\u4e3a200W\uff0c\u5982\u679c\u6309\u539f\u6765\u7684\u7b97\u6cd5\uff0ck\u7684\u503c10001000\uff0c\u4f46\u662f\u6b64\u65f6c\u4e2d\u771f\u6b63\u7528\u5230\u7684\u5730\u65b9\u53ea\u6709100\u4e2a\uff0c\u8fd9\u6837\u5bf9\u7a7a\u95f4\u9020\u6210\u4e86\u6781\u5927\u7684\u6d6a\u8d39\u3002<\/p>\n
\u6539\u8fdb\u601d\u8def\uff1a<\/strong>\u9488\u5bf9c\u6570\u7ec4\u7684\u5927\u5c0f\uff0c\u4f18\u5316\u8ba1\u6570\u6392\u5e8f<\/p>\n\u6539\u8fdb\u4ee3\u7801\uff1a<\/strong><\/p>\n\/\/ \u8ba1\u6570\u6392\u5e8f\u4f18\u5316(Java)\n\/\/ \u9488\u5bf9c\u6570\u7ec4\u7684\u5927\u5c0f\uff0c\u4f18\u5316\u8ba1\u6570\u6392\u5e8f\npublic class CountSort{\n public static void main(String []args){\n \/\/\u6392\u5e8f\u7684\u6570\u7ec4\n int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};\n int b[] = countSort(a);\n for(int i : b){\n System.out.print(i + " ");\n }\n System.out.println();\n }\n public static int[] countSort(int []a){\n int b[] = new int[a.length];\n int max = a[0], min = a[0];\n for(int i : a){\n if(i > max){\n max = i;\n }\n if(i < min){\n min = i;\n }\n }\n \/\/\u8fd9\u91cck\u7684\u5927\u5c0f\u662f\u8981\u6392\u5e8f\u7684\u6570\u7ec4\u4e2d\uff0c\u5143\u7d20\u5927\u5c0f\u7684\u6781\u503c\u5dee+1\n int k = max - min + 1;\n int c[] = new int[k];\n for(int i = 0; i < a.length; ++i){\n c[a[i]-min] += 1;\/\/\u4f18\u5316\u8fc7\u7684\u5730\u65b9\uff0c\u51cf\u5c0f\u4e86\u6570\u7ec4c\u7684\u5927\u5c0f\n }\n for(int i = 1; i < c.length; ++i){\n c[i] = c[i] + c[i-1];\n }\n for(int i = a.length-1; i >= 0; --i){\n b[--c[a[i]-min]] = a[i];\/\/\u6309\u5b58\u53d6\u7684\u65b9\u5f0f\u53d6\u51fac\u7684\u5143\u7d20\n }\n return b;\n }\n}<\/code><\/pre>\n
\n\u4e09\u3001\u603b\u7ed3<\/p>\n
\u8ba1\u6570\u7b97\u6cd5\u53ea\u80fd\u4f7f\u7528\u5728\u5df2\u77e5\u5e8f\u5217\u4e2d\u7684\u5143\u7d20\u57280-k\u4e4b\u95f4\uff0c\u4e14\u8981\u6c42\u6392\u5e8f\u7684\u590d\u6742\u5ea6\u5728\u7ebf\u6027\u6548\u7387\u4e0a\u3002 \u00c2 \u8ba1\u6570\u6392\u5e8f\u548c\u57fa\u6570\u6392\u5e8f\u5f88\u7c7b\u4f3c\uff0c\u90fd\u662f\u975e\u6bd4\u8f83\u578b\u6392\u5e8f\u7b97\u6cd5\u3002\u4f46\u662f\uff0c\u5b83\u4eec\u7684\u6838\u5fc3\u601d\u60f3\u662f\u4e0d\u540c\u7684\uff0c\u57fa\u6570\u6392\u5e8f\u4e3b\u8981\u662f\u6309\u7167\u8fdb\u5236\u4f4d\u5bf9\u6574\u6570\u8fdb\u884c\u4f9d\u6b21\u6392\u5e8f\uff0c\u800c\u8ba1\u6570\u6392\u5e8f\u4e3b\u8981\u4fa7\u91cd\u4e8e\u5bf9\u6709\u9650\u8303\u56f4\u5185\u5bf9\u8c61\u7684\u7edf\u8ba1\u3002\u57fa\u6570\u6392\u5e8f\u53ef\u4ee5\u91c7\u7528\u8ba1\u6570\u6392\u5e8f\u6765\u5b9e\u73b0\u3002<\/p>\n
\u6876\u6392\u5e8f<\/h3>\n
\u6876\u6392\u5e8f\u662f\u8ba1\u6570\u6392\u5e8f\u7684\u5347\u7ea7\u7248\u3002\u5b83\u5229\u7528\u4e86\u51fd\u6570\u7684\u6620\u5c04\u5173\u7cfb\uff0c\u9ad8\u6548\u4e0e\u5426\u7684\u5173\u952e\u5c31\u5728\u4e8e\u8fd9\u4e2a\u6620\u5c04\u51fd\u6570\u7684\u786e\u5b9a\u3002\u4e3a\u4e86\u4f7f\u6876\u6392\u5e8f\u66f4\u52a0\u9ad8\u6548\uff0c\u6211\u4eec\u9700\u8981\u505a\u5230\u8fd9\u4e24\u70b9\uff1a<\/p>\n
\n- \u5728\u989d\u5916\u7a7a\u95f4\u5145\u8db3\u7684\u60c5\u51b5\u4e0b\uff0c\u5c3d\u91cf\u589e\u5927\u6876\u7684\u6570\u91cf<\/li>\n
- \u4f7f\u7528\u7684\u6620\u5c04\u51fd\u6570\u80fd\u591f\u5c06\u8f93\u5165\u7684 N \u4e2a\u6570\u636e\u5747\u5300\u7684\u5206\u914d\u5230 K \u4e2a\u6876\u4e2d<\/li>\n<\/ol>\n
\u540c\u65f6\uff0c\u5bf9\u4e8e\u6876\u4e2d\u5143\u7d20\u7684\u6392\u5e8f\uff0c\u9009\u62e9\u4f55\u79cd\u6bd4\u8f83\u6392\u5e8f\u7b97\u6cd5\u5bf9\u4e8e\u6027\u80fd\u7684\u5f71\u54cd\u81f3\u5173\u91cd\u8981\u3002<\/p>\n
1. \u4ec0\u4e48\u65f6\u5019\u6700\u5feb<\/h4>\n
\u5f53\u8f93\u5165\u7684\u6570\u636e\u53ef\u4ee5\u5747\u5300\u7684\u5206\u914d\u5230\u6bcf\u4e00\u4e2a\u6876\u4e2d\u3002<\/p>\n
2. \u4ec0\u4e48\u65f6\u5019\u6700\u6162<\/h4>\n
\u5f53\u8f93\u5165\u7684\u6570\u636e\u88ab\u5206\u914d\u5230\u4e86\u540c\u4e00\u4e2a\u6876\u4e2d\u3002<\/p>\n
3. \u793a\u610f\u56fe<\/h4>\n
<\/div><\/p>\n\u5143\u7d20\u5206\u5e03\u5728\u6876\u4e2d\uff1a<\/p>\n
<\/div><\/p>\n\u7136\u540e\uff0c\u5143\u7d20\u5728\u6bcf\u4e2a\u6876\u4e2d\u6392\u5e8f\uff1a<\/p>\n
<\/div><\/p>\npublic class BucketSort implements IArraySort {\n\n private static final InsertSort insertSort = new InsertSort();\n\n @Override\n public int[] sort(int[] sourceArray) throws Exception {\n \/\/ \u5bf9 arr \u8fdb\u884c\u62f7\u8d1d\uff0c\u4e0d\u6539\u53d8\u53c2\u6570\u5185\u5bb9\n int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);\n\n return bucketSort(arr, 5);\n }\n\n private int[] bucketSort(int[] arr, int bucketSize) throws Exception {\n if (arr.length == 0) {\n return arr;\n }\n\n int minValue = arr[0];\n int maxValue = arr[0];\n for (int value : arr) {\n if (value < minValue) {\n minValue = value;\n } else if (value > maxValue) {\n maxValue = value;\n }\n }\n\n int bucketCount = (int) Math.floor((maxValue - minValue) \/ bucketSize) + 1;\n int[][] buckets = new int[bucketCount][0];\n\n \/\/ \u5229\u7528\u6620\u5c04\u51fd\u6570\u5c06\u6570\u636e\u5206\u914d\u5230\u5404\u4e2a\u6876\u4e2d\n for (int i = 0; i < arr.length; i++) {\n int index = (int) Math.floor((arr[i] - minValue) \/ bucketSize);\n buckets[index] = arrAppend(buckets[index], arr[i]);\n }\n\n int arrIndex = 0;\n for (int[] bucket : buckets) {\n if (bucket.length <= 0) {\n continue;\n }\n \/\/ \u5bf9\u6bcf\u4e2a\u6876\u8fdb\u884c\u6392\u5e8f\uff0c\u8fd9\u91cc\u4f7f\u7528\u4e86\u63d2\u5165\u6392\u5e8f\n bucket = insertSort.sort(bucket);\n for (int value : bucket) {\n arr[arrIndex++] = value;\n }\n }\n\n return arr;\n }\n\n \/**\n * \u81ea\u52a8\u6269\u5bb9\uff0c\u5e76\u4fdd\u5b58\u6570\u636e\n *\n * @param arr\n * @param value\n *\/\n private int[] arrAppend(int[] arr, int value) {\n arr = Arrays.copyOf(arr, arr.length + 1);\n arr[arr.length - 1] = value;\n return arr;\n }\n\n}<\/code><\/pre>\n\u57fa\u6570\u6392\u5e8f<\/h3>\n
\u4ee5\u5341\u8fdb\u5236\u4e09\u4f4d\u6570\u7684\u6570\u7ec4\u4e3a\u4f8b\uff0c\u51c6\u590710\u4e2a\u6876\uff0c\u5206\u522b\u5bf9\u5e94 0~9\u7684\u57fa\u6570\u4f4d\uff0c\u9996\u5148\u6839\u636e\u4e2a\u4f4d\u6570\u51b3\u5b9a\u8fdb\u54ea\u4e2a\u6876\uff0c\u5bf9\u4e2a\u4f4d\u6570\u8fdb\u884c\u6392\u5e8f\uff1b\u518d\u4ee5\u5341\u4f4d\u6570\u51b3\u5b9a\u8fdb\u54ea\u4e2a\u6876\uff0c\u5bf9\u5341\u4f4d\u6570\u8fdb\u884c\u6392\u5e8f\uff1b\u6700\u540e\u56e0\u4e3a\u6392\u5e8f\u4f18\u5148\u7ea7\u662f\u4ece\u5341\u4f4d\u5230\u4e2a\u4f4d\u7684\uff0c\u5c31\u53ef\u4ee5\u5f97\u5230\u6574\u4f53\u6709\u5e8f\u7684\u6570\u7ec4\u3002<\/p>\n
<\/div>
\n<\/div>
\n<\/div>
\n<\/div>
\n<\/div>
\n<\/div><\/p>\n\u5904\u7406\u4ee5\u540e\u53d8\u4e3a\uff1a<\/p>\n
<\/div><\/p>\n\/\/arr[L...R]\u6392\u5e8f digit\u662f\u6700\u5927\u7684\u6570\u5b57\u6709\u591a\u5c11\u4e2a\u5341\u8fdb\u5236\u4f4d\uff0c\n\/\/\u4e5f\u5c31\u662f\u6700\u5927\u503c\u7684\u6570 \u4f4d\u6570\npublic static radixSort(int[] arr,int L,int R,int digit)\n{\n final int radix=10;\n int i=0,j=0;\n \/\/\u6709\u591a\u5c11\u4e2a\u6570\u51c6\u5907\u591a\u5c11\u4e2a\u8f85\u52a9\u7a7a\u95f4\n int[] bucket=new int[R-L+1];\n \/\/\u6709\u591a\u5c11\u4f4d\u5c31\u64cd\u4f5c\u51e0\u6b21\n for(int d=1;d<=digit;d++)\n {\n\n int[] count=new int[radix];\n\n for(i=L;i<=R;i++)\n {\n \/\/\u5f97\u5230\u5012\u6570\u7b2cd\u4f4d\u4e0a\u7684\u6570\u5b57\u662f\u51e0\n j=getDigit(arr[i],d);\n count[j]++;\n }\n \/\/\u521b\u5efacount\u2018\u6570\u7ec4\uff0ccount[0]\u4e0a\u7684\u6570\u5b57\u4e0d\u53d8\n for(i=1;i<radix;i++)\n count[i]=count[i]+count[i-1];\n\n \/\/\u4ece\u53f3\u5411\u5de6\u904d\u5386arr\u6570\u7ec4\n for(i=R;i>=L;i--)\n {\n j=getDigit(arr[i],d);\n bucket[arr[j]-1]=arr[i];\n count[j]--;\n }\n\n \/\/\u628a\u67d0\u4e00\u4f4d\u6709\u5e8f\u7684\u6570\u7ec4copy\u56de\u539f\u6570\u7ec4\n for(i=L,j=0;i<=R;i++,j++)\n {\n arr[i]=bucket[j];\n }\n\n }\n}\n\n\/\/\u8fd4\u56dex\u8fd9\u4e2a\u6570\u5728\u5012\u6570\u7b2cd\u4f4d\u4e0a\u7684\u6570\u662f\u51e0\npublic static int getDigit(int x,int d)\n{\n return ( ( x\/ ( (int)Math.pow(10,d-1) ) ) %10 );\n}\n\n\/\/\u8fd4\u56de\u6700\u5927\u503c\u7684\u4f4d\u6570\npublic static int maxbits(int[] arr){\n int max=Integer.MIN_VALUE;\n for(int i=0;i<arr.length;i++)\n {\n max=Math.max(max,arr[i]);\n }\n int res=0;\n while(max!=0){\n res++;\n max\/=10;\n }\n return res;\n}\n\npublic static void main()\n{\n int[] arr={022,021,032,001,100}\n if(arr==null||arr.length<2){\n return;\n }\n radixSort(arr,0,arr.length-1,maxbits(arr));\n}\n<\/code><\/pre>\n\u6392\u5e8f\u603b\u7ed3<\/h3>\n
<\/div>
\n<\/div>
\n<\/div>
\n<\/div><\/p>\n4.\u94fe\u8868<\/h2>\n\u94fe\u8868\u57fa\u7840\u77e5\u8bc6<\/h3>\n\u94fe\u8868\u7684\u6982\u5ff5<\/h4>\n
\u94fe\u8868\u7684\u57fa\u672c\u601d\u7ef4\u662f\uff0c\u5229\u7528\u7ed3\u6784\u4f53\u7684\u8bbe\u7f6e\uff0c\u989d\u5916\u5f00\u8f9f\u51fa\u4e00\u4efd\u5185\u5b58\u7a7a\u95f4\u53bb\u4f5c\u6307\u9488\uff0c\u5b83\u603b\u662f\u6307\u5411\u4e0b\u4e00\u4e2a\u7ed3\u70b9\uff0c\u4e00\u4e2a\u4e2a\u7ed3\u70b9\u901a\u8fc7NEXT\u6307\u9488\u76f8\u4e92\u4e32\u8054\uff0c\u5c31\u5f62\u6210\u4e86\u94fe\u8868\u3002<\/p>\n
<\/div><\/p>\n\u94fe\u8868\u7684\u7ed3\u6784\u662f\u591a\u5f0f\u591a\u6837\u7684\uff0c\u5f53\u65f6\u901a\u5e38\u7528\u7684\u4e5f\u5c31\u662f\u4e24\u79cd\uff1a<\/p>\n
<\/div><\/p>\n<\/div><\/p>\n\n- \u65e0\u5934\u5355\u5411\u975e\u5faa\u73af\u5217\u8868\uff1a\u7ed3\u6784\u7b80\u5355\uff0c\u4e00\u822c\u4e0d\u4f1a\u5355\u72ec\u7528\u6765\u5b58\u653e\u6570\u636e\u3002\u5b9e\u9645\u4e2d\u66f4\u591a\u662f\u4f5c\u4e3a\u5176\u4ed6\u6570\u636e\u7ed3\u6784\u7684\u5b50\u7ed3\u6784\uff0c\u6bd4\u5982\u8bf4\u54c8\u5e0c\u6876\u7b49\u7b49\u3002<\/li>\n
- \u5e26\u5934\u53cc\u5411\u5faa\u73af\u94fe\u8868\uff1a\u7ed3\u6784\u6700\u590d\u6742\uff0c\u4e00\u822c\u5355\u72ec\u5b58\u50a8\u6570\u636e\u3002\u5b9e\u9645\u4e2d\u7ecf\u5e38\u4f7f\u7528\u7684\u94fe\u8868\u6570\u636e\u7ed3\u6784\uff0c\u90fd\u662f\u5e26\u5934\u53cc\u5411\u5faa\u73af\u94fe\u8868\u3002\u8fd9\u4e2a\u7ed3\u6784\u867d\u7136\u590d\u6742\uff0c\u4f46\u662f\u4f7f\u7528\u4ee3\u7801\u5b9e\u73b0\u540e\u4f1a\u53d1\u73b0\u8fd9\u4e2a\u7ed3\u6784\u4f1a\u5e26\u6765\u5f88\u591a\u4f18\u52bf\uff0c\u5b9e\u73b0\u53cd\u800c\u7b80\u5355\u4e86\u3002<\/li>\n<\/ul>\n
\u63d2\u5165\u5220\u9664\u64cd\u4f5c\u53ea\u9700\u8981\u4fee\u6539\u6307\u9488\u6240\u6307\u5411\u7684\u533a\u57df\u5c31\u53ef\u4ee5\u4e86\uff0c\u4e0d\u9700\u8981\u8fdb\u884c\u5927\u91cf\u7684\u6570\u636e\u79fb\u52a8\u64cd\u4f5c\u3002\u5982\u4e0b\u56fe\uff1a<\/p>\n
<\/div><\/p>\n\u94fe\u8868\u5305\u542b\u5355\u94fe\u8868\u3001\u53cc\u94fe\u8868\u3001\u5faa\u73af\u94fe\u8868<\/code>\uff0c\u5982\u4e0b\u56fe\uff1a<\/p>\n<\/div><\/p>\n\u5355\u94fe\u8868<\/h4>\n\/\/\u5355\u94fe\u8868\u7684\u8282\u70b9\u5b9a\u4e49\ntypedef struct Node {\n int data; \/\/\u6570\u636e\u7c7b\u578b\uff0c\u4f60\u53ef\u4ee5\u628aint\u578b\u7684data\u6362\u6210\u4efb\u610f\u6570\u636e\u7c7b\u578b\uff0c\u5305\u62ec\u7ed3\u6784\u4f53struct\u7b49\u590d\u5408\u7c7b\u578b\n struct Node *next; \/\/\u5355\u94fe\u8868\u7684\u6307\u9488\u57df\n} Node,*LinkedList; \n\/\/Node\u8868\u793a\u7ed3\u70b9\u7684\u7c7b\u578b\uff0cLinkedList\u8868\u793a\u6307\u5411Node\u7ed3\u70b9\u7c7b\u578b\u7684\u6307\u9488\u7c7b\u578b\n\/\/\u94fe\u8868\u521d\u59cb\u5316\n\/\/\u521b\u5efa\u4e00\u4e2a\u5355\u94fe\u8868\u7684\u524d\u7f6e\u8282\u70b9\u5e76\u5411\u540e\u9010\u6b65\u6dfb\u52a0\u8282\u70b9\uff0c\u4e00\u822c\u6307\u7684\u662f\u7533\u8bf7\u7ed3\u70b9\u7684\u7a7a\u95f4\uff0c\u540c\u65f6\u5bf9\u4e00\u4e2a\u7ed3\u70b9\u8d4b\u7a7a\u503c(NULL)\nLinkedList listinit(){\n Node *L;\n L=(Node*)malloc(sizeof(Node)); \/\/\u5f00\u8f9f\u7a7a\u95f4 \n if(L==NULL){ \/\/\u5224\u65ad\u662f\u5426\u5f00\u8f9f\u7a7a\u95f4\u5931\u8d25\uff0c\u8fd9\u4e00\u6b65\u5f88\u6709\u5fc5\u8981\n printf("\u7533\u8bf7\u7a7a\u95f4\u5931\u8d25");\n \/\/exit(0); \/\/\u5f00\u8f9f\u7a7a\u95f4\u5931\u8d25\u53ef\u4ee5\u8003\u8651\u76f4\u63a5\u7ed3\u675f\u7a0b\u5e8f\n }\n L->next=NULL; \/\/\u6307\u9488\u6307\u5411\u7a7a\n}<\/code><\/pre>\n\u521b\u5efa\u5355\u5217\u8868\u6709\u4e24\u79cd\u65b9\u5f0f\uff0c==\u5934\u63d2\u5165\u6cd5\u4e0e\u5c3e\u63d2\u5165\u6cd5==<\/p>\n
\u5229\u7528\u6307\u9488\u6307\u5411\u4e0b\u4e00\u4e2a\u7ed3\u70b9\u5143\u7d20\u7684\u65b9\u5f0f\u8fdb\u884c\u9010\u4e2a\u521b\u5efa\uff0c\u4f7f\u7528\u5934\u63d2\u5165\u6cd5\u6700\u7ec8\u5f97\u5230\u7684\u7ed3\u679c\u662f\u9006\u5e8f\u7684\u3002\u5982\u56fe\u6240\u793a\uff1a<\/p>\n
<\/div><\/p>\n\/\/\u5934\u63d2\u6cd5\u5efa\u7acb\u5355\u94fe\u8868\nLinkedList LinkedListCreatH() {\n Node *L;\n L = (Node *)malloc(sizeof(Node)); \/\/\u7533\u8bf7\u5934\u7ed3\u70b9\u7a7a\u95f4\n L->next = NULL; \/\/\u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u94fe\u8868\n\n int x; \/\/x\u4e3a\u94fe\u8868\u6570\u636e\u57df\u4e2d\u7684\u6570\u636e\n while(scanf("%d",&x) != EOF) {\n Node *p;\n p = (Node *)malloc(sizeof(Node)); \/\/\u7533\u8bf7\u65b0\u7684\u7ed3\u70b9\n p->data = x; \/\/\u7ed3\u70b9\u6570\u636e\u57df\u8d4b\u503c\n p->next = L->next; \/\/\u5c06\u7ed3\u70b9\u63d2\u5165\u5230\u8868\u5934L-->|2|-->|1|-->NULL\n L->next = p;\n }\n return L;\n}<\/code><\/pre>\n\u5982\u56fe\u6240\u793a\u4e3a\u5c3e\u63d2\u5165\u6cd5\u7684\u521b\u5efa\u8fc7\u7a0b:<\/p>\n
<\/div><\/p>\n\/\/\u5c3e\u63d2\u6cd5\u5efa\u7acb\u5355\u94fe\u8868\nLinkedList LinkedListCreatT() {\n Node *L;\n L = (Node *)malloc(sizeof(Node)); \/\/\u7533\u8bf7\u5934\u7ed3\u70b9\u7a7a\u95f4\n L->next = NULL; \/\/\u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u94fe\u8868\n Node *r;\n r = L; \/\/r\u59cb\u7ec8\u6307\u5411\u7ec8\u7aef\u7ed3\u70b9\uff0c\u5f00\u59cb\u65f6\u6307\u5411\u5934\u7ed3\u70b9\n int x; \/\/x\u4e3a\u94fe\u8868\u6570\u636e\u57df\u4e2d\u7684\u6570\u636e\n while(scanf("%d",&x) != EOF) {\n Node *p;\n p = (Node *)malloc(sizeof(Node)); \/\/\u7533\u8bf7\u65b0\u7684\u7ed3\u70b9\n p->data = x; \/\/\u7ed3\u70b9\u6570\u636e\u57df\u8d4b\u503c\n r->next = p; \/\/\u5c06\u7ed3\u70b9\u63d2\u5165\u5230\u8868\u5934L-->|1|-->|2|-->NULL\n r = p;\n }\n r->next = NULL;\n return L;\n}<\/code><\/pre>\n\/\/\u904d\u5386\u5355\u94fe\u8868\n\/\/\u904d\u5386\u8f93\u51fa\u5355\u94fe\u8868\nvoid printList(LinkedList L){\n Node *p=L->next;\n int i=0;\n while(p){\n printf("\u7b2c%d\u4e2a\u5143\u7d20\u7684\u503c\u4e3a:%d\\n",++i,p->data);\n p=p->next;\n }\n}\n\/\/\u94fe\u8868\u5185\u5bb9\u7684\u4fee\u6539\uff0c\u5728\u94fe\u8868\u4e2d\u4fee\u6539\u503c\u4e3ax\u7684\u5143\u7d20\u53d8\u4e3a\u4e3ak\u3002\nLinkedList LinkedListReplace(LinkedList L,int x,int k) {\n Node *p=L->next;\n int i=0;\n while(p){\n if(p->data==x){\n p->data=k;\n }\n p=p->next;\n }\n return L;\n}<\/code><\/pre>\n\u5355\u94fe\u8868\u7684\u63d2\u5165\u4e0e\u5220\u9664<\/p>\n
<\/div><\/p>\n<\/div><\/p>\n\/\/\u5355\u94fe\u8868\u7684\u63d2\u5165\u4e0e\u5220\u9664\nLinkedList LinkedListInsert(LinkedList L,int i,int x) {\n Node *pre; \/\/pre\u4e3a\u524d\u9a71\u7ed3\u70b9\n pre = L;\n int tempi = 0;\n for (tempi = 1; tempi < i; tempi++) {\n pre = pre->next; \/\/\u67e5\u627e\u7b2ci\u4e2a\u4f4d\u7f6e\u7684\u524d\u9a71\u7ed3\u70b9\n }\n Node *p; \/\/\u63d2\u5165\u7684\u7ed3\u70b9\u4e3ap\n p = (Node *)malloc(sizeof(Node));\n p->data = x;\n p->next = pre->next;\n pre->next = p;\n\n return L;\n}\n\nLinkedList LinkedListDelete(LinkedList L,int x) {\n Node *p,*pre; \/\/pre\u4e3a\u524d\u9a71\u7ed3\u70b9\uff0cp\u4e3a\u67e5\u627e\u7684\u7ed3\u70b9\u3002\n p = L->next;\n\n while(p->data != x) { \/\/\u67e5\u627e\u503c\u4e3ax\u7684\u5143\u7d20\n pre = p;\n p = p->next;\n }\n pre->next = p->next; \/\/\u5220\u9664\u64cd\u4f5c\uff0c\u5c06\u5176\u524d\u9a71next\u6307\u5411\u5176\u540e\u7ee7\u3002\n free(p);\n\n return L;\n}<\/code><\/pre>\n\u53cc\u94fe\u8868<\/h4>\n
<\/div><\/p>\n\u53cc\u5411\u94fe\u8868\u521b\u5efa\u7684\u8fc7\u7a0b\u53ef\u4ee5\u5206\u4e3a\uff1a\u521b\u5efa\u5934\u7ed3\u70b9->\u521b\u5efa\u4e00\u4e2a\u65b0\u7684\u7ed3\u70b9->\u5c06\u5934\u7ed3\u70b9\u548c\u65b0\u7ed3\u70b9\u76f8\u4e92\u94fe\u63a5->\u518d\u5ea6\u521b\u5efa\u65b0\u7ed3\u70b9<\/p>\n
typedef struct line{\n int data; \/\/data\n struct line *pre; \/\/pre node\n struct line *next; \/\/next node\n}line,*a;\n\/\/\u5206\u522b\u8868\u793a\u8be5\u7ed3\u70b9\u7684\u524d\u9a71(pre)\uff0c\u540e\u7ee7(next)\uff0c\u4ee5\u53ca\u5f53\u524d\u6570\u636e(data)\n\/\/\u521b\u5efa\u53cc\u94fe\u8868\nline* initLine(line * head){\n int number,pos=1,input_data;\n \/\/\u4e09\u4e2a\u53d8\u91cf\u5206\u522b\u4ee3\u8868\u7ed3\u70b9\u6570\u91cf\uff0c\u5f53\u524d\u4f4d\u7f6e\uff0c\u8f93\u5165\u7684\u6570\u636e\n printf("\u8bf7\u8f93\u5165\u521b\u5efa\u7ed3\u70b9\u7684\u5927\u5c0f\\n");\n scanf("%d",&number);\n if(number<1){return NULL;} \/\/\u8f93\u5165\u975e\u6cd5\u76f4\u63a5\u7ed3\u675f\n \/\/\/\/\/\/\u5934\u7ed3\u70b9\u521b\u5efa\/\/\/\/\/\/\/\n head=(line*)malloc(sizeof(line));\n head->pre=NULL;\n head->next=NULL;\n printf("\u8f93\u5165\u7b2c%d\u4e2a\u6570\u636e\\n",pos++);\n scanf("%d",&input_data);\n head->data=input_data;\n\n line * list=head;\n while (pos<=number) {\n line * body=(line*)malloc(sizeof(line));\n body->pre=NULL;\n body->next=NULL;\n printf("\u8f93\u5165\u7b2c%d\u4e2a\u6570\u636e\\n",pos++);\n scanf("%d",&input_data);\n body->data=input_data;\n\n list->next=body;\n body->pre=list;\n list=list->next;\n }\n return head;\n}<\/code><\/pre>\n\u53cc\u5411\u94fe\u8868\u7684\u904d\u5386\u3001\u63d2\u5165\u4e0e\u5220\u9664\uff1a<\/p>\n
\/\/\u904d\u5386\u53cc\u94fe\u8868,\u540c\u65f6\u6253\u5370\u5143\u7d20\u6570\u636e\nvoid printLine(line *head){\n line *list = head;\n int pos=1;\n while(list){\n printf("\u7b2c%d\u4e2a\u6570\u636e\u662f:%d\\n",pos++,list->data);\n list=list->next;\n }\n}<\/code><\/pre>\n<\/div><\/p>\n\/\/\u63d2\u5165\u6570\u636e\nline * insertLine(line * head,int data,int add){\n \/\/\u4e09\u4e2a\u53c2\u6570\u5206\u522b\u4e3a\uff1a\u8fdb\u884c\u6b64\u64cd\u4f5c\u7684\u53cc\u94fe\u8868\uff0c\u63d2\u5165\u7684\u6570\u636e\uff0c\u63d2\u5165\u7684\u4f4d\u7f6e\n \/\/\u65b0\u5efa\u6570\u636e\u57df\u4e3adata\u7684\u7ed3\u70b9\n line * temp=(line*)malloc(sizeof(line));\n temp->data=data;\n temp->pre=NULL;\n temp->next=NULL;\n \/\/\u63d2\u5165\u5230\u94fe\u8868\u5934\uff0c\u8981\u7279\u6b8a\u8003\u8651\n if (add==1) {\n temp->next=head;\n head->pre=temp;\n head=temp;\n }else{\n line * body=head;\n \/\/\u627e\u5230\u8981\u63d2\u5165\u4f4d\u7f6e\u7684\u524d\u4e00\u4e2a\u7ed3\u70b9\n for (int i=1; i<add-1; i++) {\n body=body->next;\n }\n \/\/\u5224\u65ad\u6761\u4ef6\u4e3a\u771f\uff0c\u8bf4\u660e\u63d2\u5165\u4f4d\u7f6e\u4e3a\u94fe\u8868\u5c3e\n if (body->next==NULL) {\n body->next=temp;\n temp->pre=body;\n }else{\n body->next->pre=temp;\n temp->next=body->next;\n body->next=temp;\n temp->pre=body;\n }\n }\n return head;\n}<\/code><\/pre>\n<\/div><\/p>\n\/\/\u5220\u9664\u5143\u7d20\nline * deleteLine(line * head,int data){\n \/\/\u8f93\u5165\u7684\u53c2\u6570\u5206\u522b\u4e3a\u8fdb\u884c\u6b64\u64cd\u4f5c\u7684\u53cc\u94fe\u8868\uff0c\u9700\u8981\u5220\u9664\u7684\u6570\u636e\n line * list=head;\n \/\/\u904d\u5386\u94fe\u8868\n while (list) {\n \/\/\u5224\u65ad\u662f\u5426\u4e0e\u6b64\u5143\u7d20\u76f8\u7b49\n \/\/\u5220\u9664\u8be5\u70b9\u65b9\u6cd5\u4e3a\u5c06\u8be5\u7ed3\u70b9\u524d\u4e00\u7ed3\u70b9\u7684next\u6307\u5411\u8be5\u8282\u70b9\u540e\u4e00\u7ed3\u70b9\n \/\/\u540c\u65f6\u5c06\u8be5\u7ed3\u70b9\u7684\u540e\u4e00\u7ed3\u70b9\u7684pre\u6307\u5411\u8be5\u8282\u70b9\u7684\u524d\u4e00\u7ed3\u70b9\n if (list->data==data) {\n list->pre->next=list->next;\n list->next->pre=list->pre;\n free(list);\n printf("--\u5220\u9664\u6210\u529f--\\n");\n return head;\n }\n list=list->next;\n }\n printf("Error:\u6ca1\u6709\u627e\u5230\u8be5\u5143\u7d20\uff0c\u6ca1\u6709\u4ea7\u751f\u5220\u9664\\n");\n return head;\n}<\/code><\/pre>\n\u4e24\u5355\u94fe\u8868\u76f8\u4ea4\u95ee\u9898<\/h4>\n\u9898\u76ee<\/h5>\n\n- \u7ed9\u5b9a\u4e24\u4e2a\u53ef\u80fd\u662f\u73af\u4e5f\u53ef\u80fd\u65e0\u73af\u7684\u5355\u94fe\u8868\uff0c\u5934\u8282\u70b9head1\u548chead2.\u3002\u8bf7\u5b9e\u73b0\u4e00\u4e2a\u51fd\u6570\uff0c\u5982\u679c\u4e24\u4e2a\u94fe\u8868\u76f8\u4ea4\uff0c\u8bf7\u8fd4\u56de\u76f8\u4ea4\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\uff0c\u5982\u679c\u4e0d\u76f8\u4ea4\uff0c\u8fd4\u56denull\u3002<\/li>\n<\/ul>\n
\u8981\u6c42<\/h5>\n\n- \u5982\u679c\u4e24\u4e2a\u94fe\u8868\u957f\u5ea6\u4e4b\u548c\u4e3aN\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u8bf7\u8fbe\u5230O(N)\uff0c\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u8bf7\u8fbe\u5230O(1)\u3002<\/li>\n<\/ul>\n
\u5206\u6790<\/h5>\n
\u672c\u9898\u76ee\u53ef\u4ee5\u62c6\u5206\u4e3a\uff1a<\/p>\n
\u95ee\u98981.\u5982\u4f55\u5224\u65ad\u5355\u94fe\u8868\u6709\u73af\u8fd8\u662f\u65e0\u73af\uff0c\u6709\u73af\u8fd4\u56de\u7b2c\u4e00\u4e2a\u5165\u73af\u8282\u70b9\uff0c\u65e0\u73af\u8fd4\u56denull\u3002<\/h6>\n
<\/div><\/p>\n\u7b2c\u4e00\u79cd\u65b9\u6cd5<\/p>\n
\u53ef\u4ee5\u5229\u7528\u54c8\u5e0c\u8868\uff08hashSet\uff09\uff1a\u904d\u5386\u6bcf\u4e00\u4e2a\u8282\u70b9\uff0c\u60f3\u8981\u628a\u6bcf\u4e2a\u7ed3\u70b9\u90fd\u5b58\u653e\u5230\u54c8\u5e0c\u8868\u4e2d\uff1b\u4f46\u662f\u54c8\u5e0c\u8868\u4e2d\u5df2\u7ecf\u5b58\u8fc7\u7684\u8282\u70b9\u5c31\u5b58\u4e0d\u8fdb\u53bb\u4e86\uff08\u7b2c\u4e00\u4e2a\u4e0d\u80fd\u5b58\u5165\u54c8\u5e0c\u8868\u7684\u8282\u70b9\u5c31\u662f\u7b2c\u4e00\u4e2a\u5165\u73af\u7684\u8282\u70b9\uff09\u3002<\/p>\n
\n\u6ce8\uff1a\u9700\u8981\u4e00\u4e2a\u54c8\u5e0c\u8868\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6O(n)\u4e0d\u6ee1\u8db3\u3002<\/p>\n<\/blockquote>\n
\u7b2c\u4e8c\u79cd\u65b9\u6cd5<\/p>\n
\u8bbe\u5b9a\u4e24\u4e2a\u6307\u9488\uff1a\u4e00\u4e2a\u5feb\u6307\u9488\uff08\u8d70\u4e24\u6b65\uff09\uff0c\u4e00\u4e2a\u6162\u6307\u9488\uff08\u8d70\u4e00\u6b65\uff09\uff1b\u5f53\u5feb\u6307\u9488\u548c\u6162\u6307\u9488\u76f8\u9047\u7684\u65f6\u5019\uff0c\u5feb\u6307\u9488\u56de\u5230\u5934\u7ed3\u70b9\u7684\u4f4d\u7f6e\uff0c\u548c\u6162\u6307\u9488\u4e00\u8d77\u4ee5\u4e00\u6b65\u7684\u6b65\u5e45\u8d70\uff0c\u76f8\u9047\u7684\u8282\u70b9\u5c31\u662f\u7b2c\u4e00\u4e2a\u5165\u73af\u8282\u70b9\u3002<\/p>\n
public static Node getLoopNode(Node head) {\n if (head == null || head.next == null || head.next.next == null) {\n return null;\n }\n Node n1 = head.next; \/\/ n1 -> slow\n Node n2 = head.next.next; \/\/ n2 -> fast\n while (n1 != n2) {\n if (n2.next == null || n2.next.next == null) {\n return null;\n }\n n2 = n2.next.next;\n n1 = n1.next;\n }\n n2 = head; \/\/ n2 -> walk again from head\n while (n1 != n2) {\n n1 = n1.next;\n n2 = n2.next;\n }\n return n1;\n}<\/code><\/pre>\n\u95ee\u98982.\u4e24\u4e2a\u65e0\u73af\u94fe\u8868\u600e\u4e48\u627e\u5230\u7b2c\u4e00\u4e2a\u76f8\u4ea4\u7684\u8282\u70b9<\/h6>\n
<\/div><\/p>\n\u7b2c\u4e00\u79cd\u65b9\u6cd5
\n\u5229\u7528\u54c8\u5e0c\u8868\uff1a
\n\u904d\u5386\u7b2c\u4e00\u4e2a\u94fe\u8868\uff0c\u628a\u6240\u6709\u7684\u8282\u70b9\u90fd\u5b58\u5165\u5230\u54c8\u5e0c\u8868\u4e2d\uff08\u56e0\u4e3a\u662f\u65e0\u73af\u94fe\u8868\uff0c\u6240\u4ee5\u4e00\u5b9a\u53ef\u4ee5\u5b58\u8fdb\u53bb\uff09\uff08\u54c8\u5e0c\u8868\u4e2d\u5b58\u653e\u7684\u8282\u70b9\u7684\u5185\u5b58\u5730\u5740\uff0c\u548c\u8282\u70b9\u7684\u503c\u6ca1\u6709\u5173\u7cfb\uff09\uff1b\u904d\u5386\u7b2c\u4e8c\u4e2a\u94fe\u8868\u7684\u8282\u70b9\uff0c\u6bcf\u904d\u5386\u4e00\u4e2a\u67e5\u770b\u54c8\u5e0c\u8868\u4e2d\u662f\u5426\u5df2\u7ecf\u6709\u4e86\u8fd9\u4e2a\u8282\u70b9\uff0c\u54c8\u5e0c\u8868\u4e2d\u7b2c\u4e00\u4e2a\u5b58\u4e0d\u8fdb\u53bb\u7684\u8282\u70b9\u5c31\u662f\u7b2c\u4e00\u4e2a\u76f8\u4ea4\u8282\u70b9\u3002
\n\u54c8\u5e0c\u8868\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u4e0d\u6ee1\u8db3\u9898\u76ee\u8981\u6c42\u3002<\/p>\n
\u7b2c\u4e8c\u79cd\u65b9\u6cd5<\/p>\n
1.\u5148\u786e\u5b9a\u4e24\u4e2a\u94fe\u8868\u7684\u957f\u5ea6\u5dee
\n2.\u4e24\u4e2a\u94fe\u8868\u5728\u79fb\u52a8\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5982\u679c\u76f8\u4ea4\u4e86\uff08\u6839\u636e\u94fe\u8868\u7684\u7279\u6b8a\u6027\uff0c\u53ea\u6709\u4e00\u4e2anext\u6307\u9488\uff0c\u53ea\u80fd\u8fde\u63a5\u4e00\u4e2a\u4e0b\u4e00\u4e2a\u7ed3\u70b9\uff0c\u6240\u4ee5\u7b2c\u4e00\u4e2a\u516c\u5171\u7ed3\u70b9\u4e4b\u540e\uff0c\u53ea\u77e5\u9053\u94fe\u8868\u7684\u7ed3\u5c3e\u90fd\u662f\u76f8\u540c\u7684\uff09\uff08\u53d8\u91cf\u4e2d\u5b58\u653e\u7684\u662f\u5185\u5b58\u5730\u5740\uff0c\u548c\u6570\u636e\u65e0\u5173\uff09\uff0c\u90a3\u4e48\u672b\u5c3e\u7684\u5185\u5b58\u5730\u5740\u4e00\u5b9a\u662f\u76f8\u540c\u7684
\n3.\u5982\u679c\u6700\u540e\u7684\u76f8\u7b49\uff0c\u90a3\u4e48\u8bf4\u660e\u662f\u6709\u76f8\u4ea4\u7684\u8282\u70b9\u7684\uff0c\u4f46\u662f\u4e0d\u4e00\u5b9a\u662f\u6700\u540e\u4e00\u4e2a\u3002
\n4.\u8ba9\u957f\u7684\u8282\u70b9\u4ece\u5934\u5f00\u59cb\uff0c\u5148\u8d70\u8ddd\u79bb\u5dee\u4e2a\u8ddd\u79bb\uff1b\u77ed\u7684\u4ece\u5934\u5f00\u59cb\u8d70\uff0c\u76f8\u7b49\u7684\u5c31\u662f\u4ed6\u4eec\u76f8\u4ea4\u7684\u8282\u70b9<\/p>\n
public static Node noLoop(Node head1, Node head2) {\n if (head1 == null || head2 == null) {\n return null;\n }\n Node cur1 = head1;\n Node cur2 = head2;\n int n = 0;\n while (cur1.next != null) {\n n++;\n cur1 = cur1.next;\n }\n while (cur2.next != null) {\n n--;\n cur2 = cur2.next;\n }\n if (cur1 != cur2) {\n return null;\n }\n cur1 = n > 0 ? head1 : head2;\n cur2 = cur1 == head1 ? head2 : head1;\n n = Math.abs(n);\n while (n != 0) {\n n--;\n cur1 = cur1.next;\n }\n while (cur1 != cur2) {\n cur1 = cur1.next;\n cur2 = cur2.next;\n }\n return cur1;\n}\n<\/code><\/pre>\n\u95ee\u9898\u4e09\uff1a\u5982\u4f55\u5224\u65ad\u4e24\u4e2a\u6709\u73af\u94fe\u8868\u662f\u5426\u76f8\u4ea4\uff0c\u76f8\u4ea4\u5219\u8fd4\u56de\u7b2c\u4e00\u4e2a\u76f8\u4ea4\u8282\u70b9\uff0c\u4e0d\u76f8\u4ea4\u5219\u8fd4\u56denull\u3002<\/h6>\n
\u8003\u8651\u95ee\u9898\u4e09\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5df2\u7ecf\u5f97\u5230\u4e86\u4e24\u4e2a\u94fe\u8868\u5404\u81ea\u7684\u7b2c\u4e00\u4e2a\u5165\u73af\u8282\u70b9\uff0c\u5047\u8bbe\u94fe\u8868 1 \u7684\u7b2c\u4e00\u4e2a\u5165\u73af\u8282\u70b9\u8bb0\u4e3aloop1\uff0c\u94fe\u88682 \u7684\u7b2c\u4e00\u4e2a\u5165\u73af\u8282\u70b9\u8bb0\u4e3aloop2\u3002\u4ee5\u4e0b\u662f\u89e3\u51b3\u95ee\u9898\u4e09\u7684\u8fc7\u7a0b\u3002<\/p>\n
1\uff0e\u5982\u679cloop1==loop2\uff0c\u90a3\u4e48\u4e24\u4e2a\u94fe\u8868\u7684\u62d3\u6251\u7ed3\u6784\u5982\u56fe<\/p>\n
<\/div><\/p>\n\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u53ea\u8981\u8003\u8651\u94fe\u88681 \u4ece\u5934\u5f00\u59cb\u5230loop1 \u8fd9\u4e00\u6bb5\u4e0e\u94fe\u88682 \u4ece\u5934\u5f00\u59cb\u5230loop2 \u8fd9\u4e00\u6bb5\uff0c\u5728\u90a3\u91cc\u7b2c\u4e00\u6b21\u76f8\u4ea4\u5373\u53ef\uff0c\u800c\u4e0d\u7528\u8003\u8651\u8fdb\u73af\u8be5\u600e\u4e48\u5904\u7406\uff0c\u8fd9\u5c31\u4e0e\u95ee\u9898\u4e8c\u7c7b\u4f3c\uff0c\u53ea\u4e0d\u8fc7\u95ee\u9898\u4e8c\u662f\u628anull \u4f5c\u4e3a\u4e00\u4e2a\u94fe\u8868\u7684\u7ec8\u70b9\uff0c\u800c\u8fd9\u91cc\u662f\u628aloop1(loop2)\u4f5c\u4e3a\u94fe\u8868\u7684\u7ec8\u70b9\u3002\u4f46\u662f\u5224\u65ad\u7684\u4e3b\u8981\u8fc7\u7a0b\u662f\u76f8\u540c\u7684\u3002<\/p>\n
2\uff0e\u5982\u679cloop1!=loop2\uff0c\u4e24\u4e2a\u94fe\u8868\u4e0d\u76f8\u4ea4\u7684\u62d3\u6251\u7ed3\u6784\u5982\u56fe2-9 \u6240\u793a\u3002\u4e24\u4e2a\u94fe\u8868\u76f8\u4ea4\u7684\u62d3\u6251\u7ed3\u6784\u5982\u56fe2-10 \u6240\u793a\u3002<\/p>\n
<\/div><\/p>\n\u5982\u4f55\u5206\u8fa8\u662f\u8fd9\u4e24\u79cd\u62d3\u6251\u7ed3\u6784\u7684\u54ea\u4e00\u79cd\u5462\uff1f\u8fdb\u5165\u6b65\u9aa43\u3002
\n3\uff0e\u8ba9\u94fe\u88681 \u4eceloop1 \u51fa\u53d1\uff0c\u56e0\u4e3aloop1 \u548c\u4e4b\u540e\u7684\u6240\u6709\u8282\u70b9\u90fd\u5728\u73af\u4e0a\uff0c\u6240\u4ee5 \u5c06\u6765\u4e00\u5b9a\u80fd\u56de\u5230 loop1\u3002<\/p>\n
\u5982\u679c\u56de\u5230loop1 \u4e4b\u524d \u5e76\u6ca1\u6709\u9047\u5230loop2\uff0c\u8bf4\u660e\u4e24\u4e2a\u94fe\u8868\u7684\u62d3\u6251\u7ed3\u6784\u5982\u56fe2-9 \u6240\u793a\uff0c\u4e5f\u5c31\u662f \u4e0d\u76f8\u4ea4\uff0c\u76f4\u63a5\u8fd4\u56de null\uff1b
\n\u5982\u679c\u56de\u5230loop1 \u4e4b\u524d \u9047\u5230\u4e86loop2\uff0c\u8bf4\u660e\u4e24\u4e2a\u94fe\u8868\u7684\u62d3\u6251\u7ed3\u6784\u5982\u56fe2-10\u6240\u793a\uff0c\u4e5f\u5c31\u662f \u76f8\u4ea4\u3002\u56e0\u4e3a loop1 \u548c loop2 \u90fd\u5728\u4e24\u6761\u94fe\u8868\u4e0a\uff0c\u53ea\u4e0d\u8fc7loop1 \u662f\u79bb\u94fe\u88681 \u8f83\u8fd1\u7684\u8282\u70b9\uff0cloop2 \u662f\u79bb\u94fe\u88682 \u8f83\u8fd1\u7684\u8282\u70b9\u3002\u6240\u4ee5\uff0c\u6b64\u65f6\u8fd4\u56deloop1 \u6216loop2 \u90fd\u53ef\u4ee5\u3002
\n\u95ee\u9898\u4e09\u7684\u5177\u4f53\u5b9e\u73b0\u53c2\u770b\u5982\u4e0b\u4ee3\u7801\u4e2d\u7684 bothLoop \u65b9\u6cd5\u3002<\/p>\n
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {\n Node cur1 = null;\n Node cur2 = null;\n if (loop1 == loop2) {\n cur1 = head1;\n cur2 = head2;\n int n = 0;\n while (cur1 != loop1) {\n n++;\n cur1 = cur1.next;\n }\n while (cur2 != loop2) {\n n--;\n cur2 = cur2.next;\n }\n cur1 = n > 0 ? head1 : head2;\n cur2 = cur1 == head1 ? head2 : head1;\n n = Math.abs(n);\n while (n != 0) {\n n--;\n cur1 = cur1.next;\n }\n while (cur1 != cur2) {\n cur1 = cur1.next;\n cur2 = cur2.next;\n }\n return cur1;\n } else {\n cur1 = loop1.next;\n while (cur1 != loop1) {\n if (cur1 == loop2) {\n return loop1;\n }\n cur1 = cur1.next;\n }\n return null;\n }\n}<\/code><\/pre>\n\u54c8\u5e0c\u8868<\/h3>\n
UnOrderMap UnSortedMap UnOrderSet UnSortedSet-->C++<\/p>\n
Map\uff1aKey -> Value<\/p>\n
Set\uff1aKey<\/p>\n
<\/div>
\n<\/div>
\n<\/div>
\n<\/div><\/p>\n\u53cd\u8f6c\u5355\u5411\u94fe\u8868\u548c\u53cc\u5411\u94fe\u8868<\/h4>\n\/\/\u53cd\u8f6c\u5355\u5411\u94fe\u8868\npublic static Node reverseOne(Node head){\n if(head == Null||head.next == Null){\n return head;\n }\n Node new_head = Null;\n while(head != Null){\n Node tmp = head.next;\n head.next = new_head;\n new_head = head;\n head = tmp;\n }\n return new_head;\n}<\/code><\/pre>\n\/\/\u53cd\u8f6c\u53cc\u5411\u94fe\u8868\npublic static DoubleNode reverse(DoubleNode head) {\n if (head == null || head.next == null) {\n return head;\n }\n DoubleNode pre = null;\n DoubleNode next = null;\n while (head != null) {\n next = head.next;\n head.next = pre;\n head.last = next;\n pre = head;\n head = next;\n }\n return pre;\n}<\/code><\/pre>\n\u6253\u5370\u4e24\u4e2a\u6709\u5e8f\u5217\u8868\u7684\u516c\u5171\u90e8\u5206<\/h4>\n
\u4e0a\u4e0b\u8fdb\u884c\u6bd4\u8f83\uff0c\u503c\u5c0f\u7684\u90e8\u5206\u6307\u9488\u540e\u79fb\u518d\u6bd4\u8f83\uff0c\u77e5\u9053\u5176\u4e2d\u4e00\u4e2a\u6570\u7ec4\u8d8a\u754c\u3002<\/p>\n
public static void printCommonPart(Node head1 , Node head2){\n System.out.println("common part:");\n while(head1!=null && head2!=null){\n if(head1.value<head2.value){\n head1=head1.next;\n }else if(head1.value >head2.value){\n head2=head2.next;\n }else {\n System.out.println(head1.value + "");\n head1 = head1.next;\n head2 = head2.next;\n }\n }\n System.out.println();\n}<\/code><\/pre>\n\u5224\u65ad\u5355\u94fe\u8868\u662f\u5426\u662f\u56de\u6587\u7ed3\u6784<\/h4>\n\n- \u5229\u7528\u6808\u5148\u8fdb\u540e\u51fa\u7684\u7279\u6027\uff0c\u5c06\u94fe\u8868\u4e2d\u7684\u5143\u7d20\u653e\u8fdb\u6808\u5185\uff0c\u518d\u5c06\u6808\u5185\u5143\u7d20\u63d0\u51fa\u505a\u6bd4\u8f83\uff0c\u82e5\u5168\u90e8\u76f8\u7b49\u5219\u662f\u56de\u6587\u7ed3\u6784\u3002<\/li>\n
- \u5c06\u6808\u540e\u534a\u8fb9\u7684\u5143\u7d20\u653e\u5165\u6808\u4e0e\u524d\u4e00\u534a\u5143\u7d20\u4f5c\u6bd4\u8f83\uff0c\u82e5\u5168\u90e8\u76f8\u7b49\u5219\u8bc1\u660e\u662f\u56de\u6587\u7ed3\u6784\uff08\u5b9e\u73b0\u65b9\u5f0f\uff1a\u5feb\u6162\u6307\u9488\uff09\u3002<\/li>\n
- \u6700\u4f18\u65b9\u6cd5\uff0c\u53f3\u4fa7\u94fe\u8868\u53cd\u5411\uff0c\u4f9d\u6b21\u4e0e\u5de6\u8fb9\u4f5c\u6bd4\u8f83\uff0c\u5168\u90e8\u76f8\u7b49\u5219\u662f\u56de\u6587\u7ed3\u6784\u3002<\/li>\n<\/ol>\n
package class04;\n\nimport java.util.Stack;\n\npublic class Code04_IsPalindromeList {\n\n public static class Node {\n public int value;\n public Node next;\n\n public Node(int data) {\n this.value = data;\n }\n }\n \/\/ need n extra space\n public static boolean isPalindrome1(Node head) {\n Stack<Node> stack = new Stack<Node>();\/\/\u65b0\u5efa\u6808\n Node cur = head;\/\/\u904d\u5386\u94fe\u8868\u7528\u7684\uff0c\u53e6\u5916\u4e00\u4e2aNode head\n while (cur != null) {\/\/\u538b\u6808\n stack.push(cur);\n cur = cur.next;\n }\n while (head != null) {\n if (head.value != stack.pop().value) {\n return false;\n }\n head = head.next;\n }\n return true;\n }<\/code><\/pre>\n<\/div><\/p>\n\u5c06\u5355\u94fe\u8868\u8f6c\u5316\u6210\u5de6\u8fb9\u5c0f\uff0c\u4e2d\u95f4\u76f8\u7b49\uff0c\u5de6\u8fb9\u5927\u7684\u5f62\u5f0f\u3002<\/h4>\n\/\/\u94fe\u8868\u7ed3\u6784\u5982\u4e0b\uff1a\npublic static class Node {\n public Node next;\n public int value;\n\n public Node(int data) {\n value = data;\n }\n}<\/code><\/pre>\n\u57fa\u7840\u89e3\u6cd5<\/h5>\n
\u601d\u8def<\/p>\n
\n- \u6309\u94fe\u8868\u987a\u5e8f\uff0c\u7528\u6570\u7ec4\u88c5\u6bcf\u4e00\u4e2a\u8282\u70b9 <\/li>\n
- \u7528\u8377\u5170\u56fd\u65d7\u7b97\u6cd5\u5bf9\u6570\u7ec4\u6392\u5e8f\uff0c\u5176\u5b9e\u5c31\u662f\u5feb\u62cd\u7684partition\u8fc7\u7a0b<\/li>\n
- \u5c06\u6570\u7ec4\u8fd8\u539f\u4e3a\u94fe\u8868<\/li>\n<\/ol>\n
public static Node listPartition1(Node head, int pivot) {\n if (head == null) {\n return head;\n }\n Node cur = head;\n int i = 0;\n while (cur != null) {\n i++;\n cur = cur.next;\n }\n Node[] nodeArr = new Node[i];\n cur = head;\n \/\/ \u628a\u94fe\u8868\u7684\u503c\u590d\u5236\u5230\u6570\u7ec4\u4e2d\n for(i = 0; i < nodeArr.length; i++) {\n nodeArr[i] = cur;\n cur = cur.next;\n }\n \/\/ \u5bf9\u6570\u636e\u8fdb\u884c\u201c\u8377\u5170\u56fd\u65d7\u201d\u5206\u7ec4\n arrPartition(nodeArr, pivot);\n \/\/ \u91cd\u65b0\u628a\u94fe\u8868\u8fde\u63a5\n for(i = 1; i < nodeArr.length; i++) {\n nodeArr[i - 1].next = nodeArr[i];\n }\n nodeArr[i - 1].next = null;\n return nodeArr[0];\n}\n\/\/\/ \u8377\u5170\u56fd\u65d7\u7b97\u6cd5\npublic static void arrPartition(Node[] nodeArr, int pivot) {\n int more = nodeArr.length;\n int less = -1;\n int i = 0;\n while(i != more) {\n if (nodeArr[i].value < pivot) {\n less++;\n swap(nodeArr, less, i);\n i++;\n }else if(nodeArr[i].value > pivot) {\n more--;\n swap(nodeArr, i, more);\n }else {\n i++;\n }\n }\n}<\/code><\/pre>\n\u8fdb\u9636\u89e3\u6cd5<\/h5>\n
\u601d\u8def<\/p>\n
\n- \u4f7f\u75286\u4e2a\u6307\u9488\u5efa\u7acb\u5c0f\u4e8e\uff0c\u7b49\u4e8e\uff0c\u5927\u4e8epivot\u7684\u94fe\u8868\u533a\u57df<\/li>\n
- \u6bcf\u4e00\u6b21\u904d\u5386\u90fd\u66f4\u65b0\u5bf9\u5e94\u533a\u57df\u7684\u5934\u5c3e\u8282\u70b9<\/li>\n
- \u5168\u90e8\u904d\u5386\u8282\u70b9\u5b8c\u6bd5\u540e\uff0c\u5c06\u8fde\u63a5\u5c0f\u4e8e\u7684\u5c3e->\u7b49\u4e8e\u7684\u5934->\u7b49\u4e8e\u7684\u5c3e->\u5927\u4e8e\u7684\u5934<\/li>\n<\/ol>\n
public static Node listPartition2(Node head, int pivot) {\n \/\/ \u5c0f\u4e8epivot\u7684\u94fe\u8868\u5934\u5c3e\u8282\u70b9\n Node lessSt = null;\n Node lessEnd = null;\n \/\/ \u7b49\u4e8epivot\u7684\u94fe\u8868\u5934\u5c3e\u8282\u70b9\n Node eqSt = null;\n Node eqEnd = null;\n \/\/ \u5927\u4e8epivot\u7684\u94fe\u8868\u5934\u5c3e\u8282\u70b9\n Node moreSt = null;\n Node moreEnd = null;\n \/\/ \u7528\u4e8e\u4fdd\u5b58next\u6307\u9488\n Node next = null;\n \/\/ \u904d\u5386\u94fe\u8868\n while(head != null) {\n next = head.next;\n \/\/ \u4e3a\u4e86\u4e0d\u6c61\u67d3\u5c0f\u4e8e\uff0c\u7b49\u4e8e\uff0c\u5927\u4e8e\u7684\u6307\u9488next\uff0c\u8fd9\u91cc\u6e05\u7a7a\n head.next = null;\n if(head.value < pivot) {\n if(lessSt == null) {\n lessSt = head;\n lessEnd = head;\n }else {\n lessEnd.next = head;\n lessEnd = head;\n }\n }else if(head.value == pivot) {\n if(eqSt == null) {\n eqSt = head;\n eqEnd = head;\n }else {\n eqEnd.next = head;\n eqEnd = head;\n }\n }else {\n if(moreSt == null) {\n moreSt = head;\n moreEnd = head;\n }else {\n moreEnd.next = head;\n moreEnd = head;\n }\n }\n head = next;\n }\n \/\/ \u5c0f\u4e8e\u548c\u7b49\u4e8e\u533a\u57df\u76f8\u8fde\n if(lessEnd != null) {\n lessEnd.next = eqSt;\n \/\/ \u5224\u65adequal\u7684\u7ed3\u5c3e\u6307\u9488\u662f\u5426\u4e3a\u7a7a\n eqEnd = eqEnd == null ? lessEnd : eqEnd;\n }\n \/\/ \u6700\u540e\u7b49\u4e8e\uff0c\u5927\u4e8e\u533a\u57df\u76f8\u8fde\n if (eqEnd != null) {\n eqEnd.next = moreSt;\n }\n if (lessSt != null) {\n return lessSt;\n }\n if (eqSt != null) {\n return eqSt;\n }\n if (moreSt != null) {\n return moreSt;\n }\n return null;\n}<\/code><\/pre>\n\u590d\u5236\u542b\u6709\u968f\u5373\u6307\u9488\u8282\u70b9\u7684\u94fe\u8868<\/h4>\n\u666e\u901a\u89e3\u6cd5<\/h5>\n
\u9996\u5148\u4ecb\u7ecd\u666e\u901a\u89e3\u6cd5\uff0c\u666e\u901a\u89e3\u6cd5\u53ef\u4ee5\u505a\u5230\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(N)\uff0c\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(N)\uff0c\u9700\u8981\u4f7f\u7528\u5230\u54c8\u5e0c\u8868\uff08HashMap\uff09\u7ed3\u6784\u3002\u5177\u4f53\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n
\n- \n
\u4ece\u5de6\u5230\u53f3\u904d\u5386\u94fe\u8868\uff0c\u5bf9\u6bcf\u4e2a\u8282\u70b9\u90fd\u590d\u5236\u751f\u6210\u76f8\u5e94\u7684\u526f\u672c\u8282\u70b9\uff0c\u7136\u540e\u5c06\u5bf9\u5e94\u5173\u7cfb\u653e\u5165\u54c8\u5e0c\u8868map \u4e2d\u3002\u4f8b\u5982\uff0c\u94fe\u88681->2->3->null\uff0c\u904d\u53861\u30012\u30013 \u65f6\u4f9d\u6b21\u751f\u62101\u2032\u30012\u2032\u30013\u2032\uff0c\u6700\u540e\u5c06\u5bf9\u5e94\u5173\u7cfb\u653e\u5165map \u4e2d\u3002<\/p>\n
<\/div><\/p>\n\u6b65\u9aa41 \u5b8c\u6210\u540e\uff0c\u539f\u94fe\u8868\u6ca1\u6709\u4efb\u4f55\u53d8\u5316\uff0c\u6bcf\u4e00\u4e2a\u526f\u672c\u8282\u70b9\u7684next \u548crand \u6307\u9488\u90fd\u6307\u5411null\u3002<\/p>\n<\/li>\n
- \n
\u518d\u4ece\u5de6\u5230\u53f3\u904d\u5386\u94fe\u8868\uff0c\u6b64\u65f6\u5c31\u53ef\u4ee5\u8bbe\u7f6e\u6bcf\u4e00\u4e2a\u526f\u672c\u8282\u70b9\u7684next \u548crand \u6307\u9488\u3002<\/p>\n
\u4f8b\u5982\uff1a\u539f\u94fe\u88681->2->3->null\uff0c\u5047\u8bbe1 \u7684rand \u6307\u9488\u6307\u54113\uff0c2 \u7684rand \u6307\u9488\u6307\u5411null\uff0c3 \u7684rand\u6307\u9488\u6307\u54111\u3002\u904d\u5386\u5230\u8282\u70b91 \u65f6\uff0c\u53ef\u4ee5\u4ecemap \u4e2d\u5f97\u5230\u8282\u70b91 \u7684\u526f\u672c\u8282\u70b91\u2032\uff0c\u8282\u70b91 \u7684next \u6307\u5411\u8282\u70b92\uff0c\u6240\u4ee5\u4ecemap \u4e2d\u5f97\u5230\u8282\u70b92 \u7684\u526f\u672c\u8282\u70b92\u2032\uff0c\u7136\u540e\u4ee41\u2032.next=2\u2032\uff0c\u526f\u672c\u8282\u70b91\u2032\u7684next \u6307\u9488\u5c31\u8bbe\u7f6e\u597d\u4e86\u3002\u540c\u65f6\u8282\u70b91 \u7684rand \u6307\u5411\u8282\u70b93\uff0c\u6240\u4ee5\u4ecemap \u4e2d\u5f97\u5230\u8282\u70b93 \u7684\u526f\u672c\u8282\u70b93\u2032\uff0c\u7136\u540e\u4ee41\u2032.rand=3\u2032\uff0c\u526f\u672c\u8282\u70b91\u2032\u7684rand \u6307\u9488\u4e5f\u8bbe\u7f6e\u597d\u4e86\u3002\u4ee5\u8fd9\u79cd\u65b9\u5f0f\u53ef\u4ee5\u8bbe\u7f6e\u6bcf\u4e00\u4e2a\u526f\u672c\u8282\u70b9\u7684next\u4e0erand \u6307\u9488\u3002<\/p>\n<\/li>\n
- \n
\u5c061\u2032\u8282\u70b9\u4f5c\u4e3a\u7ed3\u679c\u8fd4\u56de\u5373\u53ef\u3002<\/p>\n<\/li>\n<\/ol>\n
\u54c8\u5e0c\u8868\u589e\u5220\u6539\u67e5\u7684\u64cd\u4f5c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u662fO(1)\uff0c\u666e\u901a\u65b9\u6cd5\u4e00\u5171\u53ea\u904d\u5386\u94fe\u8868\u4e24\u904d\uff0c\u6240\u4ee5\u666e\u901a\u89e3\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(N)\uff0c\u56e0\u4e3a\u4f7f\u7528\u4e86\u54c8\u5e0c\u8868\u6765\u4fdd\u5b58\u539f\u8282\u70b9\u4e0e\u526f\u672c\u8282\u70b9\u7684\u5bf9\u5e94\u5173\u7cfb\uff0c\u6240\u4ee5\u989d\u5916\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(N)\u3002<\/p>\n
\u8fdb\u9636\u89e3\u6cd5<\/h5>\n
\u8fdb\u9636\u89e3\u6cd5\u4e0d\u4f7f\u7528\u54c8\u5e0c\u8868\u6765\u4fdd\u5b58\u5bf9\u5e94\u5173\u7cfb\uff0c\u800c\u53ea\u7528\u6709\u9650\u7684\u51e0\u4e2a\u53d8\u91cf\u5b8c\u6210\u6240\u6709\u7684\u529f\u80fd\u3002\u5177\u4f53\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n
\n- \n
\u4ece\u5de6\u5230\u53f3\u904d\u5386\u94fe\u8868\uff0c\u5bf9\u6bcf\u4e2a\u8282\u70b9cur \u90fd\u590d\u5236\u751f\u6210\u76f8\u5e94\u7684\u526f\u672c\u8282\u70b9copy\uff0c\u7136\u540e\u628acopy \u653e\u5728cur \u548c\u4e0b\u4e00\u4e2a\u8981\u904d\u5386\u8282\u70b9\u7684\u4e2d\u95f4\u3002<\/p>\n
\u4f8b\u5982\uff1a\u539f\u94fe\u88681->2->3->null\uff0c\u5728\u6b65\u9aa41 \u4e2d\u5b8c\u6210\u540e\uff0c\u539f\u94fe\u8868\u53d8\u62101->1\u2032->2->2\u2032->3->3\u2032->null\u3002<\/p>\n<\/li>\n
- \n
\u518d\u4ece\u5de6\u5230\u53f3\u904d\u5386\u94fe\u8868\uff0c\u5728\u904d\u5386\u65f6\u8bbe\u7f6e\u6bcf\u4e00\u4e2a\u526f\u672c\u8282\u70b9\u7684rand \u6307\u9488\u3002\u8fd8\u662f\u4e3e\u4f8b\u6765\u8bf4\u660e\u8c03\u6574\u8fc7\u7a0b\u3002<\/p>\n
\u4f8b\u5982\uff1a\u6b64\u65f6\u94fe\u8868\u4e3a1->1\u2032->2->2\u2032->3->3\u2032->null\uff0c\u5047\u8bbe1 \u7684rand \u6307\u9488\u6307\u54113\uff0c2 \u7684rand \u6307\u9488\u6307\u5411null\uff0c3 \u7684rand \u6307\u9488\u6307\u54111\u3002\u904d\u5386\u5230\u8282\u70b91 \u65f6\uff0c\u8282\u70b91 \u7684\u4e0b\u4e00\u4e2a\u8282\u70b91.next \u5c31\u662f\u5176\u526f\u672c\u8282\u70b91\u2032\u30021 \u7684rand \u6307\u9488\u6307\u54113\uff0c\u6240\u4ee51\u2032\u7684rand \u6307\u9488\u5e94\u8be5\u6307\u54113\u2032\u3002\u5982\u4f55\u627e\u52303\u2032\u5462\uff1f\u56e0\u4e3a\u6bcf\u4e2a\u8282\u70b9\u7684\u526f\u672c\u8282\u70b9\u90fd\u5728\u81ea\u5df1\u7684\u540e\u4e00\u4e2a\uff0c\u6240\u4ee5\u6b64\u65f6\u901a\u8fc73.next \u5c31\u53ef\u4ee5\u627e\u52303\u2032\uff0c\u4ee41\u2032.next=3\u2032\u5373\u53ef\u3002\u4ee5\u8fd9\u79cd\u65b9\u5f0f\u53ef\u4ee5\u8bbe\u7f6e\u6bcf\u4e00\u4e2a\u526f\u672c\u8282\u70b9\u7684rand \u6307\u9488\u3002<\/p>\n<\/li>\n
- \n
\u6b65\u9aa42 \u5b8c\u6210\u540e\uff0c\u8282\u70b91\uff0c2\uff0c3\uff0c\u2026\u2026\u4e4b\u95f4\u7684rand \u5173\u7cfb\u6ca1\u6709\u4efb\u4f55\u53d8\u5316\uff0c\u8282\u70b91\u2032\uff0c2\u2032\uff0c3\u2032\u2026\u2026\u4e4b\u95f4\u7684rand \u5173\u7cfb\u4e5f\u88ab\u6b63\u786e\u8bbe\u7f6e\u4e86\uff0c\u6b64\u65f6\u6240\u6709\u7684\u8282\u70b9\u4e0e\u526f\u672c\u8282\u70b9\u4e32\u5728\u4e00\u8d77\uff0c\u5c06\u5176\u5206\u79bb\u51fa\u6765\u5373\u53ef\u3002\u4f8b\u5982\uff1a\u6b64\u65f6\u94fe\u8868\u4e3a1->1\u2032->2->2\u2032->3->3\u2032->null\uff0c\u5206\u79bb\u62101->2->3->null \u548c1\u2032->2\u2032->3\u2032->null \u5373\u53ef\uff0c\u5e76\u4e14\u5728\u8fd9\u4e00\u6b65\u4e2d\uff0c\u6bcf\u4e2a\u8282\u70b9\u7684rand \u6307\u9488\u4e0d\u7528\u505a\u4efb\u4f55\u8c03\u6574\uff0c\u5728\u6b65\u9aa42 \u4e2d\u90fd\u5df2\u7ecf\u8bbe\u7f6e\u597d\u3002<\/p>\n<\/li>\n
- \n
\u5c061\u2032\u8282\u70b9\u4f5c\u4e3a\u7ed3\u679c\u8fd4\u56de\u5373\u53ef\u3002<\/p>\n
<\/div>\n<\/li>\n<\/ol>\nimport java.util.HashMap;\npublic class Code_13_CopyListWithRandom {\n public static class Node {\n public int value;\n public Node next;\n public Node rand;\n\n public Node(int data) {\n this.value = data;\n }\n }\n \/\/\u65b9\u6cd5\u4e00\uff1a\u91c7\u7528hashMap\n public static Node copyListWithRand1(Node head) {\n HashMap<Node, Node> map = new HashMap<Node, Node>();\n Node cur = head;\n while (cur != null) {\n map.put(cur, new Node(cur.value));\n cur = cur.next;\n }\n cur = head;\n while (cur != null) {\n map.get(cur).next = map.get(cur.next);\n map.get(cur).rand = map.get(cur.rand);\n cur = cur.next;\n }\n return map.get(head);\n }\n \/\/\u65b9\u6cd5\u4e8c\uff1ai \u548c i\u2019\u4e00\u7ec4\n public static Node copyListWithRand2(Node head) {\n if (head == null) {\n return null;\n }\n Node cur = head;\n Node next = null;\n \/\/ copy node and link to every node\n while (cur != null) {\n next = cur.next;\n cur.next = new Node(cur.value);\n cur.next.next = next;\n cur = next;\n }\n cur = head;\n Node curCopy = null;\n \/\/ set copy node rand\n while (cur != null) {\n next = cur.next.next;\n curCopy = cur.next;\n curCopy.rand = cur.rand != null ? cur.rand.next : null;\n cur = next;\n }\n Node res = head.next;\n cur = head;\n \/\/ split\n while (cur != null) {\n next = cur.next.next;\n curCopy = cur.next;\n cur.next = next;\n curCopy.next = next != null ? next.next : null;\n cur = next;\n }\n return res;\n }\n}<\/code><\/pre>\n5.\u4e8c\u53c9\u6811<\/h2>\n\u4e8c\u53c9\u6811\u8282\u70b9\u7ed3\u6784<\/h3>\nclass Node<V>{\n V value;\n Node left;\n Node right;\n}\n<\/code><\/pre>\n\n- \u7528\u9012\u5f52\u548c\u975e\u9012\u5f52\u4e24\u79cd\u65b9\u5f0f\u5b9e\u73b0\u4e8c\u53c9\u6811\u7684\u5148\u5e8f\uff0c\u4e2d\u5e8f\uff0c\u540e\u5e8f\u904d\u5386<\/li>\n
- \u76f4\u89c2\u6253\u5370\u4e00\u9897\u4e8c\u53c9\u6811<\/li>\n
- \u5982\u4f55\u5b8c\u6210\u4e8c\u53c9\u6811\u7684\u5bbd\u5ea6\u5bfb\u4f18\u904d\u5386<\/li>\n<\/ul>\n
\u9012\u5f52\u904d\u5386<\/h3>\n
<\/div><\/p>\npublic static void f(Node head){\n if(head == null){\n return;\n }\n f(head.left);\n f(head.right);\n}<\/code><\/pre>\n\u5148\u5e8f\u3001\u4e2d\u5e8f\u3001\u540e\u5e8f\u904d\u5386<\/h3>\n
<\/div> <\/p>\n\u5148\u5e8f\u904d\u5386\uff1a\u5bf9\u4e8e\u4e8c\u53c9\u6811\u7684\u6bcf\u4e00\u4e2a\u5b50\u6811\u90fd\u662f\uff0c\u5148\u6253\u5e94\u5934\uff0c\u518d\u6253\u5370\u5de6\u5b69\u5b50\uff0c\u518d\u6253\u5370\u53f3\u5b69\u5b50
\n\u601d\u8def\uff1a\u73b0\u5c06\u5934\u653e\u5165\u4e00\u4e2a\u6808\u4e2d\uff0c\u5f00\u59cb\u904d\u5386\uff0c\u904d\u5386\u5185\u5bb9\uff1a\u6bcf\u6b21\u4ece\u6808\u4e2d\u5f39\u51fa\u6808\u9876\u5143\u7d20\uff0c\u6253\u5370\u6808\u9876\u5143\u7d20\uff0c\u5224\u65ad\u662f\u5426\u6709\u53f3\u5b69\u5b50\uff0c\u5c06\u6808\u9876\u5143\u7d20\u53f3\u5b69\u5b50\u538b\u5165\u6808\u4e2d\uff0c\u5224\u65ad\u662f\u5426\u6709\u5de6\u5b69\u5b50\uff0c\u518d\u5c06\u6808\u9876\u5143\u7d20\u7684\u5de6\u5b69\u5b50\u538b\u8fdb\u6808\u4e2d<\/p>\n
\u4e2d\u5e8f\u904d\u5386<\/p>\n
\u601d\u8def\uff1a\u5148\u5c06\u5934\u8282\u70b9\u7684\u5de6\u8fb9\u754c\u538b\u5165\u6808\u4e2d\uff0c\u5f00\u59cb\u904d\u5386\uff0c\u904d\u5386\u5185\u5bb9\uff1a\u6bcf\u6b21\u4ece\u6808\u4e2d\u5f39\u51fa\u6808\u9876\u5143\u7d20\uff0c\u6253\u5370\u6808\u9876\u5143\u7d20\uff0c\u5224\u65ad\u662f\u5426\u6709\u53f3\u5b69\u5b50\uff0c\u5c06\u6808\u9876\u5143\u7d20\u53f3\u5b69\u5b50\u538b\u5165\u6808\u4e2d\uff0c\u518d\u5c06\u5de6\u8fb9\u754c\u90fd\u538b\u5165\u6808\u4e2d<\/p>\n
\u540e\u5e8f\u904d\u5386<\/p>\n
\u601d\u8def\uff1a\u73b0\u5c06\u5934\u653e\u5165\u4e00\u4e2a\u68081\u4e2d\uff0c\u5f00\u59cb\u904d\u5386\uff0c\u904d\u5386\u5185\u5bb9\uff1a\u6bcf\u6b21\u4ece\u68081\u4e2d\u5f39\u51fa\u6808\u9876\u5143\u7d20\uff0c\u5c06\u5143\u7d20\u653e\u5165\u68082\u4e2d\uff08\u53ea\u6709\u8fd9\u91cc\u548c\u524d\u5e8f\u904d\u5386\u4e0d\u540c\uff09\uff0c\u5224\u65ad\u662f\u5426\u6709\u53f3\u5b69\u5b50\uff0c\u5c06\u68081\u9876\u5143\u7d20\u53f3\u5b69\u5b50\u538b\u5165\u68081\u4e2d\uff0c\u5224\u65ad\u662f\u5426\u6709\u5de6\u5b69\u5b50\uff0c\u518d\u5c06\u68081\u9876\u5143\u7d20\u7684\u5de6\u5b69\u5b50\u538b\u8fdb\u68081\u4e2d\u6700\u540e\u5c06\u68082\u7684\u5143\u7d20\u4e00\u6b21pop\u51fa\u6765\u6253\u5370<\/p>\n
public static class Node {\n public int value;\n public Node left;\n public Node right;\n\n public Node(int data) {\n this.value = data;\n }\n}\npublic static void preOrderRecur(Node head) { \/\/\u5148\u5e8f\n if (head == null) {\n return;\n }\n System.out.print(head.value + " "); \/\/\u552f\u4e00\u7684\u4e0d\u540c\u5c31\u662f\u6253\u5370\u8fc7\u7a0b\u7684\u4f4d\u7f6e\n preOrderRecur(head.left);\n preOrderRecur(head.right);\n}\npublic static void inOrderRecur(Node head) { \/\/\u4e2d\u5e8f\n if (head == null) {\n return;\n }\n inOrderRecur(head.left);\n System.out.print(head.value + " ");\n inOrderRecur(head.right);\n}\npublic static void posOrderRecur(Node head) { \/\/\u540e\u5e8f\n if (head == null) {\n return;\n }\n posOrderRecur(head.left);\n posOrderRecur(head.right);\n System.out.print(head.value + " ");\n}<\/code><\/pre>\n\u76f4\u89c2\u6253\u5370\u4e00\u9897\u4e8c\u53c9\u6811<\/h3>\n
![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155469.gif\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155471.gif\")
<\/div><\/p>\n![\"image-20210927204519064\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155472.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155473.webp\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155474.webp\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155475.webp\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic2.zhimg.com\/80\/v2-6cb948b4215fd7f35dc8b48a4b803251_1440w.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic3.zhimg.com\/80\/v2-c1328359469903077d8a268aa63a2966_1440w.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic4.zhimg.com\/80\/v2-bbd72d1ab15805f2f2ee4e21f05fed43_1440w.jpg\")
<\/div><\/p>\n![\"image-20210928193206427\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155476.png\")
<\/div>![\"image-20210928193416228\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155477.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/images2017.cnblogs.com\/blog\/849589\/201710\/849589-20171015230557043-37375010.gif\")
<\/div><\/p>\n![\"image-20210928195655821\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155478.png\")
<\/div>![\"image-20210928200509527\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155479.png\")
<\/div><\/p>\n![\"image-20210928204147518\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155480.png\")
<\/div> <\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155481.png\")
<\/div>![\"image-20210928212902737\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155482.png\")
<\/div><\/p>\n![\"image-20210928213524132\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155483.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/images2017.cnblogs.com\/blog\/849589\/201710\/849589-20171015230936371-1413523412.gif\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155484.webp\")
<\/div><\/p>\n![\"image-20210928215036559\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155485.png\")
<\/div><\/p>\n![\"image-20210929133932156\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155486.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/images2017.cnblogs.com\/blog\/849589\/201710\/849589-20171015231308699-356134237.gif\")
<\/div><\/p>\n![\"image-20210929145302457\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155487.png\")
<\/div>![\"image-20210929145816301\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155488.png\")
<\/div>![\"image-20210929150455862\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155489.png\")
<\/div> <\/p>\n![\"image-20210929155349986\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155490.png\")
<\/div> <\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155491.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155492.webp\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/img-blog.csdnimg.cn\/20200316092036366.gif\")
<\/div><\/p>\n![\"img\"](\"https:\/\/www.runoob.com\/wp-content\/uploads\/2019\/03\/Bucket_sort_1.svg_.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/www.runoob.com\/wp-content\/uploads\/2019\/03\/Bucket_sort_2.svg_.png\")
<\/div><\/p>\n![\"Alt\"](\"https:\/\/img-blog.csdnimg.cn\/img_convert\/0bde68f9137bb6720d6981d6d76574d7.png\")
<\/div>![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/img-blog.csdnimg.cn\/20200316185713868.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYxNDAyNg==,size_16,color_FFFFFF,t_70\")
<\/div>![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/img-blog.csdnimg.cn\/20200316185922116.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYxNDAyNg==,size_16,color_FFFFFF,t_70\")
<\/div>![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/img-blog.csdnimg.cn\/20200316190039212.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYxNDAyNg==,size_16,color_FFFFFF,t_70\")
<\/div>![\"image-20210929181019220\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155493.png\")
<\/div>![\"image-20210929181112055\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155494.png\")
<\/div><\/p>\n![\"image-20210929181156416\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155495.png\")
<\/div><\/p>\n![\"image-20210929181629533\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155496.png\")
<\/div>![\"image-20210929181923421\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155497.png\")
<\/div>![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155498.png\")
<\/div>![\"img\"](\"https:\/\/images2018.cnblogs.com\/blog\/849589\/201804\/849589-20180402133438219-1946132192.png\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155499.png\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155500.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155501.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic4.zhimg.com\/80\/v2-fed2e1976f4fa3236e123b6313dbf467_1440w.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155502.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155503.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155504.jpg\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155505.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155506.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic3.zhimg.com\/80\/v2-576b1c27abfe76baef41c002ba94fe62_1440w.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic4.zhimg.com\/80\/v2-5f99468c24519ecc8a88c57fb30d78a3_1440w.jpg\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155507.png\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155508.png\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/img-blog.csdnimg.cn\/20201209104650722.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx,size_16,color_FFFFFF,t_70\")
<\/div><\/p>\n![\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155509.png\")
<\/div><\/p>\n![\"image-20210930173545947\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155510.png\")
<\/div>![\"image-20210930173714951\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155511.png\")
<\/div>![\"image-20210930173743357\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155512.png\")
<\/div>![\"image-20211011213523252\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155513.png\")
<\/div><\/p>\n![\"img\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155514.png\")
<\/div><\/p>\n![\"image-20211011230438504\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155515.png\")
<\/div>\n<\/li>\n<\/ol>\n![\"image-20211018105858009\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155516.png\")
<\/div><\/p>\n![\"image-20211018110140041\"](\"https:\/\/pic-for-be.oss-cn-hangzhou.aliyuncs.com\/img\/202205140155517.png\")
<\/div> <\/p>\n