Pythonで世界で闘うプログラミング力を鍛える[chap01]
大学生です。
「世界で闘うプログラミング力を鍛える本」を進めていこうかと思います。
技術力がなく、どこにも就職ができないと思ったのでプログラミングを勉強して行こうかと思います。特にGAFAに入りたいという気持ちがあるわけではありませんが、GAFAを狙うような人が使っている本だと思うとやる気が出てくるのでこの本がいいと思いました。ただ問題を解くのではなくブログにプログラムをあげることで、他人に見られるかもというプレッシャーを少しでも感じながらやって行こうと思います。
今回はChapter1[配列と文字列]をやっていきます。
ちなみに、公式（？）の答えはここにあります。
1.1 重複のない文字列
# O(n) def is_unique(st): # アスキーのとき if len(st) > 128: return False char_set = set() for s in st: if s not in char_set: char_set.add(s) else: return False return True # O(n^2) 追加メモリなし def is_unique2(st): # アスキーのとき if len(st) > 128: return False for i in range(len(st)-1): for j in range(i+1, len(st)): if st[i] == st[j]: return False return True if __name__ == "__main__": print('aiueo', is_unique('aiueo')) print('aiuea', is_unique('aiuea'))
1.2 順列チェック
# O(n) def is_reordering(st1, st2): if len(st1) != len(st2): return False char_dic = {} for s in st1: if s in char_dic: char_dic[s] += 1 else: char_dic[s] = 1 for s in st2: if s not in char_dic: return False else: if char_dic[s] < 1: return False else: char_dic[s] -= 1 return True # O(nlogn) 追加メモリなし def is_reordering2(st1, st2): if len(st1) != len(st2): return False else: return sorted(st1) == sorted(st2) if __name__ == "__main__": print('abecd', 'edcba', is_reordering('abecd', 'edcba'), is_reordering2('abecd', 'edcba')) print('abecdf', 'edcba', is_reordering('abecdf', 'edcba'), is_reordering2('abecdf', 'edcba')) print('abecd', 'edcbf', is_reordering('abecd', 'edcbf'), is_reordering2('abecd', 'edcbf')) print('abecd', 'abecd', is_reordering('abecd', 'abecd'), is_reordering2('abecd', 'abecd'))
1.3 URLify
def urlify(lst, n): space_count = 0 for s in lst: if s == ' ': space_count += 1 lst += list(' ' * (space_count*2)) idx = n + space_count*2 - 1 for i in reversed(range(n)): if lst[i] == ' ': lst[idx-2:idx+1] = list('%20') idx -= 2 else: lst[idx] = lst[i] idx -= 1 return lst def print_lst(lst): print(''.join(lst)) return if __name__ == "__main__": lst = list('fdaf fdafdas fafdkjk') print_lst(lst) print_lst(urlify(lst, len(lst)))
1.4 回文の順列
from collections import Counter from collections import defaultdict # O(n) def is_palindrome(st): st = st.lower() char_dic = Counter() for s in st: if 'a' <= s <= 'z': continue char_dic[s] += 1 flg = False for v in char_dic.values(): if v % 2 != 0: if flg: return False else: flg = True return True # O(n) def is_palindrome2(st): st = st.lower() char_dic = Counter() odd_cnt = 0 for s in st: if 'a' <= s <= 'z': continue char_dic[s] += 1 if char_dic[s] % 2 != 1: odd_cnt += 1 else: odd_cnt -= 1 return odd_cnt <= 1 if __name__ == "__main__": print(is_palindrome('Tact Coa')) print(is_palindrome2('Tact Coa'))
1.5 一発変換
def is_edit(str1, str2): cnt = 0 for s1, s2 in zip(str1, str2): if s1 != s2: cnt += 1 if cnt > 1: return False return True def is_add(str1, str2): if len(str1) > len(str2): return False cnt = 0 idx = 0 for i in range(len(str1)): if str1[i] != str2[idx]: idx += 1 if (idx-i) > 1: return False idx += 1 return True def is_one_operation(str1, str2): if abs(len(str1)-len(str2)) > 1: return False elif str1 == str2: return True elif len(str1) == len(str2): return is_edit(str1, str2) else: return is_add(str1, str2) or is_add(str2, str1) if __name__ == "__main__": str1 = 'pale' str2 = 'pal' print(str1, str2, is_one_operation(str1, str2))
1.6 文字列圧縮
# Bad 文字列の連結には O(n^2) def compress(st): new = st[0] pre = st[0] cnt = 1 for c in st[1:]: if pre == c: cnt += 1 else: new += str(cnt)+c cnt = 1 pre = c new += str(cnt) return new if len(st)>len(new) else st def compress2(st): cnt = 0 new = list() for i in range(len(st)): cnt += 1 if i+1 >= len(st) or st[i]!=st[i+1]: new.append(st[i]) new.append(str(cnt)) cnt = 0 return ''.join(new) if len(st)>len(new) else st if __name__ == '__main__': print(compress('aabcccccaaa')) print(compress2('aabcccccaaa')) print(compress('abcdefefefff')) print(compress2('abcdefefefff'))
1.7 行列の回転
# 計算量O(n^2) 追加領域O(n^2) def rotate_matrix(mat): col = len(mat) row = col new = [[-1]*row for _ in range(col)] for i in range(col): for j in range(row): new[i][j] = mat[col-1-j][i] return new # 計算量O(n^2) 追加領域O(1) def rotate_matrix2(mat): col = len(mat) row = col for i in range(int(col/2)): for j in range(i, row-1-i): tmp = mat[i][j] mat[i][j] = mat[col-j-1][i] mat[col-j-1][i] = mat[col-i-1][row-j-1] mat[col-i-1][row-j-1] = mat[j][row-i-1] mat[j][row-i-1] = tmp def print_matrix(mat): for i in range(len(mat)): print(mat[i]) print() if __name__ == '__main__': n = 8 mat = [[n*i+j for j in range(n)] for i in range(n)] print_matrix(mat) new = rotate_matrix(mat) print_matrix(new) rotate_matrix2(mat) print_matrix(mat)
1.8 ゼロの行列
# 計算量O(mn) 追加領域O(mn) def zero_padding(mat): f_row = set() f_col = set() for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j] == 0: f_col.add(i) f_row.add(j) for i in range(len(mat)): for j in range(len(mat[0])): if i in f_col or j in f_row: mat[i][j] = 0 # 計算量O(mn) def zero_padding2(mat): row_has0 = False col_has0 = False if 0 in mat[0]: row_has0 = True if 0 in [m[0] for m in mat]: col_has0 = True for i in range(1, len(mat)): for j in range(1, len(mat[0])): if mat[i][j] == 0: mat[i][0] = 0 mat[0][j] = 0 for i in range(1, len(mat)): for j in range(1, len(mat[0])): if mat[i][0]==0 or mat[0][j]==0: mat[i][j] = 0 if row_has0: for j in range(len(mat[0])): mat[0][j] = 0 if col_has0: for i in range(len(mat)): mat[i][0] = 0 def print_matrix(mat): for i in range(len(mat)): print(mat[i]) print() if __name__ == '__main__': mat = [[1, 4, 0, 3], [2, 4, 2, 1], [1, 4, 5, 3]] print_matrix(mat) zero_padding(mat) print_matrix(mat) mat = [[1, 4, 0, 3], [2, 4, 2, 1], [1, 4, 5, 3]] zero_padding2(mat) print_matrix(mat)
1.9 文字列の回転
def is_rotate(st1, st2): if len(st1) != len(st2): return False return st1 in st2*2 if __name__ == '__main__': st1 = 'waterbottle' st2 = 'erbottlewat' print(st1, st2, is_rotate(st1, st2)) st1 = 'raspberrypi' st2 = 'berrypirass' print(st1, st2, is_rotate(st1, st2))
