LeetCode / Linked List Cycle
Kaggle繋がりでTwitterでばったりフォローした人がばったり旧知の囲碁友だった件。
ちょうど今日の問題のLinked Listのようにぐるりと回って再会しました（無理矢理
https://leetcode.com/problems/linked-list-cycle/
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
連結リストというデータ構造がお題です。
与えられた連結リストに循環構造が含まれているか（＝循環リスト）、判定する問題です。
解答・解説
解法1
はじめて連結リストというデータ構造を見た人が既存の知識で対応しようと思うと、以下のようになると思います。
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): nodesSeen = set() while head is not None: if head in nodesSeen: return True else: nodesSeen.add(head) head = head.next return False
各要素をsetにどんどん入れていって、既にsetに入っている要素に再度出会ったら循環しているということなのでTrueを返し、そのようなことが起きずこれ以上要素がないところまでloopが回ったらFalseを返せば良いです。
解法2
解法1では空間計算量はになりますが、これを定数時間で行う方法が以下のコードです。
slowとfirstという２つのポインタを用意します。slowは1要素ずつ、firstは2要素ずつ進むポインタで、slowの1つ先にfirstを置いてスタートさせます。
すると、もし循環リストであれば、slowがリストの終端まで進む間に、firstは必ずどこかでslowに出会います。
なぜなら、slowがリストの終端まで進むnステップの間にfirstは2n進むことになりますが、firstが追いつかなければいけないslowとの距離は、最大で下図の場合でn-1なので、1要素ずつ距離を詰めるfirstはnステップの間に必ずslowに追いつけることになります。
class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if not head or not head.next: return False slow = head fast = head.next while slow is not fast: if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True
LeetCode / Single Number
昨夜実家の富山から帰ってきました。
台風さんがフェーン現象を巻き起こしたせいで、北陸は地獄のような気候になってます。
私が兼ねてから主張している国民総打ち水法の制定を真摯に考えるべきかと思います！
さて、今日の問題。
https://leetcode.com/problems/single-number/
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
空ではないintのlistに対して、1つだけ存在する1度しか登場しない要素を返す問題です。
事実上、NoteのYour algorithm should have a linear runtime complexity. Could you implement it without using extra memory?に対して回答できるかどうかの問題と読み替えて良いと思います。
解答・解説
自力ではextra memoryを使う解法しか思いつかなかったので、まずは2つ示します。
解法1
誰でも思いつく（けどこれじゃ問題の意味がないと気づいて書かない）コードを、一応載せておきます。
class Solution: def singleNumber(self, nums: List[int]) -> int: ans = [] for n in nums: if n in ans: ans.remove(n) else: ans.append(n) return ans[0]
解法2
こちらの解法は少し難易度が上がるでしょうか。
まずはsetで集合をとり、重複した要素を排除します。この集合の合計値の２倍と、元のlistの差分が答えになります。
class Solution: def singleNumber(self, nums: List[int]) -> int: return sum(set(nums))*2 - sum(nums)
しかし、set(nums)によって空間計算量がに達するのは変わりません。
解法3
さて、extra memoryを使わない解法ですが、ビット演算子のXOR（排他的論理和）を使います。
XORは、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算のことです。
例えば、以下のように計算されます。
>>> 1 ^ 3 2 # 3は2進数で11、1は2進数で01。これのXORは10で、10進数にすると2
このXORを利用して、以下のような解法が成立します。
class Solution: def singleNumber(self, nums: List[int]) -> int: for i in range(1,len(nums)): nums[0] ^= nums[i] return nums[0]
これは何をしているかというと、全要素についてXORをとっています。
nums = [2,1,4,5,2,4,1]であれば 2 ^ 1 ^ 4 ^ 5 ^ 2 ^ 4 ^ 1 を計算するわけですが、このとき、
- a = bのとき、 a ^ b = 0
- a ^ b = b ^ a
の性質を利用すると、以下のように計算され、解が得られます。
-> 2 ^ 1 ^ 4 ^ 5 ^ 2 ^ 4 ^ 1 => 2 ^ 2 ^ 1 ^ 1 ^ 4 ^ 4 ^ 5 => 0 ^ 0 ^ 0 ^ 5 => 0 ^ 5 => 5
LeetCode / Valid Palindrome
終日頭が重い@mhiro216です。
気象病ってやつなんだろうか。全部台風のせいだ。
さて、軽い問題で頭をほぐします。
https://leetcode.com/problems/valid-palindrome/
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false
問題を解くことよりも英語を正確に理解する方が難しいくらいかも？
英数字のみを抜き出し、大文字小文字の違いを無視して、回文（始めから読んでも、終わりから読んでも同じ）になっているかを判定する問題です。
解答・解説
解法1
私のsubmitしたコード。
正規表現を使い慣れている人なら、とりあえずreライブラリを使うこの解法は思いつくかと。
import re class Solution: def isPalindrome(self, s: str) -> bool: new_s = re.sub(r'[^a-z0-9]', '', s.lower()) return new_s == new_s[::-1]
解法2
私は初めて知りましたが、isalnumという、英数字かどうかを判定する関数（戻り値はbool型）があるんですね。これを使うと以下の通りです。
class Solution: def isPalindrome(self, s: str) -> bool: s = ''.join(e for e in s if e.isalnum()).lower() return s==s[::-1]
ちなみに文字列を同様に判定する関数には、以下３種類があるようです。ご参考まで。
- isdecimal ： 数字かどうか
- isalpha ： 英字かどうか
- isalnum ： 英数字かどうか
LeetCode / Best Time to Buy and Sell Stock II @柏の葉コワーキングスペースKOIL
今日は柏の葉のコワーキングスペースに来てみました。
日本最大級らしいので、ここまでのクオリティが他でもあるわけではないと思いますが、
1日(9時-23時まで)で1500円
ということで、圧倒的なコスパに驚愕しております。
柏の葉ということで私の自宅からdoor2doorで1時間弱かかるんですが、移動疲れせず、ここまで来たらやってやろうと言う気持ちになる、ちょうど良い具合の立地です。
さて、今日の問題。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Example 2:
Example 3:
前回記事の類題です。
今度は1度切りの売り買いではなく、何度も売り買いを繰り返したとき、最大の利益はいくらになるか算出する問題です。
但し同日に売り買いすることはできないとします。
解答・解説
解法1
今回の問題は、次の日に値が上がるか同じなら売らずに待ち、下がるなら売るという最適な行動に気づけば、簡単です。
そして、また簡潔なコードとイマイチなコードを並べておきます。
まずは私のsubmitしたコード。
class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit, sell, buy = 0, float('-inf'), float('inf') i = 0 while i < len(prices): buy = min(buy, prices[i]) if prices[i] > buy: sell = prices[i] while i < len(prices)-1 and sell <= prices[i+1]: sell = prices[i+1] i += 1 max_profit += sell - buy sell, buy = float('-inf'), float('inf') i += 1 return max_profit
次の日に値が上がるか同じなら売らずに待ち、下がるなら売るという行動をそのままコードに落としています。
解法2
続いてSolutionをPythonに翻訳したコードです。考え方は上と同じですが、
「値が下がるまで売らずに待つ」ときに得られる利益は、1日ごとの値の差分の和と同値である
という関係性を使って、より簡潔なコードに落としています。
下図のイメージです。
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 else: profit = 0 for i in range(len(prices)-1): if prices[i] < prices[i+1]: profit += prices[i+1] - prices[i] return profit
LeetCode / Best Time to Buy and Sell Stock
東京都内在住の私ですが、ひとり開発合宿なるものをやってみようと思い、とある県のホテルに泊まって、部屋から出ず黙々とコードの写経をしています。
しかし、ひとり開発合宿は、自分に対する甘えを断ち切れる精神の持ち主でないと、あまり向いていないですね。
ついLeetCodeに浮気してしまいました。
次からはコワーキングスペースに突撃してみたいと思います。
さて、今日の問題。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Example 2:
最も安い時に買い、高い時に売りぬけることで、最大の利益はいくらになるか算出する問題です。
現実には先々の値段がわかっていることはまずないですが、相当精度の高い時系列予測モデルができていればワンチャン？なアルゴリズムですかね。
解答・解説
解法1
解法を思いつくのは難しく無いと思います。
今回の問題は時間計算量はどう頑張ってもというところなのでアルゴリズムの比較はせず、簡潔なコードとイマイチなコードを並べておきます。
まずは私のsubmitしたコード。
class Solution: def maxProfit(self, prices: List[int]) -> int: ans = 0 if prices: buy = prices[0] for price in prices[1:]: if price < buy: buy = price if price - buy > ans: sell = price ans = sell - buy return ans
コードの意味は非常にシンプルで、買値buyは安い値段があれば置き換え、売値sellは利益ansを超える利益が出るようなら置き換える、という操作を要素数分繰り返しているだけです。
続いてDiscussionで見つけた5 lines solution。
class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit, min_price = 0, float('inf') for price in prices: min_price = min(min_price, price) profit = price - min_price max_profit = max(max_profit, profit) return max_profit
コードの意味は私のsubmitしたものと同じですが、とても簡潔ですね。
特に、初期値を max_profit, min_price = 0, float('inf') と設定するところがまだ自分には思いつきませんでした。
AtCoder Contest 初参戦記録
いつもLeetCodeを解いている私ですが、どうやらAtCoderという競技プログラミングサイトでの"色"がプログラマーとしてのスキルの一端を表すものであるらしいと聞き、せっかくなので参戦してみることにしました。
参戦前準備
参戦前準備というのは会員登録だとかのことを言っているだけではなく、（私にとっては）LeetCodeとの仕様の違いに慣れるところから始める必要がありました。
LeetCodeで操作できるのは、以下画面のように「関数を定義する欄」と「関数への入力値を決定する欄」の2つです。
我々がやるべきこととしては、返り値を返す関数を定義するだけでOKです。
一方でAtCoderでは、標準入力を読み取って処理にかけ、回答は標準出力で返す、というコードを書く必要があります。
この違いに慣れるのになかなか時間がかかりました。
とはいえ、5~10分くらい手間取ったくらいなので、最終スコアには影響はなかったと思います。
慣れのBiasも入っているかもしれませんが、私はLeetCode方式の方が好きではあります。
ちなみに、success/failの判定対象が「関数の返り値が正解かどうか」「処理が時間・空間計算量の制限内に完了したかどうか」なのは共通です。
コンテスト内容
参戦したコンテストはAtCoder Beginner Contest 137というものでした。
これはABCなどと称され、AtCoderのBeginner向けに、毎週土or日曜日の21時から開催されているものだそうです。
コンテスト時間になると問題が開示され、制限時間内（今回は1時間40分）に正しいコードをsubmitできればスコアを獲得できます。
submitしたコードが誤った値を返すものであったり、処理時間が制限を超えたりするとfailとなり、1度のfailにつき持ち時間5分削減のペナルティが与えられます。
問題数は6問。簡単なものから難しいものまでA-Fの問題があり、獲得できるスコアにも差があります。
問題の傾向は、まだコンテストに1度しか参加していないので私の感想はあまり参考にならないと思いますが、
A, B : プログラミングの勉強がきちんと身についているかチェックする問題
C, D : プログラマーとして独り立ちしてやっていきたいなら解答必須な問題
という感覚でしょうか。
個人的には、Dまで確実に解けるレベルを目指したいところです。
本記事では、私が制限時間内に解けたCと解けなかったDの問題の2つを、問題例として紹介します。
問題内容・解法
C - Green Bin
アナグラム（文字の入れ替えを行うと合致する文字列）になっている文字列の組み合わせ数を計算する問題です。
アナグラムかどうかを判定できるように、文字列は
s = ''.join(sorted(input()))
として各文字を要素に持つsortされたリストsに変換します。
次に、sを格納する辞書dを用意します。
アナグラムになっている文字列の群は、辞書dにおける1つのkeyとして扱うこととします。
loopを回し、アナグラムになっている文字列群の中の文字列の数を辞書のvalueとします。
一方で、最終的に解答したいアナグラムの組み合わせの数を変数ansで計算します。
例えば文字列A, B, Cが互いにアナグラムになっていたら、組み合わせの数は3となります。
そこで、dのkeyにアナグラムになっている文字列が既に存在したら、そのvalueをansに足します。
例を挙げると、s = ['a','b','c'], d[s] = 2のときに文字列'cba'が現れたら、ansに+2してやるということですね。
n = int(input()) ans = 0 d = {} for i in range(n): s = ''.join(sorted(input())) if s not in d.keys(): d[s] = 1 else: ans += d[s] d[s] += 1 print(ans)
D - Summer Vacation
M日後に得られる報酬を最大化する問題で、A日後に報酬Bを得られるアルバイトN件から適切なものを選ぶ必要があります。
解説pdfによれば、
この問題は後ろ (M 日後から 1 日前) から見ていくと、まず Aj ≤ 1 となる j の中で Bj が最大のもの(j1 とする) を選び、次に Aj ≤ 2 かつ j ̸= j1 となる j の中で Bj が最大の> ものを選び、…としていくのが最適です。
とのこと。
私は解けなかったので、以下に今回のコンテスト順位1位のconvexineqさんの解法を示します。
コードの意味についてはコード中のコメントを参照いただければと思いますが、heapというデータ型を利用している点だけ補足します。
heapとは、Wikipediaによれば
「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造
のことを指します。
常に最初の要素が最小値となるようなリストが必要な場合、heap構造を用いることで最小値（最大値）の取り出しをO(1)、要素の追加をO(log n)の時間計算量で行うことができるのがheapの利点です。
import sys sys.setrecursionlimit(10**6) readline = sys.stdin.readline from heapq import * n,m = [int(i) for i in readline().split()] ab = [[int(i) for i in readline().split()] for _ in range(n)] ab.sort(reverse = True) # 報酬をもらえるまでの日数の降順に並べ替えておく（例：[[2, 3], [2, 1], [1, 4], [1, 3], [1, 2]]） q = [] ans = 0 # 報酬の合計値 for i in range(m-1,-1,-1): # m-1日後から順に行うべきアルバイトを決めていく（未来から現在に遡っていく） while ab and ab[-1][0] + i <= m: # ab[-1][0]は報酬をもらえるまでの日数。ab[-1][0]+iがmを超えてしまうと報酬をもらうのが間に合わない (a,b) = ab.pop() heappush(q,-b) # -bが小さい=bが大きい、つまり報酬が大きいということ。heapは最小値を取得するのに適しているため、マイナスにして取り出している if q: ans -= heappop(q) # qの最小値を取得。マイナスを掛け直してプラスの値として報酬に加算 print(ans)
heapについては、同じ優先度付きキューの仲間として、LeetCodeでも何度か出てきたstack, queueとの比較で解説されている分かりやすい記事を見つけたので、貼っておきます。
いつ何時どれを使えば良いのか、1度整理したいところ…
評価
AtCoderではコンテストの戦績によってratingが付き、プログラマーとしてのスキルの証明である"色"が付与されます。
"色"と実務におけるスキルレベルの関係は、AtCoder社長の高橋さんが以下のように説明してくれています。
ちなみに私のratingは以下の通り。
参加回数が少ないとratingは非常に低く計算される傾向があるようなので、今の時点ではうわっ低。。。としか言えません。
ratingとは別に、「パフォーマンス」という各コンテスト単体で見たときの評価があります。
これは、「このレベルのパフォーマンスを続けていればこのくらいのratingになるよ」という指標と考えれば良いようです。
私のパフォーマンスは745だったので、色で言うと"緑"には及ばない"茶"相当になるようです。
私はプログラマーとして生きていきたいわけではないですが、経営者としてでも一定のスキルがないと説得力がないので、"緑"までは到達することを目指したいと思います。
LeetCode / Pascal's Triangle II
AtCoderのBeginner Contentに初参戦してみました。
結果は緑(こちらのページによれば "ソフトウェアエンジニアとして申し分ない実力です" のレベル)相当には後一歩及ばずというところ。まだまだ精進です。
さて、今日の問題。
https://leetcode.com/problems/pascals-triangle-ii/
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3
Output: [1,3,3,1]
Follow up:
Could you optimize your algorithm to use only O(k) extra space?
今度はパスカルの三角形のk行目の数列を返すことが求められています。
前回記事の問題を解けたのであれば解くこと自体は造作もないですが、の省メモリな解法を考えるところで深みがあります。
解答・解説
解法1
前回記事にて以下のコードを示しましたが、
class Solution: def generate(self, numRows: int) -> List[List[int]]: ans = [] if numRows > 0: ans.append([1]) for _ in range(numRows-1): l_pre = [0]+ans[-1]+[0] l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)] ans.append(l_nxt) return ans
これを少し改変することでも解くことができました。
class Solution: def getRow(self, rowIndex: int) -> List[int]: l_pre = [1] if rowIndex > 0: for _ in range(rowIndex): l_pre = [0]+l_pre+[0] l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)] l_pre = l_nxt return l_pre
解法2
パスカルの三角形の各数列の計算は、以下のように上段の数列の片端に[0]を付けた二つの数列を足し合わせることでも計算できます。
こちらの方が解法1よりすっきりしていますね。
これを利用した解法が以下。
class Solution(object): def getRow(self, rowIndex): """ :type rowIndex: int :rtype: List[int] """ row = [1] for _ in range(rowIndex): row = [x + y for x, y in zip([0]+row, row+[0])] return row
解法3
最も空間計算量を抑えた解法はこちらかと思います。
解に必要な要素数のリストを用意し、その中でIterativeに数列を計算していく省メモリな解法です。
class Solution(object): def getRow(self, rowIndex): """ :type rowIndex: int :rtype: List[int] """ ans = [0]*(rowIndex+1) ans[0] = 1 for i in range(1,rowIndex+1): for j in range(i,0,-1): ans[j] += ans[j-1] return ans
具体的に出力変数ansの変化を見てみると、イメージが湧くと思います。(rowIndex=5)
[1, 1, 0, 0, 0, 0] [1, 2, 1, 0, 0, 0] [1, 3, 3, 1, 0, 0] [1, 4, 6, 4, 1, 0] [1, 5, 10, 10, 5, 1]
