LeetCode之外,資料結構與演算法解題技巧-Counter, Pointer, Sliding Window

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個 小技巧重點重溫~下集待續~~

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *