Js

Trie

Implement Trie

insert、search、および startsWith メソッドを持つトライを実装します。

例

Trie trie = new Trie()；

注。

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

単語の追加と検索 - データ構造の設計

次の2つの操作をサポートするデータ構造を設計してください。

void addWord(word) bool search(word)

search(word)は、リテラルな単語、またはa-zまたは...の文字のみを含む正規表現文字列を検索することができます。 A . は任意の1文字を表します。

例

注：すべての単語は小文字のa-zで構成されていると仮定してもかまいません。

考える

1 208で作成したトライツリーを使用して、検索条件を変更するだけです。

和集合

フレンドサークル

あるクラスにN人の生徒がいます。 そのうちの何人かは友達ですが、何人かは友達ではありません。 例えば、AがBの直接の友達であり、BがCの直接の友達である場合、AはCの間接的な友達です。例えば、AがBの直接の友人であり、BがCの直接の友人である場合、AはCの間接的な友人です。

M[i][j]=1のとき、i番目の生徒とj番目の生徒は直接友達であり、そうでなければ友達ではありません。M[i][j] = 1なら，i番目とj番目の生徒は互いに直接の友達であり，そうでなければそうではありません． そして，すべての生徒間の友達サークルの総数を出力しなければなりません．

例1.

Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2 Explanation:0番目と1番目の生徒は直接の友達なので、友達サークルに入っています。 2番目の生徒自身も友達サークルに入っています。2人目も友達サークルに入っています。

例2.

Input: [[1,1,0], [1,1,1], [0,1,1]] Output: 1 Explanation:0人目と1人目は直接の友達、1人目と2人目は直接の友達なので、0人目と2人目は間接的な友達。0番目と2番目は間接的な友達であり、全員が同じ友達の輪に入っているので、1を返します。

注。

N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

離れて考える

1 タートルアイランドに似ている、タートルアイランドのアイデアが使える

2 並列チェックセット、並列チェックを使って

アイデア：1 テストでは、最後のテストケースは、コードを書くときに、それらが事前に設定された条件であるかどうかをもっと考えて合格していません。

ラインツリー

範囲合計クエリ - 変更可能

整数配列 nums が与えられたとき、添字 i から j までの要素の和を求めなさい。

update(i, val) 関数は、インデックス i の要素を val に更新して nums を変更します。

例

nums = [1, 3, 5]とします。

sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8

制約。

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.
0 <= i <= j <= nums.length - 1

思考停止

1