程式隨筆
0%

【LeetCode】Permutations II

Posted on Edited on In Disqus:

這題寫超級久，應該是自己邏輯不好的緣故，想不出邏輯最後只好直接用TDD的撰寫方式慢慢將範圍縮小，才歸納出結果，看來我的邏輯真的要好好加強了

#題目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

1
2
3
4
5
public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        
    }
}

#解題

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PermuteUniqueTest_輸入1_1()
{
    //arrange
    var sut = new Solution();
    int[] input = new int []{ 1, 1 };
    var expected = new List<List<int>>
    {
        new List<int>{ 1,1}
    };
            
    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
public partial class Solution
{
    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        var Result = new List<IList<int>>();
        Result.Add(nums.ToList());
        return Result;
    }
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[TestMethod]
public void PermuteUniqueTest_輸入空Array()
{
    //arrange
    var sut = new Solution();
    int[] input = new int[0];
    var expected = new List<List<int>>();

    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
public IList<IList<int>> PermuteUnique(int[] nums)
{
    var Result = new List<IList<int>>();

    if (nums.Length == 0)
        return Result;

    Result.Add(nums.ToList());

    return Result;
}

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[TestMethod]
public void PermuteUniqueTest_輸入1_2()
{
    //arrange
    var sut = new Solution();
    int[] input = new int[] { 1, 2 };
    var expected = new List<List<int>>
    {
        new List<int>{ 1,2},
        new List<int>{ 2,1}
    };

    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public IList<IList<int>> PermuteUnique(int[] nums)
{
    var Result = new List<IList<int>>();

    if (nums.Length == 0)
        return Result;

    Result.Add(nums.ToList());

    for (int i = 0; i < nums.Length; i++)
    {
        if (i == nums.Length - 1)
            continue;


        if (nums[i] != nums[ i+1])
        {
            //Swap
            var Temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = Temp;

            Result.Add(nums.ToList());
        }
    }

    return Result;
}

重構

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public IList<IList<int>> PermuteUnique(int[] nums)
{
    var Result = new List<IList<int>>();

    if (nums.Length == 0)
        return Result;

    Result.Add(nums.ToList());

    for (int i = 0; i < nums.Length; i++)
    {
        if (i == nums.Length - 1)
            continue;


        if (nums[i] != nums[ i+1])
        {
            //Swap
            Swap(nums, i);

            Result.Add(nums.ToList());
        }
    }

    return Result;
}

private void Swap(int[] nums, int index)
{
    var Temp = nums[index];
    nums[index] = nums[index + 1];
    nums[index + 1] = Temp;
}

案例四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[TestMethod]
public void PermuteUniqueTest_輸入1_2_3()
{
    //arrange
    var sut = new Solution();
    int[] input = new int[] { 1, 2 , 3};
    var expected = new List<List<int>>
    {
        new List<int>{ 1,2,3},
        new List<int>{ 1,3,2},
        new List<int>{ 2,1,3},
        new List<int>{ 2,3,1},
        new List<int>{ 3,1,2},
        new List<int>{ 3,2,1},
    };

    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public partial class Solution
{
    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        var Result = new List<IList<int>>();

        if (nums.Length == 0)
            return Result;

        Result.Add(nums.ToList());

        for (int i = 0; i < nums.Length; i++)
        {
            if (i == nums.Length - 1)
                continue;

            for (int s = i + 1 ; s < nums.Length; s++)
            {
                if (nums[i] != nums[s])
                {
                    var SplitLeaft = new List<int>(nums);
                    Swap(SplitLeaft, i, s);
                    Recursive(SplitLeaft, i + 1, Result);
                }
            }
        }

        return Result;
    }

    private void Recursive(List<int> nums, int start, List<IList<int>> result)
    {
        result.Add(nums);
        for (int i = start; i < nums.Count; i++)
        {
            if (i == nums.Count - 1)
                continue;

            if (nums[start] != nums[i + 1])
            {
                var SplitLeaft = new List<int>(nums);
                Swap(SplitLeaft, start, i + 1);
                Recursive(SplitLeaft, i + 1, result);
            }
        }
    }

    private void Swap(List<int> nums, int index1,int index2)
    {
        var Temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = Temp;
    }
}

重構

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public partial class Solution
{
    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        var Result = new List<IList<int>>();

        if (nums.Length == 0)
            return Result;

        Recursive(new List<int>(nums), 0 , Result);

        return Result;
    }

    private void Recursive(List<int> nums, int start, List<IList<int>> result)
    {
        result.Add(nums);
        for (int i = start; i < nums.Count; i++)
        {
            if (i == nums.Count - 1)
            {
                continue;
            }

            for (int j = i + 1; j < nums.Count; j++)
            {
                if (nums[i] != nums[j])
                {
                    var SplitLeaft = new List<int>(nums);
                    Swap(SplitLeaft, i, j);
                    Recursive(SplitLeaft, i + 1, result);
                }
            }
        }
    }

    private void Swap(List<int> nums, int index1,int index2)
    {
        var Temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = Temp;
    }
}

案例五

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[TestMethod]
public void PermuteUniqueTest_輸入1_1_2()
{
    //arrange
    var sut = new Solution();
    int[] input = new int[] { 1, 1, 2 };
    var expected = new List<List<int>>
    {
        new List<int>{ 1,1,2},
        new List<int>{ 1,2,1},
        new List<int>{ 2,1,1}
    };

    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

程式無需更動直接通過測試

#分析結果

LeetCode跑單元測試錯誤

/images/20180606/1.jpg

補上錯誤案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[TestMethod]
public void PermuteUniqueTest_輸入2_2_1_1()
{
    //arrange
    var sut = new Solution();
    int[] input = new int[] { 2, 2, 1, 1 };
    var expected = new List<List<int>>
    {
        new List<int>{ 1,1,2,2},
        new List<int>{ 1,2,1,2},
        new List<int>{ 1,2,2,1},
        new List<int>{ 2,1,1,2},
        new List<int>{ 2,1,2,1},
        new List<int>{ 2,2,1,1}
    };

    //act
    var actual = sut.PermuteUnique(input);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public IList<IList<int>> PermuteUnique(int[] nums)
{
    var Result = new List<IList<int>>();

    if (nums.Length == 0)
        return Result;

    Recursive(new List<int>(nums), 0 , Result);

    return Result;
}

private void Recursive(List<int> nums, int start, List<IList<int>> result)
{
    result.Add(nums);
    for (int i = start; i < nums.Count; i++)
    {
        HashSet<int> used = new HashSet<int>();
        if (i == nums.Count - 1)
        {
            continue;
        }

        for (int j = i + 1; j < nums.Count; j++)
        {
            if (nums[i] != nums[j])
            {
                if (used.Contains(nums[j]))
                {
                    continue;
                }
                else
                {
                    used.Add(nums[j]);
                }

                var SplitLeaft = new List<int>(nums);
                Swap(SplitLeaft, i, j);
                Recursive(SplitLeaft, i + 1, result);
            }
        }
    }
}

private void Swap(List<int> nums, int index1,int index2)
{
    var Temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = Temp;
}

這邊的原因是，同一個位置只需要跟相同的數字互換一次即可，因為遞迴會把後面的各種可能補上，否則會發生重複的排列組合

1,1,2,2, index[0] 與後面所有後面的數相比

  • 1,1,2,2 (index[0] = 1與index[1] = 1相同，不做動作)

  • 2,1,1,2 (index[0] = 1與index[2] = 2不相同，互換並產生支線)

    • 2,1,1,2 (index[1] = 1與index[2] = 1相同，不做動作)
    • 2,2,1,1 (index[1] = 1與index[3] = 2不相同，互換並產生支線)
      • 2,2,1,1 (index[2] = 1與index[3] = 1相同，不做動作，支線遞迴結束)
    • 2,1,2,1 (index[2] = 1與index[3] = 2不相同，互換並產生支線)

  • 1,1,1,2 (index[0] = 1與index[3] = 2不相同，但之前跟2互換過一次，所以不做動作)

1,1,2,2 , index[1] 與後面所有後面的數相比

  • 1,2,1,2 (index[1] = 1與index[2] = 2不相同，互換並產生支線)
    • 1,2,2,1(index[2] = 1與index[3] = 2不相同，互換並產生支線)
      • 走到最末端，遞迴結束
  • 1,1,2,2 (index[1] = 1與index[3] = 2不相同，但之前跟2互換過一次，所以不做動作)

這邊如果互換的話將導致重複的數列出現

…….以下省略…..

/images/20180606/2.jpg