-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1-10-2.html
550 lines (510 loc) · 15.4 KB
/
1-10-2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="icon" href="./public/favicon.ico" />
<meta http-equiv="cache-control" content="no-cache" />
<title></title>
<link rel="stylesheet" href=" https://necolas.github.io/normalize.css/8.0.1/normalize.css" />
<link rel="stylesheet" href="./hightlight/default.min.css" />
<link rel="stylesheet" href="./css/main.css" />
<link rel="stylesheet" href="./css/copybutton.css" />
<link rel="stylesheet" href="./css/hightlight.css" />
<script src="./hightlight/hightlight.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.11/clipboard.min.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-BEVZJDBC7Z"></script>
<script src="./js/gtag.js"></script>
</head>
<body>
<header>
<nav>
<h1>
<span id="toggle-menu"></span>
<a href="index.html"></a>
</h1>
</nav>
</header>
<main>
<aside>
<nav></nav>
</aside>
<article>
<h2 id="1-10-2">1-10-2 演算法設計</h2>
<h3>Linear Search 線性搜尋</h3>
<p>實作思路：</p>
<p>
土法煉鋼從頭到尾一個一個搜尋一集合中的目標元素，直到找到目標元素停止或是搜索到最後一個元素仍然沒有匹配的元素結做結束。
</p>
<pre><code class="language-js">
function linearSearch(array, targetElement) {
for (let index = 0;index < array.length;index++) {
if (targetElement === array[index]) {
return index;
}
}
return -1;
}
</code></pre>
<table>
<thead>
<tr>
<th>複雜度</th>
<th>Big O值</th>
<th>說明</th>
</tr>
</thead>
<tbody>
<tr>
<th>最差時間複雜度</th>
<td>O(n)</td>
<td>直到走訪到最後一個元素才找到或該集合不包含此元素</td>
</tr>
<tr>
<th>最佳時間複雜度</th>
<td>O(1)</td>
<td>第一個走訪到的元素就是目標元素。</td>
</tr>
<tr>
<th>平均時間複雜度</th>
<td>O(n)</td>
<td></td>
</tr>
</tbody>
</table>
<h3>Binary Search 二分搜尋演算法</h3>
<p>實作思路：</p>
<p>
假設有一個從小到大排序過的集合，設定集合中間的索引為基準，將集合分成兩半，另外再列出集合索引的最大值及最小值。
</p>
<p>如果這個數字大於中間值的元素表示目標在集合右側，反之則在左側。</p>
<p>
如果在右側就將最小值由中間值代換，反之則將中間值代換為最大值，代換完成再另外找中間的索引繼續下一輪動作。
</p>
<p>效率會比 Linear Search 來得好，只不過使用條件必須是在有排序的集合上。</p>
<pre><code class="language-js">
function binarySearch(arr, n) {
let min = 0;
let max = arr.length - 1;
let step = 0;
while (min <= max) {
step++;
let middle = Math.floor((max + min) / 2);
if (n > arr[middle]) {
min = middle + 1;
} else if (n < arr[middle]) {
max = middle - 1;
} else if (n === arr[middle]) {
console.log("Found number " + n + " at position " + middle);
console.log("Found it after " + step + " steps.");
return middle;
}
}
console.log("Cannot find number " + n);
return -1;
}
</code></pre>
<table>
<thead>
<tr>
<th>複雜度</th>
<th>Big O值</th>
<th>說明</th>
</tr>
</thead>
<tbody>
<tr>
<th>最差時間複雜度</th>
<td>O(log n)</td>
<td>直到走訪到最後一個元素才找到或該集合不包含此元素</td>
</tr>
<tr>
<th>最佳時間複雜度</th>
<td>O(1)</td>
<td>元素正好在集合的正中間的索引上。</td>
</tr>
<tr>
<th>平均時間複雜度</th>
<td>O(log n)</td>
<td></td>
</tr>
</tbody>
</table>
<h3>設計概念1 Counter</h3>
<p>尋找兩集合中共相似之處可以使用的概念。</p>
<p>Counter 案例1-尋找共同元素</p>
<pre><code class="language-js">
const array1 = [1,3,5,6,7,8]
const array2 = [1,4,5,9,7,8,10]
function intersection(array1,array2){
let result = []
let array3 = array1.concat(array2)
let counter = {}
for(let i = 0; i < array3.length; i++){
if(!counter[array3[i]] ){
counter[array3[i]] = 1
}else{
counter[array3[i]]++
}
}
for(key in counter){
if(counter[key]===2){
result.push(key)
}
}
return result
},
</code></pre>
<p>Counter 案例2-尋找2個字串中，不管排列組合，比較是否使用相同的字母。</p>
<pre><code class="language-js">
function sameFrequency(str1,str2){
let array1 = str1.split('')
let array2 = str2.split('')
if(array1.length != array2.length)false
let counter1 = {}
let counter2 = {}
let result = true
array1.forEach(letter){
if(!counter1[letter]){
counter1[letter] = 1
}else{
counter1[letter]++
}
}
array2.forEach(letter){
if(!counter2[letter]){
counter2[letter] = 1
}else{
counter2[letter]++
}
}
for(letter in counter1){
if(!counter2[letter])false
if( counter1[letter]!==counter2[letter]){
result = false
}
}
return result
}
sameFrequency('abbc','aabc') // false
sameFrequency('abba','abab') // true
sameFrequency('aasdebasdf','adfeebed') // false
</code></pre>
<h3>設計概念2 Pointer</h3>
<p>直接看案例：</p>
<p>
現在有一個需求，寫出一個方法，從集合中找出所有兩個為一對的數字,每一對數字的平均為選定的目標數字。
</p>
<p>
像這樣
<code>averagePair([-11,0,1,2,3,9,14,17,21],1.5)</code>
回傳
<code>[[-11,14],[0,3],[1,2]]</code>
</p>
<p>實作思路：將陣列由小到大排序後，由陣列的第一個和最後一個數字開始操作。</p>
<p>
(-11+21)/2 = 5 >
1.5。結果不成對，接著從最後一個數字往回找，也就是17，然後再運算一次。(-11+17)/2 = 3 >
1.5。結果還是不成對，接著找到 14。 (-11+14)/2 = 1.5 = 1.5。找到一組後將 [-11
,14]挑出來繼續找尋。 (0+9)/2 = 4.5 > 1.5 ..... 依此類推。
</p>
<pre><code class="language-js">
function averagePair(array,target){
let result =[]
let pointer1 = 0
let pointer2 = array.length -1
for(var i=0; i < array.length-1; i++){
if(pointer2-pointer1>0){// 避免重複
const element1 = array[pointer1]
const element2 = array[pointer2]
if((element1+element2)/2!==target){
pointer2--
}else{
result.push([element1,element2])
pointer1++
pointer2--
}
}
}
return result
}
</code></pre>
<p>
Pointer 案例2：現在有一個需求，寫一個方法判斷一個輸入的字串使否是'迴文
palindrome'(英文語系中正讀反讀一模一樣，都能通的詞句)。像這樣：
</p>
<pre><code class="language-js">
palindrome("tacocat"); // true
palindrome("amanaplanacanalpanama"); // true
palindrome("asdfsafeaw"); // false
</code></pre>
<p>同樣以 Pointer 概念實作方式如下：</p>
<pre><code class="language-js">
function palindrome(str) {
let left = 0;
let right = str.length - 1;
while (left <= right) {
console.log(str[left], str[right]);
if (str[left] == str[right]) {
left++;
right--;
} else {
console.log(false);
return false;
}
}
console.log(true);
return true;
}
</code></pre>
<p>
Pointer
案例3：現在有一個需求，寫一個方法判斷第二個字串是否刪掉幾個字之後在順序不變的情況下可以轉變成第一個字串。像這樣：
</p>
<pre><code class="language-js">
isSubsequence("hello", "hello Dear"); // true 刪掉 ' Dear'
isSubsequence("book", "brooklyn"); // true 刪掉 'r' 'lyn'
isSubsequence("abc", "bac"); // false (order matters)
</code></pre>
<pre><code class="language-js">
function isSubsequence(str1, str2) {
if (str1.length == 0) {
console.log(true);
return true;
}
let pointer1 = 0;
let pointer2 = 0;
while (pointer2 < str2.length) {
if (str1[pointer1] == str2[pointer2]) {
pointer1++;
}
if (pointer1 >= str1.length) {
console.log(true);
return true;
}
pointer2++;
}
console.log(false);
return false;
} </code></pre>
<h3>Pointer 案例4：Sliding Window 演算法</h3>
<p>
指定一個小於集合
<code>length</code>
的 size,將一組集合每連續 size 個元素分成一組子集合，依序將所有子集合列舉出來。
</p>
<p>舉個例子：</p>
<pre><code class="language-js">
// 有一組集合：[a,b,c,d,e,f,g]
// 子集合 size 指定為 3
// 結果如下
// [a,b,c]
// [b,c,d]
// [c,d,e]
// [d,e,f]
// [e,f,g]
</code></pre>
<p>下列例子除了列舉子集合之外，額外將個別子集合都加總計，並計算最大、最小值。</p>
<pre><code class="language-js">
function maxSum(arr, size) {
if (size > arr.length) {
return null;
}
let maxValue = 0;
for (let i = 0; i < size; i++) {
maxValue += arr[i];
}
let temValue = maxValue;
for (let j = size; j < arr.length; j++) {
temValue = temValue + arr[j] - arr[j - size];
if (temValue > maxValue) {
maxValue = temValue;
}
}
console.log(maxValue);
return maxValue;
}
function minSum(arr, size) {
let min_value = Infinity;
if (size > arr.length) {
return null;
}
for (let i = 0; i <= arr.length - size; i++) {
let attempt = 0;
for (let j = i; j < i + size; j++) {
attempt += arr[j];
}
if (attempt < min_value) {
min_value = attempt;
}
}
console.log(min_value);
return min_value;
}
maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 2); // 12
minSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3); // -28
</code></pre>
<h3>Pointer 案例4：案例: Min Sub Array</h3>
<p>
製作一個名叫 minSubArray 的
<code>function</code>
，該函式要從一個母集合中找出
<code>length</code>
最短且元素加總大於等於指定數字的一個子集合。找不到就回傳數字 0 。如下案例演示：
</p>
<pre><code class="language-js">
minSubArray([1,2,3,4,5,6,10],10) // [10] min length 1
minSubArray([1,2,3,4,5,6],10) // [5,6] min length 2
</code></pre>
<p>實作方式：</p>
<pre><code class="language-js">
function minSubArray(arr, sum) {
let start = 0;
let end = 0;
let total = 0;
let minLength = Infinity;
while (start < arr.length) {
if (total < sum && end < arr.length) {
total += arr[end];
end++;
} else if (total >= sum) {
let currentLength = end - start;
if (minLength > currentLength) {
minLength = currentLength;
}
total -= arr[start];
start++;
} else if (end >= arr.length) {
break;
}
}
if (minLength === Infinity) {
console.log("Cannot find subarray that can sum up to the given number");
return 0;
} else {
console.log(minLength);
return minLength;
}
}
minSubArray([8, 1, 6, 15, 3, 16, 5, 7, 14, 30, 12], 70);
</code></pre>
<h3>Pointer 案例5：案例: Unique Letter Substring</h3>
<p>
製作名叫 uniqueLetterString 的
<code>function</code>
。在順序不變的情況下，截出最短的且字母不重複的子字串。
</p>
<pre><code class="language-js">
uniqueLetterString('HatingJOJOIsaJOJOReferenceIs') // 8 'HatingJO'
</code></pre>
<p>實作方式如下：</p>
<pre><code class="language-js">
function uniqueLetterString(str) {
let start = 0;
let end = 0;
let counter = {};
let maxLength = -Infinity;
while (end < str.length) {
console.log(counter);
if (counter[str[end]]) {
counter[str[start]]--;
start++;
} else {
counter[str[end]] = 1;
end++;
if (end - start > maxLength) {
maxLength = end - start;
}
}
}
if (maxLength == -Infinity) {
console.log("Cannot find unique letters substring.");
return null;
}
console.log(maxLength);
return maxLength;
}
</code></pre>
<h3>Pointer 案例6：案例: Largest Product 最大乘積</h3>
<p>
製作名叫 largestProduct 的
<code>function</code>
。在順序不變的情況下，從輸入的有 1000 個數字的集合中找出一個子集合，子集合內為母集合中 4
個相鄰且乘積數最大的陣列。
</p>
<p>實作方式如下：</p>
<pre><code class="language-js">
function largestProduct(n) {
let currentProduct;
let maxProduct = -Infinity;
let left = 0;
let right = n - 1;
while (right < thousandDigits.length) {
currentProduct = 1;
for (let i = left; i <= right; i++) {
currentProduct *= thousandDigits[i];
}
if (currentProduct > maxProduct) {
maxProduct = currentProduct;
}
right++;
left++;
}
console.log(maxProduct);
return maxProduct;
}
</code></pre>
<h3>設計概念3 Recursion 遞迴</h3>
<p>
一個
<code>function</code>
自己執行自己。
</p>
<h3>Recursion 案例1 Fibonacci Sequence 費波南西數列</h3>
<p>
製作名叫 fibonacciSequence 的
<code>function</code>
。使之列舉出前 n 項費波南西數列。
</p>
<pre><code class="language-js">
function fibonacciSequence(n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fs(n - 1) + fs(n - 2);
}
}
for (let i = 0; i < 15; i++) {
console.log(fibonacciSequence(i));
}
</code></pre>
<h3>Recursion 案例2 RArray of Arrays</h3>
<p>
在製作 menu
或者要在有嵌套巢狀資料結構中找到或迭代等操作時經常用到。以下例子為將一個巢狀陣列中所有的元素抽取出來製作一個非巢狀的陣列。
</p>
<pre><code class="language-js">
function collector(arr1) {
let result = [];
helper(arr1);
return result;
function helper(arr2) {
for (let i = 0; i < arr2.length; i++) {
if (Array.isArray(arr2[i])) {
helper(arr2[i]);
} else {
result.push(arr2[i]);
}
}
}
}
</code></pre>
</article>
</main>
</body>
<script type="module" src="./js/main.js"></script>
</html>