betazold
Vi Veri Veniversum Vivus Vici
Дан массив длины n из нулей и единиц. Найдите в нём подмассив макисмальной длины, в котором количество единиц равно количеству нулей. Ограничения: O(n) по времени и O(n) по дополнительной памяти.

  1. function getLongest(s) {
  2. var begin = 0,
  3. finish = 0,
  4. len = 0,
  5. b = {},
  6. sum = 0,
  7. i,
  8. n = s.length;
  9. prefix,
  10. padding = '',
  11. cursor;
  12. for (i = -n; i < n; i++) {
  13. b[i] = null;
  14. }
  15. b[0] = -1;
  16. for (i = 0; i < n; i++) {
  17. sum += (s[i] == 1 ? 1 : -1);
  18. if (b[sum] == null) {
  19. b[sum] = i;
  20. console.log('for sum = ' + sum + ' index = ' + i);
  21. } else {
  22. console.log('for sum = ' + sum + ' at index = ' + i + ' b = ' + b[sum]);
  23. if (len < i - b[sum]) {
  24. begin = b[sum] + 1;
  25. finish = i;
  26. len = i - b[sum];
  27. console.log('begin = ' + begin + ' finish = ' + finish + ' len = ' + len);
  28. }
  29. }
  30. }
  31. if (begin === finish) {
  32. console.log('No subarray');
  33. return;
  34. }
  35. prefix = '['+begin+':'+finish+'] = ';
  36. for (i = 0; i < prefix.length + s.length; i++) {
  37. cursor = i - prefix.length;
  38. padding += (cursor === begin || cursor === finish) ? '^' : ' ';
  39. }
  40. console.log(prefix + s);
  41. console.log(padding)
  42. console.log(padding.substr(0, prefix.length + begin) + s.substr(begin, finish - begin + 1));
  43. }
  44. (function(tests) {
  45. var i, j, s, len;
  46. for (i = 0; i < tests; i++) {
  47. len = Math.round(Math.random() * 10) + 1;
  48. s = '';
  49. for (j = 0; j < len; j++) {
  50. s += Math.round(Math.random());
  51. }
  52. console.log(s);
  53. getLongest(s);
  54. }
  55. })(3);

@темы: Algorithms, JavaScript, PHP