leetcode 1995, 2078(two pointer), 744(이분 탐색)

1995 https://leetcode.com/problems/count-special-quadruplets/
easy문제인데 O(n^2)의 시간복잡도로 풀려고 생각해보자. a+b+c=d가 나와야 하는데 c를 넘기면 a+b=d-c로 만들수 있다. 그리고 요 두파트를 각각 계산하면 된다.
https://leetcode.com/problems/count-special-quadruplets/discuss/1446988/JavaC%2B%2BPython3-Real-O(n2)-solution

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        # a + b = d - c
        d = {}
        ret = 0
        n = len(nums)
        for i in range(n-1, -1, -1):
            for j in range(i-1, -1, -1):
                v = nums[j] + nums[i]  # a + b
                if v in d:
                    ret += d[v]
            for j in range(i, n):
                v = nums[j] - nums[i]  # d - c
                if v in d:
                    d[v] += 1
                else:
                    d[v] = 1
                    
        return ret

2078 https://leetcode.com/problems/two-furthest-houses-with-different-colors/
투 포인터로 양쪽에서 좁혀가면서 두개의 숫자가 다를경우 그값이 답이다. 근데 양쪽의 숫자가 같을경우 왼쪽을 증가시킬지 오른쪽을 줄일지 알수없으므로 한번은 오른쪽에서 줄이고, 한번은 왼쪽에서 줄인다음 최댓값을 리턴한다.

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        ret = 0
        l,r = 0, len(colors)-1
        while l < r:
            if colors[l] == colors[r]:
                r -= 1
            if colors[l] != colors[r]:
                ret = r - l
                break
        l,r = 0, len(colors)-1
        while l < r:
            if colors[l] == colors[r]:
                l += 1
            if colors[l] != colors[r]:
                ret = max(ret, r - l)
                break
        return ret

744 https://leetcode.com/problems/find-smallest-letter-greater-than-target/

이분 탐색으로 푼다. 답은 간단한데 문제 예시가 살짝 이해가 안가고 예외케이스가 좀 있다.

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        l,r = 0, len(letters)-1
        if not letters[l] <= target < letters[r]:  # target이 범위안에 있지 않은경우 첫번째 글자 리턴
            return letters[0]
        
        while l <= r:
            mid = (l+r)//2
            if letters[mid] <= target:  # 같은 숫자가 들어가 있는 경우도 있으므로 그 경우에는 오른쪽으로 밀어줌.
                l = mid+1
            else:
                r = mid-1
        return letters[l]