2024/3/31
# 二重ループにならないで済む実装がないか考える
円周率の小数点以下に、0~9が各何回出るか数える
０~9に関してループして、それぞれ頭からお尻まで見ると二重ループ
頭からお尻まで見ながら、今見てる数のグループのcntを+1すれば一回の確認ですむ。
問題のリンクは忘れた。
# ３個前のアルファベットにするシーザー暗号
単純にord()とchr()使うと、aやbやcが溢れる。aはzに変換。という例外を持たせた関数を3回走らせるようにすれば、例外の記述はaの時だけですむ。(自分で実装した時はordが96以下の時+26する、という対応表見ながらじゃないとわからないマジックナンバー入りの実装になってた。)
algo-method.com
chr() とord()
ord()の方が文字コードの数字を返してくれる。chr()はその逆
listのアンパック
mylist=[1,2,3]
print(*mylist)
→1 2 3
printは複数個をカンマ区切りで渡せて、その場合空白スペース区切りで表示する
print()したときに下記のような変のものが出る時
<__main__.Tortoise object at 0x...>
これは、自作したTortoiseクラスのインスタンスをprintしようとしている
Tortoiseクラスのインスタンスは、print()されたときにどういう挙動すべきか定義されてないからこうなる。
逆にいうと、他のstringとかlistとかもクラスであり、それらはprint()された時の挙動が最初から定義されているから、直感的なprint()による表示ができる。
定義するには__str__ メソッドを使う
def __str__(self):
return f"name: {self.name}"
https://algo-method.com/tasks/1278
# defaultdictが便利。辞書作るときに初期値に何か設定しておけるので、後からいじりやすい。
from collections import defaultdict
votes = ["aruru", "iruru", "ururu", "aruru", "eruru", "oruru", "aruru", "iruru", "aruru", "eruru", "iruru", "ururu", "eruru"]
d = defaultdict(int) # 空の辞書型変数
for vote in votes: # 投票された立候補者に 1 を足す
d[vote] += 1
# 投票結果を出力
for name, value in d.items():
https://algo-method.com/tasks/1294
#順列や組み合わせを出す時はiteretoolsを使う
nPr nCr
iteretools.permutations(iterable, r)
itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.12.2 ドキュメント
https://algo-method.com/tasks/1315/editorial
# str.join(iterable)で iterableの各要素をstrを間に入れてくっつけられる
# 空白文字で複数入力があるときはsplitだけど、改行されて２個入力されるときは普通に２つinput()作る
S = input()
T = input()
if S == T:
print("Yes")
else:
print("No")
#こうではない
S, T = map(int, input().split())
https://algo-method.com/tasks/31
# popは要素へのアクセスと削除を同時に行う
# 可変長配列であるlistから特定の順番の要素を削除したり、追加したりするのは時間がかかる
- 先頭要素を消したら、それより後ろの要素全てを前に詰めてindex振り直すみたいな作業が必要
- 先頭要素を追加しても一緒。
- 逆に末尾に削除したり追加したりする分には、既存のものに影響ないからO(1)
- なので先頭に足したりしたい時は、反転してから足すと良い
- ちなみに反転はO(n)。後ろの要素から一個ずつ新しいリストに足したく感じかな？
https://algo-method.com/tasks/832
2024/4/13
配列の要素削除/挿入がO(N)なのは何故か
・配列はメモリの中で連続したアドレスにデータを配置
→ランダムアクセスがO(1)
→mylist[i]のアドレスを下記の式でパッと1回で計算できるので、そのメモリにたどり着ける
mylist[i]のアドレス ＝ 先頭のアドレス ＋ 1データのサイズ*i
逆に、連続したアドレスにデータ入れとかないといけないので、途中で一個抜いたりすると、それより後のやつを全部前にずらさないといけなくてO(N)
→liked listなら、O(1)で済む
tech.connehito.com
* 演算子で、ミュータブルな型を並べたリストを作成する場合、参照渡しによるコピーに気をつける必要がある。
ミュータブルな型(リストとか)に対して、*を使うと、参照渡しによるコピーになる
# 「0 を 3 回繰り返したリスト」を 2 回繰り返したリスト
2# 各要素の内容は実は同じもの
3a = [[0] * 3] * 2
4print(a) # 出力: "[[0, 0, 0], [0, 0, 0]]"
5
6a[0][0] = 1 # 0 番目のリストの 0 番目の要素を 1 に変更する
7print(a) # 出力: "[[1, 0, 0], [1, 0, 0]]"
リスト内包表記によるコピーで防ごう。
# 「0 を 3 回繰り返したリスト」を 2 回生成して追加したリスト
2# 各要素の内容は独立している
3a = [[0 for j in range(3)] for i in range(2)]
4print(a) # 出力: "[[0, 0, 0], [0, 0, 0]]"
5
6a[0][0] = 1 # 0 番目のリストの 0 番目の要素を 1 に変更する
7print(a) # 出力: "[[1, 0, 0], [0, 0, 0]]"
algo-method.com
# リストへの*演算子の適用
・リストの中身を繰り返した新たなリストを作成する
