找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1920|回复: 3
收起左侧

[面经题目讨论] 常见无解题: 怎么把aabb改成abab

[复制链接]

27

主题

4

精华

288

积分

高级会员

Rank: 3Rank: 3

积分
288
发表于 9-12-2015 10:48 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
- l) h' M/ ~$ q- a0 ^: B* y
2 2 3 3 to become 2 3 2 3. ]) n" l) q+ P5 o
2 2 2 2 3 3 3 3 to become 2 3 2 3 2 3 2 3
4 x) u1 n6 L  P5 L0 ]4 ~; w2 2 2 3 3 3 to become 2 3 2 3 2 35 z1 ^0 }; O, M+ Q
5 {7 ]* j3 K- M7 {' z$ y
这里有一个解法,但太繁琐,有没有高明的解法?
# j  b; P3 J* z) D* i$ a  [% K. D* u4 V) G; L% H& j( m
        public void exchange(int[] a){6 w3 Z; i2 F1 W3 h) E# q( j0 Z- |
                exchange(a, 0, a.length-1);# A0 T8 N, i5 S/ E9 T* \6 c0 M; U
        }3 ~( I  C+ z" S! X' F; T
/ \$ C8 ^# C: O: [
        public void exchange(int[] a, int start, int end) {+ j5 x$ S- T! P$ B& Z
                if (start == end - 1)! @. K8 K+ A$ V$ b2 f
                        return;' K, O; s2 E4 k
                if ((end - start + 1) % 4 == 0) {
' ^5 i6 c: P1 Y0 E2 o; |                        int move = (end - start + 1) / 4;- X2 z$ D2 p4 Q! U  e6 }
                        int begin = (start + end) / 2 + 1;9 j7 D7 r  x2 C4 e6 S# h
                        for (int i = 0; i < move; i++) {
( ]0 q$ w6 w" R$ N, F8 n                                swap(a, begin + i, begin + i - move);, p: G$ R/ d- z2 T% N2 z! C5 S4 \. U
                        }/ {% v$ E( _. W% j" |
                        exchange(a, start, start + (end - start) / 2);
, X# C7 T' Y% W; V                        exchange(a, start + (end - start) / 2 + 1, end);: p" p2 T: y3 P
                } else {
% p3 L- {+ M3 d" Q" k1 y                        int move = (end - start + 1) / 4 + 1;
! {5 W* ~" X: d- R! ]. l9 i                        int begin = (start + end) / 2 + 1;
3 q9 U3 V; a; s1 K( w                        for (int i = 0; i < move; i++) {5 p& R# a, E3 E2 [. m( b; X8 X
                                swap(a, begin + i, begin + i - move);
1 B# U0 A, X# I                        }% D+ x" @1 j" R* X, @6 X4 z5 v
                        int med = a[begin];8 W+ E9 g: A* c
                        a[begin] = a[begin - 1];. s. u4 p+ g; j: f+ z9 I6 r, S% k0 @
                        a[begin - 1] = med;
& F; @, ^! `! ]7 {                        exchange(a, start, start + (end - start) / 2 - 1);& R& G1 }% {4 `. t1 ?  r
                        exchange(a, start + (end - start) / 2 + 2, end);. _( U2 f' V, G! f( T5 @
                }
, h& l3 o5 L2 ^2 k        }
; @4 b# h& `) }. S1 \+ l        private void swap(int[] a, int i, int j){
7 q: Y4 b4 N( |' j7 F8 N) }) p$ Y                int temp = a【i】;
8 s) S9 q3 \, w! ?                a【i】 = a[j];( n0 A1 k. y4 C" O! c
                a[j] = temp;
0 F3 y* H4 X1 h7 d6 C2 I        }

3

主题

2

精华

469

积分

高级会员

Rank: 3Rank: 3

积分
469
发表于 9-13-2015 08:56 AM | 显示全部楼层
如果可以用extra space的话,可以merge吧

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-5-2015 07:38 AM | 显示全部楼层
感觉不难啊,不知道有没有理解错问题,下面是C++代码
) M0 I, @9 T5 l3 c! }9 R4 o& s" a' q4 s
  1. #include <iostream>4 V/ h) E2 d. V5 ^, \
  2. #include <algorithm>
    2 A7 o! U$ x# P2 K1 g) b
  3. using namespace std;
    ' m2 K; M; K0 o9 z3 e0 {

  4. / ~# e8 _7 T( e6 C3 ^$ a' w
  5. void arrange(vector<int>& arr)//aaa...bbb... => ababab...
    9 e) _1 S! n/ }1 ]6 f: \# T/ ^- t  M; f
  6. {) B4 d: I/ V  c/ J, e" e0 @' O- u: M
  7.         int n = arr.size();
    : y2 Y' q) x/ q. w1 u1 N
  8.         if(n < 4) return;6 ]$ F3 y1 a3 t! a6 G9 F6 W

  9. 1 N6 `; t; ~, ]; B
  10.         int i = 0, j = n/2;4 e: b" z' `+ D; z" _/ W0 F8 E1 u
  11.         for(; i < n; i += 2){6 F' {% J* [! n8 K6 Y4 ^
  12.                 if(arr【i】 == arr[i+1]){//both aa, swap second one with next b4 K2 A, ~- {/ x0 [) A/ a
  13.                         swap(arr[i+1], arr[j++]);4 |4 V/ l- A) M- c' `$ O
  14.                 }
    2 a! P2 H3 ~7 f
  15.         }/ ^0 {1 t3 C% {' |8 i6 K
  16. }( g# K. q! F0 n9 \3 N

  17. 5 f# W5 D" v4 ]( F* W
  18. void testArrange(vector<int>& arr)
    5 @3 k3 U6 I1 ~  Y/ b# B; y
  19. {: c- b# i* h& q: j5 c! |) {; }
  20.         cout << "before arrange:";
    0 X4 ]4 J2 n( v7 F
  21.         for(int x : arr) cout << " " << x;
    $ a& C1 q& l. y1 e6 q
  22.         cout << "\n";
    , z3 C4 q9 x- k1 G

  23. 8 w- x3 V1 _' Q. q% k- r! {9 p
  24.         arrange(arr);
    7 T. |: Q. `! B  N, h+ I0 ^& q2 |
  25.        
    ! ]1 r2 X" J& B5 y( H
  26.         cout << "after  arrange:";) R9 C" }$ V6 C% u/ o2 F' I* {
  27.         for(int x : arr) cout << " " << x;
    7 h8 F5 Z6 F4 w6 {3 ~7 M" u
  28.         cout << "\n\n";
    5 k2 z! j; ~7 l5 j; e, m3 f
  29. }
      N: m  N* x1 m
  30. / P# A$ I/ B+ [' h6 [2 |  A
  31. int main()
    & S' n( [7 [6 H; m7 W( h) U! W: p
  32. {9 F/ A. m- W" h/ D) x# W
  33.         vector<int> a = {2, 2, 3, 3};% C& `7 k5 A" j, g
  34.         vector<int> b = {2, 2, 2, 3, 3, 3};
    4 ?2 U1 k- A& A( o3 Z
  35.         vector<int> c = {2, 2, 2, 2, 3, 3, 3, 3};& _( j+ c8 E5 A: Y! ?

  36. 0 o) e3 }3 |( F& g! R6 a# e: R
  37.         testArrange(a);* r2 Z6 _0 R; k% }: f
  38.         testArrange(b);
    3 _; R! N$ W2 P" X; F: z$ s# ~
  39.         testArrange(c);
    ) y6 Q3 N) T/ S" s7 F1 v

  40. & O0 ]$ v. E$ ~7 ^$ `) e
  41.         return 0;. l$ M  ^5 }. C. B% ~; H$ c
  42. }
    . G6 h! Y5 S4 w! w' V9 a& T/ h
  43. /*
    * X' g4 V  z; U; N
  44. before arrange: 2 2 3 3( I/ _4 m! t1 @" {( `& Y  o
  45. after  arrange: 2 3 2 3; }" l) Q$ d0 \( {5 w# s: `
  46. ' ?, o- s/ n; m( m
  47. before arrange: 2 2 2 3 3 3
    # r0 u' ~/ g" T
  48. after  arrange: 2 3 2 3 2 3
    2 D. H8 _; M1 ?( e) h
  49. . t/ k3 z1 V( x1 W' b. D
  50. before arrange: 2 2 2 2 3 3 3 3
    2 A) ]* d0 L6 c9 N- ~' Y
  51. after  arrange: 2 3 2 3 2 3 2 3
    3 D& f  [# T2 b' b% u; K
  52. */
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表