{"id":60584,"date":"2026-01-15T23:33:24","date_gmt":"2026-01-15T15:33:24","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/60584.html"},"modified":"2026-01-15T23:33:24","modified_gmt":"2026-01-15T15:33:24","slug":"%e5%ad%97%e8%8a%82%e5%b8%b8%e8%80%83%e7%ae%97%e6%b3%95%e9%a2%98%e8%ae%b0%e5%bd%95%e8%87%aa%e7%94%a8","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/60584.html","title":{"rendered":"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528)"},"content":{"rendered":"

\u81ea\u7528\u8bb0\u5f55<\/p>\n

\u6ce8\u610f\u8fd9\u91cc\u90fd\u662f\u5199\u5728acm\u6a21\u5f0f\u4e0b\u7684\u8981\u8003\u8651\u8f93\u5165\u8f93\u51fa，\u8fd8\u6709\u8fd9\u79cd\u9ed8\u8ba4\u662f\u9762\u8bd5\u7684\u65f6\u5019\u7ed9\u6837\u4f8b\u672c\u5730\u8dd1，\u800c\u4e0d\u662f\u76f4\u63a5\u8dd1\u6d4b\u9898\u673a\u3002\u6240\u4ee5\u53ef\u80fd\u6709\u7684\u50cf\u8f93\u5165\u662fnull\u7684\/\u6781\u7aef\u60c5\u51b5\u6ca1\u8003\u8651，\u90a3\u79cd\u5230\u65f6\u5019\u8dd1\u4e00\u6b21\u53d1\u73b0\u4e0d\u5bf9\u4e86\u76f4\u63a5\u52a0\u4e0a\u5c31\u884c\u3002<\/p>\n

\u6709\u7684\u5199\u6cd5\u662f\u76f4\u63a5\u601d\u8def\u5b9e\u73b0\u7684，\u53ef\u80fd\u590d\u6742\u5ea6\u5bf9\u4f46\u4e0d\u591f\u4f18\u96c5（\u5199\u8d77\u6765\u5f88\u9ebb\u70e6）\u4e4b\u540e\u770b\u5230\u66f4\u597d\u7684\u4f1a\u6539\u7684w<\/p>\n

1.\u6700\u957f\u4e0d\u542b\u91cd\u590d\u5b57\u7b26\u7684\u5b50\u5b57\u7b26\u4e32<\/h3>\n

\u7b2c\u4e00\u904d\u6709\u4e2a\u987a\u5e8f\u5199\u53cd\u4e86\u6392\u4e86\u4f1adebug\u4e5f\u670915min？<\/p>\n

\u7b2c\u4e8c\u904d\u8bb0\u5f97\u7ec6\u82823\u5206\u949f\u51fa\u6765<\/p>\n

package<\/span> t1<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>HashSet<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n String<\/span> s=<\/span>sc.<\/span>next<\/span>(<\/span>)<\/span>;<\/span>
\n int<\/span> sl=<\/span>s.<\/span>length<\/span>(<\/span>)<\/span>,<\/span>l=<\/span>0<\/span>,<\/span>r=<\/span>0<\/span>,<\/span>jg=<\/span>0<\/span>;<\/span>
\n HashSet<\/span><<\/span>Character<\/span>><\/span><\/span>hash=<\/span>new<\/span> HashSet<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n while<\/span>(<\/span>r<<\/span>sl)<\/span>{<\/span>
\n if<\/span>(<\/span>hash.<\/span>contains<\/span>(<\/span>s.<\/span>charAt<\/span>(<\/span>r)<\/span>)<\/span>)<\/span>{<\/span>
\n jg=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>jg,<\/span>r–<\/span>l)<\/span>;<\/span>
\n while<\/span>(<\/span>l<=<\/span>r)<\/span>{<\/span>
\n hash.<\/span>remove<\/span>(<\/span>s.<\/span>charAt<\/span>(<\/span>l)<\/span>)<\/span>;<\/span>
\n l++<\/span>;<\/span>
\n if<\/span>(<\/span>s.<\/span>charAt<\/span>(<\/span>l–<\/span>1<\/span>)<\/span>==<\/span>s.<\/span>charAt<\/span>(<\/span>r)<\/span>)<\/span>break<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n hash.<\/span>add<\/span>(<\/span>s.<\/span>charAt<\/span>(<\/span>r)<\/span>)<\/span>;<\/span>
\n r++<\/span>;<\/span>
\n }<\/span>
\n jg=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>jg,<\/span>r–<\/span>l)<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6O（N)<\/p>\n

2. \u4e8c\u53c9\u6811\u7684\u952f\u9f7f\u5f62\u5c42\u5e8f\u904d\u5386<\/h3>\n

\u7b2c\u4e00\u904d30min\u4ee5\u4e0a，\u5bf9\u8fd9\u79cd\u7ec6\u8282\u4e0b\u8d77\u6765\u4e0d\u77e5\u9053\u4e3a\u4ec0\u4e48\u8fd9\u4e48\u6162，\u4f46\u4e5f\u662f\u5bff\u53f8\u51fa\u6765\u4e86，\u5c31\u662fbfs+\u6808\u4e0d\u77e5\u9053\u4e3a\u4ec0\u4e48\u5199\u5f97\u8fd9\u4e48\u6162<\/p>\n

\u8fd8\u6709acm\u6a21\u5f0f\u6811\u7684\u8f93\u5165\u4e5f\u8981\u8bb0\u5f97（\u611f\u89c9\u6b63\u5e38\u7684\u8bdd\u4f1a\u76f4\u63a5\u9884\u5236\u6811）<\/p>\n

\u7b2c\u4e8c\u904d\u77e5\u9053\u601d\u8def\u4e00\u76f4\u5728\u6572\u4e5f\u6572\u4e8611min<\/p>\n

package<\/span> t2<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>*<\/span>;<\/span><\/p>\n

class<\/span> TreeNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n TreeNode<\/span> left;<\/span>
\n TreeNode<\/span> right;<\/span><\/p>\n

TreeNode<\/span>(<\/span>)<\/span> {<\/span>
\n }<\/span><\/p>\n

TreeNode<\/span>(<\/span>int<\/span> val)<\/span> {<\/span>
\n this<\/span>.<\/span>val =<\/span> val;<\/span>
\n }<\/span><\/p>\n

TreeNode<\/span>(<\/span>int<\/span> val,<\/span> TreeNode<\/span> left,<\/span> TreeNode<\/span> right)<\/span> {<\/span>
\n this<\/span>.<\/span>val =<\/span> val;<\/span>
\n this<\/span>.<\/span>left =<\/span> left;<\/span>
\n this<\/span>.<\/span>right =<\/span> right;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n Integer<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> Integer<\/span>[<\/span>15<\/span>]<\/span>;<\/span>
\n int<\/span> sl =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> f1 =<\/span> 1<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span> sl;<\/span> i++<\/span>)<\/span> {<\/span>
\n String<\/span> s =<\/span> sc.<\/span>next<\/span>(<\/span>)<\/span>;<\/span>
\n if<\/span> (<\/span>s.<\/span>equals<\/span>(<\/span>"null"<\/span>)<\/span>)<\/span> a[<\/span>i]<\/span> =<\/span> null<\/span>;<\/span>
\n else<\/span> a[<\/span>i]<\/span> =<\/span> Integer<\/span>.<\/span>parseInt<\/span>(<\/span>s)<\/span>;<\/span>
\n }<\/span>
\n Deque<\/span><<\/span>TreeNode<\/span>><\/span><\/span> b =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n TreeNode<\/span> root =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>root)<\/span>;<\/span>
\n while<\/span> (<\/span>!<\/span>b.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span> ><\/span> sl)<\/span> break<\/span>;<\/span>
\n TreeNode<\/span> c =<\/span> b.<\/span>pollFirst<\/span>(<\/span>)<\/span>,<\/span> d =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>f1 *<\/span> 2<\/span>]<\/span> ==<\/span> null<\/span> ?<\/span> –<\/span>1<\/span> :<\/span> a[<\/span>f1 *<\/span> 2<\/span>]<\/span>)<\/span>,<\/span> e =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span>]<\/span> ==<\/span> null<\/span> ?<\/span> –<\/span>1<\/span> :<\/span> a[<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span>]<\/span>)<\/span>;<\/span>
\n c.<\/span>left =<\/span> d;<\/span>
\n c.<\/span>right =<\/span> e;<\/span>
\n f1++<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>d)<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>e)<\/span>;<\/span>
\n }<\/span><\/p>\n

int<\/span> cs =<\/span> 1<\/span>,<\/span> f =<\/span> 0<\/span>;<\/span>
\n Deque<\/span><<\/span>TreeNode<\/span>><\/span><\/span> d =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n d.<\/span>addLast<\/span>(<\/span>root)<\/span>;<\/span>
\n List<\/span><<\/span>List<\/span><<\/span>Integer<\/span>><\/span>><\/span><\/span> jg1 =<\/span> new<\/span> ArrayList<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n while<\/span> (<\/span>!<\/span>d.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n int<\/span> bl =<\/span> cs;<\/span>
\n cs *=<\/span> 2<\/span>;<\/span>
\n f++<\/span>;<\/span>
\n List<\/span><<\/span>Integer<\/span>><\/span><\/span> jg2 =<\/span> new<\/span> ArrayList<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n Deque<\/span><<\/span>Integer<\/span>><\/span><\/span> jg3 =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> bl;<\/span> i++<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>!<\/span>d.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n TreeNode<\/span> t1 =<\/span> d.<\/span>pollFirst<\/span>(<\/span>)<\/span>,<\/span> t1l =<\/span> t1.<\/span>left,<\/span> t1r =<\/span> t1.<\/span>right;<\/span>
\n jg3.<\/span>addLast<\/span>(<\/span>t1.<\/span>val)<\/span>;<\/span>
\n if<\/span> (<\/span>t1l==<\/span>null<\/span>||<\/span>t1l.<\/span>val ==<\/span> –<\/span>1<\/span>)<\/span> {<\/span>
\n cs—<\/span>;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n d.<\/span>addLast<\/span>(<\/span>t1l)<\/span>;<\/span>
\n }<\/span>
\n if<\/span> (<\/span>t1r==<\/span>null<\/span>||<\/span>t1r.<\/span>val ==<\/span> –<\/span>1<\/span>)<\/span> {<\/span>
\n cs—<\/span>;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n d.<\/span>addLast<\/span>(<\/span>t1r)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n }<\/span>
\n if<\/span> (<\/span>f %<\/span> 2<\/span> ==<\/span> 1<\/span>)<\/span> {<\/span>
\n while<\/span> (<\/span>!<\/span>jg3.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n jg2.<\/span>add<\/span>(<\/span>jg3.<\/span>pollFirst<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span> else<\/span> {<\/span>
\n while<\/span> (<\/span>!<\/span>jg3.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n jg2.<\/span>add<\/span>(<\/span>jg3.<\/span>pollLast<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n jg1.<\/span>add<\/span>(<\/span>jg2)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>List<\/span><<\/span>Integer<\/span>><\/span><\/span> jg11 :<\/span> jg1)<\/span> {<\/span>
\n for<\/span> (<\/span>Integer<\/span> i :<\/span> jg11)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>print<\/span>(<\/span>i +<\/span> " "<\/span>)<\/span>;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

}<\/span><\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6O（N）\u5c31\u662fbfs\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n

3. \u6570\u7ec4\u4e2d\u7684\u7b2cK\u4e2a\u6700\u5927\u5143\u7d20<\/h3>\n

\u8bb0\u5f97\u8fd9\u4e2a\u662f\u5999\u5999\u9898，\u60f3\u4e0d\u8d77\u6765\u7684\u8bdd\u5c31\u60f3\u4e0d\u8d77\u6765\u4e86<\/p>\n

\u6295\u964d\u770b\u4e0b\u9898\u89e3<\/p>\n

\u65f6\u95f4nlogn\u7684\u6392\u5e8f\u8c01\u90fd\u77e5\u9053，\u65f6\u95f4n\u7684\u5806\u4f46\u662f\u4e5f\u8981n\u7684\u7a7a\u95f4\u4e5f\u77e5\u9053，\u4e3b\u8981\u5fd8\u4e86\u65f6\u95f4n\u7a7a\u95f41\u770b\u9898\u89e3\u662f\u5feb\u6392\u7c7b\u4f3c\u7684\u5feb\u901f\u9009\u62e9<\/p>\n

package<\/span> t3<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>;<\/span><\/p>\n

static<\/span> int<\/span> quicksort1<\/span>(<\/span>int<\/span> l,<\/span> int<\/span> r,<\/span> int<\/span> bm)<\/span> {<\/span>
\n if<\/span> (<\/span>l >=<\/span> r)<\/span> return<\/span> a[<\/span>l]<\/span>;<\/span>
\n int<\/span> zj =<\/span> quicksort2<\/span>(<\/span>l,<\/span> r)<\/span>;<\/span>
\n if<\/span> (<\/span>zj ==<\/span> bm)<\/span> {<\/span>
\n return<\/span> a[<\/span>zj]<\/span>;<\/span>
\n }<\/span> else<\/span> if<\/span> (<\/span>zj <<\/span> bm)<\/span> {<\/span>
\n return<\/span> quicksort1<\/span>(<\/span>zj +<\/span> 1<\/span>,<\/span> r,<\/span> bm)<\/span>;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n return<\/span> quicksort1<\/span>(<\/span>l,<\/span> zj –<\/span> 1<\/span>,<\/span> bm)<\/span>;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

static<\/span> int<\/span> quicksort2<\/span>(<\/span>int<\/span> l,<\/span> int<\/span> r)<\/span> {<\/span>
\n int<\/span> bj =<\/span> a[<\/span>l]<\/span>;<\/span>
\n while<\/span> (<\/span>l <<\/span> r)<\/span> {<\/span>
\n if<\/span> (<\/span>a[<\/span>r]<\/span> <<\/span> bj)<\/span> {<\/span>
\n a[<\/span>l]<\/span> =<\/span> a[<\/span>r]<\/span>;<\/span>
\n l++<\/span>;<\/span>
\n while<\/span> (<\/span>l <<\/span> r)<\/span> {<\/span>
\n if<\/span> (<\/span>a[<\/span>l]<\/span> ><\/span> bj)<\/span> {<\/span>
\n a[<\/span>r]<\/span> =<\/span> a[<\/span>l]<\/span>;<\/span>
\n r—<\/span>;<\/span>
\n break<\/span>;<\/span>
\n }<\/span> else<\/span> l++<\/span>;<\/span>
\n }<\/span>
\n }<\/span> else<\/span> r—<\/span>;<\/span>
\n }<\/span>
\n a[<\/span>l]<\/span> =<\/span> bj;<\/span>
\n return<\/span> l;<\/span>
\n }<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> sl =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> wz =<\/span> sl –<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span> +<\/span> 1<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> sl;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i +<\/span> 1<\/span>]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>quicksort1<\/span>(<\/span>1<\/span>,<\/span> sl,<\/span> wz)<\/span>)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u5c31\u662f\u5feb\u6392\u6539\u4e86\u4e0b\u53ea\u627ebm\u5728\u7684\u533a\u57df，\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790：<\/p>\n

\u8d34\u4e2aai\u7684\u56fe<\/p>\n

\"\"<\/p>\n

\u8fd9\u91cc\u4e3a\u4e86\u65b9\u4fbf\u5c31\u76f4\u63a5\u9009\u6700\u5de6\u8fb9\u4e3a\u57fa\u51c6\u4e86，\u968f\u673a\u9009\u80fd\u9632\u6b62\u5361\u5e38，\u4ed6\u8981\u95ee\u4e5f\u53ef\u4ee5\u8bf4<\/p>\n

4. \u53cd\u8f6c\u94fe\u8868<\/h3>\n

\u5199\u4e867min\u5f88\u795e\u79d8，\u6211\u6572\u5f97\u592a\u6162\u4e86\u5417（？）<\/p>\n

package<\/span> t4<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> Node<\/span>{<\/span>
\n int<\/span> val;<\/span>
\n Node<\/span> next;<\/span>
\n Node<\/span>(<\/span>)<\/span>{<\/span>}<\/span>
\n Node<\/span>(<\/span>int<\/span> x)<\/span>{<\/span>val=<\/span>x;<\/span>}<\/span>
\n}<\/span>
\npublic<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n Node<\/span> root=<\/span>new<\/span> Node<\/span>(<\/span>–<\/span>11111<\/span>)<\/span>,<\/span>bl1=<\/span>root;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> x=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n bl1.<\/span>next=<\/span>new<\/span> Node<\/span>(<\/span>x)<\/span>;<\/span>
\n bl1=<\/span>bl1.<\/span>next;<\/span>
\n }<\/span>
\n Node<\/span> bl2=<\/span>root.<\/span>next,<\/span>pre=<\/span>root;<\/span>
\n while<\/span> (<\/span>bl2 !=<\/span> null<\/span>)<\/span> {<\/span>
\n Node<\/span> temp=<\/span> bl2.<\/span>next;<\/span>
\n bl2.<\/span>next=<\/span>pre;<\/span>
\n pre=<\/span>bl2;<\/span>
\n bl2=<\/span>temp;<\/span>
\n }<\/span>
\n while<\/span> (<\/span>bl1!=<\/span>null<\/span>&&<\/span>bl1.<\/span>val!=<\/span>–<\/span>11111<\/span>)<\/span>{<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>bl1.<\/span>val)<\/span>;<\/span>
\n bl1=<\/span>bl1.<\/span>next;<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u53cc\u6307\u9488\u65f6\u95f4O（N）\u7a7a\u95f4O（1）\u6bd4\u9012\u5f52\u7a7a\u95f4O（N）\u597d\u70b9<\/p>\n

5. LRU \u7f13\u5b58\u673a\u5236<\/h3>\n

\u4e0d\u77e5\u9053\u8fd9\u4e2a\u9898\u5230\u65f6\u5019\u4f1a\u4e0d\u4f1a\u7ed9\u529b\u6263\u90a3\u6837\u7684\u5df2\u77e5\u6761\u4ef6<\/p>\n

\"\"<\/p>\n

\u5927\u69829min<\/p>\n

package<\/span> t5<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>LinkedHashMap<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n int<\/span> sl;<\/span>
\n LinkedHashMap<\/span><<\/span>Integer<\/span>,<\/span> Integer<\/span>><\/span><\/span> map =<\/span> new<\/span> LinkedHashMap<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span><\/p>\n

main<\/span>(<\/span>int<\/span> sl)<\/span> {<\/span>
\n this<\/span>.<\/span>sl =<\/span> sl;<\/span>
\n }<\/span><\/p>\n

int<\/span> get<\/span>(<\/span>int<\/span> k)<\/span> {<\/span>
\n if<\/span> (<\/span>map.<\/span>containsKey<\/span>(<\/span>k)<\/span>)<\/span> {<\/span>
\n int<\/span> v =<\/span> map.<\/span>get<\/span>(<\/span>k)<\/span>;<\/span>
\n map.<\/span>remove<\/span>(<\/span>k)<\/span>;<\/span>
\n map.<\/span>put<\/span>(<\/span>k,<\/span> v)<\/span>;<\/span>
\n return<\/span> v;<\/span>
\n }<\/span> else<\/span> return<\/span> –<\/span>1<\/span>;<\/span>
\n }<\/span><\/p>\n

void<\/span> put<\/span>(<\/span>int<\/span> k,<\/span> int<\/span> v)<\/span> {<\/span>
\n if<\/span> (<\/span>map.<\/span>containsKey<\/span>(<\/span>k)<\/span>)<\/span> {<\/span>
\n map.<\/span>remove<\/span>(<\/span>k)<\/span>;<\/span>
\n map.<\/span>put<\/span>(<\/span>k,<\/span> v)<\/span>;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n if<\/span> (<\/span>map.<\/span>size<\/span>(<\/span>)<\/span> ==<\/span> sl)<\/span> {<\/span>
\n map.<\/span>remove<\/span>(<\/span>map.<\/span>keySet<\/span>(<\/span>)<\/span>.<\/span>iterator<\/span>(<\/span>)<\/span>.<\/span>next<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\n map.<\/span>put<\/span>(<\/span>k,<\/span> v)<\/span>;<\/span>
\n }<\/span> else<\/span> map.<\/span>put<\/span>(<\/span>k,<\/span> v)<\/span>;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

}<\/span><\/p>\n

\u4e3b\u8981\u662f\u522b\u5fd8\u4e86\u7528\u8fed\u4ee3\u5668map.remove(map.keySet().iterator().next());\u6765\u79fb\u9664\u7b2c\u4e00\u4e2a\u6700\u8001\u7684<\/p>\n

6.\u4e09\u6570\u4e4b\u548c<\/h3>\n

\u975e\u5e38\u7ecf\u5178！<\/p>\n

\u7b2c\u4e00\u904d\u6413\u4e8614min\u8fd8\u662f\u6162（）<\/p>\n

package<\/span> t6<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>ArrayList<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Arrays<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>List<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>10005<\/span>]<\/span>;<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n List<\/span><<\/span>List<\/span><<\/span>Integer<\/span>><\/span>><\/span><\/span> jg1 =<\/span> new<\/span> ArrayList<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n if<\/span> (<\/span>n <<\/span> 3<\/span>)<\/span> System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg1)<\/span>;<\/span>
\n else<\/span> {<\/span>
\n Arrays<\/span>.<\/span>sort<\/span>(<\/span>a,<\/span> 0<\/span>,<\/span> n)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>i !=<\/span> 0<\/span> &&<\/span> a[<\/span>i]<\/span> ==<\/span> a[<\/span>i –<\/span> 1<\/span>]<\/span>)<\/span> continue<\/span>;<\/span>
\n if<\/span> (<\/span>a[<\/span>i]<\/span> ><\/span> 0<\/span>)<\/span> break<\/span>;<\/span>
\n int<\/span> l =<\/span> i +<\/span> 1<\/span>,<\/span> r =<\/span> n –<\/span> 1<\/span>;<\/span>
\n while<\/span> (<\/span>l <<\/span> r)<\/span> {<\/span>
\n while<\/span> (<\/span>l <<\/span> r &&<\/span> a[<\/span>l]<\/span> +<\/span> a[<\/span>r]<\/span> !=<\/span> –<\/span>a[<\/span>i]<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>a[<\/span>l]<\/span> +<\/span> a[<\/span>r]<\/span> ><\/span> –<\/span>a[<\/span>i]<\/span>)<\/span> {<\/span>
\n r—<\/span>;<\/span>
\n }<\/span> else<\/span> if<\/span> (<\/span>a[<\/span>l]<\/span> +<\/span> a[<\/span>r]<\/span> <<\/span> –<\/span>a[<\/span>i]<\/span>)<\/span> {<\/span>
\n l++<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n if<\/span> (<\/span>l!=<\/span>r&&<\/span>a[<\/span>l]<\/span> +<\/span> a[<\/span>r]<\/span> +<\/span> a[<\/span>i]<\/span> ==<\/span> 0<\/span>)<\/span> {<\/span>
\n List<\/span><<\/span>Integer<\/span>><\/span><\/span> jg2 =<\/span> new<\/span> ArrayList<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n jg2.<\/span>add<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>;<\/span>
\n jg2.<\/span>add<\/span>(<\/span>a[<\/span>l]<\/span>)<\/span>;<\/span>
\n jg2.<\/span>add<\/span>(<\/span>a[<\/span>r]<\/span>)<\/span>;<\/span>
\n jg1.<\/span>add<\/span>(<\/span>jg2)<\/span>;<\/span>
\n }<\/span>
\n while<\/span> (<\/span>l +<\/span> 1<\/span> <<\/span> n &&<\/span> a[<\/span>l +<\/span> 1<\/span>]<\/span> ==<\/span> a[<\/span>l]<\/span>)<\/span> l++<\/span>;<\/span>
\n while<\/span> (<\/span>r –<\/span> 1<\/span> ><\/span> 0<\/span> &&<\/span> a[<\/span>r –<\/span> 1<\/span>]<\/span> ==<\/span> a[<\/span>r]<\/span>)<\/span> r—<\/span>;<\/span>
\n l++<\/span>;<\/span>
\n r—<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg1)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u76f4\u63a5\u5206\u6790\u590d\u6742\u5ea6：<\/p>\n

\u6700\u66b4\u529b\u7684\u662fO（N3)\u5c31\u662f\u4e09\u91cd\u904d\u5386，\u4f18\u5316\u4e00\u4e0b\u60f3\u5230\u4e24\u6570\u4e4b\u548c\u7684hashmap\u7528\u5728\u8fd9\u91cc\u662fO（NlogN），\u518d\u60f3\u4e00\u4e0b\u53d1\u73b0\u65e0\u8bba\u600e\u6837\u590d\u6742\u5ea6\u90fd\u5f88\u5927，\u4f1a\u5927\u4e8e\u6392\u5e8f\u7684nlogn\u6240\u4ee5\u76f4\u63a5\u6392\u5e8f\u7528\u53cc\u6307\u9488\u8fbe\u5230O（N<\/sup>2)<\/p>\n

7. \u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a<\/h3>\n

\u5199\u4e86\u4e00\u4e0b4min\u539f\u6765\u662f\u7eb8\u8001\u864e，\u6211\u770b\u5b57\u8282\u8001\u95ee\u8fd8\u4ee5\u4e3a\u5f88\u96be，\u5c31\u662f\u4e00\u7ef4dp\u65f6\u95f4O（N）<\/p>\n

package<\/span> t7<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>10005<\/span>]<\/span>,<\/span> b[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>10005<\/span>]<\/span>;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> jg =<\/span> 0<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> n –<\/span> 1<\/span>;<\/span> n >=<\/span> 0<\/span>;<\/span> i—<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>i ==<\/span> n –<\/span> 1<\/span>)<\/span> b[<\/span>i]<\/span> =<\/span> a[<\/span>i]<\/span>;<\/span>
\n else<\/span>
\n b[<\/span>i]<\/span> =<\/span> Math<\/span>.<\/span>max<\/span>(<\/span>b[<\/span>i +<\/span> 1<\/span>]<\/span>,<\/span> a[<\/span>i]<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n jg =<\/span> Math<\/span>.<\/span>max<\/span>(<\/span>jg,<\/span> b[<\/span>i]<\/span> –<\/span> a[<\/span>i]<\/span>)<\/span>;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

8. \u4e8c\u53c9\u6811\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148<\/h3>\n

\u8fd9\u9053\u9898\u6211\u5e94\u8be5\u505a\u8fc7\u4f46\u662f\u60f3\u4e0d\u5230\u6700\u4f18\u601d\u8def<\/p>\n

\u8fd9\u9053\u9898\u6211\u60f3\u4e0d\u5230\u4ec0\u4e48\u597d\u7684\u601d\u8def，\u6211\u7684\u7b2c\u4e00\u60f3\u6cd5\u662fdfs\u627e\u4e24\u4e2a\u8282\u70b9\u7684\u9ad8\u5ea6，\u7136\u540e\u6839\u636e\u4e24\u4e2a\u8282\u70b9\u7684\u8def\u5f84\u770b\u76f8\u540c\u9ad8\u5ea6\u65f6\u5019\u662f\u4e0d\u662f\u540c\u4e00\u4e2a\u8282\u70b9\u7b2c\u4e00\u4e2a\u8fd9\u4e2a\u6570\u5c31\u662f\u7b54\u6848\u3002\u6211\u611f\u89c9\u60f3\u9ebb\u70e6\u4e86\u4f46\u662f\u5e94\u8be5\u80fd\u505a\u590d\u6742\u5ea6\u4e5f\u7b26\u5408\u8981\u6c42\u3002<\/p>\n

\u770b\u9898\u89e3：\u4ece\u4e0a\u5f80\u4e0b\u627e，\u90fd\u627e\u5230\u4e86\u80fd\u786e\u5b9a\u7236\u8282\u70b9\u3002\u518d\u56e0\u4e3a\u9012\u5f52\u7279\u6027，\u80fd\u786e\u5b9a\u4ece\u4e0b\u5230\u4e0a\u7b2c\u4e00\u4e2a\u627e\u5230\u7684\u5c31\u662f\u7b54\u6848\u3002<\/p>\n

\u77e5\u9053\u4e86\u601d\u8def\u5b9e\u73b0\u4e5f\u82b1\u4e86\u5927\u698220min，\u9012\u5f52\u592a\u4e0d\u719f\u4e86<\/p>\n

package<\/span> t8<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>ArrayDeque<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Deque<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> TreeNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n TreeNode<\/span> left;<\/span>
\n TreeNode<\/span> right;<\/span><\/p>\n

TreeNode<\/span>(<\/span>)<\/span> {<\/span>
\n }<\/span><\/p>\n

TreeNode<\/span>(<\/span>int<\/span> val)<\/span> {<\/span>
\n this<\/span>.<\/span>val =<\/span> val;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n Integer<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> Integer<\/span>[<\/span>150<\/span>]<\/span>;<\/span>
\n int<\/span> sl =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> f1 =<\/span> 1<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <=<\/span> sl;<\/span> i++<\/span>)<\/span> {<\/span>
\n String<\/span> s =<\/span> sc.<\/span>next<\/span>(<\/span>)<\/span>;<\/span>
\n if<\/span> (<\/span>s.<\/span>equals<\/span>(<\/span>"null"<\/span>)<\/span>)<\/span> a[<\/span>i]<\/span> =<\/span> null<\/span>;<\/span>
\n else<\/span> a[<\/span>i]<\/span> =<\/span> Integer<\/span>.<\/span>parseInt<\/span>(<\/span>s)<\/span>;<\/span>
\n }<\/span>
\n Deque<\/span><<\/span>TreeNode<\/span>><\/span><\/span> b =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n TreeNode<\/span> root =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>root)<\/span>;<\/span>
\n while<\/span> (<\/span>!<\/span>b.<\/span>isEmpty<\/span>(<\/span>)<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span> ><\/span> sl)<\/span> break<\/span>;<\/span>
\n TreeNode<\/span> c =<\/span> b.<\/span>pollFirst<\/span>(<\/span>)<\/span>,<\/span> d =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>f1 *<\/span> 2<\/span>]<\/span> ==<\/span> null<\/span> ?<\/span> –<\/span>1<\/span> :<\/span> a[<\/span>f1 *<\/span> 2<\/span>]<\/span>)<\/span>,<\/span> e =<\/span> new<\/span> TreeNode<\/span>(<\/span>a[<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span>]<\/span> ==<\/span> null<\/span> ?<\/span> –<\/span>1<\/span> :<\/span> a[<\/span>f1 *<\/span> 2<\/span> +<\/span> 1<\/span>]<\/span>)<\/span>;<\/span>
\n c.<\/span>left =<\/span> d;<\/span>
\n c.<\/span>right =<\/span> e;<\/span>
\n f1++<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>d)<\/span>;<\/span>
\n b.<\/span>addLast<\/span>(<\/span>e)<\/span>;<\/span>
\n }<\/span>
\n \/\/\u4e0a\u9762\u90fd\u662f\u8f93\u5165\u6811，\u4e0b\u9762\u90a3\u70b9\u662f\u7b54\u6848<\/span>
\n int<\/span> x =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> y =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>lowestCommonAncestor<\/span>(<\/span>root,<\/span> x,<\/span> y)<\/span>.<\/span>val)<\/span>;<\/span>
\n }<\/span><\/p>\n

static<\/span> TreeNode<\/span> lowestCommonAncestor<\/span>(<\/span>TreeNode<\/span> root,<\/span> int<\/span> p,<\/span> int<\/span> q)<\/span> {<\/span>
\n if<\/span> (<\/span>root==<\/span>null<\/span>||<\/span>root.<\/span>val ==<\/span> p ||<\/span> root.<\/span>val ==<\/span> q)<\/span> return<\/span> root;<\/span>
\n TreeNode<\/span> left =<\/span> lowestCommonAncestor<\/span>(<\/span>root.<\/span>left,<\/span> p,<\/span> q)<\/span>;<\/span>
\n TreeNode<\/span> right =<\/span> lowestCommonAncestor<\/span>(<\/span>root.<\/span>right,<\/span> p,<\/span> q)<\/span>;<\/span>
\n if<\/span>(<\/span>left!=<\/span>null<\/span>&&<\/span>right!=<\/span>null<\/span>)<\/span>return<\/span> root;<\/span>
\n return<\/span> left==<\/span>null<\/span> ?<\/span>right:<\/span>left;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u590d\u6742\u5ea6on<\/p>\n

9. \u76f8\u4ea4\u94fe\u8868<\/h3>\n

\u60f3\u4e86\u4f1a\u601d\u8def\u5e26\u5b9e\u73b0\u5927\u698210min<\/p>\n

\u8fd9\u4e2a\u601d\u8def\u6709\u70b9\u4e0d\u8bb0\u5f97\u4e86，\u5c31\u8bb0\u5f97\u548c\u516c\u5171\u6709\u5173\u7cfb，\u8981\u6362\u8fb9\u8d70\u3002\u4e5f\u6709\u70b9\u5fd8\u4e86\u600e\u4e48\u5224\u65ad\u6ca1\u6709\u4ea4\u70b9\u3002(\u53d1\u73b0\u4e0d\u7528\u5224\u65ad，\u6ca1\u4ea4\u70b9\u4e5f\u4f1a\u6700\u540e==\u53ea\u4e0d\u8fc7\u90fd\u662fnull，\u6b63\u5e38\u8fd4\u56de\u5c31\u597d)<\/p>\n

（\u8fd9\u79cd\u9700\u8981\u7ed3\u8bba\u8bc1\u660e\u7684\u5e38\u8003\u9898\u76ee，\u5c31\u76f4\u63a5\u8bb0\u7ed3\u8bba\u5427，\u5509\u5509）<\/p>\n

ListNode<\/span> getIntersectionNode<\/span>(<\/span>ListNode<\/span> a,<\/span> ListNode<\/span> b)<\/span> {<\/span>
\n ListNode<\/span> c =<\/span> a,<\/span> d =<\/span> b;<\/span>
\n while<\/span> (<\/span>c!=<\/span>d)<\/span> {<\/span>
\n while<\/span> (<\/span>c !=<\/span> null<\/span> &&<\/span> d !=<\/span> null<\/span> &&<\/span> c !=<\/span> d)<\/span> {<\/span>
\n c =<\/span> c.<\/span>next;<\/span>
\n d =<\/span> d.<\/span>next;<\/span>
\n }<\/span>
\n if<\/span> (<\/span>c ==<\/span> d)<\/span> {<\/span>
\n break<\/span>;<\/span>
\n }<\/span>
\n if<\/span> (<\/span>c ==<\/span> null<\/span>)<\/span> c =<\/span> b;<\/span>
\n else<\/span> d =<\/span> a;<\/span><\/p>\n

}<\/span>
\n return<\/span> c;<\/span>
\n }<\/span><\/p>\n

\u8fd9\u4e2a\u7684acm\u611f\u89c9\u592a\u4e0d\u53cb\u597d\u7684\u8f93\u5165\u4e86，\u5c31\u7528\u6838\u5fc3\u4ee3\u7801\u4e86<\/p>\n

\u590d\u6742\u5ea6on<\/p>\n

10. \u641c\u7d22\u65cb\u8f6c\u6392\u5e8f\u6570\u7ec4<\/h3>\n

\u8fd9\u4e2a\u6709\u70b9\u8d39\u8111\u888b，\u53ef\u4ee5\u80cc（？）<\/p>\n

while<\/span>(<\/span>l<<\/span>r)<\/span>{<\/span>int<\/span> m=<\/span>l+<\/span>(<\/span>r–<\/span>l)<\/span>\/<\/span>2<\/span>;<\/span> if<\/span>(<\/span>a[<\/span>m]<\/span>><\/span>a[<\/span>r]<\/span>)<\/span> l=<\/span>m+<\/span>1<\/span>;<\/span> else<\/span> r=<\/span>m;<\/span>}<\/span><\/p>\n

\u9700\u8981\u77e5\u9053\u8fd9\u4e2a\u80fd\u627e\u5230\u65cb\u8f6c\u6b21\u6570，\u8fd9\u4e2a\u662f\u5728\u627e\u6700\u5c0f\u7684\u6570\u597d\u77e5\u9053\u4f4d\u79fb\u6b21\u6570，\u8fd9\u91cc\u662f\u5de6\u5927\u53f3\u5c0f，\u6240\u4ee5\u5927\u4e86\u53f3\u79fb\u3002<\/p>\n

int<\/span> r =<\/span> (<\/span>mid2 +<\/span> l1)<\/span> %<\/span> n;<\/span><\/p>\n

\u901a\u8fc7\u8fd9\u4e2a\u6765\u6620\u5c04\u5b8c\u6210\u4e8c\u5206<\/p>\n

package<\/span> t10<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>10005<\/span>]<\/span>;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> x =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

int<\/span> l1 =<\/span> 0<\/span>,<\/span> r1 =<\/span> n –<\/span> 1<\/span>,<\/span> mid1 =<\/span> 0<\/span>;<\/span>
\n while<\/span> (<\/span>l1 <<\/span> r1)<\/span> {<\/span>
\n mid1 =<\/span> (<\/span>l1 +<\/span> r1)<\/span> \/<\/span> 2<\/span>;<\/span>
\n if<\/span> (<\/span>a[<\/span>mid1]<\/span> <=<\/span> a[<\/span>r1]<\/span>)<\/span> l1 =<\/span> mid1 –<\/span> 1<\/span>;<\/span>
\n else<\/span> r1 =<\/span> mid1;<\/span>
\n }<\/span><\/p>\n

int<\/span> l2 =<\/span> 0<\/span>,<\/span> r2 =<\/span> n –<\/span> 1<\/span>,<\/span> mid2 =<\/span> 0<\/span>,<\/span> f =<\/span> 0<\/span>;<\/span>
\n while<\/span> (<\/span>l2 <=<\/span> r2)<\/span> {<\/span>
\n mid2 =<\/span> (<\/span>l2 +<\/span> r2)<\/span> \/<\/span> 2<\/span>;<\/span>
\n int<\/span> r =<\/span> (<\/span>mid2 +<\/span> l1)<\/span> %<\/span> n;<\/span>
\n if<\/span> (<\/span>a[<\/span>r]<\/span> ==<\/span> x)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>r)<\/span>;<\/span>
\n f =<\/span> 1<\/span>;<\/span>
\n break<\/span>;<\/span>
\n }<\/span> else<\/span> if<\/span> (<\/span>a[<\/span>r]<\/span> ><\/span> x)<\/span> {<\/span>
\n r2 =<\/span> mid2 –<\/span> 1<\/span>;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n l2 =<\/span> mid2 +<\/span> 1<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n if<\/span> (<\/span>f ==<\/span> 0<\/span>)<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>–<\/span>1<\/span>)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u590d\u6742\u5ea6logn<\/p>\n

11. \u63a5\u96e8\u6c34<\/h3>\n

\u8fd9\u91cc\u6211\u6709\u4e24\u4e2a\u601d\u8def：<\/p>\n

\u6a2a\u7740\u63a5\u96e8\u6c34：\u6bcf\u4e2a\u5de6\u627e\u5230\u7b2c\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8e\u4ed6\u7684\u53f3\u7136\u540e\u7b97\u4e00\u4e0b，\u7b97\u662f\u6a21\u62df\u5199\u8d77\u6765\u9ebb\u70e6\u8fd8\u8981\u5904\u7406\u8fb9\u754c\u3002\u4e5f\u53ef\u4ee5\u914d\u5408\u5355\u8c03\u6808\u4f7f\u7528\u53ef\u80fd\u597d\u5199\u70b9，\u4e0d\u8fc7\u65f6\u95f4\u590d\u6742\u5ea6\u6ca1\u53d8\u90fd\u662fON，\u8fd8\u591a\u4e86ON\u7a7a\u95f4\u3002<\/p>\n

\u7ad6\u7740\u63a5\u96e8\u6c34：\u53cc\u6307\u9488\u590d\u6742\u5ea6\u4e5f\u662fON，\u5199\u8d77\u6765\u4e5f\u597d\u5199，\u5c31\u662f\u9488\u5bf9\u6bcf\u4e00\u4e2a\u770b\u4ed6\u5de6\u53f3\u7684\u6700\u5927，\u4e00\u7ef4dp\u518d\u538b\u7f29\u7a7a\u95f4O1\u3002<\/p>\n

package<\/span> t11<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>a[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>n+<\/span>1<\/span>]<\/span>,<\/span>jg=<\/span>0<\/span>,<\/span>m1=<\/span>0<\/span>,<\/span>m2=<\/span>0<\/span>,<\/span>l=<\/span>0<\/span>,<\/span>r=<\/span>n–<\/span>1<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span>=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n while<\/span>(<\/span>l<=<\/span>r)<\/span>{<\/span>
\n m1=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>m1,<\/span>a[<\/span>l]<\/span>)<\/span>;<\/span>
\n m2=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>m2,<\/span>a[<\/span>r]<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>m1<=<\/span>m2)<\/span>{<\/span>
\n jg+=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>0<\/span>,<\/span>m1–<\/span>a[<\/span>l]<\/span>)<\/span>;<\/span>
\n l++<\/span>;<\/span>
\n }<\/span>
\n else<\/span>{<\/span>
\n jg+=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>0<\/span>,<\/span>m2–<\/span>a[<\/span>r]<\/span>)<\/span>;<\/span>
\n r—<\/span>;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u65f6\u95f4ON\u7a7a\u95f4O1(\u60f3\u5230\u662f\u6bcf\u4e2a\u5143\u7d20\u7684\u5de6\u53f3\u6700\u5927，\u518ddp\u538b\u8fc7\u6765\u7684\u5c31\u77e5\u9053\u600e\u4e48\u5199\u4e86)<\/p>\n

12. \u87ba\u65cb\u77e9\u9635<\/h3>\n

\u6a21\u62df\u5509\u5509\u8ba8\u538c\u8d64\u77f3，\u4e0d\u8fc7\u5524\u9192\u4ee5\u524d\u7684\u8bb0\u5fc6\u60f3\u8d77\u6765s,x,z,r\u5c31\u80fd\u5199\u8d77\u6765\u5f88\u8212\u670d<\/p>\n

package<\/span> t12<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>ArrayList<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>List<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> a[<\/span>]<\/span>[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>[<\/span>1005<\/span>]<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>m=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n for<\/span> (<\/span>int<\/span> i1 =<\/span> 0<\/span>;<\/span> i1 <<\/span> m;<\/span> i1++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span>[<\/span>i1]<\/span>=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n List<\/span><<\/span>Integer<\/span>><\/span><\/span>jg=<\/span>new<\/span> ArrayList<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n int<\/span> s=<\/span>0<\/span>,<\/span>x=<\/span>n–<\/span>1<\/span>,<\/span>z=<\/span>0<\/span>,<\/span>r=<\/span>m–<\/span>1<\/span>;<\/span>
\n while<\/span>(<\/span>true<\/span>)<\/span>{<\/span>
\n for<\/span>(<\/span>int<\/span> i=<\/span>z;<\/span>i<=<\/span>r;<\/span>i++<\/span>)<\/span>jg.<\/span>add<\/span>(<\/span>a[<\/span>s]<\/span>[<\/span>i]<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>++<\/span>s><\/span>x)<\/span>break<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n for<\/span>(<\/span>int<\/span> i=<\/span>s;<\/span>i<=<\/span>x;<\/span>i++<\/span>)<\/span>jg.<\/span>add<\/span>(<\/span>a[<\/span>i]<\/span>[<\/span>r]<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>—<\/span>r<<\/span>z)<\/span>break<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n for<\/span>(<\/span>int<\/span> i=<\/span>r;<\/span>i>=<\/span>z;<\/span>i—<\/span>)<\/span>jg.<\/span>add<\/span>(<\/span>a[<\/span>x]<\/span>[<\/span>i]<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>—<\/span>x<<\/span>s)<\/span>break<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n for<\/span>(<\/span>int<\/span> i=<\/span>x;<\/span>i>=<\/span>s;<\/span>i—<\/span>)<\/span>jg.<\/span>add<\/span>(<\/span>a[<\/span>i]<\/span>[<\/span>z]<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>++<\/span>z><\/span>r)<\/span>break<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u5efa\u8bae\u5199\u7684\u65f6\u5019\u4e5f\u628a\u8f93\u51fa\u5199\u4e0a，\u4e0d\u7ba1\u5230\u65f6\u5019\u8981\u4e0d\u8981\u627ebug\u4e5f\u53ef\u4ee5\u770b\u5f97\u66f4\u6e05\u695a（）<\/p>\n

\u65f6\u95f4on^2\u7a7a\u95f4o1\u4e0d\u8fc7\u6a21\u62df\u8c08\u590d\u6742\u5ea6\u611f\u89c9\u6ca1\u4ec0\u4e48\u5fc5\u8981<\/p>\n

13. \u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u94fe\u8868<\/h3>\n

\u60f3\u660e\u767d\u601d\u8def\u518d\u5199（\u4e0d\u7136\u5bb9\u6613\u53d8\u6210\u732a\u54aa，\u5148\u770b\u80fd\u4e0d\u80fd\u601d\u8def\u8fc7\u6837\u4f8b）<\/p>\n

package<\/span> t13<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> ListNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n ListNode<\/span> next;<\/span><\/p>\n

ListNode<\/span>(<\/span>int<\/span> x)<\/span> {<\/span>
\n val =<\/span> x;<\/span>
\n next =<\/span> null<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> m =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n ListNode<\/span> r1 =<\/span> new<\/span> ListNode<\/span>(<\/span>–<\/span>1<\/span>)<\/span>,<\/span> r2 =<\/span> new<\/span> ListNode<\/span>(<\/span>–<\/span>2<\/span>)<\/span>,<\/span> bl1 =<\/span> r1,<\/span> bl2 =<\/span> r2,<\/span> wei =<\/span> new<\/span> ListNode<\/span>(<\/span>–<\/span>3<\/span>)<\/span>,<\/span> jg =<\/span> wei;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> x =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n bl1.<\/span>next =<\/span> new<\/span> ListNode<\/span>(<\/span>x)<\/span>;<\/span>
\n bl1 =<\/span> bl1.<\/span>next;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> x =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n bl2.<\/span>next =<\/span> new<\/span> ListNode<\/span>(<\/span>x)<\/span>;<\/span>
\n bl2 =<\/span> bl2.<\/span>next;<\/span>
\n }<\/span><\/p>\n

bl1 =<\/span> r1.<\/span>next;<\/span>
\n bl2 =<\/span> r2.<\/span>next;<\/span>
\n while<\/span> (<\/span>bl1 !=<\/span> null<\/span> &&<\/span> bl2 !=<\/span> null<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>bl1.<\/span>val <=<\/span> bl2.<\/span>val)<\/span> {<\/span>
\n wei.<\/span>next =<\/span> bl1;<\/span>
\n bl1 =<\/span> bl1.<\/span>next;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n wei.<\/span>next =<\/span> bl2;<\/span>
\n bl2 =<\/span> bl2.<\/span>next;<\/span>
\n }<\/span>
\n wei=<\/span>wei.<\/span>next;<\/span>
\n }<\/span>
\n wei.<\/span>next =<\/span> bl1 ==<\/span> null<\/span> ?<\/span> bl2 :<\/span> bl1;<\/span>
\n jg=<\/span>jg.<\/span>next;<\/span>
\n while<\/span> (<\/span>jg !=<\/span> null<\/span>)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>print<\/span>(<\/span>jg.<\/span>val+<\/span>" "<\/span>)<\/span>;<\/span>
\n jg =<\/span> jg.<\/span>next;<\/span>
\n }<\/span><\/p>\n

}<\/span>
\n}<\/span><\/p>\n

\u6ce8\u610f\u4e0b\u7ec6\u8282\u548c\u601d\u8def，\u590d\u6742\u5ea6ON<\/p>\n

14. \u5408\u5e76K\u4e2a\u5347\u5e8f\u94fe\u8868<\/h3>\n

\u7b2c\u4e00\u601d\u8def\u662f\u5408\u5e76\u4e24\u4e2a\u5347\u5e8f\u94fe\u8868\u5e26\u5165\u4f46\u662f\u590d\u6742\u5ea6\u662fO(N * K)<\/p>\n

\u4f18\u5316\u540e\u597d\u60f3\u7684\u662f\u4f18\u5148\u961f\u5217\u65f6\u95f4O(N * logK)\u4f46\u662f\u7a7a\u95f4O（N) \u5206\u6cbb\u65f6\u95f4O（N * K）\u4e14\u7a7a\u95f4O(1)\u5c31\u662fk-1\u6b21\u6539\u6210\u4e24\u4e24\u5408\u5e76<\/p>\n

\u7c7b\u4f3c\u5f52\u5e76\u6392\u5e8f<\/p>\n

package<\/span> t14<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> ListNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n ListNode<\/span> next;<\/span><\/p>\n

ListNode<\/span>(<\/span>int<\/span> x)<\/span> {<\/span>
\n val =<\/span> x;<\/span>
\n next =<\/span> null<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> ListNode<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> ListNode<\/span>[<\/span>1005<\/span>]<\/span>;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span><\/p>\n

for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> m =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n ListNode<\/span> wei =<\/span> new<\/span> ListNode<\/span>(<\/span>–<\/span>1<\/span>)<\/span>,<\/span> jg =<\/span> wei;<\/span>
\n for<\/span> (<\/span>int<\/span> i1 =<\/span> 0<\/span>;<\/span> i1 <<\/span> m;<\/span> i1++<\/span>)<\/span> {<\/span>
\n int<\/span> x=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n wei.<\/span>next =<\/span> new<\/span> ListNode<\/span>(<\/span>x)<\/span>;<\/span>
\n wei =<\/span> wei.<\/span>next;<\/span>
\n }<\/span>
\n a[<\/span>i]<\/span> =<\/span> jg.<\/span>next;<\/span>
\n }<\/span>
\n ListNode<\/span> merge =<\/span> merge<\/span>(<\/span>0<\/span>,<\/span> n –<\/span> 1<\/span>)<\/span>;<\/span>
\n while<\/span> (<\/span>merge!=<\/span>null<\/span>)<\/span>{<\/span>
\n System<\/span>.<\/span>out.<\/span>print<\/span>(<\/span>merge.<\/span>val+<\/span>" "<\/span>)<\/span>;<\/span>
\n merge=<\/span>merge.<\/span>next;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

static<\/span> ListNode<\/span> merge<\/span>(<\/span>int<\/span> l,<\/span> int<\/span> r)<\/span> {<\/span>
\n if<\/span> (<\/span>l ==<\/span> r)<\/span> {<\/span>
\n return<\/span> a[<\/span>l]<\/span>;<\/span>
\n }<\/span>
\n int<\/span> mid =<\/span> (<\/span>l +<\/span> r)<\/span> \/<\/span> 2<\/span>;<\/span>
\n ListNode<\/span> l1 =<\/span> merge<\/span>(<\/span>l,<\/span> mid)<\/span>;<\/span>
\n ListNode<\/span> r1 =<\/span> merge<\/span>(<\/span>mid +<\/span> 1<\/span>,<\/span> r)<\/span>;<\/span>
\n return<\/span> mergeTwoLists<\/span>(<\/span>l1,<\/span> r1)<\/span>;<\/span>
\n }<\/span><\/p>\n

static<\/span> ListNode<\/span> mergeTwoLists<\/span>(<\/span>ListNode<\/span> r1,<\/span> ListNode<\/span> r2)<\/span> {<\/span>
\n ListNode<\/span> bl1 =<\/span> r1,<\/span> bl2 =<\/span> r2,<\/span> wei =<\/span> new<\/span> ListNode<\/span>(<\/span>–<\/span>3<\/span>)<\/span>,<\/span> jg =<\/span> wei;<\/span>
\n while<\/span> (<\/span>bl1 !=<\/span> null<\/span> &&<\/span> bl2 !=<\/span> null<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>bl1.<\/span>val <=<\/span> bl2.<\/span>val)<\/span> {<\/span>
\n wei.<\/span>next =<\/span> bl1;<\/span>
\n bl1 =<\/span> bl1.<\/span>next;<\/span>
\n }<\/span> else<\/span> {<\/span>
\n wei.<\/span>next =<\/span> bl2;<\/span>
\n bl2 =<\/span> bl2.<\/span>next;<\/span>
\n }<\/span>
\n wei =<\/span> wei.<\/span>next;<\/span>
\n }<\/span>
\n wei.<\/span>next =<\/span> bl1 ==<\/span> null<\/span> ?<\/span> bl2 :<\/span> bl1;<\/span>
\n return<\/span> jg.<\/span>next;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u4e3b\u8981\u5c31\u662f\u5f52\u5e76\u914d\u548c\u5408\u5e76\u4e24\u4e2a（\u5f52\u5e76\u548c\u5feb\u6392\u7684\u5199\u6cd5\u90fd\u662f\u91cd\u8981\u7684）<\/p>\n

15. \u4ece\u524d\u5e8f\u4e0e\u4e2d\u5e8f\u904d\u5386\u5e8f\u5217\u6784\u9020\u4e8c\u53c9\u6811<\/h3>\n

\u6211\u6295\u964d，\u6211\u5927\u6982\u662f\u6ca1\u5199\u8fc7\u8fd9\u79cd\u3002\u83492025.8.10\u63d0\u4ea4\u8fc7，\u54c8\u54c8<\/p>\n

\u770b\u9898\u89e3\u5427，\u8fd8\u662f\u4e0d\u64c5\u957f\u9012\u5f52，\u592afw\u4e86<\/p>\n

package<\/span> t15<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>HashMap<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Map<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> TreeNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n TreeNode<\/span> left;<\/span>
\n TreeNode<\/span> right;<\/span><\/p>\n

TreeNode<\/span>(<\/span>)<\/span> {<\/span>
\n }<\/span><\/p>\n

TreeNode<\/span>(<\/span>int<\/span> val)<\/span> {<\/span>
\n this<\/span>.<\/span>val =<\/span> val;<\/span>
\n }<\/span><\/p>\n

TreeNode<\/span>(<\/span>int<\/span> val,<\/span> TreeNode<\/span> left,<\/span> TreeNode<\/span> right)<\/span> {<\/span>
\n this<\/span>.<\/span>val =<\/span> val;<\/span>
\n this<\/span>.<\/span>left =<\/span> left;<\/span>
\n this<\/span>.<\/span>right =<\/span> right;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> b[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>;<\/span>
\n static<\/span> Map<\/span><<\/span>Integer<\/span>,<\/span> Integer<\/span>><\/span><\/span> map =<\/span> new<\/span> HashMap<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span><\/p>\n

\/\/l1 r1 l2 r2\u662f\u6570\u7ec4\u5bf9\u5e94\u7684\u505a\u6216\u8005\u6709\u7684\u6c14\u52bf<\/span>
\n static<\/span> TreeNode<\/span> build<\/span>(<\/span>int<\/span> l1,<\/span> int<\/span> r1,<\/span> int<\/span> l2,<\/span> int<\/span> r2)<\/span> {<\/span>
\n if<\/span> (<\/span>l1 ><\/span> r1)<\/span> return<\/span> null<\/span>;<\/span>
\n int<\/span> rv =<\/span> a[<\/span>l1]<\/span>;<\/span>
\n TreeNode<\/span> root =<\/span> new<\/span> TreeNode<\/span>(<\/span>rv)<\/span>;<\/span>
\n int<\/span> wz =<\/span> map.<\/span>get<\/span>(<\/span>rv)<\/span>;<\/span>
\n int<\/span> zb =<\/span> wz –<\/span> l2;<\/span>
\n root.<\/span>left =<\/span> build<\/span>(<\/span>l1 +<\/span> 1<\/span>,<\/span> l1 +<\/span> zb,<\/span> l2,<\/span> wz –<\/span> 1<\/span>)<\/span>;<\/span>
\n root.<\/span>right =<\/span> build<\/span>(<\/span>l1 +<\/span> zb +<\/span> 1<\/span>,<\/span> r1,<\/span> wz +<\/span> 1<\/span>,<\/span> r2)<\/span>;<\/span>
\n return<\/span> root;<\/span>
\n }<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> m =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m;<\/span> i++<\/span>)<\/span> {<\/span>
\n b[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m;<\/span> i++<\/span>)<\/span> {<\/span>
\n map.<\/span>put<\/span>(<\/span>b[<\/span>i]<\/span>,<\/span> i)<\/span>;<\/span>
\n }<\/span>
\n TreeNode<\/span> build =<\/span> build<\/span>(<\/span>0<\/span>,<\/span> n –<\/span> 1<\/span>,<\/span> 0<\/span>,<\/span> m –<\/span> 1<\/span>)<\/span>;<\/span>
\n dfs<\/span>(<\/span>build)<\/span>;<\/span>
\n }<\/span><\/p>\n

static<\/span> void<\/span> dfs<\/span>(<\/span>TreeNode<\/span> a)<\/span> {<\/span>
\n if<\/span> (<\/span>a ==<\/span> null<\/span>)<\/span> return<\/span>;<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>a.<\/span>val)<\/span>;<\/span>
\n dfs<\/span>(<\/span>a.<\/span>left)<\/span>;<\/span>
\n dfs<\/span>(<\/span>(<\/span>a.<\/span>right)<\/span>)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790O(N)\u5982\u679c\u6ca1\u7528hashmap\u4f1a\u662fO(N^2)，\u611f\u89c9\u96be\u60f3\u7684\u70b9\u8fd8\u662f<\/p>\n

root.left = build(l1 + 1, l1 + zb, l2, wz – 1);
\n root.right = build(l1 + zb + 1, r1, wz + 1, r2);<\/p>\n

16. \u91cd\u6392\u94fe\u8868<\/h3>\n

\u8fd9\u9053\u9898\u7b2c\u4e00\u773c\u6709\u4e86\u5927\u6982\u601d\u8def，\u4f46\u611f\u89c9\u9ebb\u70e6，\u770b\u4e86\u9898\u89e3\u662f\u4e00\u6837\u7684，\u8349\u3002\u8fd8\u662f\u8001\u8001\u5b9e\u5b9e\u5b9e\u73b0\u53bb\u5427\u3002<\/p>\n

package<\/span> t16<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> ListNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n ListNode<\/span> next;<\/span><\/p>\n

ListNode<\/span>(<\/span>int<\/span> x)<\/span> {<\/span>
\n val =<\/span> x;<\/span>
\n next =<\/span> null<\/span>;<\/span>
\n }<\/span>
\n}<\/span>
\npublic<\/span> class<\/span> main {<\/span>
\n static<\/span> ListNode<\/span> zb;<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n ListNode<\/span> wei=<\/span>new<\/span> ListNode<\/span>(<\/span>–<\/span>2<\/span>)<\/span>,<\/span>bl1=<\/span>wei,<\/span>k=<\/span>wei,<\/span>m=<\/span>wei;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n bl1.<\/span>next=<\/span>new<\/span> ListNode<\/span>(<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\n bl1=<\/span>bl1.<\/span>next;<\/span>
\n }<\/span>
\n zb=<\/span>wei.<\/span>next;<\/span>
\n while<\/span> (<\/span>k!=<\/span>null<\/span>&&<\/span>k.<\/span>next!=<\/span>null<\/span>)<\/span>{<\/span>
\n k=<\/span>k.<\/span>next.<\/span>next;<\/span>
\n m=<\/span>m.<\/span>next;<\/span>
\n }<\/span>
\n ListNode<\/span> b=<\/span>m.<\/span>next;<\/span>
\n m.<\/span>next=<\/span>null<\/span>;<\/span>\/\/\u65ad\u5f00\u8fde\u63a5\u662f\u6709\u5fc5\u8981\u7684<\/span>
\n digui<\/span>(<\/span>b)<\/span>;<\/span>
\n wei=<\/span>wei.<\/span>next;<\/span>
\n while<\/span> (<\/span>wei!=<\/span>null<\/span>)<\/span>{<\/span>
\n System<\/span>.<\/span>out.<\/span>print<\/span>(<\/span>wei.<\/span>val+<\/span>" "<\/span>)<\/span>;<\/span>
\n wei=<\/span>wei.<\/span>next;<\/span>
\n }<\/span>
\n }<\/span>
\n static<\/span> void<\/span> digui<\/span>(<\/span>ListNode<\/span> a)<\/span>{<\/span>
\n if<\/span>(<\/span>a==<\/span>null<\/span>)<\/span>return<\/span>;<\/span>
\n digui<\/span>(<\/span>a.<\/span>next)<\/span>;<\/span>
\n ListNode<\/span> temp=<\/span>zb.<\/span>next;<\/span>
\n zb.<\/span>next=<\/span>a;<\/span>
\n a.<\/span>next=<\/span>temp;<\/span>
\n zb=<\/span>temp;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

(\u5b69\u5b50\u4eec0:07\u4e86，\u6211\u4f1a\u8d62\u5417，\u80fd\u5728\u7761\u524d\u5199\u5b8c25\u5417)<\/p>\n

\u590d\u6742\u5ea6O（N)<\/p>\n

17.\u6570\u503c\u7684\u6574\u6570\u6b21\u65b9<\/h3>\n

\u5feb\u901f\u5e42\u5417，\u6709\u70b9\u5fd8\u4e86\u8bf4\u662f，\u4e3b\u8981Java\u7684biginteger\u7c7b\u7684modpow\u7684\u5b9e\u73b0\u5c31\u662f\u5feb\u901f\u5e42\u3002\u3002\u3002\u8fd8\u8981\u624b\u6495<\/p>\n

package<\/span> t17<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n double<\/span> a =<\/span> sc.<\/span>nextDouble<\/span>(<\/span>)<\/span>,<\/span> jg =<\/span> 1<\/span>,<\/span> sum =<\/span> –<\/span>1<\/span>;<\/span>
\n int<\/span> b =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span> sl =<\/span> 0<\/span>;<\/span>
\n if<\/span> (<\/span>b <<\/span> 0<\/span>)<\/span> b *=<\/span> –<\/span>1<\/span>;<\/span>
\n a =<\/span> 1<\/span> \/<\/span> a;<\/span>
\n sum =<\/span> a;<\/span>
\n String<\/span> er =<\/span> Integer<\/span>.<\/span>toBinaryString<\/span>(<\/span>b)<\/span>;<\/span>
\n sl =<\/span> er.<\/span>length<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> sl –<\/span> 1<\/span>;<\/span> i >=<\/span> 0<\/span>;<\/span> i—<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>er.<\/span>charAt<\/span>(<\/span>i)<\/span> ==<\/span> '1'<\/span>)<\/span> {<\/span>
\n jg *=<\/span> sum;<\/span>
\n }<\/span>
\n sum *=<\/span> sum;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6\u5206\u6790logn，\u76f4\u63a5\u66b4\u529b\u7684\u8bdd\u8981ON，\u4f46\u662f\u6211\u8fd9\u79cd\u8fd8\u6709logn\u7684\u7a7a\u95f4，\u5982\u679c\u4e0d\u60f3\u8981\u5c31\u7528\u4e0b\u9762\u90a3\u79cd<\/p>\n

\u987a\u4fbf\u770b\u4e00\u4e0b\u4ee5\u524d\u7684\u5feb\u901f\u5e42\u677f\u5b50<\/p>\n

while (b != 0) {
\nif (b % 2)
\njg =(jg* a)%p;
\na = (a*a)%p;
\nb \/= 2;
\n}<\/p>\n

\u53ea\u80fd\u8bf4\u8001\u4e86，\u6015\u8bb0\u4e0d\u4f4f，\u4e0a\u9762\u7684\u901a\u4fd7\u6613\u61c2\u70b9（？）<\/p>\n

18. \u5168\u6392\u5217<\/h3>\n

\u9001\u5206\u9898！\u5c0f\u5c0fdfs\u65a9\u4e8e\u9a6c\u4e0b<\/p>\n

package<\/span> t18<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> f[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> b[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> n;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n dfs<\/span>(<\/span>0<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

static<\/span> void<\/span> dfs<\/span>(<\/span>int<\/span> x)<\/span> {<\/span>
\n if<\/span> (<\/span>x ==<\/span> n)<\/span> {<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>printf<\/span>(<\/span>"%d "<\/span>,<\/span> a[<\/span>b[<\/span>i]<\/span>]<\/span>)<\/span>;<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>f[<\/span>i]<\/span> ==<\/span> 0<\/span>)<\/span> {<\/span>
\n f[<\/span>i]<\/span> =<\/span> 1<\/span>;<\/span>
\n b[<\/span>x]<\/span> =<\/span> i;<\/span>
\n dfs<\/span>(<\/span>x +<\/span> 1<\/span>)<\/span>;<\/span>
\n f[<\/span>i]<\/span> =<\/span> 0<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u590d\u6742\u5ea6\u65f6\u95f4n * n!\u7a7a\u95f4n\u3002\u4f1a\u4e86\u8fd9\u4e2a\u5c31\u7b49\u4e8e\u4f1a\u4e86\u516b\u7687\u540e（）<\/p>\n

19. \u5c9b\u5c7f\u6570\u91cf<\/h3>\n

package<\/span> t19<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> char<\/span> a[<\/span>]<\/span>[<\/span>]<\/span> =<\/span> new<\/span> char<\/span>[<\/span>1005<\/span>]<\/span>[<\/span>1005<\/span>]<\/span>;<\/span>
\n static<\/span> int<\/span> ydh[<\/span>]<\/span> =<\/span> {<\/span>–<\/span>1<\/span>,<\/span> 0<\/span>,<\/span> 1<\/span>,<\/span> 0<\/span>}<\/span>,<\/span> ydl[<\/span>]<\/span> =<\/span> {<\/span>0<\/span>,<\/span> 1<\/span>,<\/span> 0<\/span>,<\/span> –<\/span>1<\/span>}<\/span>,<\/span> n,<\/span> m,<\/span> jg;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n m =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n jg =<\/span> 0<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>next<\/span>(<\/span>)<\/span>.<\/span>toCharArray<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n for<\/span> (<\/span>int<\/span> i1 =<\/span> 0<\/span>;<\/span> i1 <<\/span> m;<\/span> i1++<\/span>)<\/span> {<\/span>
\n if<\/span> (<\/span>a[<\/span>i]<\/span>[<\/span>i1]<\/span> ==<\/span> '1'<\/span>)<\/span> {<\/span>
\n jg++<\/span>;<\/span>
\n dfs<\/span>(<\/span>i,<\/span> i1)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span><\/p>\n

static<\/span> void<\/span> dfs<\/span>(<\/span>int<\/span> h,<\/span> int<\/span> l)<\/span> {<\/span>
\n if<\/span>(<\/span>a[<\/span>h]<\/span>[<\/span>l]<\/span>==<\/span>'0'<\/span>)<\/span>return<\/span>;<\/span>
\n a[<\/span>h]<\/span>[<\/span>l]<\/span>=<\/span>'0'<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> 4<\/span>;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> h1 =<\/span> ydh[<\/span>i]<\/span> +<\/span> h,<\/span> l1 =<\/span> ydl[<\/span>i]<\/span> +<\/span> l;<\/span>
\n if<\/span> (<\/span>h1 ><\/span> –<\/span>1<\/span> &&<\/span> h1 <<\/span> n&&<\/span>l1><\/span>–<\/span>1<\/span>&&<\/span>l1<<\/span>m)<\/span>{<\/span>
\n dfs<\/span>(<\/span>h1,<\/span>l1)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u611f\u89c9\u8fd9\u79cd\u9012\u5f52\u6bd4\u8d77\u6811\u548c\u94fe\u8868\u8fd8\u662f\u592a\u4ec1\u6148\u4e86<\/p>\n

\u65f6\u95f4O（N2)\u7a7a\u95f4O(N<\/sup>2)<\/p>\n

20. \u53cd\u8f6c\u94fe\u8868 II<\/h3>\n

package<\/span> t20<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

class<\/span> ListNode<\/span> {<\/span>
\n int<\/span> val;<\/span>
\n ListNode<\/span> next;<\/span><\/p>\n

ListNode<\/span>(<\/span>int<\/span> x)<\/span> {<\/span>
\n val =<\/span> x;<\/span>
\n next =<\/span> null<\/span>;<\/span>
\n }<\/span>
\n}<\/span>
\npublic<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>z=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>r=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>f=<\/span>0<\/span>;<\/span>
\n ListNode<\/span> wei=<\/span>new<\/span> ListNode<\/span>(<\/span>–<\/span>1<\/span>)<\/span>,<\/span>bl1=<\/span>wei,<\/span>bl2=<\/span>wei,<\/span>bl3=<\/span>null<\/span>,<\/span>bl4=<\/span>null<\/span>,<\/span>bl5=<\/span>null<\/span>,<\/span>bl6=<\/span>null<\/span>,<\/span>bl7=<\/span>null<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> x=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n bl1.<\/span>next=<\/span>new<\/span> ListNode<\/span>(<\/span>x)<\/span>;<\/span>
\n bl1=<\/span>bl1.<\/span>next;<\/span>
\n }<\/span>
\n bl1=<\/span>wei;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> z –<\/span>1<\/span>;<\/span> i++<\/span>)<\/span> {<\/span>
\n bl1=<\/span>bl1.<\/span>next;<\/span>
\n }<\/span>bl3=<\/span>bl1.<\/span>next;<\/span>bl5=<\/span>bl1;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> r;<\/span> i++<\/span>)<\/span> {<\/span>
\n bl2=<\/span>bl2.<\/span>next;<\/span>
\n }<\/span>bl4=<\/span>bl2.<\/span>next;<\/span>
\n while<\/span>(<\/span>bl3!=<\/span>bl4)<\/span>{<\/span>
\n if<\/span>(<\/span>f==<\/span>0<\/span>)<\/span>{<\/span>
\n f=<\/span>1<\/span>;<\/span>
\n bl7=<\/span>bl3;<\/span>
\n }<\/span>
\n if<\/span>(<\/span>bl3.<\/span>next==<\/span>bl4)<\/span>bl6=<\/span>bl3;<\/span>
\n ListNode<\/span> temp=<\/span>bl3.<\/span>next;<\/span>
\n bl3.<\/span>next=<\/span>bl1;<\/span>
\n bl1=<\/span>bl3;<\/span>
\n bl3=<\/span>temp;<\/span>
\n }<\/span>bl5.<\/span>next=<\/span>bl6;<\/span>bl7.<\/span>next=<\/span>bl3;<\/span>
\n wei=<\/span>wei.<\/span>next;<\/span>
\n while<\/span>(<\/span>wei!=<\/span>null<\/span>)<\/span>{<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>wei.<\/span>val)<\/span>;<\/span>
\n wei=<\/span>wei.<\/span>next;<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u522b\u770b7\u4e2abl\u5199\u7684\u5f88\u795e\u79d8，\u4f46\u662f\u6539\u4e3a\u6838\u5fc3\u540e\u529b\u6263\u4e00\u904d\u8fc7\u5f88\u723d\u597d\u5427<\/p>\n

\u590d\u6742\u5ea6O（N)\u628a<\/p>\n

21.\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/h3>\n

\u597d\u50cf\u662f\u523b\u8fdbdna\u7684dp\u9898\u76ee,\u4e8c\u5206\u8d2a\u5fc3\u6700\u4f18\u89e3nlogn，\u66b4\u529bdp O(N^2)<\/p>\n

package<\/span> t21<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Arrays<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n static<\/span> int<\/span> a[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> b[<\/span>]<\/span> =<\/span> new<\/span> int<\/span>[<\/span>1005<\/span>]<\/span>,<\/span> n;<\/span><\/p>\n

public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc =<\/span> new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n n =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span> =<\/span> sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n Arrays<\/span>.<\/span>fill<\/span>(<\/span>b,<\/span> 10005<\/span>)<\/span>;<\/span>
\n int<\/span> jg =<\/span> 0<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n int<\/span> wz =<\/span> Arrays<\/span>.<\/span>binarySearch<\/span>(<\/span>b,<\/span> a[<\/span>i]<\/span>)<\/span>;<\/span>
\n if<\/span> (<\/span>wz <<\/span> 0<\/span>)<\/span> {<\/span>
\n wz =<\/span> –<\/span>wz –<\/span> 1<\/span>;<\/span>
\n if<\/span> (<\/span>b[<\/span>wz]<\/span> ==<\/span> 10005<\/span>)<\/span> jg++<\/span>;<\/span>
\n b[<\/span>wz]<\/span> =<\/span> a[<\/span>i]<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>jg)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u4e8c\u5206\u8d2a\u5fc3\u5c3e\u6570\u6570\u7ec4\u5f88\u5999，\u53ef\u4ee5\u591a\u60f3\u60f3\u522b\u5fd8\u4e86<\/p>\n

\u590d\u6742\u5ea6nlogn<\/p>\n

22. K \u4e2a\u4e00\u7ec4\u7ffb\u8f6c\u94fe\u8868<\/h3>\n

\/**
\n * Definition for singly-linked list.
\n * public class ListNode {
\n * int val;
\n * ListNode next;
\n * ListNode() {}
\n * ListNode(int val) { this.val = val; }
\n * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
\n * }
\n *\/<\/span>
\nclass<\/span> Solution<\/span> {<\/span>
\n public<\/span> static<\/span> ListNode<\/span> reverseKGroup<\/span>(<\/span>ListNode<\/span> head,<\/span> int<\/span> k)<\/span> {<\/span>
\n ListNode<\/span> j =<\/span> new<\/span> ListNode<\/span>(<\/span>0<\/span>)<\/span>,<\/span> jg =<\/span> null<\/span>,<\/span> x =<\/span> j;<\/span>
\n int<\/span> f =<\/span> 0<\/span>;<\/span>
\n j.<\/span>next =<\/span> head;<\/span>
\n while<\/span> (<\/span>true<\/span>)<\/span> {<\/span>
\n int<\/span> pd =<\/span> 0<\/span>;<\/span>
\n x =<\/span> j;<\/span>
\n while<\/span> (<\/span>j !=<\/span> null<\/span> &&<\/span> pd <<\/span> k)<\/span> {<\/span>
\n j =<\/span> j.<\/span>next;<\/span>
\n pd++<\/span>;<\/span>
\n }<\/span>
\n if<\/span> (<\/span>j ==<\/span> null<\/span>)<\/span> break<\/span>;<\/span>
\n ListNode<\/span> a =<\/span> x,<\/span> b =<\/span> x.<\/span>next,<\/span> sum3 =<\/span> j.<\/span>next,<\/span>qd=<\/span>null<\/span>;<\/span>
\n while<\/span> (<\/span>b !=<\/span> sum3)<\/span> {<\/span>
\n if<\/span> (<\/span>b ==<\/span> j)<\/span> {<\/span>
\n if<\/span> (<\/span>f ==<\/span> 0<\/span>)<\/span> {<\/span>
\n jg =<\/span> b;<\/span>
\n f =<\/span> 1<\/span>;<\/span>
\n }<\/span>
\n qd=<\/span>b;<\/span>
\n }<\/span>
\n ListNode<\/span> temp =<\/span> b.<\/span>next;<\/span>
\n b.<\/span>next =<\/span> a;<\/span>
\n a =<\/span> b;<\/span>
\n b =<\/span> temp;<\/span>
\n }<\/span>
\n j =<\/span> x.<\/span>next;<\/span>
\n j.<\/span>next =<\/span> sum3;<\/span>
\n x.<\/span>next=<\/span>qd;<\/span>
\n }<\/span>
\n return<\/span> jg;<\/span>
\n }<\/span><\/p>\n

}<\/span><\/p>\n

\u8fd9\u9053\u9898\u76ee\u6bd4\u8f83\u5403\u903b\u8f91，\u53ef\u4ee5\u591a\u60f3\u60f3<\/p>\n

23. \u6700\u5c0f\u6808<\/h3>\n

import<\/span> java.<\/span>util.<\/span><\/span>ArrayDeque<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Date<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Deque<\/span>;<\/span><\/p>\n

\/\/leetcode submit region begin(Prohibit modification and deletion)<\/span>
\nclass<\/span> MinStack<\/span> {<\/span>
\n Deque<\/span><<\/span>Integer<\/span>><\/span><\/span> stack1;<\/span>
\n Deque<\/span><<\/span>Integer<\/span>><\/span><\/span> stack2;<\/span><\/p>\n

public<\/span> MinStack<\/span>(<\/span>)<\/span> {<\/span>
\n stack1 =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n stack2 =<\/span> new<\/span> ArrayDeque<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

public<\/span> void<\/span> push<\/span>(<\/span>int<\/span> val)<\/span> {<\/span>
\n stack1.<\/span>addLast<\/span>(<\/span>val)<\/span>;<\/span>
\n if<\/span>(<\/span>stack2.<\/span>isEmpty<\/span>(<\/span>)<\/span>||<\/span>val<=<\/span>stack2.<\/span>getLast<\/span>(<\/span>)<\/span>)<\/span>stack2.<\/span>addLast<\/span>(<\/span>val)<\/span>;<\/span>
\n }<\/span><\/p>\n

public<\/span> void<\/span> pop<\/span>(<\/span>)<\/span> {<\/span>
\n Integer<\/span> i =<\/span> stack1.<\/span>pollLast<\/span>(<\/span>)<\/span>;<\/span>
\n if<\/span>(<\/span>i.<\/span>equals<\/span>(<\/span>stack2.<\/span>getLast<\/span>(<\/span>)<\/span>)<\/span>)<\/span>stack2.<\/span>pollLast<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

public<\/span> int<\/span> top<\/span>(<\/span>)<\/span> {<\/span>
\n return<\/span> stack1.<\/span>getLast<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

public<\/span> int<\/span> getMin<\/span>(<\/span>)<\/span> {<\/span>
\n return<\/span> stack2.<\/span>getLast<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u6ce8\u610f\u4e0b\u601d\u8def\u5c31\u884c，\u5e38\u6570\u83b7\u53d6min\u7a7a\u95f4\u6362\u65f6\u95f4，\u8fd8\u6709\u8981\u6ce8\u610fpush\u90a3\u91cc\u6761\u4ef6<=\u6ca1\u6709\u7b49\u4e8emin\u6808\u53ef\u80fd\u4f1a\u7a7a<\/p>\n

24. \u4e24\u6570\u4e4b\u548c<\/h3>\n

package<\/span> t24<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>HashMap<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>x=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>a[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>10005<\/span>]<\/span>;<\/span>
\n HashMap<\/span><<\/span>Integer<\/span>,<\/span>Integer<\/span>><\/span><\/span> map=<\/span>new<\/span> HashMap<\/span><<\/span>><\/span><\/span>(<\/span>)<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span>=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span><\/p>\n

for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n if<\/span>(<\/span>map.<\/span>containsKey<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>)<\/span>{<\/span>
\n int<\/span> jg[<\/span>]<\/span>=<\/span>{<\/span>map.<\/span>get<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>,<\/span>i}<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span> i1 :<\/span> jg)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>println<\/span>(<\/span>i1)<\/span>;<\/span>
\n }<\/span>break<\/span>;<\/span>
\n }<\/span>
\n map.<\/span>put<\/span>(<\/span>x–<\/span>a[<\/span>i]<\/span>,<\/span>i)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u9001\u5206\u9898，nlogn<\/p>\n

25. \u5408\u5e76\u533a\u95f4<\/h3>\n

package<\/span> t25<\/span>;<\/span><\/p>\n

import<\/span> java.<\/span>util.<\/span><\/span>Arrays<\/span>;<\/span>
\nimport<\/span> java.<\/span>util.<\/span><\/span>Scanner<\/span>;<\/span><\/p>\n

public<\/span> class<\/span> main {<\/span>
\n public<\/span> static<\/span> void<\/span> main<\/span>(<\/span>String<\/span>[<\/span>]<\/span> args)<\/span> {<\/span>
\n Scanner<\/span> sc=<\/span>new<\/span> Scanner<\/span>(<\/span>System<\/span>.<\/span>in)<\/span>;<\/span>
\n int<\/span> n=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>,<\/span>a[<\/span>]<\/span>[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>105<\/span>]<\/span>[<\/span>2<\/span>]<\/span>,<\/span>b[<\/span>]<\/span>[<\/span>]<\/span>=<\/span>new<\/span> int<\/span>[<\/span>105<\/span>]<\/span>[<\/span>2<\/span>]<\/span>,<\/span>f=<\/span>0<\/span>;<\/span>
\n for<\/span> (<\/span>int<\/span>[<\/span>]<\/span> ints :<\/span> a)<\/span> {<\/span>
\n Arrays<\/span>.<\/span>fill<\/span>(<\/span>ints,<\/span>10005<\/span>)<\/span>;<\/span>
\n }<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n for<\/span> (<\/span>int<\/span> i1 =<\/span> 0<\/span>;<\/span> i1 <<\/span> 2<\/span>;<\/span> i1++<\/span>)<\/span> {<\/span>
\n a[<\/span>i]<\/span>[<\/span>i1]<\/span>=<\/span>sc.<\/span>nextInt<\/span>(<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span><\/p>\n

Arrays<\/span>.<\/span>sort<\/span>(<\/span>a,<\/span>(<\/span>o,<\/span>p)<\/span>-><\/span>{<\/span>
\n if<\/span>(<\/span>o[<\/span>0<\/span>]<\/span>==<\/span>p[<\/span>0<\/span>]<\/span>)<\/span> return<\/span> o[<\/span>1<\/span>]<\/span>–<\/span>p[<\/span>1<\/span>]<\/span>;<\/span>
\n else<\/span> return<\/span> o[<\/span>0<\/span>]<\/span>–<\/span>p[<\/span>0<\/span>]<\/span>;<\/span>
\n }<\/span>)<\/span>;<\/span><\/p>\n

for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> n;<\/span> i++<\/span>)<\/span> {<\/span>
\n if<\/span>(<\/span>i==<\/span>n–<\/span>1<\/span>)<\/span>{<\/span>
\n b[<\/span>f]<\/span>[<\/span>0<\/span>]<\/span>=<\/span>a[<\/span>i]<\/span>[<\/span>0<\/span>]<\/span>;<\/span>b[<\/span>f++<\/span>]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>;<\/span>break<\/span>;<\/span>
\n }<\/span>
\n int<\/span> r=<\/span>i+<\/span>1<\/span>;<\/span>
\n if<\/span>(<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>>=<\/span>a[<\/span>r]<\/span>[<\/span>0<\/span>]<\/span>)<\/span>{<\/span>
\n while<\/span>(<\/span>r<<\/span>n&&<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>>=<\/span>a[<\/span>r]<\/span>[<\/span>0<\/span>]<\/span>)<\/span>{<\/span>
\n r++<\/span>;<\/span>
\n }<\/span>
\n if<\/span>(<\/span>r==<\/span>n)<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>Math<\/span>.<\/span>max<\/span>(<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>,<\/span>a[<\/span>r–<\/span>1<\/span>]<\/span>[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
\n else<\/span>
\n a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>a[<\/span>r–<\/span>1<\/span>]<\/span>[<\/span>1<\/span>]<\/span>;<\/span>
\n }<\/span>b[<\/span>f]<\/span>[<\/span>0<\/span>]<\/span>=<\/span>a[<\/span>i]<\/span>[<\/span>0<\/span>]<\/span>;<\/span>b[<\/span>f++<\/span>]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>a[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>;<\/span>i=<\/span>r–<\/span>1<\/span>;<\/span><\/p>\n

}<\/span>
\n for<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> f;<\/span> i++<\/span>)<\/span> {<\/span>
\n System<\/span>.<\/span>out.<\/span>printf<\/span>(<\/span>"%d %d\\\\n"<\/span>,<\/span>b[<\/span>i]<\/span>[<\/span>0<\/span>]<\/span>,<\/span>b[<\/span>i]<\/span>[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
\n }<\/span>
\n }<\/span>
\n}<\/span><\/p>\n

\u6392\u5e8f\u771f\u662f\u592a\u65b9\u4fbf\u4e86，\u62ef\u6551\u4e86\u8fd9\u4e2a\u3002\u6ce8\u610f\u4e0b\u4e8c\u7ef4\u6570\u7ec4\u7684\u6392\u5e8f\u65b9\u6cd5\u8981\u91cd\u5199\u4e00\u4e2a\u4e1c\u897f\u3002\u5269\u4e0b\u5c31\u662f\u5408\u5e76\u7ec6\u8282\u6392\u5e8f\u540e\u53ea\u9700\u8981\u8003\u8651\u4e24\u4e2a\u4e86\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u662fnlogn\u6392\u5e8f\u4e86<\/p>\n

\u5176\u4ed6<\/h3>\n

\u6211\u89c9\u5f97\u6709\u610f\u601d\u7684\u9898\u76ee<\/p>\n

560. \u548c\u4e3a K \u7684\u5b50\u6570\u7ec4<\/p>\n","protected":false},"excerpt":{"rendered":"

\u81ea\u7528\u8bb0\u5f55
\n\u6ce8\u610f\u8fd9\u91cc\u90fd\u662f\u5199\u5728acm\u6a21\u5f0f\u4e0b\u7684\u8981\u8003\u8651\u8f93\u5165\u8f93\u51fa，\u8fd8\u6709\u8fd9\u79cd\u9ed8\u8ba4\u662f\u9762\u8bd5\u7684\u65f6\u5019\u7ed9\u6837\u4f8b\u672c\u5730\u8dd1，\u800c\u4e0d\u662f\u76f4\u63a5\u8dd1\u6d4b\u9898\u673a\u3002\u6240\u4ee5\u53ef\u80fd\u6709\u7684\u50cf\u8f93\u5165\u662fnull\u7684\/\u6781\u7aef\u60c5\u51b5\u6ca1\u8003\u8651，\u90a3\u79cd\u5230\u65f6\u5019\u8dd1\u4e00\u6b21\u53d1\u73b0\u4e0d\u5bf9\u4e86\u76f4\u63a5\u52a0\u4e0a\u5c31\u884c\u3002
\n\u6709\u7684\u5199\u6cd5\u662f\u76f4\u63a5\u601d\u8def\u5b9e\u73b0\u7684，\u53ef\u80fd\u590d\u6742\u5ea6\u5bf9\u4f46\u4e0d\u591f\u4f18\u96c5（\u5199\u8d77\u6765\u5f88\u9ebb\u70e6）\u4e4b\u540e\u770b\u5230\u66f4\u597d\u7684\u4f1a\u6539\u7684w
\n1.\u6700\u957f\u4e0d\u542b\u91cd\u590d\u5b57\u7b26\u7684\u5b50\u5b57\u7b26\u4e32
\n\u7b2c\u4e00\u904d\u6709\u4e2a\u987a\u5e8f\u5199\u53cd\u4e86\u6392\u4e86\u4f1adebug\u4e5f\u670915min&#xff1f<\/p>\n","protected":false},"author":2,"featured_media":60582,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[427],"topic":[],"class_list":["post-60584","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-427"],"yoast_head":"\n\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/60584.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u81ea\u7528\u8bb0\u5f55 \u6ce8\u610f\u8fd9\u91cc\u90fd\u662f\u5199\u5728acm\u6a21\u5f0f\u4e0b\u7684\u8981\u8003\u8651\u8f93\u5165\u8f93\u51fa，\u8fd8\u6709\u8fd9\u79cd\u9ed8\u8ba4\u662f\u9762\u8bd5\u7684\u65f6\u5019\u7ed9\u6837\u4f8b\u672c\u5730\u8dd1，\u800c\u4e0d\u662f\u76f4\u63a5\u8dd1\u6d4b\u9898\u673a\u3002\u6240\u4ee5\u53ef\u80fd\u6709\u7684\u50cf\u8f93\u5165\u662fnull\u7684\/\u6781\u7aef\u60c5\u51b5\u6ca1\u8003\u8651，\u90a3\u79cd\u5230\u65f6\u5019\u8dd1\u4e00\u6b21\u53d1\u73b0\u4e0d\u5bf9\u4e86\u76f4\u63a5\u52a0\u4e0a\u5c31\u884c\u3002 \u6709\u7684\u5199\u6cd5\u662f\u76f4\u63a5\u601d\u8def\u5b9e\u73b0\u7684，\u53ef\u80fd\u590d\u6742\u5ea6\u5bf9\u4f46\u4e0d\u591f\u4f18\u96c5（\u5199\u8d77\u6765\u5f88\u9ebb\u70e6）\u4e4b\u540e\u770b\u5230\u66f4\u597d\u7684\u4f1a\u6539\u7684w 1.\u6700\u957f\u4e0d\u542b\u91cd\u590d\u5b57\u7b26\u7684\u5b50\u5b57\u7b26\u4e32 \u7b2c\u4e00\u904d\u6709\u4e2a\u987a\u5e8f\u5199\u53cd\u4e86\u6392\u4e86\u4f1adebug\u4e5f\u670915min&#xff1f\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/60584.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2026-01-15T15:33:24+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/01\/20260115153321-696908c172dd9.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"18 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/60584.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/60584.html\",\"name\":\"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2026-01-15T15:33:24+00:00\",\"dateModified\":\"2026-01-15T15:33:24+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/60584.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/60584.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/60584.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/60584.html","og_locale":"zh_CN","og_type":"article","og_title":"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u81ea\u7528\u8bb0\u5f55 \u6ce8\u610f\u8fd9\u91cc\u90fd\u662f\u5199\u5728acm\u6a21\u5f0f\u4e0b\u7684\u8981\u8003\u8651\u8f93\u5165\u8f93\u51fa，\u8fd8\u6709\u8fd9\u79cd\u9ed8\u8ba4\u662f\u9762\u8bd5\u7684\u65f6\u5019\u7ed9\u6837\u4f8b\u672c\u5730\u8dd1，\u800c\u4e0d\u662f\u76f4\u63a5\u8dd1\u6d4b\u9898\u673a\u3002\u6240\u4ee5\u53ef\u80fd\u6709\u7684\u50cf\u8f93\u5165\u662fnull\u7684\/\u6781\u7aef\u60c5\u51b5\u6ca1\u8003\u8651，\u90a3\u79cd\u5230\u65f6\u5019\u8dd1\u4e00\u6b21\u53d1\u73b0\u4e0d\u5bf9\u4e86\u76f4\u63a5\u52a0\u4e0a\u5c31\u884c\u3002 \u6709\u7684\u5199\u6cd5\u662f\u76f4\u63a5\u601d\u8def\u5b9e\u73b0\u7684，\u53ef\u80fd\u590d\u6742\u5ea6\u5bf9\u4f46\u4e0d\u591f\u4f18\u96c5（\u5199\u8d77\u6765\u5f88\u9ebb\u70e6）\u4e4b\u540e\u770b\u5230\u66f4\u597d\u7684\u4f1a\u6539\u7684w 1.\u6700\u957f\u4e0d\u542b\u91cd\u590d\u5b57\u7b26\u7684\u5b50\u5b57\u7b26\u4e32 \u7b2c\u4e00\u904d\u6709\u4e2a\u987a\u5e8f\u5199\u53cd\u4e86\u6392\u4e86\u4f1adebug\u4e5f\u670915min&#xff1f","og_url":"https:\/\/www.wsisp.com\/helps\/60584.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2026-01-15T15:33:24+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/01\/20260115153321-696908c172dd9.png"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"18 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/60584.html","url":"https:\/\/www.wsisp.com\/helps\/60584.html","name":"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528) - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2026-01-15T15:33:24+00:00","dateModified":"2026-01-15T15:33:24+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/60584.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/60584.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/60584.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u5b57\u8282\u5e38\u8003\u7b97\u6cd5\u9898\u8bb0\u5f55(\u81ea\u7528)"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/60584","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=60584"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/60584\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media\/60582"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=60584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=60584"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=60584"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=60584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}