763. Partition Labels

https://leetcode.com/problems/partition-labels/

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

最好的情况，肯定是每个字符分为一组。但如果同个字母在字符串中出现两次以上，那么从第一次到最后一次之前的字符串，会被分为同一组。假设把S[i:j]划为一个分组，其中的字母在之后都不再出现，那它就能成为一个分组。算法非常简单，时间复杂度为$O(N)$。

def partitionLabels(self, S: str) -> List[int]:
	# partition each letter as a part at first
	# the last place of appearance of each word
	appear = {}
	for i in range(len(S)-1, -1, -1):
	    if S[i] not in appear:
	        appear[S[i]] = i
	# the current part is S[start:end+1]
	start, end = 0, 0
	rtn = []
	for i, w in enumerate(S):
	    end = max(end, appear[S[i]])
	    if i == end:
	        rtn.append(end-start+1)
	        start, end = i+1, i+1
	return rtn

921. Minimum Add to Make Parentheses Valid

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, or
  • It can be written as AB (A concatenated with B), where A and Bare valid strings, or
  • It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

非常经典的题目。从左到右扫描字符串，如果碰到的)多于(，那么必须在左边补上若干个(。如果(多于)则不用，因为可能右边没扫到的地方有)来匹配。扫到最后，如果(的数目更多，则需要在右边补上对应数量的)，使得括号数目相等。

def minAddToMakeValid(self, S: str) -> int:
    left = 0
    ans = 0
    for each in S:
        if each == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                ans += 1
    return ans + left

406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

要做出这道题，需要认识到以下两个事实：

  1. 假如列表里最小的身高是h，且只有一个人身高是h。那么他排在第k位，他的标号就是(h,k)，因为他前面的人都高过他。
  2. 假如一个人的标号是(h,k)，那么有一个身高为h',h'<h的人插入队列，不会影响他的标号。

从这两点，我们可以设计这样的队列插入方法：

  1. 将people按身高从高到低排。如果身高一样，就按k值从小到大排。
  2. 每轮依次从排序后的people中取出一人，假设是(h,k)，将他插入到结果队列中的第k个位置中。

这是因为，取出的(h,k)后面所有人，要么身高比他低，插到哪里都不影响他的标号；要么身高和他一样但是k值比他低，只能插到他后面的位置。总之，后面的人插入时不会影响前面的人的标号在当前队列中的正确性。因此只要按照这个办法，将所有人（正确地）插入队列中后，就能在保证所有人的标号都对的前提下排好队了。

代码的sorted部分，我本来用了functools库中的cmp_to_key写比较函数。但是看了@StefanPochmann的回答以后，我发现有简洁得多的写法（此人写出了许多令人赏心悦目的简洁代码）。以下代码借鉴了他的sorted写法。

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
	sorted_people = sorted(people, key=lambda x: (-x[0], x[1]))
	ans = []
	for each in sorted_people:
	    ans.insert(each[1], each)
	return ans