Leetcodeを進める(8)

Problem24

https://leetcode.com/problems/swap-nodes-in-pairs/

偶数番目と奇数番目をスワップしたリストを返す。

You may not modify the values in the list's nodes, only nodes itself may be changed.

とのことなのでリストのvalを書き換えてはいけない。

copy --- 浅いコピーおよび深いコピー操作 — Python 3.8.2 ドキュメント

weakref --- 弱参照 — Python 3.8.2 ドキュメント

Problem26

Remove Duplicates from Sorted Array.

in-placeでユニークな要素のみをリストに残し、リストの長さを返す問題。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:

        i = 0
        while i < len(nums)-1:
            if nums[i]==nums[i+1]:
                del nums[i]
            else:
                i = i + 1

        return len(nums)

delで重複した要素を指定して、リストから削除する。

5. データ構造 — Python 3.8.2 ドキュメント

Problem28

部分文字列一致のアルゴリズムの実装。

www.slideshare.net

ナイーブに先頭の文字列を見つけたら、それ以降がマッチするかをチェックするようにしてとりあえず提出。両者空白の場合を考慮し忘れておりWAを出してしまった。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        haysta_len = len(haystack)
        needle_len = len(needle)
        res = -1

        if needle_len == 0:
            return 0  # 必ず先頭で一致
        elif haysta_len == 0:
            return -1  # 必ず不一致
        else:
            first_c = needle[0]

            for i, ci in enumerate(haystack):
                if not ci==first_c:
                    continue
                elif i+needle_len>haysta_len:
                    break
                else:
                    if haystack[i:i+needle_len]==needle:
                        res = i
                        break

        return res

Runtime: 28 ms, faster than 75.04% of Python3 online submissions for Implement strStr(). Memory Usage: 13.1 MB, less than 98.46% of Python3 online submissions for Implement strStr().

ブログズミ: ASSERT_EQ(NULL, ptr) がコンパイルエラーにならない理由

Assert.IsNull Method (Microsoft.VisualStudio.TestTools.UnitTesting) | Microsoft Docs