LeetCode之外，資料結構與演算法解題技巧-Counter, Pointer, Sliding Window
有鑑於雖然為本科系(資管)，但是實際上在學校時期學習資料結構與演算法時，雖然那個時候都算有印象，但是都畢業這麼久了，除了偶爾看到針對 特定演算法討論，但其實更常使用的其語言函式庫提供的排序/查找，甚至Linq語法讓我們不用看到那些也可以寫出對應的程式。
最近有機會做到一些 LeetCode，汗顏只能第一直覺使用暴力法來解決問題。因此為了隨時能補足觀念問題，包含預備未來可能會遇到Dynamic Programming的演算法大魔王，因此從Udemy大特價時，快速入手了以下課程。課程連結: https://www.udemy.com/course/algorithm-data-structure/ (老師的數學觀念好，好羡慕)
從書本時代過來的我，也開始意識到其實數位課程若在合理價格的情況下，其實可以合適的當作數位書籍看待，甚至可以在anytime，anywhere(包含陪小孩去上游泳課)的時候隨時拿出來找章節來聽 ，著實方便。以下就是我重溫前幾章節 的時候，覺得不錯的技巧，事實上真實案例中 ，都會用到。不過遇到解題的時限跟題目內容理解分析過程。其實很容易 無腦使用暴力法。但下面的技巧其實就是幫助未來就算是使用O(N^2)以上的複雜度。也可以再想看看能否改善為O(N)甚至 O(logN)的方向。也作為一個小筆記吧。順勢把一些重點就重溫過一下。
Counter 技巧
使用hashtable做key/value計算次數
範例題:
Coding Practice:Intersection Problem
若寫成O(n^2)複雜度就會如下 (其關鍵是O(M*N))，有巢狀迴圈
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
foreach(var item in result)
{
Console.WriteLine(item);
}
}
public static int[] Intersection(int[] arr1, int[] arr2)
{
var result = new List<int>();
for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < arr2.Length; j++)
{
if (arr1[i] == arr2[j])
result.Add(arr1[i]);
}
}
return result.ToArray();
}
}用Counter改寫
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
foreach(var item in result)
{
Console.WriteLine(item);
}
}
public static int[] Intersection(int[] arr1, int[] arr2)
{
var result = new List<int>();
var counter = new Dictionary<int, int>();
for (int i = 0; i < arr1.Length; i++)
{
if (counter.ContainsKey(arr1[i]))
{
counter[arr1[i]]++;
}
else
{
counter.Add(arr1[i], 1);
}
}
for (int i = 0; i < arr2.Length; i++)
{
if (counter.ContainsKey(arr2[i]))
{
counter[arr2[i]]++;
}
else
{
counter.Add(arr2[i], 1);
}
}
foreach(var kv in counter)
{
if (kv.Value > 1)
{
result.Add(kv.Key);
}
}
return result.ToArray();
}
}透過Counter計數器變成分別走訪3個迴圈，其BigO應為O(m+n+m+n) = O(2(m+n)) = O(N)(常數可忽略)
課程中 再舉了一個可以用Counter解決的問題如下 :
Coding Practice:Frequency Problem
sameFrequency(“abbc”, “aabc”) false;
sameFrequency(“abba”, “abab”) true;
sameFrequency(“aasdebasdf”, “adfeebed”) false;
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
Console.WriteLine(sameFrequency("abbc", "aabc")); // false;
Console.WriteLine(sameFrequency("abba", "abab")); //true;
Console.WriteLine(sameFrequency("aasdebasdf", "adfeebed"));// false;
}
public static bool sameFrequency(string string1, string string2)
{
var arr1 = string1.ToCharArray();
var arr2 = string2.ToCharArray();
if (arr1.Length != arr2.Length)
return false;
var counter1 = new Dictionary<char, int>();
var counter2 = new Dictionary<char, int>();
for(int i = 0; i < arr1.Length;i++)
{
if (counter1.ContainsKey(arr1[i]))
{
counter1[arr1[i]]++;
}
else
{
counter1.Add(arr1[i], 1);
}
}
for(int i = 0; i < arr2.Length;i++)
{
if (counter2.ContainsKey(arr2[i]))
{
counter2[arr2[i]]++;
}
else
{
counter2.Add(arr2[i], 1);
}
}
foreach(var kv in counter1)
{
if (!counter2.ContainsKey(kv.Key))
{
return false;
}
if (counter2[kv.Key] != kv.Value)
{
return false;
}
}
return true;
}
}
在上述的程式中，可以看到篇幅不小，而且3個獨立迴圈。但在演算法時間複雜度的概念中
O(N+M+k)永遠優於O(N*M*K)，當然你可以說某一個值很小，但我們通常是假設平均的概念，所以很小情境反而應該視為特例。Pointer技巧(TwoPointer)
透過多重指針走訪所有節點
Coding Practice: Average Pair
given sorted array , find 2 integer that average is given avg value
averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);
一樣若用暴力法，做O(n^2)的解法如下:
using System;
using System.Collections;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
foreach(var itemArray in resultArray)
{
Console.WriteLine("--------------");
foreach(var item in itemArray)
{
Console.WriteLine(item);
}
}
}
public static List<int[]> averagePair(int[] array, double avg)
{
var result = new List<int[]>();
var count = 0;
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = i+1; j < array.Length; j++)
{
if ((double)(array[i] + array[j]) / 2 == avg)
{
result.Add(new[]{array[i], array[j]});
}
count++;
}
}
Console.WriteLine("total check step:" + count);
return result;
}
}結果: total check step:36 (C9取2 = 9*8/2 = 36)
————–
-11
14
————–
0
3
————–
1
2
若改用Pointer的技巧可以指定一個left pointer跟right pointer(也常稱two pointer)
using System;
using System.Collections;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
foreach(var itemArray in resultArray)
{
Console.WriteLine("--------------");
foreach(var item in itemArray)
{
Console.WriteLine(item);
}
}
}
public static List<int[]> averagePair(int[] array, double avg)
{
var result = new List<int[]>();
var count = 0;
var left = 0;
var right = array.Length-1;
while(left < right)
{
var temp = (double)(array[left] + array[right]) / 2;
if (temp > avg)
{
right--;
}
if (temp < avg)
{
left++;
}
if (temp == avg)
{
result.Add(new[]{array[left], array[right]});
right--;
left++;
}
count++;
}
Console.WriteLine("total check step:" + count);
return result;
}
}Result:
total check step:6
————–
-11
14
————–
0
3
————–
1
2
同樣的結果，可以在9步內(6步)找到一樣結果
複雜度也從巢狀迴圈走訪改成了每個節點最多走訪一次甚至因為two pointer，可以少了3次比對。
因為結果有3個符合，所以一次性left跟right同時會往內縮小範圍。
Sliding Window技巧
透過window size走訪所有的節點。每一次以給定的size橫向 移前一格索引。
Coding Practice:maxSum/minSum
given integer array , find consecutive number of given n value ‘s max and min value
maxSum([2,7,3, 0,6,1,-5,-12,-11], 3)
//minSum([2,7,3, 0,6,1,-5,-12,-11], 3)
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
Console.WriteLine(result);
}
public static int? maxSum(int[] array, int size)
{
if (array.Length < size)
return null;
var count = 0;
var max = int.MinValue;
for (int i = 0 ; i < array.Length - size; i++)
{
var temp = 0;
for (int j = i; j < i + size; j++) //
{
temp += array[j];
count++;
}
if (temp > max)
max = temp;
}
Console.WriteLine(count);
return max;
}
}上面程式的走法是 O(N*M)複雜度。(加總的迴圈的操作也是要算複雜度，也端看size的大小)
Count: 18
maxSum: 12
改善Sliding Window的寫法:
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
Console.WriteLine(result);
}
public static int? maxSum(int[] array, int size)
{
if (array.Length < size)
return null;
var count = 0;
var max = 0;
//first window
for (int i = 0 ; i < size; i++)
{
max += array[i];
count++;
}
for (int j = size ; j < array.Length; j++)
{
var temp = max + array[j] - array[j-size];
if (temp > max)
max = temp;
count++;
}
Console.WriteLine(count);
return max;
}
}Count: 9
maxSum: 12
同樣的例子變成了9次，整整省了1/2的複雜度，且變成了O(N)的複雜度(稱為線性時間)，當然那個迴圈加總還是一個關鍵。因為size不可知，所以用 迴圈動態處理，但是用sliding window的話，就每次滑動一格，所以是在可預期的步數下去做操作。最多2步。因此這也是一個滿有名的演算法，可以幫助我們在一個循序集合中，找到滿足特定條件的目標值或目標集合。
以上3個 小技巧重點重溫~下集待續~~