求IXL Message ABC经典面经的具体题目内容

紫薯紫薯紫薯紫薯

坂道的途中 发表于 2022-12-21 23:51
找到·原来发的答案，应该是work的：
第三题我是用stack做的，用三个stack去分别存A，B和C，如果发现stack ...

三个stack的话这个test case怎么过啊
a1 a2 a3 b b b c2 c1 c3

def process_logs(logs):
    a_logs = set()
    b_indexes = []
    for i in range(len(logs)):
        log = logs[i]
        if log[0] == "A":
            client_id = log[1]
            a_logs.add(client_id)
        if log[0] == "B":
            b_indexes.append(i)
        if log[0] == "C":
            client_id = log[1]
            if client_id in a_logs:
                a_logs.remove(client_id)
                b_index = b_indexes.pop(0)
                logs[b_index] = "B" + str(client_id)

    return logs

直接这样不可以吗？更直接的方式
我们只在乎A的client id
只在乎C出现的时候的client id
中间包起来的第一个B自然会去update成最先被AC包起来的id

微信用户_26dd9aa 发表于 2024-4-12 03:41
def process_logs(logs):
    a_logs = set()
    b_indexes = []

其他地方看到这个follow up：输入有可能missing A和B，比如 A1 B C2 C1 这种 ，C2对应的A2 B2丢了，但还是valid的然后填充B的id成A1 B1 C2 C1

这种情况怎么解决

微信用户_26dd9aa 发表于 2024-4-12 03:41
def process_logs(logs):
    a_logs = set()
    b_indexes = []

['A1', 'B', 'A3', 'B', 'A2', 'C3', 'C1', 'B', 'C2'] 这种情况就不太对

sicheng2022 发表于 2023-2-7 18:32
为什么要用stack不能用queue 一直没想明白？

应为这题的greedy解法需要forward greedy，不能反向greedy

1. testCase1 = "A2 B A1 B C2 C1"
   
2. testCase2 = "A2 A1 B C2 B C1"
   
3. 
   
4. // forward greedy solution, time: O(n)
   
5. def decodeMessage(log: str) -> str:
   
6.     # figure out the A that needs assign, and the location of B
   
7.     a_map = {} # key: number, value: array of letter that we have encountered
   
8.     b_arr = []
   
9.     log_arr = log.split(" ")
   
10.     for i in range(len(log_arr)):
    
11.         l = log_arr[i]
    
12.         # only B without number
    
13.         if len(l) == 1:
    
14.             # input to another array to be used later
    
15.             b_arr.append(i)
    
16.             
    
17.         # letter with number
    
18.         elif len(l) == 2:
    
19.             c = l[0]
    
20.             num = l[1]
    
21.             
    
22.             if c == 'A':
    
23.                 if num not in a_map:
    
24.                     a_map[num] = []
    
25.                 a_map[num].append('A')
    
26.             
    
27.             if c == 'C':
    
28.                 if len(a_map[num]) == 2:
    
29.                     del a_map[num]
    
30.             
    
31.     print(a_map)
    
32.             
    
33.     for i in range(len(log_arr)):
    
34.         l = log_arr[i]
    
35.         if len(l) == 2:
    
36.             c = l[0]
    
37.             num = l[1]
    
38.             if c == 'A' and num in a_map:
    
39.                 log_arr[b_arr[0]] += num
    
40.                 print(log_arr[b_arr[0]])
    
41.                 b_arr.pop(0)
    
42.    
    
43.     ret = " ".join(log_arr)
    
44.     return ret
    
45. 
    
46. ret = decodeMessage(testCase1)
    
47. print(ret)
    
48. ret = decodeMessage(testCase2)
    
49. print(ret)
    

复制代码

坂道的途中 发表于 2022-12-22 06:51
找到·原来发的答案，应该是work的：
第三题我是用stack做的，用三个stack去分别存A，B和C，如果发现stack ...

谢谢啦，思路牛逼

另外用queue其实也可以，而且更符合直觉。谢谢贡献思路。 加米了