找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

[面经总结] 数组中和不超过某个数的最大连续区间

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
 楼主| 发表于 2-3-2015 02:03 AM | 显示全部楼层
kimi0428 发表于 12-4-2014 12:08 AM
  B" F- o) S$ DLZ, MaxRange1这个function会死循环. arr: [1, 2, 5, 3], budget = 9.

9 h+ f0 `- ~0 N7 rThanks.
' E1 |# q( D4 M0 o7 D4 F* R+ PI have corrected in the bottom. The thread itself is not editable.

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
 楼主| 发表于 2-3-2015 02:10 AM | 显示全部楼层
Correct the bug found by kimi0428. Hope it works fine now.
1 ?5 z6 [. l) {6 Z2 e$ x8 m$ O/ ]$ o' T1 q3 |. I
  1. int MaxRange1(const vector<int>& arr, int budget) {
      S  U  ?: k2 J
  2.     int range = 0;
      M2 f; ?8 t  B8 G, ?  o
  3.     int a, b;: w! C- O3 v) J# S
  4.     a = b = 0;
    + F6 `; Y' c5 u. S4 g
  5.     int sum = 0;
    7 A. a0 v6 k5 r6 _
  6.     int n = arr.size();
      W" B" I0 c2 M7 s
  7.     while (true) {
    / Q* H4 g: ?9 M+ T
  8.         while (b<n && sum + arr[b] <= budget) {
    - J; L% Y; a$ p: L
  9.             sum += arr[b];
    5 T7 r/ P. m2 U! M$ g
  10.             ++b;# `/ o+ J+ s$ d' N+ o
  11.         }
    / H! |6 g) Q' o' D/ F+ X! u
  12.         range = std::max(range, b-a);' W; \% A7 E3 L9 M' z4 O
  13.         if (b<n) sum += arr[b];
    + _( x( @# n3 Z
  14.         else break;( B& U. w9 t- q1 Z4 U! _5 f* a' m
  15.         while (a<n && sum > budget) {4 p: T; g7 r0 V, w3 b
  16.             sum -= arr[a];8 @. |$ z. `) [0 ~
  17.             ++a;2 ~; a9 H- u1 n# T# g' x0 R
  18.         }; r! k2 c5 y7 T$ p. p: [, r2 L
  19.     }1 v: Y: t' Z  C1 {8 k
  20.     return range;
    $ T( ?% o8 J! k2 R$ g7 u1 s
  21. }
复制代码

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 2-3-2015 04:35 AM | 显示全部楼层
不错的题目呀,cp啥时候帮我们做成OJ的问题?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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