leetcode試験整理

今日leetcode第159 contest試験を受けて、2つの問題を作りました.1番と2番の問題しかできなかった.第三題の問題はあまり分からなかった.4番目の問題はdp問題で、とても弱いです.
1つ目の問題は、与えられた点が1つの線にあるかどうかを判断することです.明らかに、傾きが一致しているかどうかを判断すればいいのです.ただし分母が0の場合は気をつけましょう.2番目の問題はパスに含まれる問題です.例えば/a/b/a/b/c/aの3つの最後の結果は/aで、ここで私はまず/の多少で並べ替えて、それから順番にそれぞれを取り出して、スラッシュの個数によって循環して、最終的な結果の中に含まれていないならば、入れて、含んでいればpass、breakが出てきます.
3番目の問題は1つの文字列に与えられ、「Q」、「W」、「E」and「R」しか含まれていない.ここではバランスのとれた文字列を得る必要があります.各文字列の数は同じでなければなりません.サブ文字列を探す必要があります.このサブ文字列は文字列の一部を置き換えた後、文字列をバランスのとれた文字列にします.問題の構想はスライドウィンドウを採用することである.

    def balancedString(self, s):
        count = collections.Counter(s)
        res = n = len(s)
        i = 0
        for j, c in enumerate(s):
            count[c] -= 1
            while i < n and all(n / 4 >= count[c] for c in 'QWER'):
             	# 
                res = min(res, j - i + 1)
                count[s[i]] += 1
                i += 1
        return res

4番目の問題はdp問題です.この問題は後でleeの答えを見て、不思議な感じがして、専門的に整理しました.この問題は主にあなたに開始時間のリスト、終了時間のリスト、仕事をする収益のリストをあげます.開始時間、終了時間に基づいて、衝突しない期間を選択して最大の収益を得る必要があります.

import bisect
class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        dp = [[0, 0]]
        for s, e, p in jobs:
            #               ，         。
            i = bisect.bisect(dp, [s + 1]) - 1
            #               ，     dp     p          ，      ， dp      。
            #              ，     job  。
            #        ，                 。
            if dp[i][1] + p > dp[-1][1]:
                dp.append([e, dp[i][1] + p])
        return dp[-1][1]

startTime = [1,2,3,3]; endTime = [3,4,5,6]; profit = [50,60,40,70]
target = 120
m = Solution().jobScheduling(startTime, endTime, profit)
print(m)