lintcode の質問レコード 3

Expression ExpandWord Break IIPartition Equal Subset Sum

文字列展開問題、[] の前の数値に従って文字列を展開、主に 2 つのスタックを維持します。1 つは数値スタックを展開し、もう 1 つはスタックを展開します。コンテンツ スタックを展開する、コンテンツ スタックを追加する [展開するすべてのコンテンツを押し出すかどうかを決定するために使用されます。数値は 1 桁以上になる可能性がありますが、問題ではありません。

class Solution:# @param {string} s  an expression includes numbers, letters and brackets# @return {string} a stringdef expressionExpand(self, s):# Write your code herenl=[]
        sl=[]
        sc=''res=''lstr=''for i in s:if i.isdigit():if not lstr.isdigit():
                    sl.append(sc)
                    sc=''sc = sc + ielse:if i=='[':
                    nl.append(int(sc))
                    sc = ''sl.append('[')elif i==']':
                    n=nl.pop()while len(sl)>0:
                        k=sl.pop()if k== '[':breaksc = k+ sc
                    ts=''for j in range(n):ts= ts + sc
                    sc=''if len(nl) > 0:sl.append(ts)else:
                        res = res + tselse:if len(nl)>0:
                        sc = sc + ielse:
                        res = res + i
            lstr=ireturn res

] II

配列内の単語分割問題 先頭から文字列の検索を開始し、見つかったらスタックに追加し、毎回ポップをループしてポップされた文字列が完全かどうかを判断し、完全であれば結果を追加します完了していない場合は、フォローアップを探してスタックに追加します。ここでも、wordDict には特定のあいまいさが存在します。再利用されるのか？

文字列が非常に長く、その後ろに多くの辞書配列がある場合、これは非常に遅くなります。今のところ、提供されているテストデータではそのような状況はないようです。 lintcode. 特殊なケースが 1 つだけあるので、前にフィルターを追加しました。これは渡されますが、Python の startwith 関数にも注意する必要があります

パラメーターが '' の場合、常に True を返します。これは少し注意が必要です。 .. タイトルには、多くの数値が 100 を超えない整数で、配列の長さが 200 を超えないことが条件とあります。これは、ナップザック問題の簡易版です。すべての数値の合計は、偶数の場合は 2 つのグループに分割され、それ以外の場合は false が返され、グループの最終的な合計が求められます。ナップザック問題の容量は、ナップザックに入れるものと似ています。ナップザック問題と異なるのは、ナップザック問題では最後のグリッドまで移動する必要があることだけです。はこの合計に等しいです

class Solution:# @param {string} s a string# @param {set[str]} wordDict a set of wordsdef wordBreak(self, s, wordDict):# Write your code herehead=[]
        ss=''for i in s:if ss=='':
                ss=ielse:if i not in ss:
                    ss = ss + ifor i in ss:
            flag=Falsefor di in wordDict:if i in di:
                    flag=Truebreak;if not flag:return []for di in wordDict:if di !='' and  s.startswith(di):
                head.append(di)if len(head)<1:return []
        cur=s
        res=[]while len(head)>0:
            h=head.pop()
            le=len(h.replace(' ',''))
            cur=s[le:]if cur == '': 
                res.append(h)continuefor di in wordDict:if cur.startswith(di):
                    head.append(h+' '+di)                    return res

以上がlintcode の質問レコード 3の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。