# Pow(x, n)

mplement pow(xn), which calculates x raised to the power n (xn).

Example 1:

```Input: 2.00000, 10
Output: 1024.00000
```

Example 2:

```Input: 2.10000, 3
Output: 9.26100
```

Example 3:

```Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
```

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]
```class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1

if n < 0:
return 1 / self.myPow(x, -n)

if n % 2:
return x * self.myPow(x, n-1)

return self.myPow(x*x, n/2)```

# Stone Game II

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones `piles[i]`.  The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first.  Initially, `M = 1`.

On each player’s turn, that player can take all the stones in the first `X` remaining piles, where `1 <= X <= 2M`.  Then, we set `M = max(M, X)`.

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

```Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
```

Constraints:

• `1 <= piles.length <= 100`
• `1 <= piles[i] <= 10 ^ 4`

The king of concise code reigns!

```from functools import lru_cache

class Solution:
def stoneGameII(self, piles: List[int]) -> int:

N = len(piles)

for i in range(N - 2, -1, -1):
piles[i] += piles[i + 1]

@lru_cache(None)
def dp(i, m):
if i + 2 * m >= N:
return piles[i]

return piles[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))

return dp(0, 1)```

# Largest Sum of Averages

We partition a row of numbers `A` into at most `K` adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

```Example:
Input:
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation:
The best choice is to partition A into , [1, 2, 3], . The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], , [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
```

Note:

• `1 <= A.length <= 100`.
• `1 <= A[i] <= 10000`.
• `1 <= K <= A.length`.
• Answers within `10^-6` of the correct answer will be accepted as correct.

Solution 1 (TLE):

```class Solution:
def largestSumOfAverages(self, A, K) -> float:

def func(remind, groups, cur, ans):
if not remind and groups == K:
ans.append(cur)

elif groups < K:
for index in range(1, len(remind)+1):
func(remind[index:], groups + 1, cur + (sum(remind[:index]) / index), ans)

ans = []
func(A, 0, 0.0, ans)

return max(ans)```

Solution 2 (DP):

```class Solution:
def largestSumOfAverages(self, A, K) -> float:

dp = [[0 for _ in range(K)] for _ in A]

for end in range(len(A)):
for segment in range(K):
if segment == 0:
dp[end][segment] = sum(A[:end + 1]) / len(A[:end + 1])
else:
for start in range(end):
dp[end][segment] = max(dp[end][segment], dp[start][segment - 1] + sum(A[start + 1:end + 1]) / (end - start))

return dp[-1][-1]```

Solution 3 (Memory recursion):

```from functools import lru_cache

class Solution:
def largestSumOfAverages(self, A, K) -> float:

n = len(A)
p =  * (n + 1)

for i in range(n):
p[i + 1] = p[i] + A[i]

@lru_cache(maxsize=None)
def dfs(start, k):
if k == 1:
return (p[n] - p[start]) / (n - start)

ans = float('-inf')

for i in range(start + 1, n + 2 - k):
ans = max(ans, (p[i] - p[start]) / (i - start) + dfs(i, k - 1))

return ans

return dfs(0, K)```

# Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

```Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
```

Example 2:

```Input: "aba"
Output: False```

Example 3:

```Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)```
```class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
if not str:
return False

ss = (s + s)[1:-1]

return ss.find(s) != -1```

# Wiggle Sort II

Given an unsorted array `nums`, reorder it such that `nums < nums > nums < nums...`.

Example 1:

`Input: `nums = [1, 5, 1, 1, 6, 4]` Output: One possible answer is `[1, 4, 1, 5, 1, 6]`.`

Example 2:

`Input: `nums = [1, 3, 2, 2, 3, 1]` Output: One possible answer is `[2, 3, 1, 3, 1, 2]`.`

Note:
You may assume all input has valid answer.

Can you do it in O(n) time and/or in-place with O(1) extra space?

```class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort()
half = len(nums[::2])
nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]
```

# Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

`Input: [1,2,3,4,5] Output: true `

Example 2:

`Input: [5,4,3,2,1] Output: false`

Since this problem is literally similar another one (longest-increasing-subsequence), I have tried the traditional dynamic programming at very first. However, this question is not as easy as it looks be, I got a Time Limit Exceeded.

After that, I noticed that we actually can iterate the entire array by one pass with maintaining two pointers.

```class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
#         # TLE
#         if not nums:
#             return False

#         dp =  * len(nums)

#         for i in range(1, len(nums)):
#             for j in range(i):
#                 if nums[i] > nums[j]:
#                     dp[i] = max(dp[i], dp[j] + 1)
#                 if dp[i] == 3:
#                     return True

#         return False

first = second = float('inf')

for n in nums:
if n <= first:
first = n

elif n <= second:
second = n
else:
return True

return False```

# 抛硬币

让我们假设每一回合开始之前，都会有一个新的玩家加入游戏，与仍然在场的玩家们一同赌博。每个玩家最初都只有 1 元钱，并且他们的策略也都是相同的：每回都把当前身上的所有钱都押在正面上。运气好的话，从加入游戏开始，庄家抛掷出来的硬币一直是正面，这个玩家就会一直赢钱；如果连续 n 次硬币都是正面朝上，他将会赢得 2^n 元钱。这个 2^n 就是赌场老板的心理承受极限——一旦有人赢到了 2^n 元钱，赌场老板便会下令停止游戏，关闭赌场。让我们来看看，在这场游戏中存在哪些有趣的结论。

首先，连续 n 次正面朝上的概率虽然很小，但确实是有可能发生的，因此总有一个时候赌场将被关闭。赌场关闭之时，唯一赚到钱的人就是赌场关闭前最后进来的那 n 个人。每个人都只花费了 1 元钱，但他们却赢得了不同数量的钱。其中，最后进来的人赢回了 2 元，倒数第二进来的人赢回了 4 元，倒数第 n 进来的人则赢得了 2^n 元（他就是赌场关闭的原因），他们一共赚取了 2 + 4 + 8 + … + 2^n = 2^(n+1) – 2 元。其余所有人初始时的 1 元钱都打了水漂，因为没有人挺过了倒数第 n + 1 轮游戏。
另外，由于这个游戏是一个完全公平的游戏，因此赌场的盈亏应该是平衡的。换句话说，有多少钱流出了赌场，就该有多少的钱流进赌场。既然赌场的钱最终被赢走了 2^(n+1) – 2 元，因此赌场的期望收入也就是 2^(n+1) – 2 元。而赌场收入的唯一来源是每人 1 元的初始赌金，这就表明游戏者的期望数量是 2^(n+1) – 2 个。换句话说，游戏平均进行了 2^(n+1) – 2 次。再换句话说，平均抛掷 2^(n+1) – 2 次硬币才会出现 n 连正的情况。

# Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent.  The trees are given by root nodes `root1` and `root2`.

Example 1:

`Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] Output: true Explanation: We flipped at nodes with values 1, 3, and 5. `

Note:

1. Each tree will have at most `100` nodes.
2. Each value in each tree will be a unique integer in the range `[0, 99]`.
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
if root1 == root2 == None:
return True

elif root1 and root2 and root1.val == root2.val:
return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right))

else:
return False
```

# Remove Zero Sum Consecutive Nodes from Linked List

Firstly, I can’t help myself to say: “Lee, you are a fucking genius!”

Given the `head` of a linked list, we repeatedly delete consecutive sequences of nodes that sum to `0` until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

(Note that in the examples below, all sequences are serializations of `ListNode` objects.)

Example 1:

```Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
```

Example 2:

```Input: head = [1,2,3,-3,4]
Output: [1,2,4]
```

Example 3:

```Input: head = [1,2,3,-3,-2]
Output: ```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
cur = dummy = ListNode(0)

prefix = 0
seen = collections.OrderedDict()

while cur:
prefix += cur.val
node = seen.get(prefix, cur)
while prefix in seen:
seen.popitem()
seen[prefix] = node
node.next = cur = cur.next

return dummy.next```

# Printing a pyramid matrix

How to print a pyramid matrix like that:

`n = 2[1, 1, 1][1, 2, 1][1, 1, 1]n = 3[1, 1, 1, 1][1, 2, 2, 1][1, 2, 2, 1][1, 1, 1, 1]n = 4[1, 1, 1, 1, 1][1, 2, 2, 2, 1][1, 1, 3, 2, 1][1, 2, 2, 2, 1][1, 1, 1, 1, 1]`
```def func(N):
N += 1
matrix = [[1 for _ in range(N)] for _ in range(N)]
cnt = 0

while cnt < N:
# UP
for i in range(cnt, N - cnt - 1):
matrix[cnt][i] = cnt + 1

# RIGHT
for i in range(cnt, N - cnt - 1):
matrix[i][N - cnt - 1] = cnt + 1

# DOWN
for i in range(N - cnt - 1, cnt, -1):
matrix[N - cnt - 1][i] = cnt + 1

# LEFT
for i in range(N - cnt, cnt, -1):
matrix[N - cnt - 1][cnt] = cnt + 1

cnt += 1

return matrix

if __name__ == "__main__":
matrix = func(N=4)

for line in matrix:
print(line)
```