66道のフロントエンドのアルゴリズムの面接問題は構想の分析を添付してあなたを助けて不足を検査して補充します
25168 ワード
この部分は主にCavsZhouyouが《剣指Offer》を练习する时にした笔记で、主にアルゴリズムの関连する知识といくつかの関连する面接问题の时にした笔记に関连して、この総括を分かち合ってみんなにあげて、みんながアルゴリズムのに対して一回の全方位の検査と排查をすることができることを助けて、原作者CavsZhouyouの払うことに感谢して、原文のリンクは文章の一番下に置いて、もし间违いが现れたら、みんなで指摘してほしい!
1.2 D配列の検索
考え方:
(1)第1の方式は,2層ループを用いて順次遍歴し,その整数が含まれているか否かを判断する.この方式の最悪の場合の時間複雑度はO(n^2)である.
(2)第2の方法は,増分シーケンスの特徴を利用して,2次元配列の右上隅から遍歴することができる.現在の値が求めた数より小さい場合は、位置を下に移動して判断します.現在の値が求めた数より大きい場合は、位置を左に移動して判断します.この方式の最悪の場合の時間複雑度はO(n)である.
2.スペースの置換
3.末尾からチェーンテーブルを印刷する
4.ツリーの再構築
5.2つのスタックでキューを実装
6.回転配列の最小数値
関連資料は参考できる:『回転配列の最小数値』
7.フィボナッチ数列
8.階段を跳ぶ
9.変態ステップ
タイトル:
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
考え方:
変態ステップの問題は前の問題の思考案と同じであり,各項目の値が前のすべての項目の値の和に等しいという結論を得ることができる.
f(1)=1 f(2)=f(2−1)+f(2−2)/f(2−2)は、2次の1回2次ジャンプの回数を表す.f(3) = f(3-1) + f(3-2) + f(3-3)...f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
もう一度まとめると
10.長方形のオーバーライド
11.バイナリの1の個数
12.数値の整数次数
13.奇数が偶数より前になるように配列順序を調整する
14.チェーンテーブルの最後からk番目のノード
15.チェーンテーブルの反転
16.2つのソートされたチェーンテーブルをマージする
17.ツリーのサブ構造
18.ツリーのミラーリング
19.時計回りの印刷マトリックス
20.スタックを定義し、min関数を実現する
21.スタックの圧入イジェクト
22.ツリーを上から下へ印刷
23.二叉探索木の後順遍歴
24.ツリーと値パス
25.複雑なチェーンテーブルのコピー
26.ツリーと双方向チェーンテーブル
27.文字列の配置
詳細は、『文字列の並び』を参照してください.
28.配列の出現回数が半分を超える数字
詳細は、『出現回数が半分を超える数字』を参照してください.
29.最小のK個数
詳細は、『最小のk個数を探す』を参照してください.
30.連続サブ配列の最大和
詳細は、『連続サブ配列の最大和』を参照してください.
31.整数のうち1が出現した回数(理解を深める必要がある)
詳細は、「1からnまでの整数に1が現れる回数:O(logn)アルゴリズム」を参照してください.
32.配列を最小にする数
詳細は、『配列を最小にする数』を参照してください.
33.ブス数(理解を深める必要がある)
34.最初に1回しか現れない文字
35.配列内の逆順序ペア
詳細は、「配列内の逆順序ペア」を参照してください.
36.2つのチェーンテーブルの最初の共通ノード
詳細は、「2つのチェーンテーブルの最初の共通ノード」を参照してください.
37.ソート配列に数値が表示された回数
38.ツリーの深さ
39.バランスツリー
40.配列に一度しか現れない数字
41.およびSの連続正数シーケンス
詳細は、『sとの連続正数シーケンス』を参照してください.
42.とSの2つの数字
詳細は、『とSの文字列』を参照してください.
43.左回転文字列
44.単語の順序を反転する
45.トランプの順子
詳細は、『トランプの順子』を参照してください.
46.丸の最後に残った数字(ジョセフリング問題)
詳細は、「丸の最後に残った数字」を参照してください.
47. 1+2+3+...+n
48.加減算なしで加算する
49.文字列を整数に変換する.
50.配列内の重複数
51.積配列の構築
詳細は、「積配列の構築」を参照してください.
52.正規表現の一致
詳細は、正規表現の一致を参照してください.
53.数値を表す文字列
54.文字ストリームの最初の重複しない文字
55.チェーンテーブルのリングの入口接点
詳細は、『チェーンテーブルのリングの入口接点』、『剣指offer』——チェーン時計の中のリングの入り口の結点を参照してください.
56.チェーンテーブルの重複するノードを削除する
57.ツリーの次のノード
58.対称二叉木
59.二叉木をジグザグ順に印刷する(詳しく理解する必要がある)
詳細は、「二叉木をフォント順に印刷」を参照してください.
60.二叉木を上から下へ層ごとに印刷し、同じ層の接点を左から右へ出力する.各層に1行出力します.
61.二叉木を直列化する(深い理解がある)
62.二叉探索木のK番目のノード
63.データ・ストリームの中央値(詳細は後述)
64.スライドウィンドウの最大値(詳細は後述)
65.マトリクス内の経路(詳しく理解されるべき)
66.ロボットの運動範囲(理解が必要)
剣指offerに関する資料は参考になります. 『剣指offerテーマ練習及び構想分析』 『JS版剣指offer』 『剣指Offer学習心得』
推奨
筆者は再び壁裂推薦収蔵この原文をCavsZhouyou-フロントエンド面接復習ノートに収録し、この倉庫は原作者の募集時の先端復習ノートであり、主にいくつかの重要な知識点と先端面接問題を総括し、皆さんに役に立つことを望んでいる.
最後にもし文章とノートがあなたの少しの助けあるいは啓発をもたらすことができるならば、あなたの称賛とコレクションをけちけちしないでください、あなたのはきっと私の前進の最大の動力です
附笔链接,阅读往期更多优质文章可移步查看,喜欢的可以给我点赞励哦:https://github.com/Wscats/art...
1.2 D配列の検索
：
， ， 。 ，
， 。
考え方:
(1)第1の方式は,2層ループを用いて順次遍歴し,その整数が含まれているか否かを判断する.この方式の最悪の場合の時間複雑度はO(n^2)である.
(2)第2の方法は,増分シーケンスの特徴を利用して,2次元配列の右上隅から遍歴することができる.現在の値が求めた数より小さい場合は、位置を下に移動して判断します.現在の値が求めた数より大きい場合は、位置を左に移動して判断します.この方式の最悪の場合の時間複雑度はO(n)である.
2.スペースの置換
：
， “%20”。 ， We Are Happy. We%20
Are%20Happy
：
， replace “%20”
str.replace(/\s/g,"%20")
3.末尾からチェーンテーブルを印刷する
：
， 。
：
， ， 。 ， ， 。
Array push pop 。
4.ツリーの再構築
：
， 。 。
{1,2,4,7,3,5,6,8} {4,7,2,1,5,3,8,6}， 。
：
， 。 ，
， 。 。
O(n)， O(logn)。
5.2つのスタックでキューを実装
：
， Push Pop 。
：
， 。 ， 1 2。 push ，
push 1 。 pop ， 2 ， pop 。 2 ， 1
pop push 2 ， 2 pop 。
：
， 。
6.回転配列の最小数値
：
， 。 ，
。 {3,4,5,1,2} {1,2,3,4,5} ， 1。 NOTE： 0，
0， 0。
：
（1） ， 。
， 。 ， ， 。
（2）
関連資料は参考できる:『回転配列の最小数値』
7.フィボナッチ数列
：
， n， n 。 n<=39
：
， 0， 1， ， ，
n 。 ， O(n)， O(1)。
8.階段を跳ぶ
：
1 ， 2 。 n 。
：
， 1 2 ， n ， n-1 ，
n-2 ， f(n) = f(n-1) + f(n-2)。
， 1 2， 。
9.変態ステップ
タイトル:
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
考え方:
変態ステップの問題は前の問題の思考案と同じであり,各項目の値が前のすべての項目の値の和に等しいという結論を得ることができる.
f(1)=1 f(2)=f(2−1)+f(2−2)/f(2−2)は、2次の1回2次ジャンプの回数を表す.f(3) = f(3-1) + f(3-2) + f(3-3)...f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
もう一度まとめると
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2\*f(n-1),(n>=2)10.長方形のオーバーライド
：
2*1 。 n 2*1 2\*n ，
？
：
11.バイナリの1の個数
：
， 1 。 。
：
0 ， 1。 1， 1 ， 1 0，
， ， 1。 1 ，
。
：1100&1011=1000
12.数値の整数次数
：
double base int exponent。 base exponent 。
：
exponent ， 。
13.奇数が偶数より前になるように配列順序を調整する
：
， ， ，
， ， 。
：
， 。 ，
， ， 。 。 O(n)，
O(n)。
14.チェーンテーブルの最後からk番目のノード
：
， k 。
：
， ， k-1 ， k 。
， ， k 。
15.チェーンテーブルの反転
：
， ， 。
：
pre、current next， 、 。 ，
next ， pre， pre ，current ne
xt ， 。
16.2つのソートされたチェーンテーブルをマージする
：
， ， 。
：
， 。
17.ツリーのサブ構造
：
A、B， B A 。（ps： ）
：
A ， B R 。
R ， ， B ， 。
18.ツリーのミラーリング
：
， 。
：
， ， 。 。
19.時計回りの印刷マトリックス
：
， ，
， ： 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
：
（1） 。 ， ，
。
（2） ， ， 90 ， ， 。
20.スタックを定義し、min関数を実現する
：
， min 。
：
， ， 。
。
21.スタックの圧入イジェクト
：
， ， 。 。
1,2,3,4,5 ， 4,5,3,2,1 ， 4,3,5,1,2
。（ ： ）
：
， ， ，
， ， ， ， ， ，
。 ， ， 。
22.ツリーを上から下へ印刷
：
， 。
：
， 。 。 ， ，
， 0 ， 。
23.二叉探索木の後順遍歴
：
， 。 Yes， No。
。
：
， 。 ， ，
， ， 。 ，
。
24.ツリーと値パス
：
， 。
。
：
， ， 。
25.複雑なチェーンテーブルのコピー
：
（ ， ， ， ），
head。（ ， ， ）
：
（1） ， ， next 。 ， ra
ndom ， random ， O(n^2)。
（2） ， ， Map 。
， random ， Map ，
， O(n)， O(n)。 。
（3） ， ， 。 ，
random ， ， random
。 ， O(n)。
26.ツリーと双方向チェーンテーブル
：
， 。 ， 。
：
， ， ，
。
， ， ，
。 ， ，
。 ， 。
27.文字列の配置
：
， 。 abc， a,b,c
abc,acb,bac,bca,cab cba。 ： ， 9（ ）， 。
：
， ， 。 ，
， ， 。
。 ， 。
詳細は、『文字列の並び』を参照してください.
28.配列の出現回数が半分を超える数字
：
。 。 9 {1,2,3,2,2,2,5,4,2}。
2 5 ， ， 2。 0。
：
（1） ， 。 ，
O(nlogn)。
（2） ， 。
。 ， 。 partition ，
， partition index， index n/2，
， ， index n/2， index ， ，
。 index ， ， ， O(n)。
（3） ， ：
， 。 ， ， 1， ， 1，
0， ， 1。 ，
1 。 O(n)， O(1)。
詳細は、『出現回数が半分を超える数字』を参照してください.
29.最小のK個数
：
n ， K 。 4,5,1,6,2,7,3,8 8 ， 4 1,2,3,4 。
：
（1） ， k 。
， O(nlogn)。
（2） k ， k 。 part
ition 。 ， ， ，
k-1 ， k 。 k-1 ，
n-1， n ， k-n ，
。 k-1 ， k ， 。
O(n)。
（3） k 。 ， k ， ，
k k 。 k ， ，
， ， 。 ， ， 。
O(nlogk)。
詳細は、『最小のk個数を探す』を参照してください.
30.連続サブ配列の最大和
：
HZ 。 ， : ，
, ， 。 ， ， ，
？ ：{6,-3,-2,7,-15,1,2,2}， 8（ 0 ， 3 ）。
？（ 1）
：
（1） ， ， 。
， 。 O(n^2)。
（2） ， ， ， ， 。
， 。 ， 0，
， 。 ， ， 。
O(n)。
詳細は、『連続サブ配列の最大和』を参照してください.
31.整数のうち1が出現した回数(理解を深める必要がある)
：
1~13 1 ， 100~1# 300 1 ？ 1~13 1 1、10、11、
12、13 6 ， 。ACMer ， ，
1 。
：
（1） ， 1 ， 。
（2） 1 ， 。
詳細は、「1からnまでの整数に1が現れる回数:O(logn)アルゴリズム」を参照してください.
32.配列を最小にする数
：
， ， 。 {3，32，321
}， 321323。
：
（1） ， 。
（2） ， ， ， ，
， 。 ， 。
詳細は、『配列を最小にする数』を参照してください.
33.ブス数(理解を深める必要がある)
：
2、3 5 。 6、8 ， 14 ， 7。 1 。
N 。
：
（1） ， 2， 1。 3， 1。
5， 1。 ， N 。
（2） ， 。
34.最初に1回しか現れない文字
：
（1<= <=10000， ） ， 。
：
（1） ， 。 ， ， 。
O(n^2)。
（2） ， ， Map 。
， Map ， 。 O(n)。
35.配列内の逆順序ペア
：
， ， 。 ，
P。
：
（1） ， 。 ， 。
， 。 n 。 O(n）
， O(n^2)。
（2） ， ， ，
O(nlogn)。
詳細は、「配列内の逆順序ペア」を参照してください.
36.2つのチェーンテーブルの最初の共通ノード
：
， 。
：
（1） ， ， 。
， ， 。
m， n。 O(mn）。
（2） ， ， ，
， 。 ， ， 。
O(m+n)， O(m+n)。
（3） ， ， 。 。
， n ，n ， ，
。 O(m+n)， 。
詳細は、「2つのチェーンテーブルの最初の共通ノード」を参照してください.
37.ソート配列に数値が表示された回数
：
： 。 ｛ 1, 2, 3, 3, 3, 3, 4, 5｝ 3 ， 3
4 ， 4 。
：
（1） ， 。 O(n)。
（2） ， ， 。 ，
， 。
。 k ， k ， ，
k ， 。 k ，
。 ， 。 ，
。 ，
。 O(logn)。
38.ツリーの深さ
：
， 。 （ 、 ） ，
。
：
， 。
39.バランスツリー
：
， 。
：
（1） ， 。 1 ，
。 ， ， 。
（2） ， 。 -1， 。
-1， -1 ， 。 。
40.配列に一度しか現れない数字
：
， 。 。
：
（1） ， ， 。
（2） ， ， 0， 0 。
， 。 ，
。 ， 。 1 A
B 。 1 ， 3 ， ，
。 ， 。
41.およびSの連続正数シーケンス
：
， ， 9~16 ， 100。 ，
100（ ）。 ， 100 ：18,19,20,21,22。
， S ？Good Luck! ： S 。
， 。
：
， 1 2， 3 ， ，
。 ， （ ）。 ，
， 。 ， ， ，
， 。
詳細は、『sとの連続正数シーケンス』を参照してください.
42.とSの2つの数字
：
S， ， S， S，
。 ： ， ， 。
：
， ， ， 。
s 。 ， ，
。 s ， s ， 。
s ， 。 s ， 。
詳細は、『とSの文字列』を参照してください.
43.左回転文字列
：
（ROL）， ， 。
S， K 。 ， S=”abcXYZdef”， 3 ， “X
YZdefabc”。 ？OK， ！
：
44.単語の順序を反転する
：
Fish， ， 。 Cat Fish ，
Fish ， 。 ，“student. a am I”。 ，
， “I am a student.”。Cat ， ？
：
， ， 。
45.トランプの順子
：
LL ， ， 2 ，2 （ 54 ^\_^）...
5 ， ， ， ， ， ！！“ A， 3， ，
， 5”，“Oh My God!” ..... LL ， ， \ ， A 1，J 11，
Q 12，K 13。 5 “1,2,3,4,5”（ 2 4），“So Lucky!”。LL 。
， ， LL 。 ， 0。
：
5 ， 。 ， 0 ， 0
。 ， ， 。
， 。
3 ： ， 0 ， 。
0 ， ： 。 ， ： 0
， 。 ， 。
詳細は、『トランプの順子』を参照してください.
46.丸の最後に残った数字(ジョセフリング問題)
：
0, 1, … , n-1 n ， 0 m 。
。
：
（1） 。
（2） （ ）
詳細は、「丸の最後に残った数字」を参照してください.
47. 1+2+3+...+n
：
1+2+3+...+n， 、for、while、if、else、switch、case （A?B:C）。
：
， 。 ， &&
。
48.加減算なしで加算する
：
， ， ＋、－、×、÷ 。
：
， 。
49.文字列を整数に変換する.
：
， 。 0 0。
： ， ， 。 ： ， 0。
：
， 0 ， 。
50.配列内の重複数
：
n 0 n-1 。 ， ，
。 。
：
（1） ， 。 O(nlogn)。
（2） Map ， ， 。 O
(n)， O(n)。
（3） ， ， ， ，
。 ， 。
。
51.積配列の構築
：
A[0,1,...,n-1]， B[0,1,...,n-1]， B B[i]=A[0]_A[1]_...*A[i-1]*A
[i+1]*...*A[n-1]。 。
：
（1） C[i]=A[0]×A[1]×...×A[i-1]=C[i-1]×A[i-1]
D[i]=A[i+1]×...×A[n-1]=D[i+1]×A[i+1]
B[i]=C[i]×D[i]
， ， 。
（2） ， ， 。（ ）
詳細は、「積配列の構築」を参照してください.
52.正規表現の一致
：
'.' '_' 。 '.' ， '_'
（ 0 ）。 ， 。 ， "aaa" "a.a" "ab*ac*a" ，
"aa.a" "ab\*a" 。
：
（1） （ ）
詳細は、正規表現の一致を参照してください.
53.数値を表す文字列
：
（ ）。 ， "+100","5e2","-123","3.1416" "-1E-
16" 。 "12e","1a3.14","1.2.3","+-5" "12e+4.3" 。、
：
54.文字ストリームの最初の重複しない文字
：
。 ， "go" ，
"g" 。 "google" ， "l"。 ：
， # 。
：
34
55.チェーンテーブルのリングの入口接点
：
， ？
：
， ， 。 ，
， ， ， ， ，
， n 。
， ， n ， ， ，
。
詳細は、『チェーンテーブルのリングの入口接点』、『剣指offer』——チェーン時計の中のリングの入り口の結点を参照してください.
56.チェーンテーブルの重複するノードを削除する
：
， ， ， ， 。 ， 1->2->3-
> 3->4->4->5 1->2->5
：
。 。 ，
， 。
。 ， ， 。
， 。 prev
。
57.ツリーの次のノード
：
， ？ ，
。
：
。
， ， ， 。
， ， 。
， ， ，
。
， ， ， ，
， 。 。58.対称二叉木
：
。 ， 。
：
， ， 。
， ， 。 ，
。59.二叉木をジグザグ順に印刷する(詳しく理解する必要がある)
：
， ， ，
， ， ， 。
：
。 ， 。
， ； ， 。
。詳細は、「二叉木をフォント順に印刷」を参照してください.
60.二叉木を上から下へ層ごとに印刷し、同じ層の接点を左から右へ出力する.各層に1行出力します.
：
， ， 。
：
。 ， ：
， 。61.二叉木を直列化する(深い理解がある)
：
， 。
：
62.二叉探索木のK番目のノード
：
， k 。
：
， ， k ， k 。63.データ・ストリームの中央値(詳細は後述)
：
？ ， 。
， 。64.スライドウィンドウの最大値(詳細は後述)
：
， 。 ， {2,3,4,2,6,2,5,1}
3， 6 ， {4,4,6,6,6,5}； {2,3,4,2,6,2,5,1}
6 ： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2
,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
：
65.マトリクス内の経路(詳しく理解されるべき)
：
， 。 ，
， ， ， 。 ，
。 a b c e s f c s a d e e "bcced" ， "abcb" ，
b ， 。66.ロボットの運動範囲(理解が必要)
：
m n 。 0,0 ， ， ， ， ，
k 。 ， k 18 ， （35,37）， 3+5+3+7 = 18。
， （35,38）， 3+5+3+8 = 19。 ？剣指offerに関する資料は参考になります.
推奨
筆者は再び壁裂推薦収蔵この原文をCavsZhouyou-フロントエンド面接復習ノートに収録し、この倉庫は原作者の募集時の先端復習ノートであり、主にいくつかの重要な知識点と先端面接問題を総括し、皆さんに役に立つことを望んでいる.
最後にもし文章とノートがあなたの少しの助けあるいは啓発をもたらすことができるならば、あなたの称賛とコレクションをけちけちしないでください、あなたのはきっと私の前進の最大の動力です
附笔链接,阅读往期更多优质文章可移步查看,喜欢的可以给我点赞励哦:https://github.com/Wscats/art...