https://leetcode.com/problems/longest-palindromic-substring/ class Solution: def longestPalindrome(self, s: str) -> str: res = '' for i in range(len(s)): # odd case tmp = self.helper(s, i, i) if len(tmp) > len(res): res = tmp # even tmp = self.helper(s, i, i+1) if len(tmp) > len(res): res = tmp return res def helper(self, s, l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 return s[l+1:r]
https://leetcode.com/problems/longest-increasing-subsequence/ LIS はどんな場合でも最低1になるので、 1を入れた、list を作る。 reverse order でループし、 ネストしたループで最初にループしている i 以降の数と比較する。 nums[i] と nums[j] で nums[i] が小さい場合、 subsequence となるので、 LIS[i] に max(LIS[i], 1 + LIS[j]) を入れる。 j は i 以降の数字を見ているので、max()を使わないと LISの最後の 1 で置き換えて 2 となってしまうので注意。 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: LIS = [1] * len(nums) for i in range(len(nums) - 1, -1, -1): for j in range(i + 1, len(nums)): if nums[i] < nums[j]: LIS[i] = max(LIS[i], 1 + LIS[j]) return max(LIS)
https://leetcode.com/problems/longest-common-subsequence/ 2d grid を作る。 row, col にそれぞれ、1行、1列追加して 0 を入れる。 grid の右下からループし、 縦横が同じ文字でマッチしたら、斜め左上に進む。 その際に1を足す。 マッチしなかったら、右横か下のどちらか大きい数字を入れる。 ループが終わりgrid[0][0] の箇所に 1番長い subsequence の数が入る。 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)] for i in range(len(text1) - 1, -1, -1): for j in range(len(text2) - 1, -1, -1): if text1[i] == text2[j]: dp[i][j] = 1 + dp[i + 1][j + 1] else: dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) return dp[0][0]
F / \ B G / \ \ A D I / \ / C E H Pre-order Traversal root left subtree right subtree F B A D C E G I H https://leetcode.com/problems/binary-tree-preorder-traversal/ Iterative approach class Solution(object): def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: """ :type root: TreeNode :rtype: List[int] """ res, stack = [], [(root, False)] while stack: node, visited = stack.pop() if node: if visited: res.append(node.val) else: stack....
https://leetcode.com/problems/search-insert-position/ algorithm の runtime は O(log n) である必要があるため、 binary search で target の数の位置を調べる。 変数 left に 0、 right に len(nums) - 1 を設定する。 (left + right) // 2 で真ん中の値が取得出来るので、 真ん中の位置を mid とする。 nums の mid の値が target なら、mid の index の値を返す。 もし、target の値が mid より大きい場合、 left を mid + 1 にする。 target の値が mid より小さい場合、 right を mid - 1 にする。 [1, 3, 5, 6] で target = 2 の場合、...