C++LeetCode 구현(134.주유소 문제)

[LeetCode]134.주유소 문제
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
이 턴 주유 문 제 는 어렵 지 않 아 그 원 리 를 납득 하기 만 하면 간단 하 다.우 리 는 먼저 전체 고 리 를 걸 을 수 있 는 전 제 는 gas 의 총량 이 cost 의 총량 보다 커 야 출발점 이 존재 한 다 는 것 을 알 아야 한다.시작 점 start=0 을 설정 하고 여기 서 출발 하면 현재 의 gas 값 이 cost 값 보다 크 면 계속 전진 할 수 있 습 니 다.이때 다음 사이트 에 도착 하면 나머지 gas 에 현재 의 gas 를 더 해서 cost 를 빼 고 0 보다 크 면 계속 전진 할 수 있 습 니 다.어떤 사이트 에 도 착 했 을 때 이 값 이 0 보다 작 으 면 출발점 에서 이 점 사이 의 어떤 점 도 출발점 으로 할 수 없다 는 것 을 설명 하고 출발점 을 다음 점 으로 설정 하여 계속 옮 겨 다 닌 다.전체 링 을 옮 겨 다 닐 때 현재 저 장 된 시작 점 은 원 하 는 것 입 니 다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, sum = 0, start = 0;
        for (int i = 0; i < gas.size(); ++i) {
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
        }
        return (total < 0) ? -1 : start;
    }
};

우 리 는 또한 뒤에서 앞으로 옮 겨 다 닐 수 있 습 니 다.하나의 변수 mx 로 나타 난 잉여 유량 의 최대 치 를 기록 할 수 있 습 니 다.totalk 은 현재 잉여 유량 의 값 을 기록 하고 start 는 출발점 의 위 치 를 기록 할 수 있 습 니 다.totalk 이 mx 보다 클 때 현재 위 치 를 기점 으로 start 를 업데이트 하고 mx 를 업데이트 할 수 있 음 을 설명 합 니 다.왜?우 리 는 매번 totalk 에 현재 위치의 유량 을 더 해서 소 모 를 줄인다.만약 에 이 차이 가 0 보다 크 면 현재 위 치 를 기점 으로 할 수 있다 는 것 을 의미한다.현재 위치 에서 끝까지 유량 이 부족 한 상황 이 나타 나 지 않 기 때문이다.만약 에 차이 가 0 보다 적 으 면 현재 위치 가 출발점 이 라면 유량 이 부족 하고 전 과정 을 다 갈 수 없다 는 것 을 의미한다.그래서 시작 위치 start 를 업데이트 하지 않 습 니 다.마지막 으로 끝 난 후에 우 리 는 totooa 가 0 보다 큰 지 여 부 를 보 았 습 니 다.만약 에 0 보다 작 으 면 그 어떠한 출발점 도 전 과정 을 완성 할 수 없다 는 것 을 설명 합 니 다.총 유량 이 부족 하기 때문에 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, mx = -1, start = 0;
        for (int i = gas.size() - 1; i >= 0; --i) {
            total += gas[i] - cost[i];
            if (total > mx) {
                start = i;
                mx = total;
            }
        }
        return (total < 0) ? -1 : start;
    }
};

유사 한 제목:
Reaching Points
Transform to Chessboard
Cheapest Flights Within K Stops
참고 자료:
https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas.
https://leetcode.com/problems/gas-station/discuss/42656/8ms-simple-O(n)-c++-solution
C++실현 LeetCode(134.주유소 문제)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++실현 주유소 문제 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!