A. Check if All A's Appears Before All B's (opens new window)

Check if the string contains ba.

DETAILS

def checkString(self, s: str) -> bool:
        find = False
        for ch in s:
            if ch == 'b':
                find = True
            else:
                if find:
                    return False
        return True

B. Number of Laser Beams in a Bank (opens new window)

Calculte the product of laser numbers between two adjacent layers.

DETAILS

def numberOfBeams(self, A: List[str]) -> int:
        ans = []
        for row in A:
            c = collections.Counter(row)
            if c['1'] > 0:
                ans.append(c['1'])
        if len(ans) < 2: return 0
        res = 0
        for i in range(len(ans) - 1):
            res += ans[i] * ans[i + 1]
        return res

C. Destroying Asteroids (opens new window)

Sort the array and check the mass of mass and the sorted elements.

DETAILS

def asteroidsDestroyed(self, mass: int, A: List[int]) -> bool:
        A.sort()
        for a in A:
            if mass < a:
                return False
            mass += a
        return True

2127. Maximum Employees to Be Invited to a Meeting (opens new window)

LeetCode题解 (opens new window)\

这是一道比较有意思的题，分两种情况讨论：

• 参会人员构成一个环
• 参会人员由n段线段“构成”一个环。

我们要分别找出两种情况下可参加的最大人数。 对于情况一，我们可以用BFS或者DFS找出最大的环，这本身是个NP问题，不过题目给出的条件是每个人有且只有一个preferred people，所以可以在P内解决。

对于情况二，可以简单证明，每条线段必定有且只有一组相邻的二人a,b, 两人互为对方的preferred people，找出所有这样的二人对，并且找出从这二人出发所构成的最长的线段（人数），每一个二人对构成的最长线段之和，即为情况二下可参会的最大人数。

比较情况一和二各自的最大人数即可。

DETAILS

def maximumInvitations(A):
		# First, we find the largest circle.
        n, maxc = len(A), 0
        seen = [0] * n
        for idx in range(n):
		
			# If a people hasn't been visited:
            if seen[idx] == 0:
                
				# start is for locating the first visited people, cur_people stands 
				#for the current people we are visiting, we use curset to store all 
				# the visited people in this iteration.
				start = idx
                cur_people = idx
                curset = set()
				
				# As long as we are visiting new people, we keep finding his/her favorite.
                while seen[cur_people] == 0:
                    seen[cur_people] = 1
                    curset.add(cur_people)
                    cur_people = A[cur_people]
					
				# Until we find the first visited people. Depends on if this 
				# visited people has been visited in eariler iteration or just this iteration.
				if cur_people in curset:       # if current people is in current set, meaning we have found a new circle
                    cursum = len(curset)
					
					# use 'start' to find the distance from the first visited people in this iteration 
					# to this current people.
                    while start != cur_people:
                        cursum -= 1
                        start = A[start]
                    maxc = max(maxc, cursum)
                                       
		# Then we try to find the sum of largest arms. Firstly, find all mutal-favorite peoples.
        pair = []
        visited = [0] * n
        for i in range(n):
		
			# If a is b's favorite and vise versa, we put them in 'pair'.
            if A[A[i]] == i and visited[i] == 0:
                pair.append([i, A[i]])
                visited[i] = 1
                visited[A[i]] = 1
		
		# for every people I, find out all the people whos favorite is I.
        res = 0
        child = collections.defaultdict(list)
        for i in range(n):
            child[A[i]].append(i)
        
        for a, b in pair:
            # max arm length start from first people a
            maxa = 0
            dq = collections.deque()
            for cand in child[a]:
                if cand != b:
                    dq.append([cand, 1])
            while dq:
                cur, n = dq.popleft()
                maxa = max(maxa, n)
                for nxt in child[cur]:
                    dq.append([nxt, n + 1])
                    
            # max arm length start from first people b
            maxb = 0
            dq = collections.deque()
            for cand in child[b]:
                if cand != a:
                    dq.append([cand, 1])
            while dq:
                cur, n = dq.popleft()
                maxb = max(maxb, n)
                for nxt in child[cur]:
                    dq.append([nxt, n + 1])
            
			# Thus the total length is the two longest arm plus 2 (a and b themselves)
            res += 2 + maxa + maxb
			
		# select the larger one as the answer.
        return max(maxc, res)