達観データ筆記試験問題の最長男列とチェーンテーブルの重複要素の除去

達観データ筆記試験のテーマ
タイトル1:
サブストリング内のすべての文字が重複しないようにする文字列を指定します.

Example:

Input: "abcabcbb"

Output: 3

Explanation:              "abc",    3.

考え方:
解法1:この問題は暴力解法を使うと複雑度が高い.暴力解法は2つのサイクルを繰り返して重複しているかどうかを判断することです
解法2:

スライドウィンドウで時間の複雑さが低い.

は、文字および文字を格納するための辞書dの位置

を定義する.

変数startを定義して、スライドウィンドウの始点

を保存します.

は、このウィンドウを格納するための変数tmpの長さ

を定義する.

変数resを定義して最大の長さ

を格納する
コードは次のとおりです.

def lengthOfLongestSubstring(s):
    res = 0
    if s is None or len(s) == 0:
        return res
    d = {}
    tmp = 0
    start = 0
    for i in range(len(s)):
        if s[i] in d and d[s[i]] >= start:
            start = d[s[i]] + 1
        tmp = i - start + 1
        d[s[i]] = i
        res = max(res, tmp)
    print(d)
    return res

res = lengthOfLongestSubstring('abcabcbb')
print(res)

タイトル2:
2つの順序付きチェーンテーブルAとBがあり、AとBを結合して新しいシーケンステーブルCとなり、その重複要素を除去する.できるだけ新しい記憶空間を開かないようにし,時間的複雑度O(n)である.
考え方:
新しいチェーンテーブルnodeを定義し、同期してaリストとbリストを下に移動します.
aとb次のノードの値が小さい人はnodeチェーンテーブルの後ろに接続し、nextノードの値が小さいチェーンテーブルを後ろに移動します.
aとbのnextノードの値が等しい場合、aとbはいずれも1ビット後退する.aをnodeの後ろにつなぎます.
コードは次のとおりです.

#     
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def mergeTwoLists(l1,l2):
    res = ListNode(None)
    node = res
    while l1 and l2:
        if l1.val<l2.val:
            node.next,l1 = l1,l1.next
        elif l1.val>l2.val:
            node.next,l2 = l2,l2.next
        else:
            node.next,l1,l2 = l1,l1.next,l2.next
        node = node.next
    if l1:
        node.next = l1
    else:
        node.next = l2
    return res.next