leetcode 160(linked list), 2006(caching), 1850(permutation, 구현)

160 https://leetcode.com/problems/intersection-of-two-linked-lists/
easy난이도인데 맨 아래의 제한조건이 O(n) 시간복잡도, O(1) 공간복잡도이다. 이거 생각하면서 풀려면 어렵다. 예제들을 살펴보면 교차로부터는 값이 전부 동일한걸 알수있다.
input a,b중에 길이가 긴 링크드 리스트를 짧은 링스크 리스트랑 길이를 맞춰줄만큼 앞으로 전진해서 탐색을 시작한다. 둘다 똑같이 한칸씩 전진하면서, 값이 같으면 그걸 리턴해주고, 같은 값이 없으면 아무것도 리턴해주지 않으면 된다.

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        len_a, len_b = 0, 0
        t_headA, t_headB = headA, headB
        while t_headA:
            len_a += 1
            t_headA = t_headA.next
        while t_headB:
            len_b += 1
            t_headB = t_headB.next
        change_flag = False
        if len_a < len_b:
            change_flag = True
            len_a, len_b = len_b, len_a
            headA, headB = headB, headA
        for i in xrange(len_a - len_b):
            headA = headA.next
        for i in xrange(len_b):
            if headA is headB:
                if change_flag:
                    headA, headB = headB, headA
                return headA
            headA = headA.next
            headB = headB.next
        
        if change_flag:
            headA, headB = headB, headA

근데 아래 해답을 보자..
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
소스코드를 보고도 잘 이해가 안갔는데 첫번째 댓글로 누가 그림으로 그려줬다. 진심 천재인듯;

2006 https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/
easy난이도인데 단순하게 반복문 두번 써서 O(n^2)으로 풀지 말고 O(n)으로 해보려고 생각해보면 괜찮은 문제 같다. i < j가 전제조건이므로 이전에 나온 값들을 딕셔너리에 저장해두고 |현재값 - k| 인 값이 이전에 있었는지, 몇번 존재했었는지 딕셔너리에서 찾아서 그만큼 더해준다.
요 글에서 2 sum문제를 풀었었는데, 이거랑 비슷한 컨셉이다.

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        value_before = {}
        ret = 0
        for num in nums:
            if num - k in value_before:
                ret += value_before[num - k]
            if num + k in value_before:
                ret += value_before[num + k]
            value_before[num] = value_before.get(num, 0) + 1
        
        return ret

1850 https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/
permutation을 먼저 구현하는데 이전에 써놨던 글을 그대로 가져왔다.
그리고 바꾸는 부분을 구현해야하는데, 달라지는 부분 이후의 문자의 인덱스를 찾은 후에 왼쪽에서 오른쪽으로 가면서가 아닌, 오른쪽에서 왼쪽으로 가면서 swap해준다.
11112를 예시로 보면 쉬운데, 11112에서 21111을 만들려는데 왼쪽에서 오른쪽으로 가면서 swap해주면 21111을 만들수가 없다.

class Solution(object):
    def getMinSwaps(self, num, k):
        #num = "00123"
        #k = 1
        
        def nextPermutation(nums):
            change_index = -1
            for i in xrange(len(nums)-1, 0, -1):
                if nums[i] > nums[i-1]:
                    change_index = i-1
                    break
            if change_index == -1:
                nums[:] = nums[::-1]
                return nums

            for i in xrange(len(nums)-1, -1, -1):
                if nums[i] > nums[change_index]:
                    nums[change_index], nums[i] = nums[i], nums[change_index]
                    nums[:] = nums[:change_index+1] + nums[change_index+1:][::-1]
                    return nums
                
        num = list(num)
        perm = num[:]
        for i in xrange(k):
            perm = nextPermutation(perm)
        
        ret = 0
        i = 0
        while i < len(num):
            if num[i] != perm[i]:
                destination_index = num.index(perm[i], i+1)
                #print 'i =', i, destination_index
                j = destination_index - 1
                while i <= j:
                    #print 'change',j,j+1
                    num[j], num[j+1] = num[j+1], num[j]
                    j -= 1
                    ret += 1
                #print 'num =',num
            i += 1
                    
        return ret