{"id":224,"date":"2013-06-19T20:34:38","date_gmt":"2013-06-19T12:34:38","guid":{"rendered":"http:\/\/coderbee.net\/?p=224"},"modified":"2013-06-19T23:08:29","modified_gmt":"2013-06-19T15:08:29","slug":"%e5%90%91%e9%87%8f%e6%97%8b%e8%bd%ac","status":"publish","type":"post","link":"https:\/\/coderbee.net\/index.php\/algorithm\/20130619\/224","title":{"rendered":"\u5411\u91cf\u65cb\u8f6c"},"content":{"rendered":"<h2>\u5411\u91cf\u65cb\u8f6c<\/h2>\n<p>\u9898\u76ee\u5747\u6765\u81ea\u300a\u7f16\u7a0b\u73e0\u7391\u300b\u3002<\/p>\n<h3>\u9898<\/h3>\n<p>\u5c06\u4e00\u4e2an\u5143\u4e00\u7ef4\u5411\u91cf\u5411\u5de6\u65cb\u8f6c\uff08\u5faa\u73af\u79fb\u4f4d\uff09i\u4e2a\u4f4d\u7f6e\u3002\u4f8b\u5982\uff0c\u5f53n=8\u65f6\u4e14i=3\u65f6\uff0c\u5411\u91cfabcdefgh\u65cb\u8f6c\u4e3adefghabc\u3002\u7b80\u5355\u7684\u4ee3\u7801\u4f7f\u7528\u4e00\u4e2an\u5143\u7684\u4e2d\u95f4\u5411\u91cf\u5728n\u6b65\u5185\u5b8c\u6210\u8be5\u5de5\u4f5c\u3002\u80fd\u5426\u4ec5\u7528\u6570\u5341\u4e2a\u989d\u5916\u76f4\u63a5\u7684\u5b58\u50a8\u7a7a\u95f4\uff0c\u5728\u6b63\u6bd4\u4e8en\u7684\u65f6\u95f4\u5185\u5b8c\u6210\u5411\u91cf\u7684\u65cb\u8f6c\uff1f<\/p>\n<p>\u65cb\u8f6c\u64cd\u4f5c\u5bf9\u5e94\u4e8e\u4ea4\u6362\u76f8\u90bb\u7684\u4e0d\u540c\u5927\u5c0f\u7684\u5185\u5b58\u5757\uff1a\u6bcf\u5f53\u62d6\u52a8\u6587\u4ef6\u4e2d\u7684\u4e00\u5757\u6587\u4ef6\u5230\u5176\u4ed6\u5730\u65b9\u65f6\uff0c\u5c31\u8981\u6c42\u7a0b\u5e8f\u4ea4\u6362\u4e24\u5757\u5185\u5b58\u4e2d\u7684\u5185\u5bb9\u3002<\/p>\n<h3>\u4e24\u4e2a\u7b80\u5355\u76f4\u63a5\u7684\u65b9\u6cd5<\/h3>\n<p>\u65b9\u6cd5\u4e00\uff1a\u9996\u5148\u5c06 <code>x<\/code> \u7684\u524d <code>i<\/code> \u4e2a\u5143\u7d20\u590d\u5236\u5230\u4e00\u4e2a\u4e34\u65f6\u6570\u7ec4\u4e2d\uff0c\u7136\u540e\u5c06\u4f59\u4e0b\u7684 <code>n-i<\/code> \u4e2a\u5143\u7d20\u5411\u5de6\u79fb\u52a8 <code>i<\/code> \u4e2a\u4f4d\u7f6e\uff0c\u6700\u597d\u5c06\u6700\u521d\u7684 <code>i<\/code> \u4e2a\u5143\u7d20\u4ece\u4e34\u65f6\u6570\u7ec4\u4e2d\u590d\u5236\u5230 <code>x<\/code> \u4e2d\u4f59\u4e0b\u7684\u4f4d\u7f6e\u3002\u8fd9\u79cd\u529e\u6cd5\u4f7f\u7528 <code>i<\/code> \u4e2a\u989d\u5916\u7684\u4f4d\u7f6e\u4ea7\u751f\u4e86\u8fc7\u5927\u7684\u5b58\u50a8\u7a7a\u95f4\u7684\u6d88\u8017\u3002<\/p>\n<p>\u65b9\u6cd5\u4e8c\uff1a\u5b9a\u4e49\u4e00\u4e2a\u51fd\u6570\u5c06 <code>i<\/code> \u5411\u5de6\u65cb\u8f6c\u4e00\u4e2a\u4f4d\u7f6e\uff08\u5176\u65f6\u95f4\u6b63\u6bd4\u4e8e <code>n<\/code>\uff09\uff0c\u7136\u540e\u8c03\u7528\u8be5\u51fd\u6570 <code>i<\/code> \u6b21\u3002\u8be5\u65b9\u6cd5\u4ea7\u751f\u4e86\u8fc7\u591a\u7684\u8fd0\u884c\u65f6\u95f4\u6d88\u8017\u3002<\/p>\n<p>\u4e0b\u9762\u4ecb\u7ecd\u4e09\u79cd\u66f4\u597d\u7684\u65b9\u6cd5\u3002<\/p>\n<p><!--more--><\/p>\n<h3>\u8df3\u8dc3\u4ea4\u6362\u5b9e\u73b0<\/h3>\n<p>\u8fd9\u4e2a\u7b97\u6cd5\u7684\u601d\u8def\u5c31\u662f\uff1a\u5411\u91cf\u65cb\u8f6c\u540e\uff0cvec[i]\u5b58\u50a8\u7684\u5c06\u662fvec[2i]\u7684\u503c\uff0cvec[2i]\u5b58\u50a8\u7684\u662fvec[3i]\u7684\u503c\uff0c\u5982\u6b64\u7c7b\u63a8\u3002<\/p>\n<p>\u8981\u6ce8\u610f\u7684\u5c31\u662f\uff0c\u5982\u679c <code>n % i  != 0<\/code>\uff0c\u90a3\u4e48\uff0c\u8981\u79fb\u52a8\u7684\u90e8\u5206\u8d85\u51fa <code>n%i<\/code> \u7684\u957f\u90e8\u5206\u4f4d\u4e8e <code>i - n%i<\/code>  \u7684\u540e\u9762\uff0c\u672c\u6765\u5e94\u8be5\u5728\u524d\u7684\uff0c\u6240\u4ee5\u53c8\u9700\u8981\u5bf9\u8fd9\u4e00\u90e8\u5206\u8fdb\u884c\u65cb\u8f6c\u3002<\/p>\n<h4>\u5b9e\u73b0<\/h4>\n<pre><code>\r\nfunc VectorRotateByMagic(vec []byte, n int) {\r\n    need, n := checkParam(vec, n)\r\n    if !need {\r\n        return\r\n    }\r\n\r\n    length := len(vec)\r\n    for i := 0; i < n; i++ {\r\n        v, j := vec[i], i+n\r\n        for ; j < length; j += n {\r\n            vec[j-n] = vec[j]\r\n        }\r\n        vec[j-n] = v\r\n    }\r\n\r\n    mod := length % n\r\n    if mod != 0 {\r\n        VectorRotateByMagic(vec[length-n:], n-mod)\r\n    }\r\n}\r\n\r\nfunc checkParam(vec []byte, n int) (bool, int) {\r\n    length := len(vec)\r\n    if length < 2 {\r\n        return false, n\r\n    }\r\n\r\n    if n < 0 {\r\n        n = -1 * n\r\n        n = n % length\r\n        n = length - n\r\n    } else {\r\n\r\n        n = n % length\r\n    }\r\n\r\n    if n == 0 {\r\n        return false, n\r\n    }\r\n\r\n    return true, n\r\n}\r\n<\/code><\/pre>\n<h3>\u7528\u6c42\u9006\u5b9e\u73b0<\/h3>\n<p>\u4e0b\u9762\u8fd9\u5f20\u56fe\u8db3\u4ee5\u8bf4\u660e\u8fd9\u4e2a\u7b97\u6cd5\u7684\u601d\u8def\u6765\u4e86\uff1a<br \/>\n<a href=\"\/\/coderbee.net\/wp-content\/uploads\/2013\/06\/vector-rotate-by-reverse.jpg\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" src=\"\/\/coderbee.net\/wp-content\/uploads\/2013\/06\/vector-rotate-by-reverse-300x168.jpg\" alt=\"vector-rotate-by-reverse\" width=\"300\" height=\"168\" class=\"alignnone size-medium wp-image-223\" srcset=\"https:\/\/coderbee.net\/wp-content\/uploads\/2013\/06\/vector-rotate-by-reverse-300x168.jpg 300w, https:\/\/coderbee.net\/wp-content\/uploads\/2013\/06\/vector-rotate-by-reverse-624x351.jpg 624w, https:\/\/coderbee.net\/wp-content\/uploads\/2013\/06\/vector-rotate-by-reverse.jpg 782w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<h4>\u5b9e\u73b0<\/h4>\n<pre><code language=\"go\">\r\nfunc VectorRotateWithReverse(vec []byte, n int) {\r\n    need, n := checkParam(vec, n)\r\n    if !need {\r\n        return\r\n    }\r\n\r\n    util.Reverse(vec[0:n])\r\n    util.Reverse(vec[n:])\r\n    util.Reverse(vec)\r\n}\r\n\r\n\/\/ util.Reverse\r\nfunc Reverse(arr []byte) {\r\n    var b byte\r\n    for l, r := 0, len(arr)-1; l < r; l, r = l+1, r-1 {\r\n        b = arr[l]\r\n        arr[l] = arr[r]\r\n        arr[r] = b\r\n    }\r\n}\r\n<\/code><\/pre>\n<h3>\u7528\u4ea4\u6362\u5411\u91cf\u5b9e\u73b0<\/h3>\n<p>\u539f\u7406\uff1a\u65cb\u8f6c\u5411\u91cfx\u5176\u5b9e\u5c31\u662f\u4ea4\u6362\u5411\u91cfab\u7684\u4e24\u6bb5\uff0c\u5f97\u5230\u5411\u91cfba\u3002<br \/>\n\u8fd9\u91cc\u7684a\u4ee3\u8868x\u4e2d\u7684\u524di\u4e2a\u5143\u7d20\u3002\u5047\u8bbea\u6bd4b\u77ed\uff0c\u5c06b\u5206\u4e3abL\u548cbR\uff0c\u4f7f\u5f97bR\u5177\u6709\u4e0ea\u76f8\u540c\u7684\u957f\u5ea6\u3002<br \/>\n\u4ea4\u6362a\u548cbR\uff0c\u4e5f\u5c31\u5c06a bL bR\u8f6c\u6362\u4e3abR bL a\u3002\u5e8f\u5217a\u6b64\u65f6\u5df2\u5904\u4e8e\u5176\u6700\u7ec8\u4f4d\u7f6e\uff0c\u56e0\u6b64\u73b0\u5728\u7684\u540c\u6837\u95ee\u9898\u5c31\u96c6\u4e2d\u5230\u4ea4\u6362b\u7684\u4e24\u90e8\u5206\u3002<br \/>\n\u7531\u4e8e\u65b0\u95ee\u9898\u4e0e\u539f\u6765\u7684\u95ee\u9898\u5177\u6709\u76f8\u540c\u7684\u5f62\u5f0f\uff0c\u53ef\u4ee5\u9012\u5f52\u5730\u89e3\u51b3\u3002<\/p>\n<h4>\u5b9e\u73b0<\/h4>\n<pre><code language=\"go\">\r\nfunc VectorRotate(vec []byte, n int) {\r\n    need, n := checkParam(vec, n)\r\n    if !need {\r\n        return\r\n    }\r\n\r\n    rotate(vec, n)\r\n}\r\n\r\nfunc rotate(vec []byte, l int) {\r\n    length := len(vec)\r\n    if length < 2 {\r\n        return\r\n    }\r\n\r\n    r := length - l\r\n\r\n    if l <= r {\r\n        swapChunk(vec, 0, vec, length-l, l)\r\n        rotate(vec[0:length-l], l)\r\n    } else {\r\n        swapChunk(vec, 0, vec, length-r, r)\r\n        rotate(vec[r:], l-r)\r\n    }\r\n}\r\n\r\nfunc swapChunk(src []byte, srcIndex int, dst []byte, dstIndex int, length int) {\r\n    for i := 0; i < length; i, srcIndex, dstIndex = i+1, srcIndex+1, dstIndex+1 {\r\n        t := src[srcIndex]\r\n        src[srcIndex] = dst[dstIndex]\r\n        dst[dstIndex] = t\r\n    }\r\n}\r\n\r\nfunc checkParam(vec []byte, n int) (bool, int) {\r\n    length := len(vec)\r\n    if length < 2 {\r\n        return false, n\r\n    }\r\n\r\n    if n < 0 {\r\n        n = -1 * n\r\n        n = n % length\r\n        n = length - n\r\n    } else {\r\n\r\n        n = n % length\r\n    }\r\n\r\n    if n == 0 {\r\n        return false, n\r\n    }\r\n\r\n    return true, n\r\n}\r\n<\/code><\/pre>\n<h3>\u95ee\u9898\u6269\u5c55<\/h3>\n<p>\u5411\u91cf\u65cb\u8f6c\u51fd\u6570\u5c06\u5411\u91cfab\u53d8\u4e3aba\u3002\u5982\u4f55\u5c06\u5411\u91cfabc\u53d8\u4e3acba\uff1f\uff08\u8fd9\u5bf9\u4ea4\u6362\u975e\u76f8\u90bb\u5185\u5b58\u5757\u7684\u95ee\u9898\u8fdb\u884c\u5efa\u6a21\uff09<\/p>\n<p>\u8fd9\u4e2a\u95ee\u9898\u5176\u5b9e\u53ef\u4ee5\u5148\u628a bc\u770b\u4f5c\u4e00\u4e2a\u6574\u4f53\uff0c\u90a3\u4e48\u95ee\u9898\u5c31\u53d8\u4e3a\u5411\u91cf\u65cb\u8f6c\u7684\u95ee\u9898\uff0c\u65cb\u8f6c\u540e\u53d8\u4e3abca\uff0c\u518d\u5bf9bc\u90e8\u5206\u8fdb\u884c\u65cb\u8f6c\uff0c\u4ecd\u7136\u662f\u4e2a\u5411\u91cf\u65cb\u8f6c\u95ee\u9898\uff0c\u65cb\u8f6c\u540e\u5373\u53ef\u5f97\u5230\u6700\u7ec8\u7ed3\u679ccba\u3002<\/p>\n<p>\u5982\u679c\u7528\u6c42\u9006\u7684\u601d\u8def\uff0c\u4ecd\u7136\u8ddf\u4e0a\u9762\u7684\u7c7b\u4f3c\u3002<\/p>\n<hr\/>\n<p>\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: <strong>coderbee\u7b14\u8bb0<\/strong>\uff0c\u53ef\u4ee5\u66f4\u53ca\u65f6\u56de\u590d\u4f60\u7684\u8ba8\u8bba\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" width=\"258\" height=\"258\" src=\"https:\/\/coderbee.net\/wp-content\/uploads\/2019\/01\/coderbee-note.jpg\" class=\"alignnone size-full wp-image-1707\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5411\u91cf\u65cb\u8f6c \u9898\u76ee\u5747\u6765\u81ea\u300a\u7f16\u7a0b\u73e0\u7391\u300b\u3002 \u9898 \u5c06\u4e00\u4e2an\u5143\u4e00\u7ef4\u5411\u91cf\u5411\u5de6\u65cb\u8f6c\uff08\u5faa\u73af\u79fb\u4f4d\uff09i &hellip; <a href=\"https:\/\/coderbee.net\/index.php\/algorithm\/20130619\/224\">\u7ee7\u7eed\u9605\u8bfb <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[53],"tags":[55,57],"_links":{"self":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/224"}],"collection":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/comments?post=224"}],"version-history":[{"count":18,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/224\/revisions"}],"predecessor-version":[{"id":245,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/224\/revisions\/245"}],"wp:attachment":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/media?parent=224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/categories?post=224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/tags?post=224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}