C++LeetCode 165 버 전 비교 실현)

[LeetCode]165.Commare 버 전 Numbers 버 전 비교
Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Example 1:
Input: version1 = "0.1", version2 = "1.1"
Output: -1
Example 2:
Input: version1 = "1.0.1", version2 = "1"
Output: 1
Example 3:
Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1
Credits:
Special thanks to  @ts  for adding this problem and creating all test cases.
이 문 제 는 오랫동안 테스트 를 했 는데 인터넷 에서 다른 사람의 해법 을 찾 고 싶 지 않 았 다.왜냐하면 자신 이 풀 수 있 을 것 같 아서 고 쳐 서 마침내 통과 했다.다시 인터넷 에 접속 해서 검색 해 보 니 과연 다른 사람의 방법 과 다 르 고 작은 성취 감 을 느 꼈 다.제 생각 은 두 버 전 번호 에 포 함 된 소수점 개수 가 다 르 기 때문에 1 과 1.1.1 을 비교 할 수도 있 고 시작 에 0 이 무효 일 수도 있 습 니 다.예 를 들 어 01 과 1 은 같은 버 전 이 고 끝 에 0 이 무효 일 수도 있 습 니 다.예 를 들 어 1.0 과 1 도 같은 버 전 입 니 다.소수점 이 없 는 숫자 에 대해 서 는 기본적으로 마지막 이 소수점 이 고 버 전 번호 비교 의 핵심 사상 은 같은 위치의 숫자 비교 이다.예 를 들 어 제목 이 준 예,1.2 와 13.37 을 비교 하면 우 리 는 모두 1 과 13 을 비교 해 야 한 다 는 것 을 알 고 있다.13 대 1 이 크기 때문에 뒤의 것 은 더 이상 비교 할 필요 가 없다.예 를 들 어 1.1 과 1.2 를 비교 하면 앞 은 모두 1 이다.소수점 뒤의 숫자 를 비교 합 니 다.그러면 알고리즘 은 매번 같은 위치의 소수점 을 꺼 내기 전의 모든 문 자 를 숫자 로 비교 하고 다 르 면 바로 답 을 얻 을 수 있 으 며 같 으 면 아래로 내 려 가 야 합 니 다.만약 한 숫자 가 소수점 이 없다 면,기본적으로 0 으로 꺼 내 고,다른 숫자 와 비교 하면,끝 이 0 이 되 지 않 는 상황 도 해결 할 수 있다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n1 = version1.size(), n2 = version2.size();
        int i = 0, j = 0, d1 = 0, d2 = 0;
        string v1, v2;
        while (i < n1 || j < n2) {
            while (i < n1 && version1[i] != '.') {
                v1.push_back(version1[i++]);
            }
            d1 = atoi(v1.c_str());
            while (j < n2 && version2[j] != '.') {
                v2.push_back(version2[j++]);
            }
            d2 = atoi(v2.c_str());
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            v1.clear(); v2.clear();
            ++i; ++j;
        }
        return 0;
    }
};
물론 우 리 는 문자열 을 정형 으로 바 꾸 는 atoi 함 수 를 사용 하지 않 아 도 됩 니 다.우 리 는 한 사람의 누적 을 사용 하여 다음 코드 에 참가 할 수 있 습 니 다.
해법 2:

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n1 = version1.size(), n2 = version2.size();
        int i = 0, j = 0, d1 = 0, d2 = 0;
        while (i < n1 || j < n2) {
            while (i < n1 && version1[i] != '.') {
                d1 = d1 * 10 + version1[i++] - '0';
            }
            while (j < n2 && version2[j] != '.') {
                d2 = d2 * 10 + version2[j++] - '0';
            }
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            d1 = d2 = 0;
            ++i; ++j;
        }
        return 0;
    }
};
이 문 제 는 버 전 번 호 를''로 나 누 어야 하기 때문에 우 리 는 강력 한 문자 직렬 stringstream 기능 을 빌려 세그먼트 와 정수 로 전환 할 수 있 습 니 다.이런 방법 으로 쓴 코드 는 매우 간결 합 니 다.다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    int compareVersion(string version1, string version2) {
        istringstream v1(version1 + "."), v2(version2 + ".");
        int d1 = 0, d2 = 0;
        char dot = '.';
        while (v1.good() || v2.good()) {
            if (v1.good()) v1 >> d1 >> dot;
            if (v2.good()) v2 >> d2 >> dot;
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            d1 = d2 = 0;
        }
        return 0;
    }
};
마지막 으로 C 언어의 문자열 포인터 로 이 루어 지 는 방법 을 살 펴 보 겠 습 니 다.이 방법의 관건 은 문자열 을 긴 정형 으로 바 꾸 는 strtol 함수 입 니 다.이 함수 에 대한 용법 은 제 다른 블 로 그 를 참조 할 수 있 습 니 다strtol 함수 용법참조 코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int res = 0;
        char *v1 = (char*)version1.c_str(), *v2 = (char*)version2.c_str();
        while (res == 0 && (*v1 != '\0' || *v2 != '\0')) {
            long d1 = *v1 == '\0' ? 0 : strtol(v1, &v1, 10);
            long d2 = *v2 == '\0' ? 0 : strtol(v2, &v2, 10);
            if (d1 > d2) return 1;
            else if (d1 < d2) return -1;
            else {
                if (*v1 != '\0') ++v1;
                if (*v2 != '\0') ++v2;
            }
        }
        return res;
    }
};
유사 한 제목:
First Bad Version
참고 자료:
https://leetcode.com/problems/compare-version-numbers/discuss/?orderBy=most_votes
https://leetcode.com/problems/compare-version-numbers/discuss/50774/Accepted-small-Java-solution.
https://leetcode.com/problems/compare-version-numbers/discuss/50788/My-JAVA-solution-without-split
https://leetcode.com/problems/compare-version-numbers/discuss/50804/10-line-concise-solution.-(C%2B%2B)
https://leetcode.com/problems/compare-version-numbers/discuss/50767/My-2ms-easy-solution-with-CC%2B%2B
C++구현 LeetCode 165.버 전 비교)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 버 전 비교 내용 은 저희 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 읽 어 주시 기 바 랍 니 다.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!

좋은 웹페이지 즐겨찾기