Posts in 2019 dec

leetcode weekly contest 169

[source to contest page](https://leetcode.com/contest/weekly-contest-169) 5295. Find N Unique Integers Sum up to Zero The code is quite self-explanatory. This is one of the easiest I've seen so far. ```python class Solution: def sumZero(self, n: int) -> List[int]: return [i for i in range(n-1)]+[-sum(range(n-1))] ``` 5296. All Elements in Two Binary Search Trees This can be brute-forced. ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def getAllElements(self, A: TreeNode, B: TreeNode) -> List[int]: l=[] def flat(T): if T: l.append(T.val) flat(T.left) flat(T.right) flat(A) flat(B) return sorted(l) ``` 5297. Jump Game III thought of bunch of ideas, settled on dfs: ```python class Solution: def canReach(self, A: List[int], s: int) -> bool: if A[s]==0: return True n=len(A) Z=[False]*n found=False for i in range(n): if A[i]==0: Z[i]=True found=True if not found: return False R=[False]*n R[s]=True #dfs st=[s] while st: cur=st.pop() r=cur+A[cur] if 0<=r<n: if Z[r]: return True if not R[r]: st.append(r) R[r]=True l=cur-A[cur] if 0<=l<n: if Z[l]: return True if not R[l]: st.append(l) R[l]=True return False ``` And finally, the [last problem](https://leetcode.com/problems/verbal-arithmetic-puzzle/). I solved the first three in 13 minutes and try to pass the given test cases for more than half an hour before I finally gave up. [One way](https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/463886/Python-backtracking-w-Explanation) is to back-track on columns, from right to left, keeping track of current row, current column, and a carry. There are [other backtracking methods](https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/463900/ACCEPTED-Java-Backtracking-Using-an-Int-Array-as-Map-passed-all-test-cases) available but it seems some only works in certain languages. Overall I did okay this time (ranked ~340 / ~5800), the last problem is really hard this time.

leetcode weekly contest 136 question 4: 1044. Longest Duplicate Substring

[source](https://leetcode.com/contest/weekly-contest-136/problems/longest-duplicate-substring/) This is your geeky problem, throwing all sorts of heavy armories at it and a glorious victory awaits you. Solution 1: binary search + [Rabin Karp (rolling hash)](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm) Adapted from [here](https://leetcode.com/problems/longest-duplicate-substring/discuss/290871/Python-Binary-Search) ```python from functools import reduce class Solution: def longestDupSubstring(self, S: str) -> str: A = [ord(c) - ord('a') for c in S] mod = 2 ** 63 - 1 def verify(L): p = pow(26, L, mod) cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0) seen = {cur} for i in range(L, len(S)): cur = (26 * cur + A[i] - p * A[i - L]) % mod if cur in seen: return i - L + 1 seen.add(cur) res, lo, hi = 0, 0, len(S) while lo < hi: mid = (lo + hi + 1) // 2 start = verify(mid) if start: lo, res = mid, start else: hi = mid - 1 return S[res:res + lo] ``` Solution 2: [suffix array](https://en.wikipedia.org/wiki/Suffix_array) See [this](https://leetcode.com/problems/longest-duplicate-substring/discuss/290852/Suffix-array-clear-solution)

leetcode weekly contest 136 question 3: 1043. Partition Array for Maximum Sum

[sauce](https://leetcode.com/contest/weekly-contest-136/problems/partition-array-for-maximum-sum/) This is a dynamic programming problem and the standard approach works pretty well. Some attention is needed when implementing the solution. ```python class Solution: def maxSumAfterPartitioning(self, a,k): dp=[0]*len(a)#ans for first x elements in a for i in range(len(a)): for j in range(min(i+1,k)): y=dp[i-j-1] if i-j-1>-1 else 0 dp[i]=max(dp[i],y+(j+1)*max(a[i-j:i+1])) print(dp) return dp[-1] ```

leetcode weekly contest 136 question 2: 1042. Flower Planting With No Adjacent

[sauce](https://leetcode.com/contest/weekly-contest-136/problems/flower-planting-with-no-adjacent/) Well, at first I thought this is a medium or hard problem as it is a [graph coloring](https://en.wikipedia.org/wiki/Graph_coloring) problem on a large undirected graph with very low degree. But it is labelled as easy. I did not really know how to proceed. Then I saw [this solution](https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/290858/JavaC%2B%2BPython-Greedily-Paint), pointing out the catch is that there will always be a way to color the next neighbor, as the degree is smaller than the chromatic numbers. I should really go back and review basic discrete math... The implementation is quite easy, other than the part that converts 0-based and 1-based indices. ```python class Solution: def gardenNoAdj(self, N: int, P: List[List[int]]) -> List[int]: G=collections.defaultdict(list) for u,v in P: G[u - 1].append(v - 1) G[v - 1].append(u - 1) res=[0] * N for i in range(N): avoid = [False] * 5 for j in G[i]: avoid[res[j]] = True for k in range(1,5): if not avoid[k]: res[i] = k break return res ```

leetcode weekly contest 136 question 1: 1041. Robot Bounded In Circle

[source](https://leetcode.com/contest/weekly-contest-136/problems/robot-bounded-in-circle/) The trick is to treat the entire instruction set as a vector plus a direction. The only case it goes off the grid is when it moved (end coordinate nonzero) and facing the same direction as it started with. In this case, it will move by the same vector again and again and a circle cannot bound it. In all other cases, either it returns to the origin or goes in four vectors that ends up at the origin. ```python class Solution: def isRobotBounded(self, s: str) -> bool: x,y=0,0 d=[[1,0],[0,1],[-1,0],[0,-1]] face=1 for c in s: if c=='G': x+=d[face][0] y+=d[face][1] elif c=='L': face=(face+1)%4 else: face=(face-1)%4 if x==0 and y==0: return True if face==1: #same dir will go off return False return True ```

1 2 3 Next Last