找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: ridershen
收起左侧

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

  [复制链接]

8

主题

7

精华

475

积分

高级会员

Rank: 3Rank: 3

积分
475
 楼主| 发表于 2-3-2015 02:03 AM | 显示全部楼层
kimi0428 发表于 12-4-2014 12:08 AM
! T% F0 Y# ^3 j1 A* J% x9 T4 l4 LLZ, MaxRange1这个function会死循环. arr: [1, 2, 5, 3], budget = 9.
; g( o! s8 B2 o% T9 w
Thanks.; x; z2 g' M9 W
I 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.9 a: W# u: X2 G, g

) v  U6 y/ K  l4 t' R
  1. int MaxRange1(const vector<int>& arr, int budget) {2 h- [5 u( r! P. L2 L" t
  2.     int range = 0;
    / L& ^+ T) w& n' r8 w- I
  3.     int a, b;. b3 U: \! l) s2 Y3 ^9 R9 Z- W9 Z/ i
  4.     a = b = 0;& W8 ~- y! a* V- v- m/ f$ U
  5.     int sum = 0;: }5 v; y3 r+ ^0 ?+ [7 t
  6.     int n = arr.size();
    ( J* w( _/ N4 B* @5 V
  7.     while (true) {
    ' T( ~5 ?& L. [# k" f
  8.         while (b<n && sum + arr[b] <= budget) {
    & i; ~7 t2 m/ G- K, j% C, L4 l
  9.             sum += arr[b];/ Y! [/ x/ s  P$ G# R4 {; c6 ~  J" U
  10.             ++b;3 W) V8 f% E, |/ `! k2 O- \4 q
  11.         }
    , j5 [4 I, u2 ?- h. H$ I
  12.         range = std::max(range, b-a);
    9 R4 A7 F/ G& x% a! h  F/ a" q7 I- M
  13.         if (b<n) sum += arr[b];8 I) L8 ?/ r# {  G
  14.         else break;
    ! Q* ^! Q" W0 T/ u: b' W3 H: J- G+ }" i
  15.         while (a<n && sum > budget) {
    ( D% Z1 R: G( ?" V' h, X
  16.             sum -= arr[a];
    9 W- g1 z5 ~- D, k( `
  17.             ++a;" x8 ?  A1 a. |* V; Z9 @3 X
  18.         }
    " A9 ]5 i6 o3 h# R/ e1 A
  19.     }/ e# Y# I/ |  P  i, W
  20.     return range;
    7 b" }% g" X4 t- P. r: Q
  21. }
复制代码

0

主题

0

精华

0

积分

新米人

Rank: 1

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

本版积分规则

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