問題2.2
夕飯休憩中にもう1問。
テキストだと再帰で解いてますね。
まぁなんとなく分かるけど、再帰って頭こんがらがるんですよね。。。
ってことで地味な方法でやります。
問題
単方向連結リストにおいて、末尾から数えてk番目の要素を見つけるアルゴリズムを実装してください。
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def index_from_last(linked_list, offset_from_last): ''' 単方向リスト中で、末尾から数えてoffset_from_last番目の要素を取得する関数 # リストの先頭セル取得 >>> linked_list = LinkedList() >>> linked_list.insert(0, 'a') >>> linked_list.insert(1, 'b') >>> linked_list.insert(2, 'c') >>> linked_list.insert(3, 'd') >>> linked_list.insert(4, 'e') >>> linked_list.insert(5, 'f') >>> index_from_last(linked_list, 2) 'e' ''' cell = linked_list.get_top() # リストの長さ取得 list_length = 1 while cell.get_next(): list_length += 1 cell = cell.get_next() # 指定セルの取得 cell = linked_list.get_top() offset = list_length - offset_from_last for counter in range(0, offset): cell = cell.get_next() return cell.get_data() def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題2.1
昨日、作りながら寝落ちしたので、昼休みに残り完成。
時間切れなので、発展問題は検討すらしてないです。
問題
ソートされていない連結リストから、重複する要素を削除するコードを書いてください。
発展問題
もし、一時的なバッファが使用できないとすれば、どうやってこの問題を解きますか？
pylist.py (短方向連結リスト)
#encoding: utf-8 class Cell: ''' リストを構成するセルを表すクラス >>> cell = Cell(5) >>> print cell.get_data() 5 >>> print cell.get_next() None >>> cell.set_data('a') >>> print cell.get_data() a >>> cell.set_next(10) >>> print cell.get_next() 10 ''' def __init__(self, data, next=None): self.data = data self.next = next # セルのデータ取得 def get_data(self): return self.data # セルが指す次のセルのポインタ取得 def get_next(self): return self.next # セルのデータを更新 def set_data(self, data): self.data = data # セルが指す次のセルのポインタ更新 def set_next(self, next): self.next = next class LinkedList: ''' 連結リストクラス >>> linked_list = LinkedList() >>> linked_list.get_top() >>> linked_list.insert(0, 100) >>> print linked_list.index(100) 0 >>> linked_list.get_top().get_data() 100 >>> linked_list.insert(1, 200) >>> print linked_list.index(200) 1 >>> linked_list.insert(1, 150) >>> print linked_list.index(150) 1 >>> print linked_list.index(200) 2 >>> linked_list.delete(2) True >>> linked_list.index(200) -1 >>> linked_list.index(150) 1 >>> linked_list.delete(0) True >>> linked_list.index(150) 0 >>> linked_list.delete(0) True >>> linked_list.delete(0) False ''' def __init__(self): self.top = None # リストの先頭セルを取得 def get_top(self): return self.top # dataに示すデータがリストの何番目かを取得 def index(self, data): offset = 0 cell = self.top while cell: if cell.get_data() == data: return offset offset += 1 cell = cell.get_next() return -1 # リストのoffset番目にdataを格納 def insert(self, offset, data): # offsetが0もしくはリストが空の時 if offset == 0 or not self.top: self.top = Cell(data, self.top) else: cell = self.top while cell.get_next(): offset -= 1 if offset == 0: break cell = cell.get_next() # 新たにセルを作成し、リストに挿入する added_cell = Cell(data, cell.get_next()) cell.set_next(added_cell) # リストのoffset番目を削除 def delete(self, offset): # リストの先頭を削除 if offset == 0: # リストにデータが1つ以上ある if self.top: self.top = self.top.get_next() return True else: return False else: cell = self.top while cell.get_next(): offset -= 1 if offset == 0: # 対象のセルをリストから外す cell.set_next(cell.get_next().get_next()) return True cell = cell.get_next() return False def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
2-1.py (重複の削除)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def erase_duplication(linked_list): ''' リスト中の重複セルを削除 >>> linked_list = LinkedList() >>> linked_list.insert(0, 100) >>> linked_list.insert(1, 200) >>> linked_list.insert(2, 300) >>> linked_list.insert(3, 200) >>> linked_list.insert(4, 100) >>> linked_list.insert(5, 500) >>> linked_list.index(500) 5 >>> erase_duplication(linked_list) >>> linked_list.index(500) 3 ''' # 重複セルチェック用のハッシュテーブル hash_table = {} # 重複セルのチェック counter = 0 cell = linked_list.get_top() while cell.get_next(): # 重複セルは削除 if cell.get_data() in hash_table: # 重複セルを削除する前に、次のセルを指定 cell = cell.get_next() linked_list.delete(counter) counter -= 1 else: hash_table[cell.get_data()] = True cell = cell.get_next() counter += 1 # リストの最後のセルの処理 if cell.get_data() in hash_table: linked_list.delete(counter + 1) def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題1.8
これもまぁ解けたけど、面接とかでいきなり解けって言われたら思いつかないかも。
いやー、思った以上に脳が腐ってきてる。笑。
問題
片方の文字列が、もう片方の文字列の一部分になっているかどうかを調べるメソッド「isSubstring」が使えると仮定します。2つの文字列s1とs2が与えられたとき、isSubstringメソッドを一度だけ使ってs2がs1を回転させたものかどうかを判定するコードを書いてください(たとえば、「waterbottle」は「erbottlewat」を回転させたものになっています)。
#encoding: utf-8 def is_rotated_strs(str1, str2): ''' str2がstr1を回転させた文字列かどうかをチェックする関数 >>> is_rotated_strs('waterbottle', 'erbottlewat') True >>> is_rotated_strs('waterbottle', 'erbottlewta') False ''' # str1を2つ連結。str2を含めば、str1を回転させた文字列。 if is_substring(str1 + str1, str2) is True: return True else: return False def is_substring(str1, str2): ''' str2がstr1の一部分であるかどうかをチェックする関数 >>> is_substring('helloworld', 'hello') True >>> is_substring('helloworld', 'helo') False >>> is_substring('helloworld', 'olleh') True ''' # str2がstr1の一部分かをチェック for counter in range(0, len(str1) - len(str2)): if str1[counter:counter + len(str2)] == str2: return True elif str1[counter:counter + len(str2)] == str2[::-1]: return True return False def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題1.5
ちょっと汚いかも。まぁ。。。
問題
文字の連続する数を使って基本的な文字列処理圧縮を行うメソッドを実装してください。たとえば、「aabcccccaaa」は「a2b1c5a3」のようにしてください。もし、圧縮変換された文字列が元の文字列よりも短くならなかった場合は、元の文字列を返してください。
#encoding: utf-8 def compress_string(string): ''' 引数で渡された文字列を圧縮する関数 >>> compress_string('aabcccccaaa') 'a2b1c5a3' >>> compress_string('abcd') 'abcd' ''' # 圧縮した文字列 compressed_string = '' # 引数で渡された文字列をリストに変換 char_list = list(string) # 圧縮不可であれば、引数で渡された文字列をそのまま返す if _is_compressable(char_list) is False: return string # 圧縮処理 counter = 0 char_counter = 0 char_list_size = len(char_list) current_last_char = char_list[0] while counter < char_list_size: if char_list[counter] == current_last_char: char_counter = char_counter + 1 else: compressed_string \ = compressed_string + current_last_char + str(char_counter) char_counter = 1 current_last_char = char_list[counter] counter = counter + 1 # 文字リスト中の最後の連続する文字を付け加えてリターン return compressed_string + current_last_char + str(char_counter) def _is_compressable(char_list): ''' 引数で渡された文字リストが圧縮可能かどうかのチェック >>> _is_compressable('aaa') True >>> _is_compressable('abc') False ''' counter = 0 char_list_size = len(char_list) while counter < (char_list_size - 1): if char_list[counter] == char_list[counter + 1]: return True counter = counter + 1 return False def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
ほいじゃ、走ってくる。
問題1.7
寝る前に一問。
問題
MxNの行列について、要素が0であれば、その行と列のすべてを0にするようなアルゴリズムを書いてください。
#encoding: utf-8 def initialize_with_zero(matrix): ''' 引数で受け取ったMxNの行列で、要素が0であれば、その行と列の全てを0にする関数 >>> initialize_with_zero([[1, 1, 1], [1, 0, 1], [1, 1, 1]]) [[1, 0, 1], [0, 0, 0], [1, 0, 1]] >>> matrix = [[0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 0]] >>> initialize_with_zero(matrix) [[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]] ''' # 要素が0である箇所を記憶するリスト zero_list = [] # 要素が0である箇所を探す for row_counter in range(0, len(matrix)): for column_counter in range(0, len(matrix[0])): if matrix[row_counter][column_counter] == 0: zero_list.append({'row_counter': row_counter, 'column_counter': column_counter}) # 要素が0である箇所の列と行を全て0にする for zero_target in zero_list: for row_counter in range(0, len(matrix)): matrix[row_counter][zero_target['column_counter']] = 0 for column_counter in range(0, len(matrix[0])): matrix[zero_target['row_counter']][column_counter] = 0 return matrix def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
備考
計算量的によくない解き方だったようです。計算量がO(MN)となる。
要素が0の箇所を行と列で記憶するんじゃなくて、要素が0を含む行、要素が0を含む列で記憶しておけば、
0をセットする時にもっとシンプルになりますね。。。
問題1.6
あー。マトリクスとか、面倒すぎる。
この辺、普段から頭使ってないと、咄嗟に出来ないなー。
Numpy使っちゃいたくなるよね。。。
問題
NxNの行列に書かれた、1つのピクセルが4バイト四方の画像があります。その画像を90度か移転させるメソッドを書いてください。あなたはこれを追加の領域なしでできますか？
#encoding: utf-8 def rotate_matrix_90_degrees(matrix): ''' 引数で受け取ったNxNの行列を90度回転する >>> rotate_matrix_90_degrees([[0, 1, 2], [3, 4, 5], [6, 7, 8]]) [[6, 3, 0], [7, 4, 1], [8, 5, 2]] ''' # 引数で受け取った２次元配列のサイズ取得 matrix_size = len(matrix) matrix_last = matrix_size - 1 # 行列を90度回転 layer = 0 while layer < (matrix_size / 2): first_pos = layer last_pos = matrix_last - layer for counter in range(first_pos, last_pos): offset = counter - first_pos # 上端の一時保存 tmp_top = matrix[first_pos][counter] # 左端を上端に移動 matrix[first_pos][counter] = matrix[last_pos - offset][first_pos] # 下端を左端に移動 matrix[last_pos - offset][first_pos] \ = matrix[last_pos][last_pos - offset] # 右端を下端に移動 matrix[last_pos][last_pos - offset] = matrix[counter][last_pos] # 上端の一時保存を左端に移動 matrix[counter][last_pos] = tmp_top counter = counter + 1 layer = layer + 1 return matrix def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
問題1.4
はいはい。サクサクっとね。
問題
文字列内に出現するすべての空白文字を"%20"で置き換えるメソッドを書いてください。ただし、文字列の後ろには新たに文字を追加するためのスペースが十分にある(バッファのサイズは気にしなくてもよい)ことと、その追加用スペースをのぞいた文字列の真の長さが与えられます(注意:Javaで実装する場合は、追加の領域を使用せずに処理できるよう文字配列を使ってください)。
#encoding: utf-8 def convert_space_in_string(str): ''' 先頭と末尾以外の連続する空白を%20に変換する関数 >>> convert_space_in_string('Mr John Smith ') 'Mr%20John%20Smith' ''' # 変換後の文字列 converted_string = '' # 引数で渡された文字列を空白で分割した文字列のリストに入れる splited_strs_list = str.split() # 分割した文字列リストを'%20'を挟んだ文字列に置き換える。 for splited_str in splited_strs_list: converted_string = converted_string + splited_str + r'%20' # 文字列の後ろに'%20'がついたままなので、その部分をカット return converted_string[0:len(converted_string) - 3] def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
さて、寝ます。
