Algorithm

Posted on Edited on In ,
Algorithms

1. Prefix Sum

1.1. Maximum Sub-array

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        res = [None for _ in range(n)]
        res[0] = nums[0]
        for i in range(1, n):
            res[i] = res[i - 1] + nums[i]

        min_ = [None for _ in range(n)]
        min_[0] = 0
        for i in range(1, n):
            min_[i] = min(min_[i - 1], res[i - 1])
        ans = float('-inf')
        for i in range(n):
            ans = max(ans, res[i] - min_[i])
        return  ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        result = [0] * n
        result[0] = nums[0]
        ans = nums[0]
        for i in range(1, n):
          # Automaticlly drop the prefix when it become a negative number
          # result[i] stores the maximum sum of subarrays when they are end with i
            result[i] = max(result[i - 1] + nums[i], nums[i])
            ans = max(ans, result[i])
        return ans

2. Sliding Window

2.1. Grumpy Bookstore Owner [2022-07-26]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        res = 0
        for i in range(n):
            if not grumpy[i]:
                res += customers[i]


        ans = 0
        for i in range(minutes):
            if grumpy[i]:
                ans += customers[i]

        res_m = ans
        for i in range(minutes, n):
            if grumpy[i - minutes]:
                ans -= customers[i - minutes]
            if grumpy[i]:
                ans += customers[i]

            res_m = max(res_m, ans)
        return res + res_m

3. Stack and Deque

3.1. 滑动窗口的最大值 [2022-10-20]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
         #窗口大于数组长度的时候，返回空
        if size <= len(num) and size != 0:
            from collections import deque
            #双向队列
            dq = deque()
            #先遍历一个窗口
            for i in range(size):
                #去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                     dq.pop()
                dq.append(i)
            #遍历后续数组元素
            for i in range(size, len(num)):
                res.append(num[dq[0]])
                while len(dq) != 0 and dq[0] < (i - size + 1):
                    #弹出窗口移走后的值
                    dq.popleft()
                #加入新的值前，去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                    dq.pop()
                dq.append(i)
            res.append(num[dq[0]])
        return res

4. Binary Tree

4.1. 在二叉树中找到两个节点的最近公共节点 [2022-10-19]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        self.ans = None
        def dfs(root):
            if not root:
                return False, False
            find1_left, find2_left = dfs(root.left)
            find1_right, find2_right = dfs(root.right)

            find1 = find1_left or find1_right
            find2 = find2_left or find2_right
            if root.val == o1:
                if find2:
                    self.ans = root
                return True, find2
            if root.val == o2:
                if find1:
                    self.ans = root
                return find1, True
            if (find1_left or find2_left) and (find1_right or find2_right):
                self.ans = root
            return find1, find2
        dfs(root)
        return self.ans.val

4.2. 镜像的二叉树 [2022-10-19]

Sample

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        def dfs(root):
            if not root:
                return
            root.right, root.left = root.left, root.right
            dfs(root.right)
            dfs(root.left)
        dfs(pRoot)
        return pRoot

4.3. 合并二叉树 [2022-10-19]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        def dfs(root1, root2):
            root1.val += root2.val
            if root1.right:
                if root2.right:
                    dfs(root1.right, root2.right)
            else:
                root1.right = root2.right
            if root1.left:
                if root2.left:
                    dfs(root1.left, root2.left)
            else:
                root1.left = root2.left
        dfs(t1, t2)
        return t1

4.4. 对称的二叉树 [2022-10-19]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def recursion(self, root1: TreeNode, root2: TreeNode):
        # 可以两个都为空
        if not root1 and not root2:
            return True
        # 只有一个为空或者节点值不同，必定不对称
        if not root1 or not root2 or root1.val != root2.val:
            return False
        # 每层对应的节点进入递归
        return self.recursion(root1.left, root2.right) and self.recursion(root1.right, root2.left)

    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return self.recursion(pRoot, pRoot)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        ans = [True]
        def wfs(cur_nodes):
            if not cur_nodes:
                return
            res = []
            nex = []
            flag = False
            for i in cur_nodes:
                if not i:
                    nex.append(None)
                    nex.append(None)
                    res.append(None)
                    res.append(None)
                    continue
                if i.left:
                    nex.append(i.left)
                    res.append(i.left.val)
                    flag = True
                else:
                    nex.append(None)
                    res.append(None)
                if i.right:
                    flag = True
                    nex.append(i.right)
                    res.append(i.right.val)
                else:
                    nex.append(None)
                    res.append(None)
            if res != res[::-1]:
                ans[0] = False
                return
            if flag:
                wfs(nex)
        wfs([pRoot])
        return ans[0]

5. Backtrack

We can cope with only simple tasks. But there is only a complex task.

If we can transfer it into a relative simpler one, do it again and again till we can cope with it.

When transfer, the simpler task may have some relationship with the complex one, e.g., the complex task gives some restrictions to to the simpler one.

5.1. N-Queens II [2022-06-20]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row: int) -> int:
            # fill the row
            # two kinds of return

            # when row == n, the last row (n - 1) is filled
            # thus it must be only 1 solution to reach here so return 1

            # if row < n - 1, the solution there is may be multiple solutions
            # clear the count (count = 0), then find the number of solutions
            # and return it

            # thus this function calculates the number of  solutions when the first
            # row - 1 rows is filled, how they are filled are recorded by columns,
            # diagonal1 and giagonal2

            # two key points:
            # 1. How the backtrack end: that is the condition return 1
            # 2. How to transfer the task to a smaller one, that is else.

            # we can crop it if  and only if row == n, thus we only need
            # to transfer the task to a simpler one till we can crop it
            if row == n:
                return 1
            else:
                count = 0
                for i in range(n):
                    # i is the columns if it is used continue
                    # two position A and B, if their row -/+ i is the same number
                    # they are in one diagonal then continue
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    count += backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                return count

        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        return backtrack(0)

6. Wide First Search

6.1. Count Complete Tree Nodes [2022-07-01]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        res = [1, 0]

        def wide_first_search(cur_nodes):
            res[0] += 1
            nex_nodes = []
            flag = True

            for i in cur_nodes:
                if i.left and i.right:
                    nex_nodes.append(i.left)
                    nex_nodes.append(i.right)
                else:
                    flag = False
                    res[1] = len(nex_nodes)
                    if i.left or i.right:
                        res[1] += 1
                    break
            if flag:
                wide_first_search(nex_nodes)

        if  not root:
            return 0
        wide_first_search([root])
        return 2 ** (res[0] - 1) -1 + res[1]

7. Depth First Search

7.1. Keys and Rooms [2022-08-11]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        num_rooms = len(rooms)
        keys = set()
        keys.add(0)
        visited = set()
        cur = [0]

        # depth first
        while cur:
            nex = []
            for i in cur:
                visited.add(i)
                for j in rooms[i]:
                    keys.add(j)
                    if not j in visited:
                        nex.append(j)
            cur = nex
        return len(keys) == num_rooms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        num_rooms = len(rooms)
        visited = set()
        cur = [0]

        # depth first
        while cur:
            nex = []
            for i in cur:
                visited.add(i)
                for j in rooms[i]:
                    if not j in visited:
                        nex.append(j)
            cur = nex
        return len(visited) == num_rooms

7.2. Binary Tree Tilt [2022-07-31]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def __init__(self):
        self.ans = 0

    def findTilt(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.ans

    def dfs(self, node):
        if not node:
            return 0
        # left sum
        sum_left = self.dfs(node.left)
        # right sum
        sum_right = self.dfs(node.right)
        # for every node the distance is the left sum - right sum
        self.ans += abs(sum_left - sum_right)
        # calculate the sum
        return sum_left + sum_right + node.val

7.3. Chasing Game [2022-07-29]

Hard

  1. If StartA can reach startB by one step, then the answer is 1
  2. if there is a circle large than 3 nodes, and B can reach it earlier than A, the answer is -1. Which means that if there is any node that B can reach earlier than A.
  3. If B can reach a node 2 or more steps earlier than A. A can only catch B in the end. Thus choose the max step that A will take between these nodes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution:
    def chaseGame(self, edges: List[List[int]], startA: int, startB: int) -> int:
        # the number of paths and the number of nodes
        n=len(edges)
        # the node a can reach d[a] by one step
        d=defaultdict(list)
        for a,b in edges:
            d[a].append(b)
            d[b].append(a)

        def calcDist(node):
            que=[node]
            dist,step={},0
            while que:
                tmp=[]
                for q in que:
                    if q in dist:
                        continue
                    # node needs dist[q] step to reach q
                    dist[q]=step
                    for nxt in d[q]:
                        tmp.append(nxt)
                que=tmp
                step+=1
            return dist

        circleNodes,depthdict=set(),{}

        def findCircle(parent,node,depth):
            # if already know the depth of node
            # return it
            if node in depthdict:
                return depthdict[node]

            # 1 can reach a by depthdict[a] steps
            depthdict[node]=depth
            for nxt in d[node]:
                # a's parent be in d[a]
                # and it must be searched
                if nxt==parent:
                    continue

                # find the step of nxt by node
                mindepth=findCircle(node,nxt,depth+1)
                # if mindepth != depth + 1, the nxt can be reached
                # by another way both  from one start, thus node can be
                # reached by another way too, there must
                # be a circle, and node and nxt are in the circle
                # regard the circle as one node and both node and nxt
                # have  the same depth, the minstep that can reach the
                # circle
                if mindepth != depth + 1:
                    depthdict[node]= min(mindepth, depth)
                    circleNodes.add(node)
            return depthdict[node]

        findCircle(-1,1,0)
        distA,distB=calcDist(startA),calcDist(startB)
        # startA  reaches startB by 1 step
        if distA[startB]==1:
            return 1
        if len(circleNodes)>3:
            for node in circleNodes:
                # if the circle is larger than 3
                # and there are one node in the circle that B reach first
                # then A can never catch B
                if distB[node]<distA[node]:
                    return -1
        # B reach node earlyer than 2 steps before A
        # if only 1 step earler it should be catched before
        return max(distA[node] for node in range(1,n+1) if distA[node]-distB[node]>1)

7.4. Distribute Coins in Binary Tree [2022-07-22]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def distributeCoins(self, root):
        self.ans = 0

        def dfs(node):
            if not node: return 0
            # the number of coins needed for the right node and
            # the left node to set them into 1
            L, R = dfs(node.left), dfs(node.right)

            # remove the abs(L) and abs(R) from this node to the left
            # node and right node then they are 1
            self.ans += abs(L) + abs(R)
            # the number of coins needed for this node
            return node.val + L + R - 1

        dfs(root)
        return self.ans

7.5. Closest Dessert Cost [2022-06-30]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        baseCosts.sort()
        toppingCosts.sort()
        res = []
        cost = 0
        def check_cost(cost):
            if not res:
                min_distance = float('inf')
            else:
                min_distance = abs(target - res[-1])
            distance = abs(target - cost)
            if distance < min_distance:
                res.clear()
                res.append(cost)
            if distance == min_distance:
                res.append(cost)
        def choose_cur(j, cost):
            if j == len(toppingCosts):
                return
            price = toppingCosts[j]
            choose_cur(j + 1, cost)

            check_cost(cost + price)
            choose_cur(j + 1, cost + price)

            check_cost(cost + 2 * price)
            choose_cur(j + 1, cost + 2 * price)

        for i in baseCosts:
            cost = i
            check_cost(cost)
            choose_cur(0, cost)
        return min(res)

7.6. Find All Possible Recipes from Given Supplies [2022-06-24]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        res = []
        def remove_cur(cur_supplies):
            nex_supplies = set()
            for i, cur_ingredients in enumerate(ingredients):
                if cur_ingredients:
                   # Be careful. How to remove items in a loop
                    # https://segmentfault.com/a/1190000007214571
                    cur_ingredients = list(filter(lambda x: x not in cur_supplies, cur_ingredients))
                    ingredients[i] = cur_ingredients
                    if not cur_ingredients:
                        nex_supplies.add(recipes[i])
                        res.append(recipes[i])
                        recipes[i] = None
                        ingredients[i] = None
            return nex_supplies

        supplies = set(supplies)
        while supplies:
            supplies = remove_cur(supplies)
        return res

7.7. Longest Increasing Path in a Matrix

Given an m×nm \times n integers matrix, return the length of the longest increasing path in matrix.

Move direction: left, right, up, or down.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:

    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        @lru_cache(None) # save  the storage
        def find_max(i, j):
        # find the next value and try the four directions
        # return the longest direction.
            max_ = 1
            for dr in Solution.DIRS:
                try_i = i + dr[0]
                try_j = j + dr[1]
                # the direction will be discarded if do not meet the condition
                # and a direction meet the condition will be searched for the next
                # value first.
                if 0 <= try_i and try_i < n and 0<= try_j and try_j < m and \
                matrix[i][j] < matrix[try_i][try_j]:
                    max_ = max(max_, find_max(try_i, try_j) + 1)
                    # The value is increasing, so by setting `matrix[i][j] \
                    # < matrix[try_i][try_j]`, a searched position will never
                    # be searched again.
            return max_

        n, m = len(matrix), len(matrix[0])
        res = 0
        for i in range(n):
            for j in  range(m):
                res = max(res, find_max(i, j))
        return res

7.8. Keyboard

A keyboard only have 26 keys, a~z. Each key can be only typed k times at most.

How many possible content there is, when the keyboard is typed n times?

7.8.1. Method 1: dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
   # depth first search: from the first letter to the last letter
   # fill the n positions.
   def keyboard(self, k: int, n: int) -> int:
       MOD = 1000000007

       # c is the number of remain letters
       # n is the number of letters needed to type in
       # k is the max number that each letter can type
       @lru_cache(None)
       def dfs(c, n, k):
           if n == 0:
               # no letters is needed any more
               # only 1 way: type nothing
               # pick 0 letters
               return 1
           if c <= 0:
               # no letter remained but n is not 0
               # this is a failed type scheme
               return 0
           res = 0
           for i in range(0, min(n, k) + 1):
           # there are math.comb(n, i) ways to put i letters
           # into n position.
               res += math.comb(n, i) * dfs(c-1, n - i, k) % MOD
           return res % MOD
       ans = dfs(26, n, k)
       return ans % MOD

7.8.2. Method 2: dynamic programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def keyboard(self, k: int, n: int) -> int:
        MOD = 1000000007
        res = [[0 for _ in range(27)] for _ in range(n + 1)]
        # res[i][j] is the number of possibilities when first j letters
        # is used to fill i positions.
        # when the position is 0, no matter how many letters are used.
        # there is only one possibility, i.e., filling nothing.
        # thus, res[0][i] are all 1.
        res[0][0] = 1
        for i in range(27):
            res[0][i] = 1

        # res[i][j] can be divided into several possibilities.
        # When 0 letter is filled for the $j^{th}$ letter, res[i][j-1]
        # when 1 letter is filled for the j-th letter, res[i-1][j-1]
        # * C_i^1
        # when 2 letters are filled for the j-th letter, res[i-2][j-1]
        # * C_i^2
        # C_i^m represent how many possibilities there are filling m of
        # the same letters into i positions.
        # m can be 0, but can not be larger than k or i.
        for i in range(1, n + 1):
            for j in range(1, 27):
                for m in range(min(i + 1, k + 1)):
                    res[i][j] += res[i - m][j - 1] * math.comb(i, m)
                    res[i][j] %= MOD

        return res[-1][-1] % MOD

8. Dynamic Programming

8.1. Palindrome Partitioning II [2022-08-12]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        g = [[True] * n for _ in range(n)]

        # Calculate if s[i:j + 1] is a palindrome
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                # if s[i + 1 : j] is a palindrome
                # and s[i] == s[j] then s[i:j + 1]
                # is a palindrome
                g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]

        f = [float("inf")] * n
        # f[i] is the min cuts for s[0: i+1]
        for i in range(n):
            if g[0][i]:
                f[i] = 0
            else:
                for j in range(i):
                    if g[j + 1][i]:
                        f[i] = min(f[i], f[j] + 1)
        return f[n - 1]

8.2. Minimum Cost to Cut a Stick [2022-07-30]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        # the number of cuts
        m = len(cuts)
        cuts = [0] + sorted(cuts) + [n]

        f = [[0] * (m + 2) for _ in range(m + 2)]
        # f[i][j] means the minimal cost of [i-1, j+1]
        # thus f[1][m] is the answer
        # f[i][i] is the minimal cost of [i -1, i + 1]
        # which is cut[i+1] - cut[i -1]
        # when j > i, f[i][j] = cut[j + 1] - cut[i - 1] + min(xxxx)
        for i in range(m, 0, -1):
            for j in range(i, m + 1):
                if i == j:
                    f[i][j] = 0
                else:
                    f[i][j] =  min(f[i][k - 1] + f[k + 1][j] for k in range(i, j + 1))

                f[i][j] += cuts[j + 1] - cuts[i - 1]

        return f[1][m]

8.3. Unique Paths II [2022-07-20]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        res = [[0 for _ in range(n)] for _ in range(m)]

        for i in range(n):
            if obstacleGrid[0][i] == 0:
                res[0][i] = 1
            else:
                break

        for i in range(m):
            if obstacleGrid[i][0] == 0:
                res[i][0] = 1
            else:
                break

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    res[i][j] = res[i][j - 1] + res[i - 1][j]
        return res[-1][-1]

8.4. Find Two Non-overlapping Sub-arrays Each With Target Sum [2022-07-07]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        n = len(arr)
        res = n + 1

        pre = {}

        # make sure the sub array start from 0 can be visited
        pre[0] = -1
        dp = [float('inf')] * n

        p = 0
        for i, a in enumerate(arr):
            # p is the sum from idex 0 to i
            p += a
            dp[i] = dp[i - 1]

            # if p - target in pre then target = p - pre which is a sub array
            # the sum eqaul to target
            if (p - target) in pre:
                cur = i - pre[p - target]
                # dp[pre[p - target]] != float if and only if there are sub
                # array whose sum eqauls to the target, and it can not connect
                # with cur sub array because current sub array is from index
                # pre[p - target]
                # Note that: this can find all the possible pairs of sub
                # arrays
                if pre[p - target] >= 0 and dp[pre[p - target]] != float('inf'):
                    res = min(res, cur + dp[pre[p - target]])
                # dp does not equal to inf anymore, only if there are sub
                # array whose sum equals to the target
                dp[i] = min(i - pre[p - target], dp[i - 1])

            # the sum from index 0 to i is p
            pre[p] = i
        return -1 if res == n + 1 else res

8.5. Minimum One Bit Operations to Make Integers Zero [2022-06-27]

Really Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minimumOneBitOperations(self, n):
        dp1 = [0 for _ in range(32)]
    #dp1[i] 表示 仅第 i 位 为 1 时 将 第 i 位变为 0 的最小修改次数
        res = 0
        dp1[0] = 1
        for i  in range(1,32):
            dp1[i] = dp1[i - 1] + 1 + dp1[i - 1]
        f = True
        # 1. 0 变位仅i位为1的过程中，其后每一位都需要经历若干次从0到1,再从1到0的变化
        # 2. 其后位中若原本就为1,则不会经历第一次从0到1的变化，因为它本身就是1
        # 所以若把第i位从1变为0,记为dp[i]，是多记录了，因为其后有1
        # 所以如果其后遇到1的要减去。但是减去的话又多减了，因为其后还有1,所以又加上
        for i in range(31, -1, -1):
            if n >> i & 1:
                if f:
                    res += dp1[i]
                    f = False
                else:
                    res -= dp1[i]
                    f = True
        return res

8.6. The number of palindromes

Given a string return the number of the palindromes. The substrings are regarded as different strings if they are start and end at different position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        res = [[False for _ in range(n)] for _ in range(n)]
        # if n == 0, there are 0 palindromes.
        # if n == 1, there are 1 palindromes.
        if not n or n == 1:
            return n
        ans = n

        for i in range(n):
            res[0][i] = True

        for i in range(n - 1):
            res[1][i] = s[i] == s[i + 1]
            if res[1][i]:
                ans += 1
# if n == 2 it will not enter the following circle.
# if n > 2 it will contnue to caculate palindromes whose length is larger than 2
        for l in range(2, n):
            for st in range(n - l):
                res[l][st] = res[l - 2][st + 1] and s[st] == s[st + l]
                if res[l][st]:
                    ans += 1
        return ans

8.7. Knight Dialer

The topic is here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def knightDialer(self, N):
        MOD = 10**9 + 7
        # From 0 can reach 4 and 6
        # From 1 can reach 6 and 8
        moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],
                     [1,7,0],[2,6],[1,3],[2,4]]

        # There is dp[i]==1 ways to reach i by one step
        dp = [1] * 10
        for hops in range(N-1):
            dp2 = [0] * 10
            for node, count in enumerate(dp):
              # There are count way to reach node by hops + 1 steps
                for nei in moves[node]:
                    dp2[nei] += count
                    dp2[nei] %= MOD
              # There are dp2[nei] way to reach nei by hops + 2 steps
            dp = dp2
        return sum(dp) % MOD

9. Linked List

9.1. Combine Two Linked List [2022-10-13]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        dump_head = ListNode(0)
        cur = dump_head
        while pHead1 and pHead2:
            if pHead1.val > pHead2.val:
                cur.next = pHead2
                cur = cur.next
                pHead2 = pHead2.next
            elif pHead1.val < pHead2.val:
                cur.next = pHead1
                cur = cur.next
                pHead1 = pHead1.next
            else:
                # Be careful the order
                cur.next = pHead1
                cur = cur.next
                pHead1 = pHead1.next

                cur.next = pHead2
                cur = cur.next
                pHead2 = pHead2.next
        if not pHead1 and not pHead2:
            return dump_head.next
        if not pHead1:
            cur.next = pHead2
            return dump_head.next
        if not pHead2:
            cur.next = pHead1
            return dump_head.next

9.2. The sum of two Linked List [2022-10-13]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        def reverse(h):
            if not h or not h.next:
                return h
            head = h
            h = h.next
            head.next = None
            while h:
                cur = h
                h = h.next
                cur.next = head
                head = cur
            return head
        head1 = reverse(head1)
        head2 = reverse(head2)
        add = 0
        ans = None
        while head1 or head2 or add:
            a = 0
            b = 0
            if head1:
                a = head1.val
                head1 = head1.next
            if head2:
                b = head2.val
                head2 = head2.next
            s = a + b + add
            add = s // 10
            cur = ListNode(s % 10)
            if ans:
                cur.next = ans
            ans = cur
        return ans

9.3. Combine K Linked List [2022-10-13]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import heapq

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

9.4. Partition List LCCI [2022-07-15]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small_head = ListNode(None)
        large_head = ListNode(None)
        small_cur = small_head
        large_cur = large_head

        while head:
            if head.val < x:
                small_cur.next = head
                small_cur = head
            else:
                large_cur.next = head
                large_cur = head

            head = head.next

        large_cur.next = None
        small_cur.next = large_head.next
        return small_head.next

9.5. Find The Minimum and Maximum Number of Nodes Between Critical Points [2022-06-18]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        import numpy as np
        cur = head
        left_sign = 0
        pre_idx = None
        start_idx = None
        min_distance = float('inf')
        idx = 0

        while cur.next:
            right_sign = np.sign(cur.next.val - cur.val)
            if left_sign * right_sign == -1:
                if not start_idx:
                    start_idx = idx
                if pre_idx and idx - pre_idx < min_distance:
                    min_distance = idx - pre_idx

                pre_idx = idx
            cur = cur.next
            left_sign = right_sign
            idx += 1

        if pre_idx != start_idx:
            return [min_distance, pre_idx - start_idx]
        return [-1, -1]

9.6. Reverse a Linked List [2022-06-16]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        cur = head.next
        start = head
        # head is the last node
        start.next = None
        while cur:
            next_cur = cur.next
            cur.next = start
            start = cur
            cur = next_cur
        return start

9.7. Reverse Nodes in K-Group [2022-06-10]

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
      # reverse a link node, the length is k
    def reverse(self, head: ListNode, tail: ListNode, k):
        current = head
        crop = head.next
        for i in range(k - 1):
            follow = crop.next
            crop.next = current
            current = crop
            crop = follow
        return current, head


    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dump = ListNode(0)
        dump.next = head

        current = dump
        end = current

# while the end has next, check if it has k nodes followed
        while end.next:
            start = end.next
            # check if followed k nodes
            for i in range(k):
                end = end.next
                 # do not have k nodes followed, then do not reverse
                 # and also the link node have been done, and return.
                if not end:
                    return dump.next

# if have k nodes followed
            follow = end.next
             # reverse the k nodes and return the reversed start and end
            r_start, r_end = self.reverse(start, end, k)
             # connect the reversed k nodes with the original nodes
            current.next = r_start
            r_end.next = follow
            current = r_end
            end = current
            # the length of the link node is a multiple of k, and end.next is None, return
        return dump.next

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

9.8. Palindrome Linked List

Given the head of a singly linked list, return true if it is a Palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        res = []
        if not head:
            return True
        num = 0
        first = head
        while first.next:
            res.append(first.val)
            num += 1 # count the length of the linked list
            first = first.next
        res.append(first.val) # store all the node value
        for i in range(num // 2 + 1): # does not need to check all the nodes
            if res[i] != res[num - i]:
                return False
        return True

If one want only use O(n) time and O(1) storage, must reverse the last half of the linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        def find_the_middle(node):
            slow = node
            fast = node
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            second_start = slow.next
            slow.next = None
            return second_start
        second_start = find_the_middle(head)
        def reverse(node):
            start = node
            pre = node.next
            start.next = None
            while pre:
                cur = pre
                pre = pre.next
                cur.next = start
                start = cur
            return start
        new_start = reverse(second_start)
        while head and new_start:
            if head.val != new_start.val:
                return False
            head = head.next
            new_start = new_start.next
        return True

10. String

10.1. Group Anagrams [2022-08-28]

Medium

1
2
3
4
5
6
7
8
9
10
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for i in strs:
            res[''.join(sorted(i))].append(i)

        ans = []
        for key in res:
            ans.append(res[key])
        return ans

10.2. Strong Password Checker II [2022-06-22]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def strongPasswordCheckerII(self, password: str) -> bool:
        n = len(password)

        if_length = n >= 8

        contain_lower = False
        contain_upper = False
        contain_number = False
        contain_special = False
        contain_twosame = False

        special = set("!@#$%^&*()-+")
        pre_char = ''
        for i in password:
            if i == pre_char:
                contain_twosame = True
            pre_char = i
            if not contain_lower and i.islower():
                contain_lower = True
                continue
            if not contain_upper and i.isupper():
                contain_upper = True
                continue
            if not contain_number and i.isdigit():
                contain_number = True
                continue
            if not contain_special and i in special:
                contain_special = True
                continue
        return if_length and contain_lower and contain_upper and contain_number and contain_special and not contain_twosame

10.3. Minimum Changes to Make Alternating Binary String

You are given a string s consisting only of the characters 0 and 1. In one operation, you can change any 0 to 1 or vice versa.

The string is called alternating if no two adjacent characters are equal. Return the minimum number of operations needed to make s alternating.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)
        # The ans is the operation needed to turn s into `010101`
        ans = 0
        for i in range(n):
            if i % 2 and s[i] != "1":
              ans += 1
            if not i % 2 and s[i] != "0":
                ans += 1
        return min(ans, n - ans)

11. Sort

11.1. 旋转数组的最小数字 [2022-10-17]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        n = len(rotateArray)
        left = 0
        right = n - 1
        while left < right:
            mid = (left + right) // 2
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            else:
                right -= 1
        return rotateArray[left]

11.2. 数组中的逆序对 [2022-10-17]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        res = data
        n = len(res)
        ans = [0]
        def divide(left, right):
            if left >= right:
                return
            mid = (left + right) // 2
            divide(left, mid)
            divide(mid + 1, right)
            merge(left, mid, right)
        def merge(left, mid, right):
            l = left
            r = mid + 1
            tmp = []
            while l <= mid and r <= right:
                if res[l] > res[r]:
                    tmp.append(res[r])
                    r += 1
                    ans[0] += mid -l + 1
                    ans[0] %= 1000000007
                else:
                    tmp.append(res[l])
                    l += 1
            while l <= mid:
                tmp.append(res[l])
                l += 1
            while r <= right:
                tmp.append(res[r])
                r += 1
            for i in range(left, right + 1):
                res[i] = tmp.pop(0)
        divide(0, n -1)
        return ans[0]

11.3. Sort Color [2022-10-12]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        idx_f = 0
        idx_e = len(nums) - 1
        while idx_f < idx_e:
            while idx_f < idx_e and nums[idx_f] == 0:
                idx_f += 1
            while idx_f < idx_e and nums[idx_e] != 0:
                idx_e -= 1
            nums[idx_e], nums[idx_f] = nums[idx_f], nums[idx_e]
        if nums[idx_f] == 0:
            idx_f += 1
        idx_e = len(nums) - 1
        while idx_f < idx_e:
            while idx_f < idx_e and nums[idx_f] == 1:
                idx_f += 1
            while idx_f < idx_e and nums[idx_e] != 1:
                idx_e -= 1
            nums[idx_e], nums[idx_f] = nums[idx_f], nums[idx_e]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        idx_0 = 0
        idx_2 = n - 1
        i = 0
        while i <= idx_2:
            while i <= idx_2 and nums[idx_2] == 2:
                idx_2 -= 1
            if i <= idx_2 and nums[i] == 2:
                nums[i], nums[idx_2] = nums[idx_2], nums[i]
                idx_2 -= 1
            if nums[i] == 0:
                nums[i], nums[idx_0] = nums[idx_0], nums[i]
                idx_0 += 1
            i += 1

11.4. Relative Rank [2022-06-28]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        dic = {
            0 : 'Gold Medal',
            1 : 'Silver Medal',
            2 : 'Bronze Medal',
            }
        res = sorted(range(n), key = lambda x : score[x], reverse = True)
        for i in range(n):
            if i in dic:
                score[res[i]] = dic[i]
            else:
                score[res[i]] = str(i + 1)
        return score

11.5. Sort Integers by the Number of 1 Bits [2022-06-16]

here

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        res = []
        for i in arr:
            c = 0
            for s in bin(i):
                if s == '1':
                    c += 1

            res.append([c, i])
        res.sort()
        return [a[1] for a in res]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict as d

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        dic = d(list)

        for i in arr:
            c = 0
            for s in str(bin(i)):
                if s == "1":
                    c += 1
            dic[c].append(i)

        output = []
# The range of integer is less than 0b111111111111111.
        for j in range(15):
            if dic[j]:
                for temp in sorted(dic[j]):
                    output.append(temp)

        return output

11.6. K Highest Ranked Items Within a Price Range [2022-06-13]

The topic is here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        res = []

        curs = [
            [0, grid[start[0]][start[1]], start[0], start[1]]
            ]

# gird set to 0 is to avoid visiting a coordinate for multiple time.
# The position to set the grid to be 0 is important.
# in  this example, the price of a coordinate is set to 0 when it is visited by curs.
# also can set the price to be 0, when it is checked if within the price range.
# However, this is time expensive, for a position maybe append to curs many times before it is checked.
# It is the best to set the price to be 0, once it is visited by curs. The curs will not visits it again.
        grid[start[0]][start[1]] = 0

        r = len(grid)
        c = len(grid[0])

        dirctions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        while curs:
            cur = curs.pop(0)
            cur_step = cur[0]
            cur_price = cur[1]
            cur_row = cur[2]
            cur_cln = cur[3]

            if pricing[0] <= cur_price <= pricing[1]:
               res.append(cur)

            for dirction in dirctions:
                next_step = cur_step + 1
                next_row = cur_row + dirction[0]
                next_cln = cur_cln + dirction[1]
                if 0 <= next_row < r and 0 <= next_cln < c:
                    next_price = grid[next_row][next_cln]
                    grid[next_row][next_cln] = 0
                    if next_price > 0:
                        curs.append([next_step, next_price,next_row, next_cln])

        res.sort()
        return [res[2:] for res in res[:k]]

11.7. Wiggle Sort 2

Given an integer array nums, recorder it such that nums[0] < nums[1] > nums[2] < nums[3] > .... You may assume the input array always has a valid answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        res = []
        for i in nums:
            res.append(i)
        res.sort()
        n = len(nums)
        # Because the smaller number is always filled first,
        # let len(smaller numbers) - len(larger numbers) == 1
        # if the len(nums) is odd.
        # if n is even, the small half from 0 to n // 2 - 1
        # the large half from n // 2 to n - 1
        # if n is odd, small number from 0 to n // 2
        # large number from n // 2 + 1 to n - 1,
        # Thus, no matter n is odd or even, small number from 0 to
        # (n + 1) // 2 - 1, large number from (n + 1) // 2 to n - 1
        half = (n + 1) // 2
        # to avoid that the last small number is equal to the first large
        # number, fill the small number from *last* to first,
        # also, fill the large number from last to *first*
        # ** means that the number should try to be apart.

        # if n is even, half * 2 == n
        # if n is odd, half * 2 == n + 1
        for i in range(half):
            nums[2 * i] = res[half - 1 -i]
            # len(large number) is smaller than len(small number),
            # thus, the when i = half -1, maybe no large number anymore
            try:
                nums[2 * i + 1] = res[n - 1 - i]
            except:
                pass

11.8. Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition, e.g., one gives ABC, one gives BCA.

The ordering of teams is decided by who received the most position-one votes. If A received the most 1-st place Then A is the first. If B received the same first place as A then compare the number of second place they received. If A and B received all the places the same number then ordered them by their letter, i.e., A is in front of B.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        # initialization of a hash map, the default value is list [0, 0, ..., 0]
        # NOTE: How to set defaultdict by lambda without input, it is indeed a function factory.
        ranking = collections.defaultdict(lambda: [0] * n)
         # count the vote situation for each team, vid is the name of teams.
        for vote in votes:
            for i, vid in enumerate(vote):
                ranking[vid][i] += 1

        # result is a list, e.g., [('A', [5, 0, 0]), ('B', [0, 2, 3]), ('C', [0, 3, 2])]
        result = list(ranking.items())
        # sort the order of letter -ord(x[0]) is regard as the last criterion
        result.sort(key=lambda x: (x[1], -ord(x[0])), reverse=True)
        # return the ordered vid
        return "".join([vid for vid, rank in result])

11.9. Number Game

Give a list of numbers. You can + 1 or - 1 at position i which is regarded as one operator at position i. Please return the minimum operators for position i to make the list of numbers satisfying nums[a] + 1 == nums[a + 1], 0 <= a <= i. The original topic is here.

11.9.1. Analysis

To satisfying nums[a] + 1 == nums[a + 1], we do not know which number it is for position i which makes the operators minimum.

Thus we can transform this problem, we make nums[a] = nums[a] - a. Then we only need to make each position of the nums all equal to the same number. Then the minimum way is to set the number as the median number of nums.

NOTE: it is the median number, not the mean value. If the length of the list is even then the median is the mean of the middle two numbers.

It is easy to prove that the mean value can not bring the minimum operators. For examples, for list [1, 3, 8] the mean value is 4 and it needs 3 + 1 + 4 = 8 operators to make the list into [4, 4, 4]. The median is 3 and it needs only 2 + 0 + 5 = 7 operators to make the list into [3, 3, 3].

The reason for why it is the median.

Let s be the value that each position will reach and m be the median. If s is large than m, then #(nums[i] > s) < #(nums[i] < s). If set s = s - 1, nums[i] will add 1 operator if nums[i] > s and nums[i] will decrease 1 operator if nums[i] < s. For #(nums[i] > s) < #(nums[i] < s), the total number of operators will decrease. It will always decrease until s == m, i.e., #(nums[i] > s) = #(nums[i] < s).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from typing import List
from heapq import heappush, heappushpop


class MedianFinder:
    def __init__(self):
        self.small = []  # 大顶堆
        self.large = []  # 小顶堆
        self.leftSum = 0
        self.rightSum = 0

    def add(self, num: int) -> None:
        # if #small == #large then put the num in large
        # How to push it in large.
        # NOTE: not put it in large directly, find the largest value then put it in to the large.
        # This ensure that large is always larger than small.
        # #small always smaller than #large and only larger than 1
        if len(self.small) == len(self.large):
            leftMax = -heappushpop(self.small, -num)
            heappush(self.large, leftMax)
            self.leftSum += num - leftMax
            self.rightSum += leftMax
        elif len(self.small) < len(self.large):
            rightMin = heappushpop(self.large, num)
            heappush(self.small, -rightMin)
            self.leftSum += rightMin
            self.rightSum += num - rightMin

    def getMedian(self) -> float:
     # self.large[0] is the smallest value in large
     # -self.small[0] is the largest value in small
     # get the median if the length is odd, else the mean of the two middle numbers
        if len(self.small) == len(self.large):
            return (self.large[0] - self.small[0]) / 2
        else:
            return self.large[0]

    def getDiffSum(self) -> float:
        median = self.getMedian()
        return self.rightSum - len(self.large) * median + len(self.small) * median - self.leftSum


class Solution:
    def numsGame(self, nums: List[int]) -> List[int]:
        MOD = int(1e9 + 7)
        res = []
        medianFinder = MedianFinder()
        for i in range(len(nums)):
            normalized = nums[i] - i
            medianFinder.add(normalized)
            res.append(int(medianFinder.getDiffSum() % MOD))
        return res

12. Dichotomy

12.1. 二位二分 [2022-08-31]

Medium

12.1.1. 线性搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        n = len(array)
        m = len(array[0])
        idx = [n - 1, 0]
        while 0 <= idx[0] < n and 0 <= idx[1] < m:
            if array[idx[0]][idx[1]] < target:
                idx[1] += 1
            elif array[idx[0]][idx[1]] > target:
                idx[0] -= 1
            else:
                return True
        return False

12.1.2. 每行二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        def find_mid(ma, target):
        #  return the idx, whose left is all smaller than
        # target and right is larger or equal to the target
            left = 0
            right = len(ma) - 1
            while left < right:
                mid = (left + right) // 2
                if ma[mid] < target:
                    left = mid + 1
                else: # ma[mid] => target
                    right = mid
            return right
        for i in array:
            idx = find_mid(i, target)
            if 0 <= idx < len(i) and i[idx] == target:
                return True
        return False

12.2. 二分查找-I [2022-08-29]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            if nums[mid] > target:
                right = mid - 1
            if nums[mid] == target:
                return mid
        return -1

12.3. Minimum Garden Perimeter to Collect Enough Apples [2022-06-22]

Medium

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        left, right, ans = 1, 100000, 0
        while left <= right:
            mid = (left + right) // 2
            if 2 * mid * (mid + 1) * (mid * 2 + 1) >= neededApples:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans * 8

13. Greedy

13.1. Lemonade Change [2022-08-04]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        num_5 = 0
        num_10 = 0
        for i in bills:
            if i == 5:
                num_5 += 1

            if i == 10:
                num_10 += 1
                if num_5 == 0:
                    return False
                else:
                    num_5 -= 1

            if i == 20:
                if num_10 > 0 and num_5 > 0:
                    num_10 -= 1
                    num_5 -= 1
                elif num_5 > 2:
                    num_5 -= 3
                else:
                    return False
        return True

13.2. Time Needed To Buy Tickets [2022-07-10]

Simple

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        res = 0
        target = tickets[k]
        n = len(tickets)
        for i in range(n):
            if i <= k:
                res += min(tickets[i], target)
            else:
                res += min(tickets[i], target - 1)
        return res

13.3. Form Array by Concatenating Sub-arrays in Another Array [2022-07-09]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        num_row = len(groups)
        n = len(nums)

        idx = 0
        def if_find(cur_r, idx):
            num_column = len(groups[cur_r])
            for i in range(idx, n - num_column + 1):
                if groups[cur_r] == nums[i: i + num_column]:
                    return i + num_column
            return -1

        for i in range(num_row):
            idx = if_find(i, idx)
            if idx == -1:
                return False
        return True

13.4. Longest Chunked Palindrome Decomposition [2022-06-19]

hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestDecomposition(self, text: str) -> int:
        def get_sub_str(s):
            n = len(s)
            for i in range(1 , n // 2 + 1):
                if s[ : i] == s[n - i : ]:
                    return i
            return 0

        ans = 0
        while text:
            cur_sub_length = get_sub_str(text)
            if not cur_sub_length:
                return ans + 1

            text_length = len(text)
            text = text[cur_sub_length : text_length  - cur_sub_length]
            ans += 2
        return ans

13.5. Orderly Queue [2022-06-17]

Hard

When K >= 2 the minimum queue can be obtained, thus only need to sort it and do not need to know how the minimum queue is obtained.

1
2
3
4
5
class Solution(object):
    def orderlyQueue(self, S, K):
        if K == 1:
            return min(S[i:] + S[:i] for i in range(len(S)))
        return "".join(sorted(S))

14. Brute Force Search

14.1. Non-overlapping Intervals [2022-07-08]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        # sort by the end position
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        ans = 1

        for i in range(1, n):
            # do not overlap the previse interval add it
            # this is equal to reomve the interval when it is overlap with
            # the previse one
            # it is the right way, because when overlap, the interval must be
            # removed or remove at least one of added intervals and the right
            # will get larger when remove the added intervals.
            if intervals[i][0] >= right:
                ans += 1
                right = intervals[i][1]
        return n - ans

14.2. Longest Nice Substring [2022-07-05]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestNiceSubstring(self, s: str) -> str:
        n = len(s)
        maxPos, maxLen = 0, 0
        for i in range(n):
            lower, upper = 0, 0
            for j in range(i, n):
                if s[j].islower():
                    lower |= 1 << (ord(s[j]) - ord('a'))
                else:
                    upper |= 1 << (ord(s[j]) - ord('A'))
                if lower == upper and j - i + 1 > maxLen:
                    maxPos = i
                    maxLen = j - i + 1
        return s[maxPos: maxPos + maxLen]

14.3. Number of String That Appear as Substrings in Word [2022-06-17]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        ans = 0
        n = len(word)
        def check(pa):
            m = len(pa)
            for i in range(n - m + 1):
                if word[i : i + m] == pa:
                    return 1
            return 0

        for pa in patterns:
            ans += check(pa)
        return ans

14.4. Coordinate with Maximum Network Quality [2022-05-10]

An array of network towers towers is given, where towers[i]=[xi,yi,qi]towers[i] = [x_i, y_i, q_i]. xix_i and yiy_i are the integral coordinates of the network tower location and qiq_i is the network quality factor. The network quality of towers[i] at (x,y)(x, y) is qi/(1+d)q_i / (1 + d) where d=(x−xi)2+(y−yi)2d = \sqrt{(x - x_i)^2 + (y - y_i)^2}.

You are also given an integer radius. All the tower is not reachable if and only if d > radius.

The network quality of a location is the sum of network qualities from all towers. Return the location with the maximum network quality.

If there are multiple coordinates with the same network quality, return the lexicographically minimum non-negative coordinate.

Constraints:

  1. 1 <= towers.length <= 50
  2. towers[i].length == 3
  3. 0 <= xix_i, yiy_i, qiq_i <=50
  4. 1 <= radius <= 50

14.4.1. Analysis

For 0 <= xix_i, yiy_i, qiq_i <=50, if x or y is large than 51, it can not be the answer. All the network quality will be stronger when x or y is smaller. Thus, we do only need to search within [0, 51].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:
        max_signal, x, y = 0, 0, 0
        # search from small coordinate to large then we will get the small coordinate first
        for i in range(51):
            for j in range(51):
                signal_ij = 0
                for tower in towers:
                    delta_x, delta_y = tower[0] - i, tower[1] - j
                    d = math.sqrt(delta_x * delta_x + delta_y * delta_y)
                    # if > radius no quality
                    if d > radius:
                        continue
                      # use floor
                    signal_ij += math.floor(tower[2] / (1 + d))
                if signal_ij > max_signal:
                    max_signal, x, y = signal_ij, i, j
        return [x, y]

15. Flip the Char

15.1. Flip the Char [2022-06-16]

here

The position ‘max_idx’ that the number of 0 on the left hand - the number of 1 on the left hand get the maximum is the dividing line of 0 and 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        num_0 = 0
        num_1 = 0
        max_off_set = 0
        max_num_0 = 0
        max_num_1 = 0
        for idx, num in enumerate(s):
            if num == "0":
                num_0 += 1
                off_set = num_0 - num_1
                if off_set > max_off_set:
                    max_off_set = off_set
                    max_idx = idx
                    max_num_0 = num_0
                    max_num_1 = num_1
            else:
                num_1 += 1
        return num_0 - max_num_0 + max_num_1

16. Stack

16.1. Valid Parentheses [2022-06-17]

here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {')' : '(',
        '}' : '{',
        ']' : '['
        }
        res = []
        for i in s:
            if i in dic:
                if not res:
                    return False
                cur = res.pop()
                if cur != dic[i]:
                    return False
            else:
                res.append(i)
        if res:
            return False
        return True

17. Other

17.1. 缺失的第一个正整数 [2022-10-28]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        n = len(nums)
        #遍历数组
        for i in range(n):
            #数全部记为n+1
            if nums[i] <= 0:
                nums[i] = n + 1
        for i in range(n):
            #对于1-n中的数字
            if abs(nums[i]) <= n:
                #这个数字的下标标记为负数
                nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1])
        for i in range(n):
            #找到第一个元素不为负数的下标
            if nums[i] > 0:
                return i + 1
        return n + 1

17.2. Find All Numbers Disappeared in an Array [2022-10-12]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in nums:
            x = i  % n
            nums[x] += n
        res = []
        for i in range(n):
            if nums[i] <= n:
                if i == 0:
                    res.append(n)
                else:
                    res.append(i)
        return res

17.3. Rearrange Characters to Make Target String [2022-07-27]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        res = {}
        for i in target:
            if i in res:
                res[i] += 1
            else:
                res[i] = 1
        ans = {}
        for i in s:
            if i in res:
                if i in ans:
                    ans[i] += 1
                else:
                    ans[i] = 1

        out = float('inf')
        for i in res:
            if not i in ans:
                out = 0
                break
            else:
                out = min(out, ans[i] // res[i])
        return out

17.4. Buddy Strings [2022-07-21]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        res = []
        n = len(s)
        ex = set()
        two = False

        if n != len(goal):
            return False

        for i in range(n):
            if s[i] in ex:
                two = True
            else:
                ex.add(s[i])

            if s[i] != goal[i]:
                res.append(i)
        if not res and two:
            return True
        if len(res) == 2 and s[res[0]] == goal[res[1]] and s[res[1]] == goal[res[0]]:
            return True
        return False

17.5. Display Table of Food Orders in a Restaurant [2022-07-11]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
    # use dict to quickly find the food
        tables = defaultdict(lambda: defaultdict(int))
        food_set = set()
        for _, table, food in orders:
            food_set.add(food)
            tables[table][food] += 1

        res = []
        # sort the food
        food_list = sorted(food_set)
        res.append(['Table']+food_list)
        for table in sorted(tables.keys(),key=int):
            res.append([table] + [str(tables[table][item]) for item in food_list])
        return res

17.6. Minimum Cost to Set Cooking Time [2022-06-29]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        # 给定输入的最小花费
        def cost(m: int, s: int) -> int:
            if not (0 <= m <= 99 and 0 <= s <= 99):
                # 输入不合法
                return float("INF")
            digits = [m // 10, m % 10, s // 10, s % 10]
            # 寻找起始位
…                    res += moveCost
                res += pushCost
            return res

        mm, ss = targetSeconds // 60, targetSeconds % 60
        return min(cost(mm, ss), cost(mm - 1, ss + 60))   # 两种可能方案的较小值

17.7. Random Pick with Weight [2022-06-26]

Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:

    def __init__(self, w: List[int]):
        self.array = []
        res = 0
        for i in w:
            res += i
            self.array.append(res)
        self.sum = res

    def pickIndex(self) -> int:
        import numpy as np
        import bisect
        num = np.random.uniform(0, self.sum, 1)
        return bisect.bisect_left/right(self.array, num)

17.8. Intersections of Two Arrays II [2022-06-25]

Simple

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        res1 = defaultdict(lambda : 0)
        res2 = defaultdict(lambda : 0)
        for i in nums1:
            res1[i] += 1
        for i in nums2:
            res2[i] += 1
        for key in res1:
            if key in res2:
                num = min(res1[key], res2[key])
                ans += [key] * num
        return ans

17.9. Check if There is a Valid Path in a Grid [2022-06-21]

medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        res = {
        1 :[[0, -1], [0, 1]],
        2: [[-1, 0], [1, 0]],
        3: [[0, -1], [1, 0]],
        4: [[0, 1], [1, 0]],
        5: [[0, -1], [-1, 0]],
        6: [[0, 1], [-1, 0]],
        }
        n = len(grid)
        m = len(grid[0])
        if n == m == 1:
            return True

        def to_position(position, direction):
            return [position[0] + direction[0], position[1] + direction[1]]

        def reach(cur):
            pre = [0, 0]
            while cur != [0, 0] and 0 <= cur[0] < n and 0 <= cur[1] < m:
                nex1 = to_position(cur, res[grid[cur[0]][cur[1]]][0])
                nex2 = to_position(cur, res[grid[cur[0]][cur[1]]][1])
                if nex1 != pre and nex2 != pre:
                    return False
                # be careful about the position of checking if reach the destination
                # can not be after `cur = nex`, because it can be reachable only
                 # checked nex1 or nex2 == pre
                if cur == [n - 1, m - 1]:
                    return True
                nex = nex1 if nex1 != pre else nex2
                pre = cur
                cur = nex
            return False
        start = [0, 0]
        cur1 = to_position(start, res[grid[0][0]][0])
        cur2 = to_position(start, res[grid[0][0]][1])
        return reach(cur1) or reach(cur2)

17.10. Find K-th Smallest Pair distance [2022-07-06]

Hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def count(mid: int) -> int:
            # count the pairs whose distance smaller and equil to mid
            cnt = 0
            for j, num in enumerate(nums):
                # when num is the larger one in the pair
                # the number in some position could be the
                # smaller one, it must larger than num - mid
                i = bisect_left(nums, num - mid, 0, j)
                cnt += j - i
            return cnt

        nums.sort()

        # The answer must be in range(0, nums[-1] - nums[0])
        # when pick a number in the range, we count the pair of numbers
        # whose distance is smaller or equal than it.

        # for example, if number 5, 6, 7, 8 have count k - 1, k, k, k +1
        # the answer will be 6, 5 has k - 1 pairs smaller or equal
        # 6 has k, thus will have pairs distance euqal to 6, and it is
        # the top-k smallest distance.
        # there are no pair whose distance is 7

        # if  number 5, 6, 7 have count k - 10, k + 10, k + 20
        # the answer is 6, there is 20 pairs whose distace is 6, and
        # and the top-k smallest distance is in them.

        # if the number nums[-1] - nums[0] - 1  has n counts and k > n
        # then k will be nums[-1] - nums[0]
        # thus, we need to use bisect_left and do not need to exame
        # nums[-1] - nums[0]
        return bisect_left(range(nums[-1] - nums[0]), k, key=count)

17.11. Maximum Number of Visible Points [2022-06-19]

hard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        sameCnt = 0
        polarDegrees = []
        for p in points:
            if p == location:
                sameCnt += 1
            else:
                # obain all the angles the range is (-pi, pi]
                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))

        polarDegrees.sort()

        n = len(polarDegrees)
        # and 2 pi, the -pi will changed to pi, and thus -pi and pi
        # will be adjoined to each other
        # deg and deg + 2pi are both counted only if the angle is 2pi
        polarDegrees += [deg + 2 * pi for deg in polarDegrees]

        # change the degree into pi
        degree = angle * pi / 180
        # bisect_right/bisect_left require from bisect import xxxx
        # both bisect_right or bisect_left return the index that the val
        # placed in to the array and keeps the array ranked.

        # when there are numbers equal to val bisect_right places the val to the right
        # side of the equaled numbers, thus the returned value is the number of digits
        # smaller and equil to val in the array

        # bisect_left places the val to the left side of the equaled numbers. Thus the
        # returned value is the number of digits smaller to the val in the array

        # here bisect_right should be used
        maxCnt = max((bisect_right(polarDegrees, polarDegrees[i] + degree) - i for i in range(n)), default=0)
        return maxCnt + sameCnt

17.12. Number of Different Integers in a String [2022-06-17]

here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        res = set()
        cur = 0
        word += 'a'
        flag = False
        for i in word:
            if i.isdigit():
                flag = True
                cur = cur * 10 + int(i)
            else:
                if flag:
                    res.add(cur)
                    cur = 0
                    flag = False
        return len(res)

17.13. Max Length of Pair Chain [2022-06-16]

here

1
2
3
4
5
6
7
8
9
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        res  = sorted(pairs, key = lambda a: a[1])
        ans = [res[0]]
        n = len(res)
        for i in range(1, n):
            if ans[-1][-1] < res[i][0]:
                ans.append(res[i])
        return len(ans)

17.14. Two City Scheduling [2022-06-16]

here

Think about how to divide these people.

  • The gain of changing the people from one city to another is only related to the difference between the costs of a and b.
  • Thus, we can set the cost of a always 0, and set the cost of b to cost(b) - cost(a).
  • The cost of a is always 0 and we only need to pick n people to b which reach the minimum cost.
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        res = [a[1] - a[0] for a in costs]
        nn = len(res)
        sort_idx = sorted(range(nn), key = lambda k: res[k], reverse = False)
        cost = 0
        for i in range(nn // 2):
            cost += costs[sort_idx[i]][1]
        for i in range(nn // 2, nn):
            cost += costs[sort_idx[i]][0]
        return cost

17.15. Exchange LCCI [2022-06-16]

here

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def exchangeBits(self, num: int) -> int:
        num_bin = bin(num)
        n = len(num_bin)
        res = ''
        start = 2
        if n % 2:
            res += '10'
            start = 3
        for i in range(start, n, 2):
            res += num_bin[i + 1]
            res += num_bin[i]
        return int(res, 2)

17.16. The First Char which Only Appears once [2022-06-16]

The topic is here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstUniqChar(self, s: str) -> str:
        res = collections.defaultdict(lambda: [0, 1])
        for idx, c in enumerate(s):
            if not c in res:
                res[c][0] = idx
            else:
                res[c][1] += 1
        ans = " "
        min_idx = len(s)
        for i in res:
            if res[i][1] == 1 and res[i][0] < min_idx:
                min_idx = res[i][0]
                ans = i
        return ans

17.17. The Gas Station

There are n stations along a circular route, where the amount of gas at the ithi^{th} station is gas[i].

A car costs cost[i] of gas to travel from the ithi^{th} station to its next (i+1)th(i + 1)^{th} station.

Can the car run a circle. If can, return the start station. If not, return -1. If there exists a solution, it is guaranteed to be the unique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int
        n = len(gas)
        res = [0] * n
        # a car pass station i, it can get gas[i] and cost
        # cost[i]. Thus gets gas[i] - cost[i].

        # if in station i, gas[i] - cost[i] >= 0, it can
        # arrive the next station.
        # after arrive the next station, and gets the station
        # if the remain >= 0 it can gets the next next station.
        for i in range(n):
            res[i] = gas[i] - cost[i]
        first = 0
        second = 0
        sum_ = res[0]
        key = False
        # second represents the station the car already getting.
        # first represents the starting station.
        # sum_ represents if the car can get the next staion.
        # if sum_ >= 0, it can, else, it can not.
        while True:
            if sum_ >= 0:
                second += 1
                if second == n:
                    second = 0
                    key = True
                if key and second == first:
                    return first
                sum_ += res[second]
            else:
                sum_ -= res[first]
                first += 1
                # from 0 to n, first do not find an answer, return -1.
                if first == n:
                    return -1
                else:
                    if first > second:
                        second += 1
                        sum_ += res[second

Consider this, if y is the first station that the car can not arrive from x. That is to say ∑i=yxres[i]<0\sum_{i = y}^x res[i] < 0. For a station z between x and y. It can arrive z from x, which means the sum >0> 0. Then from z to y, the sum is definitely <0< 0. It can not arrive y from z.

Thus, if a car can not arrive y from x, it can not arrive y from any station between x and y. It is no need to search such stations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        res = [0] * n
        for i in range(n):
            res[i] = gas[i] - cost[i]
        first = 0
        second = 0
        sum_ = res[0]
        key = False
        while True:
            if sum_ >= 0:
                second += 1
                if second == n:
                    second = 0
                    key = True
                if key and second == first:
                    return first
                sum_ += res[second]
            else:
            # if can not arrive second + 1, then
            # starting from second + 1
                second += 1
                first = second
                # if the new starting point equal or bigger than
                # n, first move from 0 to n fails to find.
                # if key is True, second + 1 is actually larger than
                # n, first move from 0 to n fails to find.
                if first == n or key:
                    return -1
                sum_ = res[first]

17.18. Maximum Number of Tasks You Can Assign [2022-05-11]

The topic is here.

17.18.1. Analysis

  1. The task need small strength is preferred.
  2. The worker with large strength is preferred

A wrong code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        tasks.sort()
        workers.sort()
        n =  len(tasks)
        m =  len(workers)
        ans = 0
        j = 0
        for i in range(m):
            if j < n:
                # A new worker waiting for task
                if workers[i] >= tasks[j]:
                    ans += 1
                    # the task has been assigned, consider the next task
                    j += 1
                else:
                    # if there is pills avaliable
                    if pills and workers[i] + strength >= tasks[j]:
                        # use this pill
                        pills -= 1
                        ans += 1
                        j += 1
        return ans

This code prefers to use small strength workers, which is wrong. When the workers can do k tasks, it must be the top k strength workers taking the bottom k tasks.

The final answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from sortedcontainers import SortedList


class Solution:
    def maxTaskAssign(self, tasks, workers, pills, strength):
        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()

        def check(mid: int) -> bool:
            p = pills
            #  the workers needed to be check
            ws = SortedList(workers[m - mid:])
            # tasks from large to small
            for i in range(mid - 1, -1, -1):
                if ws[-1] >= tasks[i]:
                    # tasks[i] is assigned to ws[-1]
                    ws.pop()
                else:
                    if p == 0:
                        # if does not have pills anymore
                        return False
                    # has pills
                    # Note: find the smallest worker can take the task by pill
                    rep = ws.bisect_left(tasks[i] - strength)
                    if rep == len(ws):
                        return False
                    p -= 1
                    ws.pop(rep)
            return True

        # The scope of k needed to be checked if 1 checked false, answer is 0
        # if right = min(m, n) checked true, answer is right
        left, right, ans = 1, min(m, n), 0
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                # if mid is true, then ans is larger than mid
                # find it in [mid + 1, right]
                ans = mid
                left = mid + 1
            else:
                # if mid is false, then ans is smaller than mid
                # find it in [left, mid - 1]
                right = mid - 1

        return ans