DSA流程优化

算法

近几天签到题碰到蛮多流程优化的题, 简单记录下.

首先是不太清楚算法里面有没有流程优化这个概念, 不过有些题目硬撕就会TLE, 把中间的模拟过程优化出来的话可以少执行很多代码.

最简单的例子: 对一个字符串相邻位置的字符交换位置, 任务为将这个操作从字符串首执行到尾, 比如'abcd'->'bacd'->'bcad'->'bcda'. 手动模拟全过程,复杂度为O(n), 然而一旦我们注意到这个操作本质为将首字母移到末尾, 就可以s=s[1:]+s[0].

贪心算法那边会有很多这样的题, 所以我个人一直感觉贪心很吃脑子. 类似还有一些题, 这里简单记录.

1717. Maximum Score From Removing Substrings

今天的签到题.

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

  • Remove substring "ab" and gain x points.
    • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
  • Remove substring "ba" and gain y points.
    • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:
    Input: s = "cdbcbbaaabab", x = 4, y = 5
    Output: 19
    Explanation:
    - Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
    - Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
    - Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
    - Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
    Total score = 5 + 4 + 5 + 5 = 19.

Example 2:
    Input: s = "aabbaaxybbaabb", x = 5, y = 4
    Output: 20

首先分析这题是个贪心, 永远先匹配高分字符串, 再匹配低分字符串; 可以用stack来循环删除; 可以写个helper处理不同字符串情况.

bruteforce

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
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def helper(high_match, low_match, high_score, low_score):
            stack = []
            ans = 0
            for i in s:
                stack.append(i)
                if i not in ['a', 'b']:
                    new_stack = []
                    for i in stack:
                        new_stack.append(i)
                        if new_stack[-2:] == low_match:
                            ans += low_score
                            new_stack.pop()
                            new_stack.pop()
                    stack = []
                if stack[-2:] == high_match:
                    ans += high_score
                    stack.pop()
                    stack.pop()
            if stack:
                new_stack = []
                for i in stack:
                    new_stack.append(i)
                    if new_stack[-2:] == low_match:
                        ans += low_score
                        new_stack.pop()
                        new_stack.pop()
            return ans
        if x > y:
            return helper(['a', 'b'], ['b', 'a'], x, y)
        else:
            return helper(['b', 'a'], ['a', 'b'], y, x)

这是我一开始的思路, stack存串, 检测到高分直接替换出去, 然后new_stack检测低分, 全程模拟一遍, leetcode全部case跑完400+ms.

时间空间都是O(n), 看起来还行, 但其实中间包含大量尾串匹配操作, 即使是O(n), 操作时间也是不同的.

另一个做法, 直接简化中间流程, 计算统计的字符:

  1. 因为不管哪种串, 匹配到最后一定只剩下数量多的字符, 数量少的一定被匹配完了
  2. 为了同时记录相对顺序, 还得判断这些匹配里面有多少次是高分串.

count代替过程模拟

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
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        high_prefix = 'a'
        # make x > y
        if y > x:
            high_prefix = 'b'
            x, y = y, x
        count_high = 0
        count_low = 0
        count_high_low = 0
        ans = 0
        for i in s:
            if i not in 'ab':
                ans += count_high_low * x + max(min(count_high-count_high_low, count_low - count_high_low), 0) * y
                count_high = 0
                count_low = 0
                count_high_low = 0
            else:
                if i == high_prefix:
                    count_high += 1
                else:
                    count_low += 1
                    if count_high > count_high_low:
                        count_high_low += 1
        
        ans += count_high_low * x + max(min(count_high-count_high_low, count_low - count_high_low), 0) * y
        return ans

可以看到这里根本就没用到具体子过程, 全程count, 直接算出子结果加到ans, 返回即可. 执行时间从400+ms变成200+ms.

1190. Reverse Substrings Between Each Pair of Parentheses

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:
    Input: s = "(abcd)"
    Output: "dcba"

Example 2:
    Input: s = "(u(love)i)"
    Output: "iloveu"
    Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:
    Input: s = "(ed(et(oc))el)"
    Output: "leetcode"
    Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

stack(bruteforce)

最简单的思路, stack记录index, 检测到括号就翻转stack[-1]到i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def reverseParentheses(self, s: str) -> str:
        lst = list(s)
        stack = []
        n = len(s)
        for i in range(n):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                start = stack.pop()
                lst[start:i] = lst[start:i][::-1]
        ans = ''
        for i in lst:
            ans += i if i not in [')','('] else ''
        return ans

Wormhole Teleportation

天才做法, 用list记录某个idx跳转到哪, 使用curr_idx遍历, 碰到括号就去list里面找跳转点并且切换方向, 直到读到末尾.

全程不需要翻转字符串, 只有一个读字符的操作.

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 reverseParentheses(self, s: str) -> str:
        n = len(s)
        idx_lst = [0 for i in range(n)]
        stack = []
        for i in range(n):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                target = stack.pop()
                idx_lst[target] = i
                idx_lst[i] = target
        direction = 1
        curr_idx = 0
        ans = ''
        while curr_idx < n:
            if s[curr_idx] == '(' or s[curr_idx] == ')':
                direction = -direction
                curr_idx = idx_lst[curr_idx]
            else:
                ans += s[curr_idx]
            curr_idx += direction
        return ans

1823. Find the Winner of the Circular Game

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

  1. Start at the 1st friend.
  2. Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
  3. The last friend you counted leaves the circle and loses the game.
  4. If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
  5. Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

这题还有个说法是处刑犯人, 每隔k个人处死一个, 最后一个豁免, 问谁能活下去.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:
    Input: n = 5, k = 2
    Output: 3
    Explanation: Here are the steps of the game:
    (1) Start at friend 1.
    (2) Count 2 friends clockwise, which are friends 1 and 2.
    (3) Friend 2 leaves the circle. Next start is friend 3.
    (4) Count 2 friends clockwise, which are friends 3 and 4.
    (5) Friend 4 leaves the circle. Next start is friend 5.
    (6) Count 2 friends clockwise, which are friends 5 and 1.
    (7) Friend 1 leaves the circle. Next start is friend 3.
    (8) Count 2 friends clockwise, which are friends 3 and 5.
    (9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2:
    Input: n = 6, k = 5
    Output: 1
    Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

simulation

1
2
3
4
5
6
7
8
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        arr = [i for i in range(1,n+1)]
        idx = 0
        while len(arr) != 1:
            idx = (idx + k - 1) % len(arr)
            arr.pop(idx)
        return arr[0]

这还算改过的, 最初的应该是全程模拟, 遍历k, 然后arr.append(arr.pop(0))

Josephus problem

存在公式

\[ g(n,k) = (g(n-1,k)+k) mod n \]

其中g(1,k) = 0

因此我们代码可以这么写

1
2
3
4
5
6
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        winner = 0
        for i in range(2, n + 1):
            winner = (winner + k) % i
        return winner + 1

552. Student Attendance Record II

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

  • 'A': Absent.
  • 'L': Late.
  • 'P': Present.

Any student is eligible for an attendance award if they meet both of the following criteria:

  • The student was absent ('A') for strictly fewer than 2 days total.
  • The student was never late ('L') for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 10^9 + 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:
    Input: n = 2
    Output: 8
    Explanation: There are 8 records with length 2 that are eligible for an award:
    "PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
    Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).

Example 2:
    Input: n = 1
    Output: 3

Example 3:
    Input: n = 10101
    Output: 183236316

dp

这题的dp我就没读, 写的都挺复杂的.

官方解

状态机

维护一个有限状态自动机即可, 状态切换都记录上去即可. 转换过程可以自己画图, 贴一个别人的记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// https://leetcode.com/problems/student-attendance-record-ii/solutions/5210986/0-skill-100-hard-work-faster-than-95-memory-less-than-99-38

//NOW STATE-|-------  NEXT STATE ---------|
//0: 0A 0L => P: 0A0L    A: 1A0L   L: 0A1L
//1: 0A 1L => P: 0A0L    A: 1A0L   L: 0A2L
//2: 0A 2L => P: 0A0L    A: 1A0L   L: X
//3: 1A 0L => P: 1A0L    A: X      L: 1A1L
//4: 1A 1L => P: 1A0L    A: X      L: 1A2L
//5: 1A 2L => P: 1A0L    A: X      L: X
//    every turn
//0A0L =0+1+2
//0A1L =0
//0A2L =1
//1A0L =0+1+2+3+4+5
//1A1L =3
//1A2L =4
1
2
3
4
5
6
7
class Solution:
    def checkRecord(self, n: int) -> int:
        state = [1,1,0,1,0,0]
        mod = 10**9 + 7
        for _ in range(n-1):
            state = [sum(state[:3]) % mod, state[0], state[1], sum(state) % mod, state[3], state[4]]
        return sum(state) % mod

一行代码解决的智力题

这里只放一个我看过的repo, 之前搜并查集的时候看到的.

一行代码就能解决的算法题