[TDD] leet code 219. Contains Duplicate II

用 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 名稱、參數名稱與型別、回傳的型別。

測試程式碼如下:

    [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。

測試程式碼如下:

        [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。

測試程式碼如下:

        [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。

測試程式碼如下:

        [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 中移除。

重構後的產品程式碼如下:

        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/