{"id":5528,"date":"2019-09-07T21:12:57","date_gmt":"2019-09-08T04:12:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5528"},"modified":"2019-09-07T21:13:31","modified_gmt":"2019-09-08T04:13:31","slug":"leetcode-1184-distance-between-bus-stops","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1184-distance-between-bus-stops\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1184. Distance Between Bus Stops"},"content":{"rendered":"\n

A bus has n<\/code> stops numbered from 0<\/code> to n - 1<\/code> that form a circle. We know the distance between all pairs of neighboring stops where distance[i]<\/code> is the distance between the stops number i<\/code> and (i + 1) % n<\/code>.<\/p>\n\n\n\n

The bus goes along both directions i.e. clockwise and counterclockwise.<\/p>\n\n\n\n

Return the shortest distance between the given start<\/code> and destination<\/code> stops.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> distance = [1,2,3,4], start = 0, destination = 1\nOutput:<\/strong> 1\nExplanation:<\/strong> Distance between 0 and 1 is 1 or 9, minimum is 1.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> distance = [1,2,3,4], start = 0, destination = 2\nOutput:<\/strong> 3\nExplanation:<\/strong> Distance between 0 and 2 is 3 or 7, minimum is 3.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> distance = [1,2,3,4], start = 0, destination = 3\nOutput:<\/strong> 4\nExplanation:<\/strong> Distance between 0 and 3 is 6 or 4, minimum is 4.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= 10^4<\/code><\/li>
  • distance.length == n<\/code><\/li>
  • 0 <= start, destination < n<\/code><\/li>
  • 0 <= distance[i] <= 10^4<\/code><\/li><\/ul>\n\n\n\n
    Solution: Summation<\/strong><\/p>\n\n\n\n
    1. compute the total sum<\/li>
    2. compute the sum from s to d, c<\/li>
    3. ans = min(c, sum – c)<\/li><\/ol>\n\n\n\n
      Time complexity: O(d-s)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int distanceBetweenBusStops(vector& ds, int s, int d) {    \n    if (s > d) swap(s, d);\n    int sum = accumulate(begin(ds), end(ds), 0);\n    int d1 = accumulate(begin(ds) + s, begin(ds) + d, 0);\n    return min(d1, sum - d1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      A bus has n stops numbered from 0 to n – 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,77,62],"class_list":["post-5528","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-graph","tag-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5528","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5528"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5528\/revisions"}],"predecessor-version":[{"id":5530,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5528\/revisions\/5530"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5528"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5528"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5528"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}