2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

  1. The n will be in the range [1, 1000].
from functools import lru_cache

class Solution:
    def minSteps(self, n: int) -> int:
        
#         @lru_cache(None)
#         def operation(notepad, current):
#         def operation(notepad, current):
#             if len(current) <= n:
#                 if len(current) == n:
#                     return 0

#                 # no notepad
#                 t1 = (operation(current, current) if not notepad else 0x7777777) + 1

#                 # paste from notepad
#                 t2 = (operation(notepad, current + notepad) if notepad else 0x7777777) + 1

#                 # update notepad
#                 t3 = (operation(current, current) if notepad and notepad != current else 0x7777777) + 1

#                 return min(t1, t2, t3)

#             else:
#                 return 0x7777777

#         result = operation(0, "A")

#         return result

        if n == 1: 
            return 0
        
        for i in range(2,n+1):
            if n % i == 0: 
                return i + self.minSteps(int(n/i))

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 [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [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):
这是一个二维的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):
这个解法首先对区间和的计算进行了一些优化,之后使用Python Functools Library的LRU_Cache实现了记忆化递归。

from functools import lru_cache

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

        n = len(A)
        p = [0] * (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[0] < nums[1] > nums[2] < nums[3]....

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.

Follow Up:
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 = [1] * 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

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.

Flipped Trees Diagram

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: [1]
# 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)
        dummy.next = head
        
        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)