AtCoder-cli(online-judge-tools)を導入しようとして詰まった
TL;DR
なんかOpenSSLのバージョン関係で詰まったが、urllib3のバージョンを2.x => 1.xにしたらいけた。
AtCoder-cliを導入しようとして詰まった
2ヶ月弱くらい何も分からないながらABCに参加していて、そろそろ手元でテストとか提出とかできるように整備したいなと思った。
そこで、この辺りの情報を参考にさせていただいて導入を進めたものの、少々詰まってしまったので備忘録として残しておく。
どう詰まったか
online-judge-toolsをpip installし、Successしたのでoj -hで動作確認しようとしたところ下記のエラーになった。
ImportError: urllib3 v2.0 only supports OpenSSL 1.1.1+, currently the 'ssl' module is compiled with LibreSSL 2.8.3. See: https://github.com/urllib3/urllib3/issues/2168
環境構築時のエラーには未だに冷静でいられない。。
Issueを読む
See: https://github.com/urllib3/urllib3/issues/2168とあるので、とりあえずは見てみる。
OpenSSLとurllib3についての記述があり、このIssueでこのエラーが追加されたことがわかる。
多分OpenSSLのバージョンの話だと思う。
試行錯誤
OpenSSLのバージョンを上げる
Mac OSに入っていたsslをそのまま使っていたのでHomebrew経由でインストールし、それを使用するようにPATHも通したが、ダメだった。。
urllib3のバージョンを下げる
当該issueを見ると、urllib3 2.0以上を使っててOpen SSL<1.1.1だとまずいみたいなことが書いてある（と思う）。
そこで上ではOpenSSLのバージョンを上げたつもりだったが、特にエラーは変わらなかった。
なので試しにurllib3のバージョンを下げてみた。
pip3 install 'urllib3<2.0'
(中略)
oj -h
usage: oj [-h] [-v] [-c COOKIE] [--version] {download,d,dl,login,l,submit,s,test,t,generate-output,g/o,generate-input,g/i,test-reactive,t/r,test-interactive,t/i} ...
Tools for online judge services
positional arguments:
{download,d,dl,login,l,submit,s,test,t,generate-output,g/o,generate-input,g/i,test-reactive,t/r,test-interactive,t/i}
for details, see "/Users/masa/Library/Python/3.9/bin/oj COMMAND --help"
download (d, dl) download sample cases
login (l) login to a service
submit (s) submit your solution
test (t) test your code
generate-output (g/o)
generate output files from input and reference implementation
generate-input (g/i)
generate input files from given generator
test-reactive (t/r, test-interactive, t/i)
test for interactive problem
optional arguments:
-h, --help show this help message and exit
-v, --verbose
-c COOKIE, --cookie COOKIE
path to cookie. (default: /Users/masa/Library/Application Support/online-judge-tools/cookie.jar)
--version print the online-judge-tools version number
tips:
The official tutorial exists on the web: https://github.com/online-judge-tools/oj/blob/master/docs/getting-started.md
あれ、できたぞ？
できた
OpenSSLのバージョンを上げてもダメだった理由がよくわかってないので、解説してくれる人がいたら嬉しいです。
26. Remove Duplicates from Sorted Array
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCode を始めたのであった。
一旦は Easy 問題を番号の若い順に Python で解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
7回目、まだあまり進歩は感じない。
問題
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
ソート済みの数値配列が与えられるので、重複する値を削除した後、ユニークな値の個数を返却するという内容
配列の前からn個(ユニークな数値の個数)の要素が想定と合っていれば、それ以降はなんでもいいらしい
別の配列を用意するのはNGで、与えられた物を加工する必要があるらしい
思考プロセス
とりあえずループしていく方法を検討したが、ループの中で要素を削除するという事をしたことが無かったので少し手間取った。
ズレが出ないように要素を削除しつつ全探索するようにしたところ、下記のような実装になった。
最初に提出した解
from typing import List class Solution: def removeDuplicates(self, nums: List[int]) -> int: cnt = 0 i = 0 while i < len(nums): if i != 0 and nums[i] == nums[i-1]: del nums[i-1] i -= 1 else: cnt += 1 i += 1 return cnt
結果
Accepted
Beats: 48.52% Runtime: 156ms Memory: 15.5MB
もうちょい考える
うーん、そろそろ遅いのわかりつつとりあえず全探索を提出するのやめたいな。
pythonならnumpy辺りに重複を削除する関数があるような気もしたが、クリティカルな解答が出てきそうだったので調べなかった。
調べたらnumpy.uniqueというドンピシャの関数があったが、これは使用できなかった。
詳しくはわからないが計算量敵にNGなのかな。
計算量減らす方法を考えたが、結局思いつかないので解法を見ます。
Solutions を見る
class Solution: def removeDuplicates(self, nums: List[int]) -> int: size = len(nums) insertIndex = 1 for i in range(1, size): # Found unique element if nums[i - 1] != nums[i]: # Updating insertIndex in our main array nums[insertIndex] = nums[i] # Incrementing insertIndex count by 1 insertIndex = insertIndex + 1 return insertIndex
Beats: 84.80% Runtime: 89ms Memory: 15.5MB
何をしているのか？
要素を削除するのではなく並び変えるという方法っぽい。
numsはソート済みなので、同じ数値が続く限りは処理をせず、違う数値が出てくるタイミングでそれを記憶しておいたinsertIndexにinsertしていく。
これなら、処理はユニークな数値の分だけで済むので速い。 (私の処理では数値がダブっていると毎回削除の処理が走ることになっている)
結果的に半分くらいの処理時間で解決している。
かなり納得感があり、これなら自分でも思いついたんじゃないか？という悔しさも同時にある。
どう考えるべきだったのか
なるべく処理の回数を減らすという思考が必要だ（当然だろ）
今回なら、重複する数値を削除するよりユニークな数値を前に持ってくる方が速いという事に気付く必要があった。
難しいが、こういう思考プロセスは実務でも役立つだろうな～と感じた。
21. Merge Two Sorted Lists
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCode を始めたのであった。
一旦は Easy 問題を番号の若い順に Python で解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
新年一発目、だがかなりサボったな。。
DaD の α テストや tarkov が存外面白かったり、年末年始のゴタゴタがあったりで仕方ない、むしろ失踪しなかったのは偉い（ポジティブ）
問題
- Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
シンプルに 2 つのリストをマージ・ソートするという内容
思考プロセス
これ簡単じゃないか？と思った。
Python なら sorte 関数があるので、単純にそれでいいのではないか。
と思ったが、list1,2 はシンプルな数字のリストではなく ListNode クラスのリストになっていた。
ListNode クラスは val と Next を持ち、返却する型もOptional[ListNode]である必要がある。
ソートアルゴリズム、知らね〜〜〜(Final Fantasy)という感情である。
とりあえず思いつくのはこれを普通の list になんとか変換する方法かな。
最初に提出した解
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: if not list2: return [] else: return list2 simpleList1 = [node.val for node in list1] simpleList2 = [node.val for node in list2] simpleMergedList = sorted(simpleList1.extend(simpleList2)) mergedNodeList = [] for i in range(len(simpleMergedList)): if i == 0: continue node = ListNode( val = simpleMergedList[i-1], next = simpleMergedList[i] ) mergedNodeList[i] = node return mergedNodeList
結果
TypeError: 'ListNode' object is not iterable
なんか勘違いしていた
てっきり「node,value を持つクラスのリスト」かと思っていたが、Optional[NodeList]なので引数は NodeList そのものだった
じゃあ Example のはどういう事・・・？
問題文の日本語が理解できない、国語 5 なのに・・・英語だけど・・・
Solutions を見る
マジで混乱したので Solutions を見た
class Solution: def mergeTwoLists(self, list1, list2): if list1 != None and list2 == None: return list1 elif list1 == None and list2 != None: return list2 elif list1 == None and list2 == None: return None elif list1.val <= list2.val: return ListNode(list1.val, self.mergeTwoLists(list1.next, list2)) else: return ListNode(list2.val, self.mergeTwoLists(list1, list2.next))
何をしているのか？
あ、そういうことか。
ListNode の Next には次の ListNode が入っているんだな。
普通に理解力が欠如していた。
2 つの value を比較する関数内で再起的に自信を呼び出していき、どちらかが None になったら終わるという感じ。
どう考えるべきだったのか
問題の意図を読み取れないのは不慣れなのが問題だとは思う。
それはさておくにしても、このやり方は思いつかなかったと思う。
再帰関数作るの苦手なんだよな、多分ちゃんと理解できてないから応用できないんだと思う。
一度ちゃんと学ぶ必要があるな。
20. Valid Parentheses
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCode を始めたのであった。
一旦は Easy 問題を番号の若い順に Python で解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
5 回目
最近アルゴリズムの本を読み始めてみた。
問題を解き進める日と技術書を読み進める日に別れそう、毎日１問以上解く人すげーーーという感情。
問題
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
括弧だけで構成された文字列が与えられ、全ての括弧がちゃんと閉じられているか判定する、というもの。
Example を見ただけだと'({})'のようなケースが OK なのかわからないが、文章的にも問題的にもまあ普通にOKだろうなと思った。
思考プロセス
しばらく考えて、stack が使える気がした。
出てきた open bracket を stack に入れて、close が出てきた時に stack から 1 つ取り出して比較する。
括弧は順番通りに閉じられるので、対応する括弧でなければ NG という形。
最後は stack が空になっていることを確認すれば、全ての brackets が正常に閉じられていることがわかる。
最初に提出した解
from collections import deque class Solution: def isValid(self, s: str) -> bool: brackets = { "(": ")", "[": "]", "{": "}" } q = deque() for c in s: if c in brackets.keys(): q.append(c) else: if not q or c != brackets[q.pop()]: return False return not q
今までで一番自信があるかも。
これ以上なんとかしようがあるのか？という気持ち。
結果
Accepted
Beats: 79.83% Runtime: 38ms Memory: 13.8MB
自力で 50ms を切れたのは初めてな気がするので、素直に嬉しい。
能力の向上の結果というよりはたまたま思いついたという感じではあるが、まあいいでしょう。
もうちょい考える
正常系の時に全文字を処理しないといけないのは、あまり良くないのかなという気はする。
しかしこの問題は最大 10000 文字なので、全文字処理してもこのくらいで済むのかという感想。
（10000 文字の正常系がケースとしてあったのかはわからないが）
とはいえ自力でこれ以上高速化できる気はしないので、大人しく先人の叡智に頼ることにする。
Solutions を見る
公式の Solutions は有料プラン専用だったので、python で search して上に出たものを見てみる。
def isValid(self, s: str) -> bool: dic = {'(':1 , ')':2 , '[':3 , ']':6 , '{':5 , '}':10} res = [] for one in s: temp = dic[one] if(temp %2 ): res.append(temp) else: if(len(res) and res[-1]==temp//2): del res[-1] else: return False return res==[]
Beats: 82.31% Runtime: 37ms Memory: 13.8MB
何をしているのか？
open と close の判定方法が面白いなと思った。
ただ、list でやるより deque の方が早いという認識だったので、微妙に腑に落ちない。
私がbrackets.keys()で open の判定をしているのがちょっと遅いのかもな。。。
少し気になったので、この考えを流用してより高速にできるのか検討してみる。
融合
from collections import deque class Solution: def isValid(self, s: str) -> bool: dic = {"(": 1, ")": 2, "[": 3, "]": 6, "{": 5, "}": 10} res = deque() for one in s: temp = dic[one] if temp % 2: res.append(temp) else: if not res or res.pop() != temp // 2: return False return not res
Beats: 99.60% Runtime: 22ms Memory: 13.8MB
おおーーーー、めっちゃ早くなった。
これは面白いな、やはりdequeの方が早いという私の認識は合っていて、私の実装のボトルネックは先述の判定部分だったのだと思う。
ちなみにlistがdequeより遅いのは、listでpopと同じことをすると、残りの要素全ての位置を変更するような処理になるためらしい。
どう考えるべきだったのか
これは考え付かなかったなーと思う。
2個のペアを考える時はこのやり方を思い出してみよう。
とはいえ、最後に書いたものを100点とするなら90点くらいの状態には自力で持って行けたのではないか。
満足度は高めだった。
14. Longest Common Prefix
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCode を始めたのであった。
一旦は Easy 問題を番号の若い順に Python で解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
4 回目。とりあえずは 3 回で終わらなくてよかった。
問題
『14. Longest Common Prefix』
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
与えられた文字列の配列の中身で共通している最長の接頭辞を返却するという内容。
Constraints
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.
Example
Input: strs = ["flower","flow","flight"]
Output: "fl"
それぞれ'fl'が共通しているので、それを返却する。
共通するものが無ければ空文字を返却する。
思考プロセス
すぐ思いつくのは、各文字列を index で比較して合うところまで返却するという方法。
でもこれは例のごとく全探索になりそうなので止めた方が良さそうだ。
条件として配列の長さは 200 以下、文字列の長さも 200 以下なので、全部一致するようなケースで計算量が増えすぎそう。
共通部分を抜き出すような関数があるかと思いググっていたところ、クリティカルな答えに当たりそうだったため中止した。
ループして 1 文字ずつ調べるやり方以上にいい方法が思いつかないので、とりあえずそれで実装してみる
最初に提出した解
from typing import List class Solution: prefix: str = "" def compare(self, strs: List[str]) -> bool: for st in strs: if not st.startswith(self.prefix): self.prefix = self.prefix[:-1] return False return True def longestCommonPrefix(self, strs: List[str]) -> str: self.prefix = strs[0] if len(strs) == 1: return self.prefix while True: if not self.prefix: break if self.compare(strs): break print(self.prefix) return self.prefix
結果
Accepted
Beats: 35.93% Runtime: 72ms Memory: 14MB
思っていたより遅くは無いという印象ではあるが、最適なのか？と言う疑問は残る。
もう少しやりようはあると思うが、いまいち具体的な改善案がスッと出てこない。
Solutions を見る
ここからは私が英文の公式解説を読んで理解した内容を記述するので、内容の正しさは保証できません。悪しからず。
元ソースを見ましょう。
水平走査(Horizontal scanning)
各文字列を順に比較していく方法。
私がやったのと違うのは、例えば["flower","flow","flight"]という配列の場合、"flower"を他の要素全てと比較していくのではなく、
"flower"と"flow"の共通最長接頭辞(Longest Common Prefix 解説に倣い以下 LCP)である"flow"を次の要素と比較して、、、と言うことを続けていく。
公式解説では Java の記述が載っているので、Python で記述してみる。
class SolutionHorizon: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" prefix = strs[0] for st in strs: while prefix and not st.startswith(prefix): prefix = prefix[:-1] return prefix
おおー、簡潔だ。。。
というか私がやってたことが冗長だっただけだな。。。
私がやりたかったことの延長がこれなのだが、while 文をうまく使えてなかった。
Beats: 69.59% Runtime: 53ms Memory: 13.9MB
垂直走査(Vertical scanning)
上の水平走査の問題は、配列の最後にごく短い LCP が存在するようなケースである。
そのネックを解決する垂直走査では、各文字の index を垂直に比較していく。
["flower","flow","flight"]という配列の場合、index=1x の f を比較していき、index=3 で"flight"が not equal になるので LCP が出る。
同様に python で実装してみる。
class SolutionVertical: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" if len(strs) == 1: return strs[0] for i, c in enumerate(strs[0]): for st in strs: if i == len(st) or st[i] != c: return strs[0][:i] return strs[0]
これ全探索では？遅そうじゃない？と思った。
Beats: 13.26% Runtime: 84ms Memory: 13.9MB
遅かった。全探索とは違うのかな？あまりよくわからない。
どう考えるべきだったのか
Solutionsにはもう少し別の解法も載っていた。
strsを分割して、それぞれのLCP同士のLCPを出すという方法も載っていて少し気になった。
ただ、これ以上考えてると嫌になりそうだったので終わることにする、続けることの方が大事なので。。。
13. Roman to Integer
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCode を始めたのであった。
一旦は Easy 問題を番号の若い順に Python で解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
3 問目
問題
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV.
Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
面倒くさそ～～～というのが第一印象だ。
逆に、これをアルゴリズムによって簡単に表現できるのだとすればある種のワクワクのような物は感じる。
すべきことは、ローマ数字が与えられるのでそれをアラビア数字に変換する、というものだ。
それだけだとシンプルに聞こえるが、IV が 4 であるとか、考慮しないといけない事は多そうだ。
Example
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
思考プロセス
上記の MCMXCIV について考える。
アルファベット 1 文字がそれぞれ該当する数字を表すのであれば足し算なので楽だが、それぞれ対応する文字の左に I, X, C がつくとマイナスになるという感じだ。
順番に気を付ければマイナスなのか判断できそうではある。
C が 100 として登場するのは絶対に M の後なので、M より前に出てきたらマイナスにできる。
或いは、取り得る 2 つのアルファベットのペアを最初から抜き出して、それ以外を 1 文字ずつに分割すればいいだろうか。
2 つで特殊な意味をもつ組み合わせは IV, IX, XL, XC, CD, CM の 6 種類なのでそこまで多くは無い。
最初に提出した解
from typing import Dict class Solution: def romanToInt(self, s: str) -> int: normal: Dict[str, str] = { "I": "1", "v": "4", "V": "5", "x": "9", "X": "10", "l": "40", "L": "50", "c": "90", "C": "100", "d": "400", "D": "500", "m": "900", "M": "1000", } con_normal = str.maketrans(normal) s2 = ( s.replace("IV", "v") .replace("IX", "x") .replace("XL", "l") .replace("XC", "c") .replace("CD", "d") .replace("CM", "m") ) s2_list = list(s2) num_list = [int(n.translate(con_normal)) for n in s2_list] return sum(num_list)
結果
Accepted
Beats: 83.11% Runtime: 57ms Memory: 13.8MB
汚いというか、pythonicではない感じがする。。 しかしどうすればいいかと言われるとこれくらいしか思いつかなかった。
解説するほどのこともしていないが、2文字で1セットになる数字を1文字に変換し、それぞれ対応する数字に変換後に全部足しているだけだ。
Acceptedにはなりそうだと思ったが、流石に的確な解法ではなさそう。
Solutions を見る/
class Solution: def romanToInt(self, s: str) -> int: rd = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000} n = len(s) rt = 0 for i in range(n): if i == n - 1 or rd[s[i]] >= rd[s[i + 1]]: rt += rd[s[i]] else: rt -= rd[s[i]] return rt
何をしているのか？
なるほどなーーーーーーーと言う気持ちになった。
要するに、次の数字より対象が大きいならそれは特殊な例なので、マイナスにしている。
最初に順番見ればできそうと思ったが、そっちのアプローチと言う感じだ。
Beats: 99.32% Runtime: 38ms Memory: 13.9MB
上記の結果的にもこっちの方が良さそうだ。 私の解答は変換処理があるので、それが無い分早いのは納得できる。
どう考えるべきだったのか
これは案としては頭にあったので、どちらが早いかをもっと検討すべきだった。
考え方としてはそこまで悪くなかったのかなと言う印象ではある。
9. Palindrome Number
前書き
よわよわばっくえんどえんじにゃーである筆者が、そろそろちゃんとアルゴリズムやんないとやべーじゃんとなり、LeetCodeを始めたのであった。
注意としては、解説記事では無い。
ただ、クソ初心者が理解するまでの思考プロセスを残しているので、どこかの誰かの参考程度にはなるかもしれない。
理解が間違っている箇所などの指摘（マサカリ）は常に募集中。メンタルは強いので大丈夫。
一旦はEasy問題を番号の若い順にPythonで解いていく予定。
いつまで続くかもわからないが、せっかくなら記事に残そうということで連載を開始。
2回目の今回はタイトルの問題を解く。
問題
Given an integer x, return true if x is a palindrome, and false otherwise.
palindromeは回文のことであり、つまり与えられたのが前後を入れ替えても同様に読める数値である場合はtrue,そうでなければfalseというはなし。
Example
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
特に条件に付いてわかりにくい事はない(主観)
思考プロセス
シンプルに考えると、数値を1桁ずつ分割して配列化し、先頭と末尾から見ていって偶数個ならn/2, 奇数個ならn/2 - 1回見た時点で全てequalであればtrueとなる。
それで絶望的に計算量が多くなる気もあまりしないので、とりあえずその方向で実装してみる。
詰まった点
整数への変換
まず、数値を1桁の整数のリストへ変換する処理で少し悩んだ。
リスト内包表記でやればできるが、不要な型変換をするのはスマートではないと思ったからだ。
少し調べた結果、理解できる形で実現できるのは内包表記だと思ったためそのままいくことにした。
ValueError
list = [int(i) for i in str(x)]としテストを実行したところ、下記のようなエラーになった。
ValueError: invalid literal for int() with base 10: '-'
最初はよくわからなかったが、テストケースを見て気づいた。
-121というケースがあり、マイナス符号が数値変換できないためエラーになっているのだった。
これは、変換できない記号が含まれている時点でNGでも問題無い気はする(-121-という数値は存在しない為)ので、ハンドリングを追加する。
最初に提出した解
class Solution: def isPalindrome(self, x: int) -> bool: # 数値を1桁の整数のリストへ変換 try: list = [int(i) for i in str(x)] except ValueError: return False even_flg = len(list) % 2 == 0 for i, num in enumerate(list): if even_flg and i >= len(list) / 2: return True elif not even_flg and i >= len(list) / 2 - 1: return True # 末尾から取る場合は-1スタートになる為+1する。 if num != list[-(i + 1)]: return False # ここには来ない return False
結果
Acceptedになった。
Beats: 5.4% Runtime: 215ms Memory: 13.9MB
Q: LeetCode上に表示されるBeatsとは何の数値ですか？
A: 知らん。100%が上限で、高い方がいいっぽい（有識者教えてください）
もうちょい考える
1.Two Numで詰んで密かに精神的ダメージを受けたので、とりあえず自力でAcceptedに持って行けたのは一安心ではある。（Easyは最悪Brute forceでならいけると思ってた）
とは言え、いろいろスマートでは無さそうというのは実感としてある。
しかし問題の性質上全ての数字を洗わずに正解を出すというのは難しいのではとも思い、整数変換部分以外の具体的な改善案は思いつかない。
他のアプローチがあるかもしれないので、回文の特性を考える。
- 先頭から読んでも末尾から読んでも差異が無い(特性ではなく定義である)
- 文字数が偶数の場合の中央の1文字を除き、登場する文字は偶数個になる
これくらいしか思いつかない。
ここまで書いて1つ思ったが、下記手順でも可能そうだ。(マジでリアルタイムで考えながら書いているのである。思考整理の目的もある。)
- 配列化する
- 中央で配列を2つに分割する(要素数が奇数の場合中央は消す)
- 後者の配列を逆順に修正する
- 2つの配列を比較する
というかこっちの方がループしなくて済むので良さそうだ。
第二提出案
import math class Solution: def isPalindrome(self, x: int) -> bool: # 数値を1桁の整数のリストへ変換 try: list = [int(i) for i in str(x)] except ValueError: return False list_a = list[: math.floor(len(list) / 2)] list_b = list[math.ceil(len(list) / 2) :] list_b.reverse() return list_a == list_b
結果2
Acceptedになった。
Beats: 5.4% Runtime: 207ms Memory: 14MB
個人的には結構いい案を思いついたと思ったのだが、結果としてはほとんど差異はなかった。
(解法に気づいたくらいのテンションだったので正直結構残念だった)
reverseの計算コストが高いのかな？原因はいまいちわからない。
ん？というか、今気づいたがreverseするならlistを分割する必要ないな。草生える。
難しく考えすぎていたな、答えを出すだけなら配列にしてreverseして比較すればそれだけでよかった。
第三提出案
import copy class Solution: def isPalindrome(self, x: int) -> bool: # 数値を1桁の整数のリストへ変換 try: list = [int(i) for i in str(x)] except ValueError: return False list_b = copy.copy(list) list_b.reverse() return list == list_b
結果3
Acceptedになった。
Beats: 87.68% Runtime: 68ms Memory: 13.8MB
Memoryの数値はさほど変わらないものの、3倍程度高速になった。
これが自分の中での最適解だが、とりあえずSolutionsを確認してみる。
Solutionsを見る
以下、Solutionsより引用し翻訳
最初に思いつくのは、数を文字列に変換し、その文字列が回文であるかどうかを調べることである。しかし、この場合、文字列を作るために余分な非定常領域が必要となり、問題の記述では許されない。
次に、数字そのものを反転させて、元の数字と比較し、同じであれば回文である、という考え方もあります。しかし、反転した数がint.MAXtext{int.MAX}より大きい場合、整数オーバーフロー問題にぶつかる。
2番目の考えに基づいて、反転した数のオーバーフロー問題を避けるために、intの半分だけを反転させたらどうだろう。結局のところ、回文であれば、回文の後半部分の逆数は前半部分と同じになるはずである。
例えば、入力が「1221」の場合、「1221」という数字の最後の部分を「21」から「12」に直して、「12」という数字の前半部分と比較すれば、12は12と同じなので、その数字が回文であることが分かります。
この考え方をアルゴリズムに置き換えるとどうなるか見てみましょう。
まず、いくつかのエッジケースに注意する必要があります。例えば、-123は'-'が'3'にならないので回文にはならない。したがって、すべての負の数に対してfalseを返すことができる。
次に、数字の後半を元に戻す方法を考えてみよう。1221という数字について、1221 % 10とすると、最後の一桁が1になってしまいます。そして、下一桁の数字を10倍して、下二桁の数字を足すと、1 * 10 + 2 = 12 となり、目的の回帰した数字が得られます。この作業を続けると、さらに桁数の多い逆数が出てくる。
さて、問題は、どうやって数字の半分に到達したことを知るかである。
元の数字を10で割って、反転した数字に10を掛けたのだから、元の数字が反転した数字より小さければ、数字の半分の桁を処理したことになるのだ。
つまり、どういうことだってばよ・・？
つまりどういうことか
数値をそのまま反転すればええやんけ！というのはNGらしい。
数値をそのまま反転するというのは考えてなかったが、配列化して反転したのは結果的に良かった。
負の数は全てFalseとするのもとりあえずOKだったようだ。
問題はこの辺である。
次に、数字の後半を元に戻す方法を考えてみよう。1221という数字について、1221 % 10とすると、最後の一桁が1になってしまいます。そして、下一桁の数字を10倍して、下二桁の数字を足すと、1 * 10 + 2 = 12 となり、目的の回帰した数字が得られます。この作業を続けると、さらに桁数の多い逆数が出てくる。
ちょっと何言ってるかわかんないですね（サンドウィッチマン）
翻訳機にかけてそのまま読んでたが、どうやら翻訳が悪そうだったので再度部分的に翻訳機にかけた（意地でも自分で読まないスタイル）
では、数字の下半分を元に戻す方法を考えてみましょう。1221という数字について、1221 % 10とすると、下1桁が出ます。下2桁を得るには、1221から下1桁を取り除く必要がありますが、それには、1221 / 10 = 122と10で割ればよいでしょう。そして、下一桁の数字を10倍して、下二桁の数字を足すと、1 * 10 + 2 = 12 となり、目的の回帰した数字が得られます。この作業を続けると、さらに桁数の多い反数が出てくる。
あー－－－なるほど、なんとなく30%くらいわかった気がするな。
でもうまいこと言語化はできないのでコードで書こう。
公式のSolutionsではC#のコードしか載っていないので、そのまま載せる。
public class Solution {
public bool IsPalindrome(int x) {
// Special cases:
// As discussed above, when x < 0, x is not a palindrome.
// Also if the last digit of the number is 0, in order to be a palindrome,
// the first digit of the number also needs to be 0.
// Only 0 satisfy this property.
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber/10;
}
}
何をしているのか？
上のSolutionsで書いてあるとおりなのだが、自分なりに嚙み砕いてみる。
まず、エッジケースについて
これは、xが負数であるケースと、x % 10が0であり、かつxが0でないケースを弾いている。 (10の倍数が回文であることは無い)
問題はwhile以降である。
x = 1221のケースを考える
1回目のループ
revertedNumber = 0 * 10 + 1221 % 10
revertedNumberには1が入る。
xは122 (これでクソ詰まったのだが、C#だと1221/10は122に丸められるらしい、それアリ？？？？？？？)
2回目のループ
revertedNumber = 1 * 10 + 122 % 10
revertedNumberには12が入る
xは12
ここでx > revertedNumber == Falseになるため、ループが終了する。
判定
x == revertedNumber or x == revertedNumber / 10
12 == 12となり、Trueになる
これ速いの？
Pytonで似たことをしてるSolutionsがあったので試してみたが、そんなに早く無さそう。
結果3の方が速かった。
ただ、これは半分で処理が終わらずにreverse()を実装でやってるみたいな感じなので、公式SolutionをPythonにしたら速いのかもしれない。
どう考えるべきだったのか
結果的に、おおむね当初考えた方向は間違いとは言えないっぽかった。
アルゴリズム的に？言えば、x % 10で末尾が取れるからそれ繰り返せば数字をひっくり返せるねというのは気づかなかった。
Pythonにreverse()が無かったらもっと時間かかっていたと思う。ビバ・Pythonである(イタリア)
残った疑問等
Pythonで公式Solutionを実装しようとしばらくこねこねしていたが、少数計算が面倒くさすぎて諦めてしまった。
時間がある時にやってみたい。
かかった時間
3時間くらい。文章書きながらというのはあるが、かかりすぎだろ。
