TDD LeetCode：905. Sort Array By Parity
RojerChen.2018.10.01
Given an array
A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:
Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Note:
1 <= A.length <= 50000 <= A[i] <= 5000
Step0 這個要怎麼測試啊？
這個要怎樣測試啊？這是我看完題目後的第一個想法。根據題目給的測試案例，這個題目有三個答案，所以我可能需要有個方法來驗證奇數資料都在偶數的後面。
有甚麼現成的方法可以驗證「奇數在偶數的後面」，如果沒有那就先來寫一個吧！
題目要求：將奇數資料排在偶數的後面
驗證程式：驗證奇數在偶數後面
Step1 給測試用的驗證程式
private bool testAlgorithm(int[] array) {
return flag;
}
Step2 準備「驗證程式」的測試資料
接下來就準備相關的測試資料。
[TestMethod]
public void 題目測試範例()
{
int[] data = new int[] { 4, 2, 3, 1 };
Boolean actual = testAlgorithm(data);
Boolean expected = true;
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void 全偶數()
{
int[] data = new int[]{ 0,0,0,0};
Boolean actual = testAlgorithm(data);
Boolean expected = true;
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void 全奇數()
{
int[] data = new int[] { 1, 1, 1, 1 };
Boolean actual = testAlgorithm(data);
Boolean expected = true;
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void 偶數奇數()
{
int[] data = new int[] { 0,1 };
Boolean actual = testAlgorithm(data);
Boolean expected = true;
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void 錯誤案例()
{
int[] data = new int[] { 1, 2 };
Boolean actual = testAlgorithm(data);
Boolean expected = false;
Assert.AreEqual(expected, actual);
}
Step3 撰寫驗證邏輯
測試資料準備完畢，接下來就是撰寫「驗證邏輯」了，我的驗證方式也很簡單，就是如果當有抓到資料是奇數的，後面的資料就必須是奇數，後面的資料如果是偶數就算失敗。
private bool testAlgorithm(int[] array)
{
bool flag = true;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] % 2 == 1)
{
if (array[i + 1] % 2 != 1)
{
flag = false;
}
}
}
return flag;
}
Step4 進入正題
終於可以進入正題了，別急，還是先準備測試資料。
public int[] SortArrayByParity(int[] A)
{
return null;
}
Step5 提供測試資料
我們準備的這些測試資料透過 SortArrayByParity 處理後，都必須是偶數在前、奇數在後，至於要如何驗證，就透過 testAlgorithm 來驗證是否正確。
[TestMethod]
public void Case1()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
[TestMethod]
public void Case2()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { 1 };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
[TestMethod]
public void Case3()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { 2 };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
[TestMethod]
public void Case4()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { 0, 2 };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
[TestMethod]
public void Case5()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { 1, 2, 3 };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
[TestMethod]
public void Case6()
{
Algorithm alg = new Algorithm();
int[] sourceArray = new int[] { 3, 1, 2, 4 };
int[] destArray = alg.SortArrayByParity(sourceArray);
Assert.IsTrue(testAlgorithm(destArray));
}
Step6 撰寫邏輯
忙了這麼久，邏輯的部分好像還沒開始寫啊，終於可以開始了(累)
關於這個題目有很多種解法，我的方是是這樣，透過兩個變數X、Y，一個從前面往後、一個從後面往前逐個檢查，如果前面的是奇數、後面的是偶數就互換。
當邏輯的部分寫得差不多了，就可以透過測試來輔助，看看寫得到底對不對。
public int[] SortArrayByParity(int[] A)
{
int x = 0;
int y = A.Length - 1;
while (x < y)
{
while (A[x] % 2 == 0 && x < y)
{
x++;
}
while (A[y] % 2 == 1 && y > x)
{
y--;
}
if (A[x] % 2 == 1 && A[y] % 2 == 0 && x < y)
{
int temp = A[x];
A[x] = A[y];
A[y] = temp;
}
x++;
y--;
}
return A;
}
由於這題實在是太簡單了，只是即便題目這麼簡單，我還是沒辦法一次寫完就收工，沒想到思緒不周還多修正了幾次，實在是太糟糕了(哭泣)
※延伸閱讀
TDD LeetCode：461. Hamming Distance
TDD LeetCode：804. Unique Morse Code Words
0 意見:
張貼留言