1. e289.美麗的彩帶 + dict
    1. 題目
    2. 解題
    3. dict用法

e289.美麗的彩帶 + dict

最後更新: 作者: 字数: 435 预计阅读时间: 1min

e289.美麗的彩帶 + dict

APCS歷屆

題目

url
來看一下題目，簡單來說就是會給你一條五彩繽紛的彩帶，如果連續m個不一樣顏色就代表漂亮度+1。

解題

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
# 用dic
# 起初先用m個在裡面 固定用get 去察看是否在 在的話+= 1
from sys import stdin
def fun():
    global dic, idx, ans
    if dic.get(list1[idx]) > 1:
        dic[list1[idx]] -= 1
    else:
        dic.pop(list1[idx])
    if idx + m < n:
        if dic.get(list1[idx + m]) == None:
            #print("a")
            dic[list1[idx + m]] = 1
        else:
            #print("b")
            dic[list1[idx + m]] += 1
        #print(dic)
        idx += 1
        if len(dic) == m:
            #print(dic)
            ans += 1
    else:
        print(ans)
        exit()

m, n = 3, 7
list1 = [1, 2, 3, 5, 4, 5, 4]
m, n = map(int, stdin.readline().split())
list1 = list(map(int, stdin.readline().split()))
dic = dict()
idx = 0
ans = 0
for i in range(m):
    if dic.get(list1[i]) == None:
        dic[list1[i]] = 1
    else:
        dic[list1[i]] += 1
#print(dic)
if len(dic) == m:
    ans += 1

while True:
    fun()

這個解法其實蠻重要的會很常用到可以稍微練一下，簡單來說我們會用到一個叫做字典的資料結構，然後我們要用一個window，簡單來說就是我們一開始window會包含m個數字，我們用dict去紀錄那m個數字中有哪些數字像這樣:3:1, 2:2，這就代表3有一個2有兩個，那如果沒有重複我們就照著題目答案+1，不然就移動window，將最前面的拔掉，後面加上一個，只是要注意那個數字是不是在window中的唯一。

dict用法

字典是一個常見的資料結構，跟日常生活的字典很像，一個key對上一個東西:

1
2
3
4
5
# python用法
dic = dict()
dic["a"] = 1 #新增或更改
dic.pop("a") #del
dic.get("b") #沒有則回傳None