找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3500|回复: 5
收起左侧

[精选面经题目] 【G家电面】详细题解

[复制链接]

84

主题

32

精华

1278

积分

顶级会员

Rank: 6Rank: 6

积分
1278

活跃会员热心会员最佳新人精华帖之王

发表于 2-17-2016 12:10 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 2-17-2016 12:56 AM 编辑
; x6 [% X# x* k! n' K( S  ^+ E1 Y7 @" |+ j' A! {3 D0 P
原题传送门5 k0 b/ P% b/ o2 Q

+ b" N( w8 e7 z0 }% `7 f1. 把string数组合并成一个string,并且能复原!' b$ l8 @4 c% w! a" x$ F* _
解法:这个题说白了就是简单的序列化和反序列化。当然业界业界会有很多的序列化和反序列化方法。这里就只用最简单的类似于压缩的来弄。) f: D( `! w7 c
利用开头的32位来记录string的长度,然后这里写了int和string的互转函数。" E9 _4 }1 C$ a+ v8 g$ F1 Q: f
然后又写了一个编码和解码函数。
% m1 y( Y$ J  l& k0 n) V' T
  1. 6 {4 ]* G) T2 T- h/ {
  2. string itostr(int num) {
    " O* c! ~4 [  ?) t% A. z
  3.     string res(4,0);
    % J+ y7 ]+ C1 y$ M$ a( P
  4.     int i = 3;
    : y; ~. M: P+ _( C  r
  5.     while (i >= 0 && num != 0) {7 n7 z/ f7 i( S) F7 G
  6.         res[i--] = num % 256;* s) K0 q) _0 W- W& f$ e
  7.         num = num / 256;
      J/ ]  @' D$ x* a4 [
  8.     }
    5 V' N; i( T2 z( Z
  9.     return res;
    . t! f- s6 Y7 d9 v/ a
  10. }9 s, ]2 `; T: P3 o' ?9 ^+ k
  11. int strtoi(string str) {6 M9 F" ]1 [9 \: L' C
  12.     int res = 0, i = 0;
    9 W3 G! C- p; i0 l( a9 l! w
  13.     while (i < 4) {/ g3 N4 {3 B" F. h6 [, m& t, m
  14.         res = res*256 + (int)(unsigned char)str[i++];
    4 F5 G1 H( W( b! [9 K; t1 v
  15.     }
    * }% z5 R6 m# \2 F' C
  16.     return res;
    # l# i9 b3 r  Z) h
  17. }( Q, [* @8 P1 S: q: {7 o/ r/ i
  18. string encode(vector<string> src) {
    * W. G5 S, M' x' f2 a
  19.     if (src.empty()) return \"\";
    " s% E/ G6 e. ~% m6 x$ [; j
  20.     string res;
    $ i! W$ p5 B3 _9 O# O: G
  21.     for (int i = 0; i < src.size(); ++i) {
    & ^+ U% F% ?/ u! F, T
  22.         res += itostr(src【i】.length()) + src【i】;7 M% U5 o" j3 j7 e$ L* d! d
  23.     }
    5 M( |7 z4 a. b# v1 k- C
  24.     return res;
    0 D& b; q4 \0 [" J* F
  25. }
    % a! N  z, g  l, @
  26. vector<string> decode(string src) {
    9 s( r, x; \9 Y. }' W' g
  27.     std::vector<string> res;
    3 H8 H0 }" l* {# ^% y
  28.     int i = 0;* G2 A4 w! }' Q5 u
  29.     while (i + 4 <= src.size()) {
    8 y0 [! e0 L' c; f6 ~& J3 J* K
  30.         int num = strtoi(src.substr(i,4));
    ' C% U) J, S4 g- |6 d5 {# o
  31.         string now = src.substr(i+4, num);
    7 b3 E+ x% c) O, b/ I+ n# W6 e
  32.         res.push_back(now);, V# R, i8 C% s3 M8 s
  33.         i += 4 + num;+ {) C4 w2 c# v$ }) L/ Y) X. Z% k
  34.     }! k1 z7 V9 x# i3 g9 ^
  35.     return res;
    % A, b1 E3 Q$ f. Y4 _' P! g4 ]' P, g
  36. }
    / a5 E2 Y" ?, v- @
  37. int main(int argc, char const *argv[])
    6 U3 F" q6 I7 {* Y" ^
  38. {
    $ W, }3 P0 u+ N' i8 i0 o) i
  39.     vector<string> src;
    ' u- X2 B5 n( i( n5 J8 {9 P0 m
  40.     src.push_back(\"hello\");) ?9 O8 M* B8 j. L# L" l$ v
  41.     src.push_back(\"world\");
    " X# f; h% J2 B# i
  42.     src.push_back(\"hell\");
    ) i7 n. c2 z: }% A7 D
  43.     string res = encode(src);, t" ^# G3 I. Q, R* N( c$ K
  44.     vector<string> ans = decode(res);& G0 ~8 ~+ S( a$ O9 K0 f
  45.     for (int i = 0; i < ans.size(); ++i)
    9 u/ C) M* m4 w0 Q
  46.         cout << ans【i】 << \" \";: X( s$ a/ L& ~  \) H) P
  47.     cout << endl;
    # K/ u+ M" B) D0 \3 x
  48.         return 0;8 y2 {( ^3 Y9 W. X$ C
  49. }5 ?+ l2 ^# k/ x- z
复制代码

: Q% K. i8 m3 q; G( ?+ t2. given k, n, find all lists of k positive integers which sum up to n
' |! g1 y% s: _; F解法:这题就是简单的dfs,这里的k个数可能是重复的也有可能是不重复的,我不知道原题的到底是要重复的还是不重复的。这里就当成重复的来做了。- B* L- o4 @( A# |1 \$ i; B
如果重复的话只要k<=n,那么肯定会有解的。
; `5 h2 Q$ ^: m0 Y; p如果不允许重复的话,那就不一定有解了。. `. W) D2 Q) g: ~. Z
  1. 2 ?& {. Y$ a# ]# o" ?5 w. m
  2. void findKNRe(vector<vector<int> > &res, int k, int n, vector<int> &path) {
      |5 ^& o* D, E, R: Y- O: P
  3.     if (path.size() == k && n == 0) {
    6 p" n, |: F  t8 z* v
  4.         res.push_back(path);1 G0 }: a2 s2 i& X  `1 K$ J* @0 Y# F
  5.         return;
    3 c& w* i, r. B) r8 _* D
  6.     }, ~) K8 r1 F' h8 {( O
  7.     int i = path.empty() ? 1 : path.back();' e% n4 A8 l6 k
  8.     for (; i <= n; ++i) {  @( B2 g8 Y5 b; T3 M
  9.         path.push_back(i);
    7 N% B" a* ]( t2 W/ w/ r, j
  10.         findKNRe(res, k, n - i, path);/ B; C/ {- n: }" O9 ^" T9 x
  11.         path.pop_back();
    # Z; j+ E5 Z% ~  V3 ^
  12.     }. Q# M# ^  \) k: G" b
  13. }
    + ]4 a6 x. Q7 u& d6 P4 U
  14. vector<vector<int> > findKN(int k, int n) {
    ' L( h- H& g0 d$ M* B& @6 V9 p+ Y
  15.     vector<vector<int> > res;1 T1 l5 h0 a( Y
  16.     if (k > n) return res;
    ! D9 z( O$ \7 S# u6 Y& P: o
  17.     if (k == n) {
    ) Y" c" G' U$ }- C) }) j
  18.         res.push_back(vector<int>(n, 1));7 k) X% D$ \# p4 A; t! p
  19.         return res;! d$ a& [/ f7 J+ {' W# Z
  20.     }" U! Z4 u* t2 K
  21.     vector<int> path;3 o& s) z1 {3 M6 M! L
  22.     findKNRe(res, k, n, path);( Q# r+ y  |" a7 o$ T
  23.     return res;
      n! z5 H6 O- O( p, I
  24. }
    2 a& C5 q' z" W' K, x
  25. int main(int argc, char const *argv[])
    4 g9 K& P% n% B# c* f4 b$ F
  26. {
    & j5 _% k6 ?( E2 r
  27.         cout << \"hello world!\" << endl;
    " f  b* P# W; a8 |% Q$ F
  28.     vector<vector<int> > res = findKN(4, 8);
      y2 g5 w4 V# W2 a4 c* |- [, g
  29.     for (int i = 0; i < res.size(); ++i) {
    5 ]% B/ {. M( u0 _' c' v$ N
  30.         for (int j = 0; j < res【i】.size(); j++) {
    " E5 l& U! V, F  D# `
  31.             cout << res【i】[j] << \" \";9 b4 ], d$ r* U
  32.         }# u6 ~+ N6 i1 B1 ^' W
  33.         cout << endl;5 B6 G3 |: F/ s  b
  34.     }3 g- b2 Z, |8 ^: [2 T
  35.     cout << endl;) O/ \4 e, W0 O4 N. c
  36.         return 0;
    $ }$ t/ B% N2 _) x& c* k1 p% E
  37. }/ L; |; V5 `4 m0 Y. H

  38. 7 A1 c! O) h4 |
复制代码

6 p2 |8 l2 D9 F3 b% p- y. O
/ ~5 v3 G( \9 p4 q7 m来源: 【G家电面】详细题解

本帖被以下淘专辑推荐:

  • · Google|主题: 3, 订阅: 0

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 2-17-2016 04:52 PM | 显示全部楼层
感谢分享~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

10

主题

0

精华

132

积分

资深会员

Rank: 2

积分
132
发表于 2-19-2016 12:53 PM | 显示全部楼层
楼主好人,帮顶!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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