用 TDD 來練習完成 leet code 的第 219 題，題目描述如下。
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
題目解釋：給一個 int[] nums ，以及一正整數 k ，如果存在著 i 與 j 使得 nums[i] = nums[j]，且 |i-j|<= k，則回傳 true。若不然，則回傳 false。
這篇文章要透過 TDD 的方式，來解釋我的思路跟程式碼演進過程。
第一個紅燈，k = 0，應回傳 false。
這個測試案例代表的用意，是先用最簡短的路徑，處理實際的商業邏輯，透過測試驅動產生出來產品程式碼的 class 名稱、function 名稱、參數名稱與型別、回傳的型別。
這個測試案例代表的用意，是先用最簡短的路徑，處理實際的商業邏輯，透過測試驅動產生出來產品程式碼的 class 名稱、function 名稱、參數名稱與型別、回傳的型別。
測試程式碼如下：
[TestClass]
public class UnitTest1
{
[TestMethod]
public void Test_k_is_zero_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 0;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
}
產品程式碼，是由測試程式碼透過 Visual Studio 產生的 class 與 function，內容如下：
public static class Solution
{
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
throw new NotImplementedException();
}
}
用最簡單的程式碼，符合測試案例邏輯，迅速通過第一個紅燈，得到第一個綠燈。
產品程式碼的處理：針對 k = 0 的情況，return false;
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
throw new NotImplementedException();
}
新增一個測試案例， nums = {5,5}, k = 1, return true;
這個測試案例代表的用意，是為了找到相同數字，回傳 true。
這個測試案例代表的用意，是為了找到相同數字，回傳 true。
測試程式碼如下：
[TestMethod]
public void Test_nums_5_5_and_k_is_1_should_return_true()
{
var nums = new int[] { 5, 5 };
var k = 1;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
產品程式碼，相同數字的部分，使用
HashSet<T> 來判斷。產品程式碼如下：
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
}
throw new NotImplementedException();
}
新增一個測試案例，nums = {5,6}, k = 1, return false;
這個測試案例用意為，當都不存在相同的數字時，該回傳 false。
這個測試案例用意為，當都不存在相同的數字時，該回傳 false。
測試程式碼如下：
[TestMethod]
public void Test_nums_5_6_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
產品程式碼邏輯，如果每一個數字都不相同，回傳 false。
產品程式碼如下：
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
}
return false;
}
目前還沒用到 k, 所以新增一個測試案例，nums = {5,6,5}, k = 1, return false;
這個測試案例用意，是假設 nums 中有重複的數字 5, 但其 index 差距大於 k，應回傳 false。目前會 failed, 原因是 HashSet 只要加不進去就回傳 true。
這個測試案例用意，是假設 nums 中有重複的數字 5, 但其 index 差距大於 k，應回傳 false。目前會 failed, 原因是 HashSet 只要加不進去就回傳 true。
測試程式碼如下：
[TestMethod]
public void Test_nums_5_6_5_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6, 5 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
產品程式碼的實作，我這邊使用 slide window 的概念，也就是把 k 當作 window 的 size 基準。（嚴格來說是 k + 1，因為 k 是距離，window size 是 window 裡面的 int 個數），判斷 window 裡面是否存在著重複的數字，若存在則 return true; 否則 return false;
產品程式碼透過 Skip().Take() 取得 window 裡面的 numbers 判斷 window 中是否存在重複數字，如不存在，則往下一個 index 滑動。程式碼如下：
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
var windowSize = k + 1;
for (int i = 0; i < nums.Length; i++)
{
var windowNums = nums.Skip(i).Take(windowSize);
var set = new HashSet<int>();
foreach (var windowNum in windowNums)
{
if (!set.Add(windowNum)) return true;
}
}
return false;
}
這一步跳比較大，同時滿足了下面的測試案例：nums = {5,6,5}, k = 2, return true 的情況。測試案例如下：
[TestMethod]
public void Test_nums_5_6_5_and_k_is_2_should_return_true()
{
var nums = new int[] { 5, 6, 5 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
演算法的主要功能已經完成了，在我提供我的產品程式碼作法與 wechat 上的朋友 @武可 討論之後，他提出了一個演算法優化的寫法。
目前產品程式碼的作法，是每次 window 要往右滑時，起一個新的 window 去拿框框內的元素，進而檢查是否存在重複數字。
而他的建議是，只保留一個 window 的 instance ，當 window 右滑時，如果有元素的位置已經不在 window size 框框內，就將其從 window 中移除。
而他的建議是，只保留一個 window 的 instance ，當 window 右滑時，如果有元素的位置已經不在 window size 框框內，就將其從 window 中移除。
重構後的產品程式碼如下：
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
//keep only 1 window sliding, remove int just out of window
if (i >= k) set.Remove(nums[i - k]);
}
return false;
}
通過 leet code 的所有測試案例，並符合執行效能限制。
結論
- 拿 leet code 來練 TDD 挺過癮的
- leet code 通常都會針對演算法而有效能限制，而優化演算法效能的部分，很難從 TDD 來驅動優化的設計過程。
但這並非代表 TDD 無用，因為在一開始使用 TDD 透過一個一個代表關鍵商業邏輯的測試案例，來一步步堆砌成滿足需求的產品程式碼，是很有幫助的。在這個過程中，會一步步釐清自己的想法與需求的複雜性。
到最後如果需要對效能或演算法進行優化，不論是判斷式或迴圈的搬移、合併、調整，甚至整個演算法重寫，透過版本控管的保護，你隨時可以還原到可運作的版本。透過先前完整的關鍵商業邏輯測試案例保護，你不必擔心優化或重寫演算法的過程中，漏了什麼特別的需求。 - TDD 是種修煉，也是種習慣的養成。當你茫然毫無頭緒，想理頭緒時，TDD 讓你很容易下手。TDD 可以讓你先求有，再求好。
我的 github commit history 可以看到 TDD 的過程
最後的完整程式碼如下：
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;
namespace ContainsDuplicateII
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void Test_k_is_zero_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 0;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_5_5_and_k_is_1_should_return_true()
{
var nums = new int[] { 5, 5 };
var k = 1;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_5_6_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_5_6_5_and_k_is_1_should_return_false()
{
var nums = new int[] { 5, 6, 5 };
var k = 1;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_5_6_5_and_k_is_2_should_return_true()
{
var nums = new int[] { 5, 6, 5 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_1_2_3_2_1_k_is_2_should_return_true()
{
var nums = new int[] { 1, 2, 3, 2, 1 };
var k = 2;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_1_2_3_1_2_k_is_2_should_return_false()
{
var nums = new int[] { 1, 2, 3, 1, 2 };
var k = 2;
Assert.IsFalse(Solution.ContainsNearbyDuplicate(nums, k));
}
[TestMethod]
public void Test_nums_9_5_6_9_4_4_9_and_k_is_3_should_return_true()
{
var nums = new int[] { 9, 5, 6, 4, 9, 4, 4, 9 };
var k = 3;
Assert.IsTrue(Solution.ContainsNearbyDuplicate(nums, k));
}
}
public static class Solution
{
public static bool ContainsNearbyDuplicate(int[] nums, int k)
{
if (k == 0) return false;
var set = new HashSet<int>();
for (int i = 0; i < nums.Length; i++)
{
if (!set.Add(nums[i])) return true;
//keep only 1 window sliding, remove int just out of window
if (i >= k) set.Remove(nums[i - k]);
}
return false;
}
}
}
blog 與課程更新內容，請前往新站位置：http://tdd.best/
