8.8 - medium 요약 31

드디어 마지막 편!오늘 위치까지 309개의 medium 문제를 모두 총결산을 마쳤습니다. 총결산의 총결산 한 편이 모자라서 내일 쓰겠습니다.8.10 Hard를 시작하는데 희망도 하루에 열 문제입니다. 그러면 8월 20일에 완성할 수 있습니다.
646. Maximum Length of Pair Chain: LIS와 유사한 dp, 1차원 dp는 비교적 간단하다 647.Palindromic Substrings: 각 값에 대해 중간에서 양쪽으로 확장하면 됩니다. 648.Replace Words: Trie 하나로 649.Dota2 Senate: 게임을 하는 문제는 모두 먼저 기억화 검색을 해 보세요. 이 문제는 안 될 것 같아요. 경기를 할 때 기본적인 생각은 알아요. 항상 자기가 가장 뒤에 있는 첫 번째 상대방의 선수를 떨어뜨리지만 Recursion을 사용할 때 TLE를 떨어뜨리는 거예요.이런 순환 비교 문제는 deque로 표시하는 것을 기억해라. 당시에는 index로 표시하였는데, 그야말로 죽을 지경이었다.We have people = [int, int] representing how many people are in the queue, and bans = [int, int] representing how many "floating"bans there are. When we meet a person, if there is a floating ban waiting for them, then they are banned and we skip them. Eventually, the queue will just have one type of person, which is when we break.

class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        A = collections.deque()
        people = [0, 0]
        bans = [0, 0]

        for person in senate:
            x = person == 'R'
            people[x] += 1
            A.append(x) # A is a list of 0 1

        while all(people): # 
            x = A.popleft()
            people[x] -= 1
            if bans[x]:
                bans[x] -= 1
            else:
                bans[x^1] += 1
                A.append(x)
                people[x] += 1

        return "Radiant" if people[1] else "Dire"

650.2 Keys Keyboard: dp 문제, dp[i]=min(dp[i], dp[j]+(i/j-1)+1)는 현재 작업에 대해 i/j-1은 몇 개의 j를 더 넣어야 하는지를 나타낸다. 예를 들어 j=2 i=6이면 6/2-1 = 2 두 번의 paste가 필요하고 한 번의 copy 651.4 Keys Keyboard: 생각은 매우 간단하다. 바로 모든 값에 대해 가능한 형성 방식은 dp[i]=dp[b]*(i-b-1)이다. 즉, dp[b]가 형성된 후에 i까지 ctr-v를 눌러야 한다.특수한 상황은 앞의 여섯 개의 값이니 제거하면 된다. 사실 이것은 계단을 오르는 것과 매우 유사하다.652. Find Duplicate Subtrees: 이 문제는 경연 대회에서도 풀지 못했습니다. 사실divide and conquer의 과정에서 모든 node에 대해hash를 업데이트하고 이hash는subtree의 정보를 포함해야 합니다. 654.Maximum Binary Tree: 전형적인divide and conquer의 제목, 경연에서 나온 것은 여기서 하지 않습니다.655. Print Binary Tree: 이 문제도 경연에서 나온 문제인데 먼저 공간을 낸 다음에 preorder로 채워주세요.