程式隨筆
0%

Posted on Edited on Disqus:

#前情提要

不定時、不定量、不特定API跳出**【System.InvalidOperationException】 - The connection was not closed. The connection’s current state is connecting.**錯誤，這個錯誤以前公司也遇到過，當時研判是Entity Framework與Unity套件生命週期的問題，當時專案不算太大又一直找不到確切解決方案，所以索性將Repository Layer整個用Dapper改寫讓問題得以解決了。

當時的筆記

【Entity Framework】DBContext Dispose與否，與DB的連線數是否有關係

但這次退無可退，再次印證了一句話

你不解決問題，問題就會解決你

   

#分析

透過Elmah的Log分析，發現共同點都壞在一支Token驗證的DelegatingHandler裡面，因為呼叫每支API都會經過這，可以解釋為何壞在不特定API。

而關鍵在其中的一行

1
2
var Service = AutofacConfig.Container.Resolve<ISupplierApiProfileService>();
var Profile = Service.GetSupplierApiProfileByToken(token);

透過Autofac Container取得ISupplierApiProfileService，猜測當時這樣撰寫是希望每次產生新的Service的實體來使用，在這之前先一下看一下整體的架構

/images/20180724/1.gif

而每個實體分別Autofac註冊的生命週期為

/images/20180724/2.jpg

這導致了一個結果，因為Actofac Container為Singleton的實體，透過他Resolve出來的DBContext (InstancePerLifetimeScope)也會變成Singleton的生命週期。

而Entity Framework非Thread Safe的設計，所以如果不同Thread共用同一個DBContext時，如果前一個交易尚未完成，撞在一起時就會有機率產生這個錯誤

/images/20180724/3.jpg

相關討論

https://github.com/aspnet/EntityFrameworkCore/issues/3887

#解法

而DBContext會設定為InstancePerLifetimeScope的生命週期是希望DBContext隨著每次Request產生與消滅(亦即每個Request只會產生一次DBContext實體)，如果後續應用Transaction才不會發生問題，但在DelegatingHandler這邊的應用情境卻導致了Singleton的情況。

BeginLifetimeScope

官方文件 - Working with Lifetime Scopes

Autofac提供給使用者產生一個動態的生命週期的方法，所有透過這個生命週期產生的實體會隨著它的消滅一併被Disposed掉，使用方式如下

1
2
3
4
5
using (var scope = AutofacConfig.Container.BeginLifetimeScope())
{
    var Service = scope.Resolve<ISupplierApiProfileService>();
    var Profile = Service.GetSupplierApiProfileByToken(token);
}

這樣可以確保在DelegatingHandler裡面產生的DBContext不會變成Singleton，也不用動到最基底DBContext InstancePerLifetimeScope的生命週期，確保了每次Request共用同一個DBContext。

上線後觀察Elmah，確認這個伴隨著我將近三年的問題終於徹底消滅了，可喜可賀 可喜可賀。

Posted on Edited on Disqus:

2019/08/21 補充 ： 將之前在公司分享的 Demo Code 整理並放到 Github，有興趣的可以下載來試試看。

#什麼是Autofac

用來實作控制反轉(Inversion of Control, IoC)的套件,幫我們管理抽象與實體之間的對應關係, 除了Autofac之外還有Unity等其它套件可以實作,但概念都大同小異。

Autofac官網

#Autofac的生命週期有哪些

  • InstancePerDependency
  • SingleInstance
  • InstancePerLifetimeScope
  • InstancePerRequest

下面會一一解說跟實作測試,在這之前先準備一個WebAPI的專案,並且將Autofac與Autofac WebAPI2裝起來

/images/20180712/1.jpg

然後在App_Start資料夾新增AutofacConfig類別

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static class AutofacConfig
{
    public static IContainer Container { get; private set; }

    public static void BuildContainer()
    {
        var builder = new ContainerBuilder();

        Register(builder);

        Container = builder.Build();
        GlobalConfiguration.Configuration.DependencyResolver = new AutofacWebApiDependencyResolver(Container);
    }

    private static void Register(ContainerBuilder builder)
    {
        var assembly = typeof(AutofacConfig).Assembly;
        builder.RegisterApiControllers(assembly);
    }
}

Global.asax加上這行

1
2
3
4
5
6
7
8
9
10
11
protected void Application_Start()
{
    //Autofac Init
    AutofacConfig.BuildContainer();

    AreaRegistration.RegisterAllAreas();
    GlobalConfiguration.Configure(WebApiConfig.Register);
    FilterConfig.RegisterGlobalFilters(GlobalFilters.Filters);
    RouteConfig.RegisterRoutes(RouteTable.Routes);
    BundleConfig.RegisterBundles(BundleTable.Bundles);
}

InstancePerDependency

Also called ‘transient’ or ‘factory’ in other containers. Using per-dependency scope, a unique instance will be returned from each request for a service.

每次呼叫都回傳一個新的實體,產生的Instance隨著呼叫者的生命週期消滅

1
2
3
4
5
6
7
8
9
10
11
12
public class LiftTimeModel
{
    public static int Count;

    public int ID { get; private set; }

    public LiftTimeModel()
    {
        Count++;
        this.ID = LiftTimeModel.Count;
    }
}

AutofacConfig

1
2
3
4
5
6
7
8
9
10
11
12
public static class AutofacConfig
{
	....省略....
        
    private static void Register(ContainerBuilder builder)
    {
        var assembly = typeof(AutofacConfig).Assembly;
        builder.RegisterApiControllers(assembly);

        builder.RegisterType<LiftTimeModel>().InstancePerDependency();
    }
}

TestController

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class TestController : ApiController
{
	private LifeTimeModel _lifeTimeModel;
	public TestController(LifeTimeModel lifeTimeModel)
	{
		this._lifeTimeModel = lifeTimeModel;
	}

	// GET api/<controller>
	public string Get()
	{
		StringBuilder sb = new StringBuilder();
		sb.AppendLine(string.Concat("PerDependencyModel ID :", this._lifeTimeModel.ID));

    	return sb.ToString();
	}
}

呼叫/api/test會發現隨著呼叫的次數增加，LifeTimeModel ID 也會一直增加，因為每次Request呼叫開始都會產生新的TestController Instance，隨著Request結束TestController也會被消滅，依賴在它身上的LifeTimeModel也隨之產生與消滅。而每次產生新的LifeTimeModel Instance都會在建構子將static的Count加1，這是數字一直增加的緣故。

此外Autofac預設使用的生命週期即為InstancePerDependency，所以這兩行的意思是一樣的

1
2
builder.RegisterType<LiftTimeModel>().InstancePerDependency();
builder.RegisterType<LiftTimeModel>();

InstancePerDependency圖解

SingleInstance

This is also known as ‘singleton.’ Using single instance scope, one instance is returned from all requests in the root and all nested scopes.

不管呼叫幾次都只有產生一個Instance，以WebAPI為例只有當Application Shut down的時候會消滅

1
2
3
4
5
6
7
8
9
10
11
12
public static class AutofacConfig
{
    ...省略....

    private static void Register(ContainerBuilder builder)
    {
        var assembly = typeof(AutofacConfig).Assembly;
        builder.RegisterApiControllers(assembly);
        //改成SingleInstance
        builder.RegisterType<LifeTimeModel>().SingleInstance();
    }
}

會發現不管呼叫/api/test幾次ID永遠都是1,原因是LifeTimeModel只會產生一次

SingleInstance圖解

InstancePerLifetimeScope

This scope applies to nested lifetimes. A component with per-lifetime scope will have at most a single instance per nested lifetime scope.

這個非常容易跟InstancePerRequest搞混,簡單理解方式就是,每個Scope只會最多產生一個Instance。

所以在Root只會產生一個，在Autofac WebRequest只會產生一組

新增TestPerLifetimeScopeModel做為觀察標的

1
2
3
4
5
6
7
8
public class TestPerLifetimeScopeModel
{
    public LifeTimeModel LifeTimeModel { get; set; }
    public TestPerLifetimeScopeModel(LifeTimeModel lifeTimeModel)
    {
        this.LifeTimeModel = lifeTimeModel;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static class AutofacConfig
{
    ...省略....

    private static void Register(ContainerBuilder builder)
    {
        var assembly = typeof(AutofacConfig).Assembly;
        builder.RegisterApiControllers(assembly);
        
        builder.RegisterType<TestPerLifetimeScopeModel>();
         //改成InstancePerLifetimeScope
        builder.RegisterType<LifeTimeModel>().InstancePerLifetimeScope();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class TestController : ApiController
{
	private LifeTimeModel _lifeTimeModel;
    private TestPerLifetimeScopeModel _testPerLifetimeScopeModel;
    public TestController(LifeTimeModel lifeTimeModel, TestPerLifetimeScopeModel testPerLifetimeScopeModel)
    {
    	this._lifeTimeModel = lifeTimeModel;
    	this._testPerLifetimeScopeModel = testPerLifetimeScopeModel;
    }

	// GET api/<controller>
    public string Get()
    {
    	StringBuilder sb = new StringBuilder();
    	sb.AppendLine(string.Concat("PerDependencyModel ID :", this._lifeTimeModel.ID));
        sb.AppendLine(string.Concat("TestPerLifetimeScopeModel's LifeTimeModel ID :", this._testPerLifetimeScopeModel.LifeTimeModel.ID));
        
        return sb.ToString();
	}
}

會發現兩個得到的ID都是相同的，原因是Autofac WebRequest Scope中，一次Request只會產生一組LifeTimeModel，所以ID都會一樣

/images/20180712/4.jpg

更進一步說，如果我們今天有使用WebAPI DelegatingHandler，因為Handler只會在Application起來時產生一次Instance，所以在這產生的LifeTimeModel也會變成Singleton *註1

1
2
3
4
5
6
7
8
9
10
public class TestHandler: DelegatingHandler
{
	protected override Task<HttpResponseMessage> SendAsync(HttpRequestMessage request, CancellationToken cancellationToken)
    {
    	var Model = AutofacConfig.Container.Resolve<LifeTimeModel>();
    	var TestID = Model.ID;
		
		return base.SendAsync(request, cancellationToken);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static class WebApiConfig
{
    public static void Register(HttpConfiguration config)
    {
        // Web API 設定和服務

        // Web API 路由
        config.MapHttpAttributeRoutes();

        // 註冊Handler
        config.MessageHandlers.Add(new TestHandler());

        config.Routes.MapHttpRoute(
            name: "DefaultApi",
            routeTemplate: "api/{controller}/{id}",
            defaults: new { id = RouteParameter.Optional }
        );
    }
}

會發現Handler裡面的ID永遠拿到的都是1，而API回傳的結果則會慢慢增加，兩邊是各自獨立的實體

/images/20180712/6.jpg

/images/20180712/7.jpg

InstancePerLifetimeScope圖解

註1

這邊觀念有錯誤，會Singleton的原因不在於DelegatingHandler的問題，而是因為使用AutofacConfig.Container來產生實體，Container是Root層級也是Singleton，請它產生LifeTimeModel (InstancePerLifetimeScope)，所以會變成Singleton。

交叉測試的方法是把這段 AutofacConfig.Container.Resolve()放到Controller的Action之中，產出來的實體也會是Singleton，所以癥結在AutofacConfig.Container而非DelegatingHandler或Controller Action的生命週期，特此更正

InstancePerRequest

Some application types naturally lend themselves to “request” type semantics, for example ASP.NET web forms and MVC applications. In these application types, it’s helpful to have the ability to have a sort of “singleton per request.”

基本上跟InstancePerLifetimeScope認知是一致的，唯一差別是它無法Root Scope產生Instance，因為生命週期隨著Request產生與消滅，不會有Singleton的可能，所以如果改成InstancePerRequest，剛剛的TestHandler就會產生Exception。

/images/20180712/8.jpg

/images/20180712/9.jpg

Unity跟Autofac的生命週期一直都不是很好懂所以之前也踩了不少雷，筆記起來希望對大家能有幫助

補充

產生在AutofacWebRequest Scope的實體，一定會在每次Request結束後被消滅

參考文件

WebAPI, Autofac, and Lifetime Scopes

Posted on Edited on Disqus:

#什麼是Code Snippet

從字面來看是程式碼片段，如果已經寫程式一段時間應該都有用到過，例如在Visual Studio打上Switch後按兩下Tab自動產生的程式碼就是Code Snippet功能做出來的。

/images/20180711/1.png

/images/20180711/2.jpg

所以將常常重複寫的程式碼做成Code Snippet是一件很方便的事情

#如何自訂

因為寫單元測試常常需要寫3A原則,所以把它做成Code Snippet就可以重用。

1
2
3
4
5
6
7
8
//// arrange
var sut = GetSystemUnderTest();
var expected = true;

//// act
var actual = sut.DoSomething();

//// assert

建立3A Pattern.snippet的檔案

打開一個記事本命名成3A Pattern，然後副檔名儲存成.snippet

撰寫內容

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
<?xml version="1.0" encoding="utf-8"?>
<CodeSnippets xmlns="http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet">
  <CodeSnippet Format="1.0.0">
    <Header>
      <SnippetTypes>
        <SnippetType>Expansion</SnippetType>
        <SnippetType>SurroundsWith</SnippetType>
      </SnippetTypes>
      <Title>你的Code Snippet名稱</Title>
      <Author>Steven</Author>
      <Description>
      </Description>
      <HelpUrl>
      </HelpUrl>
      <Shortcut>你想要呼叫時的代碼</Shortcut>
    </Header>
    <Snippet>
      <Declarations>
        <Literal Editable="true">
          <ID>變數ID</ID>
          <ToolTip>變數描述</ToolTip>
          <Default>預設值</Default>
          <Function>
          </Function>
        </Literal>
      </Declarations>
      <Code Language="csharp" Delimiter="$"><![CDATA[
		......
         放入程式碼的地方        
		......
        ]]></Code>
    </Snippet>
  </CodeSnippet>
</CodeSnippets>

依據上面的Template,將3A Pattern Code Snippet改成

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
<?xml version="1.0" encoding="utf-8"?>
<CodeSnippets xmlns="http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet">
  <CodeSnippet Format="1.0.0">
    <Header>
      <SnippetTypes>
        <SnippetType>Expansion</SnippetType>
        <SnippetType>SurroundsWith</SnippetType>
      </SnippetTypes>
      <Title>3A Pattern</Title>
      <Author>Steven</Author>
      <Description>
      </Description>
      <HelpUrl>
      </HelpUrl>
      <Shortcut>aaa</Shortcut>
    </Header>
    <Snippet>
      <Declarations>
        <Literal Editable="true">
          <ID>expected</ID>
          <ToolTip>expected</ToolTip>
          <Default>true</Default>
          <Function>
          </Function>
        </Literal>
        <Literal Editable="true">
          <ID>DoSomthing</ID>
          <ToolTip>DoSomthing</ToolTip>
          <Default>DoSomething()</Default>
          <Function>
          </Function>
        </Literal>
      </Declarations>
      <Code Language="csharp" Delimiter="$"><![CDATA[
        //// arrange
        var sut = GetSystemUnderTest();
        var expected = $expected$;
        
        //// act
        var actual = sut.$DoSomthing$;
        
        //// assert
        ]]></Code>
    </Snippet>
  </CodeSnippet>
</CodeSnippets>

$變數$ , 兩個前字號中間的就是變數ID,在Snippet > Declarations > Literal 設定變數相關值

#匯入Visual Studio

最後一步就是匯入Visual Studio中,點擊工具 > 程式碼片段管理員

/images/20180711/4.jpg

點擊匯入，選擇剛剛的3A Pattern.snippet檔案

/images/20180711/5.jpg

匯入到My Code Snippets > 完成 ，就可以看到3A Pattern了

/images/20180711/6.jpg

/images/20180711/7.jpg

#結果

在程式碼中打aaa加兩次Tab就會呼叫出我們設定的Code Snippet

/images/20180711/8.jpg

/images/20180711/9.jpg

參考文章

逐步解說：建立程式碼片段

Posted on Edited on In Disqus:

#題目

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1
Output: “2”

Example 3:

Input: numerator = 2, denominator = 3
Output: “0.(6)”

1
2
3
4
5
public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        
    }
}

#解題

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_1_denominator_2()
{
    //arrange
    var sut = new Solution();
    var numerator = 1;
    var denominator = 2;

    var expected = "0.5";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}
1
2
3
4
5
6
public string FractionToDecimal(int numerator, int denominator)
{
    decimal result = Convert.ToDecimal(numerator) / Convert.ToDecimal(denominator);

    return result.ToString();
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_2_denominator_1()
{
    //arrange
    var sut = new Solution();
    var numerator = 2;
    var denominator = 1;

    var expected = "2";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

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

直接通過測試

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_2_denominator_3()
{
    //arrange
    var sut = new Solution();
    var numerator = 2;
    var denominator = 3;

    var expected = "0.(6)";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();
    sb.Append(numerator / denominator);

    //餘數
    var Remainder = (numerator % denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<int, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / denominator);
        Remainder = (Remainder * 10) % denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

關鍵在找出餘數相同時的那一刻，餘數開始重複代表規律產生了，因為餘數乘10等於下次的被除數，除數永遠不變的情況下將開始循環。

記錄下每次餘數當下字串的長度，當下次產生相同餘數，則從Dictionary取得上一次出現的位置補上括號即可

#解析

溢位問題

LeetCode測試錯誤

/images/20180627/leetcode/1.jpg

/images/20180627/leetcode/2.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_負2147483648_denominator_負1()
{
    //arrange
    var sut = new Solution();
    var numerator = -2147483648;
    var denominator = -1;

    var expected = "2147483648";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();

    var _numerator = Convert.ToInt64(numerator);
    var _denominator = Convert.ToInt64(denominator);
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / denominator);
        Remainder = (Remainder * 10) % denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

負數問題

/images/20180627/leetcode/3.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_負50_denominator_8()
{
    //arrange
    var sut = new Solution();
    var numerator = -50;
    var denominator = 8;
    
    var expected = "-6.25";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

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

如果運算之中有正負號時，則可能組出來的字串為 -6.-2-5，顯然這不是我們要的，要將負號在最前面優先處理，接著後面的計算都用正數來處理

結果為負數，只有在兩個數為一正一負時，當兩正或兩負算出來的皆還是會正值，可以用^(XOR)來判別

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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();

    //考慮負數
    sb.Append((numerator >= 0) ^ (denominator >= 0) ? "-" : string.Empty);

    //只取正數
    var _numerator =Math.Abs(Convert.ToInt64(numerator));
    var _denominator = Math.Abs(Convert.ToInt64(denominator));
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / _denominator);
        Remainder = (Remainder * 10) % _denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

被除數為0問題

當被除數為0時，回傳結果應為0且無關正負

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_0_denominator_負5()
{
    //arrange
    var sut = new Solution();
    var numerator = 0;
    var denominator = -5;

    var expected = "0";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(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
public string FractionToDecimal(int numerator, int denominator)
{
    if (numerator == 0)
    {
        return "0";
    }

    StringBuilder sb = new StringBuilder();

    //考慮負數
    sb.Append((numerator >= 0) ^ (denominator >= 0) ? "-" : string.Empty);

    //只取正數
    var _numerator =Math.Abs(Convert.ToInt64(numerator));
    var _denominator = Math.Abs(Convert.ToInt64(denominator));
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / _denominator);
        Remainder = (Remainder * 10) % _denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

/images/20180627/leetcode/5.jpg

Posted on Edited on In Disqus:

Demo範例 ：Git位置

#目標

將網路上下載來的免費漂亮版型套進專案中，從實作中瞭解如何套版跟應用.Net提供的一些API方法，過程中或許會有許多小地方不懂，例如Html結構，View Render的機制等等，沒關係，這會在後續的篇章中慢慢補足，而此篇主要是希望讓讀者知道套版原理，並享受網頁隨著套版變漂亮的過程。

在Google搜尋中輸入free template download可以找到一大堆免費授權的版型，而這次從這個TEMPLATED挑了一個喜歡的，有興趣可以先看一下該版型的Live Demo

/images/20180627/1.jpg

如果不方便從網路下載也無妨，我已經將下載好且解壓的版本放到Git的專案之中，如果要練習可以直接從裡面取得Source Code

/images/20180627/2.jpg

#實作

套版前準備

Chrome

通常我會用Chrome瀏覽器來輔助套版的工作，所以以下的操作都是針對Chrome撰寫，不過現在各家瀏覽器其實都大同小異了，只要有相對應的功能即可。

Chrome下載

Web Server For Chrome(非必要)

為了方便瀏覽下載的版型，可以安裝Web Server For Chrome這個套件

/images/20180627/3.jpg

安裝完後應該會在Chrome的應用程式中看到Web Server

/images/20180627/4.jpg

打開它並把資料夾選到版型的根目錄

/images/20180627/5.jpg

/images/20180627/6.jpg

點擊**Web Server URL(s)**，應該就可以看到網站出現了

/images/20180627/7.jpg

/images/20180627/8.jpg

首頁套版

從Visual Studio中開啟Index.html

/images/20180627/9.jpg

/images/20180627/10.jpg

將所有內容複製貼到我們的/Home/Index.cshtml之中

/images/20180627/11.jpg

這時候會發現第一個錯誤

/images/20180627/12.jpg

跳脫字元

原因是.Net MVC預設用的套版語法是Razor，而**@是它的保留字，所以要用跳脫字元來解決，只要將*@*templatedco變成@@templatedco**，它在顯示網頁的時候就會印出我們想要的@templatedco了

/images/20180627/13.jpg

執行網站看首頁結果會發現，它怪怪的…

/images/20180627/14.jpg

Layout

首先網頁最上面那排黑黑的Header，明明我們版型的Header沒這塊，它是從哪邊長出來的?

這邊就要瞭解Layout是什麼

/images/20180627/15.jpg

很多網頁都會有一個特性，那就是不管切換到哪個頁面都會有共用的區塊，以Sony頁面為例

PlayStation頁面

/images/20180627/16.jpg

消費性電子>電視頁面

/images/20180627/17.jpg

共通點就是Header不管到哪一頁都不會換

/images/20180627/18.jpg

而如果每頁都要重新把Header套版一次會衍伸一些問題

  • 重工 : 有一百頁就要把一樣的內容貼一百次
  • 維護困難 : 如果想在Header多一顆按鈕，就要打開一百個頁面調整一百次

所以實務上會透過Layout來解決這問題，將全站幾乎都會共用的部分抽出來當Layout，而會變動的部分當作Body。

所以套用了新的版型還會跑出Header，那是因為Layout裡面有這個區塊

/images/20180627/19.jpg

依照剛剛說的，我們把共用的區塊抽到Layout裡面去放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<!DOCTYPE HTML>
<!--
    Hielo by TEMPLATED
    templated.co @@templatedco
    Released for free under the Creative Commons Attribution 3.0 license (templated.co/license)
-->
<html>
<head>
    <title>Hielo by TEMPLATED</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <link rel="stylesheet" href="assets/css/main.css" />
</head>
	<body>
        ....
	</body>
</html>

Layout調整成

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
<!DOCTYPE HTML>
<!--
    Hielo by TEMPLATED
    templated.co @@templatedco
    Released for free under the Creative Commons Attribution 3.0 license (templated.co/license)
-->
<html>
<head>
    <title>Hielo by TEMPLATED</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <link rel="stylesheet" href="assets/css/main.css" />
</head>
<body>
    @RenderBody()

    @RenderSection("scripts", required: false)
    <script>
        @if (TempData["Message"] != null)
        {
            <text>alert('@TempData["Message"]')</text>
        }
    </script>
</body>
</html>

Index調整成

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
@{
    ViewBag.Title = "Home Page";
}



<!-- Header -->
<header id="header" class="alt">
    <div class="logo"><a href="index.html">Hielo <span>by TEMPLATED</span></a></div>
    <a href="#menu">Menu</a>
</header>

<!-- Nav -->
<nav id="menu">
    <ul class="links">
        <li><a href="index.html">Home</a></li>
        <li><a href="generic.html">Generic</a></li>
        <li><a href="elements.html">Elements</a></li>
    </ul>
</nav>

<!-- Banner -->
<section class="banner full">
    <article>
        <img src="images/slide01.jpg" alt="" />
        <div class="inner">
            <header>
                <p>A free responsive web site template by <a href="https://templated.co">TEMPLATED</a></p>
                <h2>Hielo</h2>
            </header>
        </div>
    </article>
    <article>
        <img src="images/slide02.jpg" alt="" />
        <div class="inner">
            <header>
                <p>Lorem ipsum dolor sit amet nullam feugiat</p>
                <h2>Magna etiam</h2>
            </header>
        </div>
    </article>
    <article>
        <img src="images/slide03.jpg" alt="" />
        <div class="inner">
            <header>
                <p>Sed cursus aliuam veroeros lorem ipsum nullam</p>
                <h2>Tempus dolor</h2>
            </header>
        </div>
    </article>
    <article>
        <img src="images/slide04.jpg" alt="" />
        <div class="inner">
            <header>
                <p>Adipiscing lorem ipsum feugiat sed phasellus consequat</p>
                <h2>Etiam feugiat</h2>
            </header>
        </div>
    </article>
    <article>
        <img src="images/slide05.jpg" alt="" />
        <div class="inner">
            <header>
                <p>Ipsum dolor sed magna veroeros lorem ipsum</p>
                <h2>Lorem adipiscing</h2>
            </header>
        </div>
    </article>
</section>

<!-- One -->
<section id="one" class="wrapper style2">
    <div class="inner">
        <div class="grid-style">

            <div>
                <div class="box">
                    <div class="image fit">
                        <img src="images/pic02.jpg" alt="" />
                    </div>
                    <div class="content">
                        <header class="align-center">
                            <p>maecenas sapien feugiat ex purus</p>
                            <h2>Lorem ipsum dolor</h2>
                        </header>
                        <p> Cras aliquet urna ut sapien tincidunt, quis malesuada elit facilisis. Vestibulum sit amet tortor velit. Nam elementum nibh a libero pharetra elementum. Maecenas feugiat ex purus, quis volutpat lacus placerat malesuada.</p>
                        <footer class="align-center">
                            <a href="#" class="button alt">Learn More</a>
                        </footer>
                    </div>
                </div>
            </div>

            <div>
                <div class="box">
                    <div class="image fit">
                        <img src="images/pic03.jpg" alt="" />
                    </div>
                    <div class="content">
                        <header class="align-center">
                            <p>mattis elementum sapien pretium tellus</p>
                            <h2>Vestibulum sit amet</h2>
                        </header>
                        <p> Cras aliquet urna ut sapien tincidunt, quis malesuada elit facilisis. Vestibulum sit amet tortor velit. Nam elementum nibh a libero pharetra elementum. Maecenas feugiat ex purus, quis volutpat lacus placerat malesuada.</p>
                        <footer class="align-center">
                            <a href="#" class="button alt">Learn More</a>
                        </footer>
                    </div>
                </div>
            </div>

        </div>
    </div>
</section>

<!-- Two -->
<section id="two" class="wrapper style3">
    <div class="inner">
        <header class="align-center">
            <p>Nam vel ante sit amet libero scelerisque facilisis eleifend vitae urna</p>
            <h2>Morbi maximus justo</h2>
        </header>
    </div>
</section>

<!-- Three -->
<section id="three" class="wrapper style2">
    <div class="inner">
        <header class="align-center">
            <p class="special">Nam vel ante sit amet libero scelerisque facilisis eleifend vitae urna</p>
            <h2>Morbi maximus justo</h2>
        </header>
        <div class="gallery">
            <div>
                <div class="image fit">
                    <a href="#"><img src="images/pic01.jpg" alt="" /></a>
                </div>
            </div>
            <div>
                <div class="image fit">
                    <a href="#"><img src="images/pic02.jpg" alt="" /></a>
                </div>
            </div>
            <div>
                <div class="image fit">
                    <a href="#"><img src="images/pic03.jpg" alt="" /></a>
                </div>
            </div>
            <div>
                <div class="image fit">
                    <a href="#"><img src="images/pic04.jpg" alt="" /></a>
                </div>
            </div>
        </div>
    </div>
</section>


<!-- Footer -->
<footer id="footer">
    <div class="container">
        <ul class="icons">
            <li><a href="#" class="icon fa-twitter"><span class="label">Twitter</span></a></li>
            <li><a href="#" class="icon fa-facebook"><span class="label">Facebook</span></a></li>
            <li><a href="#" class="icon fa-instagram"><span class="label">Instagram</span></a></li>
            <li><a href="#" class="icon fa-envelope-o"><span class="label">Email</span></a></li>
        </ul>
    </div>
    <div class="copyright">
        &copy; Untitled. All rights reserved.
    </div>
</footer>

<!-- Scripts -->
<script src="assets/js/jquery.min.js"></script>
<script src="assets/js/jquery.scrollex.min.js"></script>
<script src="assets/js/skel.min.js"></script>
<script src="assets/js/util.js"></script>
<script src="assets/js/main.js"></script>

@RenderBody()

Layout中間有一行@RenderBody()這是Razor提供的方法，意思是所有套用這個Layout的頁面，它的內容會取代@RenderBody()。

假設我們的Index內容為

1
<p>I'm Index</p>

那套上Layout後產生給使用者看到的完整Html就會是這樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<!DOCTYPE HTML>
<!--
    Hielo by TEMPLATED
    templated.co @@templatedco
    Released for free under the Creative Commons Attribution 3.0 license (templated.co/license)
-->
<html>
<head>
    <title>Hielo by TEMPLATED</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <link rel="stylesheet" href="assets/css/main.css" />
</head>
<body>
    <p>I'm Index</p>
    .....
</body>
</html>

@RenderSection()

實務上會希望Javascript或是CSS在特定的地方載入，如果只是單純放在Index中將會變成這樣

Index

1
2
<p>I'm Index</p>
<script src="assets/js/jquery.min.js"></script>

結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<!DOCTYPE HTML>
<!--
    Hielo by TEMPLATED
    templated.co @@templatedco
    Released for free under the Creative Commons Attribution 3.0 license (templated.co/license)
-->
<html>
<head>
    <title>Hielo by TEMPLATED</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <link rel="stylesheet" href="assets/css/main.css" />
</head>
<body>
    <p>I'm Index</p>
    <script src="assets/js/jquery.min.js"></script>
    ....
</body>
</html>

此時就可以透過在Layout中挖**@RenderSection()**區塊來解決

Layout

1
2
3
4
5
6
7
8
9
10
11
12
13
<!DOCTYPE HTML>
<html>
<head>
    ....
    @RenderSection("css", required: false)
</head>
<body>
    @RenderBody()

    @RenderSection("scripts", required: false)
    ....
</body>
</html>

Index

1
2
3
4
5
6
7
8
@section scripts{
    <script src="assets/js/jquery.min.js"></script>
}
@section css{
    <link rel="stylesheet" href="assets/css/main.css" />
}

<p>I'm Index</p>

結果

1
2
3
4
5
6
7
8
9
10
11
12
13
<!DOCTYPE HTML>
<html>
<head>
    ....
    <link rel="stylesheet" href="assets/css/main.css" />
</head>
<body>
    <p>I'm Index</p>

    <script src="assets/js/jquery.min.js"></script>
    ....
</body>
</html>

@RenderSection(“scripts”, required: false)

required參數意義為

True :套用這個Layout的子版面一定要寫@section scripts{ }這個區段

False :套用這個Layout的子版面可以沒有@section scripts{ }區段

_ViewStart

檢視Index頁面，為何它知道要套用Layout呢?其實這寫在_ViewStart.cshtml之中

/images/20180627/20.jpg

_ViewStart.cshtml

1
2
3
@{
    Layout = "~/Views/Shared/_Layout.cshtml";
}

所有頁面如果沒有特別指定Layout的情況下，預設套用這個設定。

但這不意謂著不能自行修改，假設所有專案有兩三個頁面要套用_Layout2.cshtml，那我們可以在各自的頁面中指定Layout，而指定的Layout優先於預設。

Index

1
2
3
4
@{
    Layout = "~/Views/Shared/_Layout2.cshtml";
}
<p>I'm Index</p>

載入CSS、Javascript

重新調整Layout與Index內容後，頁面依然沒有正常顯示

/images/20180627/21.jpg

在Chrome按下F12點擊右上角的錯誤可以得知是因為沒有載入CSS與Javascript

/images/20180627/22.jpg

將Javascript與CSS移到專案之中

/images/20180627/23.jpg

/images/20180627/24.jpg

同時我們也刪除掉原本在專案內的Javascript與CSS

修改Index中Javascript的位置

1
2
3
4
5
6
7
8
9
....

<!-- Scripts -->
<script src="~/assets/js/jquery.min.js"></script>
<script src="~/assets/js/jquery.min.js"></script>
<script src="~/assets/js/jquery.scrollex.min.js"></script>
<script src="~/assets/js/skel.min.js"></script>
<script src="~/assets/js/util.js"></script>
<script src="~/assets/js/main.js"></script>

修改_Layout中CSS的位置

1
2
3
4
5
6
7
8
...
<head>
    <title>Hielo by TEMPLATED</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <link href="~/assets/css/main.css" rel="stylesheet" />
</head>
...

~/assets/css/main.css

~/assets/js/main.js

前面的 ~ 符號表示從根目錄開始算起

再次執行專案

發生錯誤，原因是BundleConfig的地方有抓原本放Javascript的資料夾但被我們砍掉了，Bundle基本上目前我們很少用到所以先暫時不理它，把內容清空不影響結果

1
2
3
4
5
6
7
public class BundleConfig
{
    // 如需統合的詳細資訊，請瀏覽 https://go.microsoft.com/fwlink/?LinkId=301862
    public static void RegisterBundles(BundleCollection bundles)
    {
    }
}

執行起來後

/images/20180627/25.jpg

看起來正常許多但圖片還是沒有出來，將圖片移入

/images/20180627/26.jpg

/images/20180627/27.jpg

#小結

/images/20180627/28.jpg

已經成功將首頁移入專案之中，下一篇將來客製化將之前完成的登入頁面也套進這個漂亮的版型之中，中間將會碰到更多套版的Razor API與一些小技巧。

Posted on Edited on In Disqus:

#題目

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

Answer this question, and write an algorithm for the follow-up general case.

Follow-up:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the “poison” bucket within p minutes? There is exact one bucket with poison.

1
2
3
4
5
public class Solution {
    public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) {
        
    }
}

#解題

喝下毒藥15分鐘毒發身亡，假設每15分鐘沒事就喝下一桶這樣循環，一隻豬一小時可喝下四桶水，假設中間喝到任一桶毒藥，則提前找到目標，如果沒有，則第五桶就會是毒藥。(全部五桶的狀況)

換句話說，假設2隻豬可以測試25桶水(二維)，依據豬隻毒發的時間可以知道哪桶水有毒

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

豬隻A每次喝一行(1,2,3,4,5)，豬隻B每次喝一列(1,6,11,16,21)，一小時剛好可以測試25桶水，毒發時即可推測哪一桶水有毒了

所以公式為**(測試時間/毒發時間 + 1 ) ^ n >= 水桶數** ，求n的最小值

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_5桶水_1小時_毒發時間15分鐘_最少需要1隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 5;
    var minutesToDie = 15;
    var minutesToTest = 60;

    var expected = 1;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int PoorPigs(int buckets, int minutesToDie, int minutesToTest)
{
    var OnePigCanTestBukets = (minutesToTest / minutesToDie) + 1;

    var Pigs = 0;
    double TotalCanTestBukets = 0;
    while (TotalCanTestBukets < buckets)
    {
        Pigs++;
        TotalCanTestBukets = Math.Pow(OnePigCanTestBukets, Pigs);
    }

    return Pigs;
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_6桶水_1小時_毒發時間15分鐘_最少需要2隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 6;
    var minutesToDie = 15;
    var minutesToTest = 60;

    var expected = 2;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}

直接通過單元測試

#解析

LeetCode測試發生錯誤

/images/20180619/1.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod]
public void PoorPigsTest_1桶水_1分鐘測試時間_毒發時間1分鐘_最少需要0隻豬來測試()
{
    //arrange
    var sut = new Solution();
    var bukets = 1;
    var minutesToDie = 1;
    var minutesToTest = 1;

    var expected = 0;
    //act
    var actual = sut.PoorPigs(bukets, minutesToDie, minutesToTest);

    //assert
    actual.Should().Be(expected);

}

一桶水根本不需要測試，所以修改一下Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int PoorPigs(int buckets, int minutesToDie, int minutesToTest)
{
    var Pigs = 0;
    if (buckets <= 1)
    {
        return Pigs;
    }

    var OnePigCanTestBukets = (minutesToTest / minutesToDie) + 1;
    double TotalCanTestBukets = 0;
    while (TotalCanTestBukets < buckets)
    {
        Pigs++;
        TotalCanTestBukets = Math.Pow(OnePigCanTestBukets, Pigs);
    }

    return Pigs;
}

過關

心得

一開始沒想清楚，想說算出一隻豬能測試幾桶後直接除即可，但這樣會發生一個狀況是剛好全部豬都活下來，那就會有一堆水桶還沒測試，參考了答案後想了一下才想通這是幾維的問題，只要讓這些豬喝下的水有交錯的可能，那有辦法推斷哪桶有毒。

另外Math.Pow的用法也是查了後才知道如何使用，雖然理解上不難，但也是很有收穫的一題

MSDN - Math.Pow

Posted on Edited on In Disqus:

#題目

Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] =”abcabcabc”.

On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example:

Input:
s1=”acb”, n1=4
s2=”ab”, n2=2

Return:
2

#解題

如何判定S2會包含在S1的倍數之中，我採取的方法是將遍歷S1的每個字元，每當該字元與S2相同時，S2的指標往前一格。

[a]cb
S1 : a
[a]b
S2 : a

a[c]b
S1 : c
a[b]
S2 : b

ac[b]
S1 : b
a[b]
S2 : b

[a]cb
S1 : a
[a]b
S2 : a

以下省略….

直到S1 * N1的字元次數被跑完時，可以知道S2被重複了幾次，這時候將重複次數除以N2即為真正可重複的次數

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[TestMethod()]
public void GetMaxRepetitionsTest()
{
    //arrange
    var s1 = "acb";
    var n1 = 4;
    var s2 = "ab";
    var n2 = 2;
    var sut = new Solution();

    var expected = 2;

    //act
    var actual = sut.GetMaxRepetitions(s1, n1, s2, n2);
    
    //assert
    actual.Should().Be(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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var SlChars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();

    int Repetitions = 0;
    int Cursor = 0;

    for (int i = 0; i < SlChars.Length * n1 ; i++)
    {
        if (SlChars[i % SlChars.Length] == S2Chars[Cursor])
        {
            Cursor++; 
        }

        if (Cursor == S2Chars.Length)
        {
            Repetitions++;
            Cursor = 0;
        }
    }


    return Repetitions / n2;
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[TestMethod()]
public void GetMaxRepetitionsTest_2()
{
    //arrange
    var s1 = "ab";
    var n1 = 3;
    var s2 = "ab";
    var n2 = 4;
    var sut = new Solution();

    var expected = 0;

    //act
    var actual = sut.GetMaxRepetitions(s1, n1, s2, n2);

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

單元測試直接通過

#解析

LeetCode回傳Time Limit Exceeded，表示這效率不能接受，所以來試試看優化它

優化

想先把迴圈內計算餘數的地方拿掉，這個地方應該卡掉一堆效能

1
if (SlChars[i % SlChars.Length] == S2Chars[Cursor])

改寫之後不再迴圈內計算餘數，讓每個變數的操作都盡量簡單化

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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var SlChars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();

    int Repetitions = 0;

    int S1Cursor = 0;
    int S2Cursor = 0;


    int Count = 0;
    while (Count < n1)
    {
        if (SlChars[S1Cursor] == S2Chars[S2Cursor])
        {
            S2Cursor++;
        }

        S1Cursor++;

        if (S2Cursor == S2Chars.Length)
        {
            Repetitions++;
            S2Cursor = 0;
        }

        if (S1Cursor == SlChars.Length)
        {
            S1Cursor = 0;
            Count++;
        }

    }

    return Repetitions / n2;
}

結果LeetCode還是判定逾時,果然事情不是憨人我想的那麼簡單，暴力破解法行不通

/images/20180611/3.jpg

尋找Loop Pattern

在這邊決定改變作法，首先如果S1會重複表示有可能發生重複狀況的發生，例如

S1 = aabaabaab
n1 = 3

S2 = aba
n2 = 1

0 4 7 1 4 7
a a b a a b a a b a a b a a b a a b a …..
a b a a b a a b a a b a a b a a b a …..

*第一列表示S2字首a比對到時，相對於各組S1的Index

*第二列 S1的排序組

*第三列 S2比對相符組

可以發現第一次重複的Index為4，所以繼續往下排就會一直重複的狀況發生，也藉著這個特性可以找出一個算法。

  • 第二次4在整個S1的排列組裡面Index為13，第一次4在整個排列組裡面Index也是4
  • 兩者之間總共可以包含3組S2
  • 所以之後只要每加9個字元，就會多出3組S2

依照此特性修改程式

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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var S1Chars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();


    int S2Cursor = 0;
    int Repetitions = 0;
    var LogFirstLetterMatchInS1Index = new Dictionary<int, Tuple<int, int>>();
    for (int i = 0; i < S1Chars.Length * n1 ; i++)
    {
        var S1Index = i % s1.Length;
        if (S1Chars[S1Index] == S2Chars[S2Cursor])
        {
            if (S2Cursor == 0)
            {
                if (LogFirstLetterMatchInS1Index.ContainsKey(S1Index))
                {
                    //形成Loop了
                    var PreSameIndexValue = LogFirstLetterMatchInS1Index[S1Index];

                    //Repetitions
                    var OneLoopS2Count = (Repetitions - PreSameIndexValue.Item2);

                    var OneLoopDistance = i - PreSameIndexValue.Item1;

                    while ((i + OneLoopDistance) < S1Chars.Length * n1)
                    {
                        Repetitions += OneLoopS2Count;

                        i += OneLoopDistance;
                    }

                }
                else
                {
                    LogFirstLetterMatchInS1Index.Add(S1Index,new Tuple<int, int>(i, Repetitions));
                }
            }
            S2Cursor++;
        }

        if (S2Cursor == S2Chars.Length)
        {
            Repetitions++;

            S2Cursor = 0;
        }
    }

    return Repetitions / n2;
}

雖然終於通過LeetCode測驗，但成績依然不是很理想，不過一些大神的解法目前還沒完全了解，所以先用這個算法勉強過關，之後有懂更佳的方式再繼續優化。

這題寫了兩天且數次拿著計算紙在床上睡著後終於勉強想通，不愧是Hard等級的題目阿

Posted on Edited on In Disqus:

#題目

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

#解題

serialize

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void serializeTest()
{
    //arrange
    var node = new TreeNode(1);
    var sut = new Codec();

    var expected = "1!#!#!";

    //act
    var actual = sut.serialize(node);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Codec
{
    public string serialize(TreeNode root)
    {
        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        return null;
    }
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[TestMethod()]
public void serializeTest_傳入Null應回傳空字串()
{
    //arrange
    var sut = new Codec();
    
    var expected = "#!";

    //act
    var actual = sut.serialize(null);

    //assert
    actual.Should().Be(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Codec
{
    public string serialize(TreeNode root)
    {
        if (root == null)
        {
            return "#!";
        }

        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        return null;
    }
}

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod()]
public void serializeTest_有左邊子節點()
{
    //arrange
    var node = new TreeNode(1);
    node.left = new TreeNode(2);

    var sut = new Codec();

    var expected = "1!2!#!#!#!";

    //act
    var actual = sut.serialize(node);

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

測試直接通過

案例四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod()]
public void serializeTest_有右邊子節點()
{
    //arrange
    var node = new TreeNode(1);
    node.right = new TreeNode(2);

    var sut = new Codec();

    var expected = @"1!#!2!#!#!";

    //act
    var actual = sut.serialize(node);

    //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
[TestMethod()]
public void serializeTest_三層節點()
{
    //arrange
    var node = new TreeNode(1);
    node.left = new TreeNode(2);
    node.right = new TreeNode(3);

    node.left.left = new TreeNode(4);
    node.right.right = new TreeNode(5);

    var sut = new Codec();

    var expected = "1!2!4!#!#!#!3!#!5!#!#!";

    //act
    var actual = sut.serialize(node);

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

圖解

/images/20180609/1.gif

deserialize

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[TestMethod()]
public void deserializeTest()
{
    //arrange
    var nodeSerializeString = @"1!#!#!";
    var sut = new Codec();
           
    var expected = new TreeNode(1);
    //act
    var actual = sut.deserialize(nodeSerializeString);

    //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
public class Codec
{
    public string serialize(TreeNode root)
    {
        if (root == null)
        {
            return "#!";
        }

        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        var nodeData = data.Split(new string[] { "!" }, StringSplitOptions.RemoveEmptyEntries);

        var queue = new Queue<string>();

        foreach (var node in nodeData)
        {
            queue.Enqueue(node);
        }

        return RebuildNode(queue);
    }

    private TreeNode RebuildNode(Queue<string> queue)
    {
        var Value = queue.Dequeue();

        if (Value == "#")
        {
            return null;
        }

        TreeNode node = new TreeNode(int.Parse(Value));

        node.left = RebuildNode(queue);
        node.right = RebuildNode(queue);

        return node;
    }
}

Queue類別為先進先出**(FIFO)，與Stack**後進先出(LIFO)使用方法相反

MSDN - Queue 類別

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
[TestMethod()]
public void deserializeTest_Null_Node()
{
    //arrange
    var nodeSerializeString = "#!";
    var sut = new Codec();

    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeNull();
}

直接通過測試

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void deserializeTest_有左邊子節點()
{
    //arrange
    var nodeSerializeString = @"1!4!#!#!#!";
    var sut = new Codec();

    var expected = new TreeNode(1);
    expected.left = new TreeNode(4);
    //act
    var actual = sut.deserialize(nodeSerializeString);

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

直接通過測試

案例四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void deserializeTest_有右邊子節點()
{
    //arrange
    var nodeSerializeString = @"1!#!2!#!#!";
    var sut = new Codec();

    var expected = new TreeNode(1);
    expected.right = new TreeNode(2);
    //act
    var actual = sut.deserialize(nodeSerializeString);

    //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
[TestMethod()]
public void deserializeTest_三層節點()
{
    //arrange
    var nodeSerializeString = @"1!2!4!#!#!#!3!#!5!#!#!";
    var sut = new Codec();


    var expected = new TreeNode(1);
    expected.left = new TreeNode(2);
    expected.right = new TreeNode(3);

    expected.left.left = new TreeNode(4);
    expected.right.right = new TreeNode(5);

    //act
    var actual = sut.deserialize(nodeSerializeString);

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

直接通過測試

#解析

/images/20180609/2.jpg

這題一樣是參考了別人的答案然後去理解，一開始搞得很複雜，想說回傳Json然後再去解析，忽略了二元樹遍歷規則，果然還要多練練才行。

Posted on Edited on In Disqus:

#題目

Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.

Example:

Input:
s = “abcd”
t = “abcde”

Output:
e

Explanation:
‘e’ is the letter that was added.

1
2
3
4
5
public class Solution {
    public char FindTheDifference(string s, string t) {
        
    }
}

#解題

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[TestMethod()]
public void FindTheDifferenceTest_輸入S為abcd_輸入T為abcde()
{
    //arrange
    var sut = new Solution();
    var S = "abcd";
    var T = "abcde";

    char expected = 'e';

    //act
    var actual = sut.FindTheDifference(S, T);

    //assert
    actual.Should().Be(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public char FindTheDifference(string s, string t)
{
    var originalString =  s.ToCharArray();

    var addSomeSaltString = t.ToCharArray();

    for (int i = 0; i < addSomeSaltString.Length; i++)
    {
        var checkThisChar = addSomeSaltString[i];
        if (i > originalString.Length -1)
        {
            return checkThisChar;
        }

        if (originalString[i] != checkThisChar)
        {
            return checkThisChar;
        }
    }

    return '\0';
}

#解析

LeetCode跑測試錯誤

補上錯誤案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod()]
public void FindTheDifferenceTest_LeetCode_Error1()
{
    //arrange
    var sut = new Solution();
    var S = "ymbgaraibkfmvocpizdydugvalagaivdbfsfbepeyccqfepzvtpyxtbadkhmwmoswrcxnargtlswqemafandgkmydtimuzvjwxvlfwlhvkrgcsithaqlcvrihrwqkpjdhgfgreqoxzfvhjzojhghfwbvpfzectwwhexthbsndovxejsntmjihchaotbgcysfdaojkjldprwyrnischrgmtvjcorypvopfmegizfkvudubnejzfqffvgdoxohuinkyygbdzmshvyqyhsozwvlhevfepdvafgkqpkmcsikfyxczcovrmwqxxbnhfzcjjcpgzjjfateajnnvlbwhyppdleahgaypxidkpwmfqwqyofwdqgxhjaxvyrzupfwesmxbjszolgwqvfiozofncbohduqgiswuiyddmwlwubetyaummenkdfptjczxemryuotrrymrfdxtrebpbjtpnuhsbnovhectpjhfhahbqrfbyxggobsweefcwxpqsspyssrmdhuelkkvyjxswjwofngpwfxvknkjviiavorwyfzlnktmfwxkvwkrwdcxjfzikdyswsuxegmhtnxjraqrdchaauazfhtklxsksbhwgjphgbasfnlwqwukprgvihntsyymdrfovaszjywuqygpvjtvlsvvqbvzsmgweiayhlubnbsitvfxawhfmfiatxvqrcwjshvovxknnxnyyfexqycrlyksderlqarqhkxyaqwlwoqcribumrqjtelhwdvaiysgjlvksrfvjlcaiwrirtkkxbwgicyhvakxgdjwnwmubkiazdjkfmotglclqndqjxethoutvjchjbkoasnnfbgrnycucfpeovruguzumgmgddqwjgdvaujhyqsqtoexmnfuluaqbxoofvotvfoiexbnprrxptchmlctzgqtkivsilwgwgvpidpvasurraqfkcmxhdapjrlrnkbklwkrvoaziznlpor";

    var T = "qhxepbshlrhoecdaodgpousbzfcqjxulatciapuftffahhlmxbufgjuxstfjvljybfxnenlacmjqoymvamphpxnolwijwcecgwbcjhgdybfffwoygikvoecdggplfohemfypxfsvdrseyhmvkoovxhdvoavsqqbrsqrkqhbtmgwaurgisloqjixfwfvwtszcxwktkwesaxsmhsvlitegrlzkvfqoiiwxbzskzoewbkxtphapavbyvhzvgrrfriddnsrftfowhdanvhjvurhljmpxvpddxmzfgwwpkjrfgqptrmumoemhfpojnxzwlrxkcafvbhlwrapubhveattfifsmiounhqusvhywnxhwrgamgnesxmzliyzisqrwvkiyderyotxhwspqrrkeczjysfujvovsfcfouykcqyjoobfdgnlswfzjmyucaxuaslzwfnetekymrwbvponiaojdqnbmboldvvitamntwnyaeppjaohwkrisrlrgwcjqqgxeqerjrbapfzurcwxhcwzugcgnirkkrxdthtbmdqgvqxilllrsbwjhwqszrjtzyetwubdrlyakzxcveufvhqugyawvkivwonvmrgnchkzdysngqdibhkyboyftxcvvjoggecjsajbuqkjjxfvynrjsnvtfvgpgveycxidhhfauvjovmnbqgoxsafknluyimkczykwdgvqwlvvgdmufxdypwnajkncoynqticfetcdafvtqszuwfmrdggifokwmkgzuxnhncmnsstffqpqbplypapctctfhqpihavligbrutxmmygiyaklqtakdidvnvrjfteazeqmbgklrgrorudayokxptswwkcircwuhcavhdparjfkjypkyxhbgwxbkvpvrtzjaetahmxevmkhdfyidhrdeejapfbafwmdqjqszwnwzgclitdhlnkaiyldwkwwzvhyorgbysyjbxsspnjdewjxbhpsvj";

    char expected = 't';

    //act
    var actual = sut.FindTheDifference(S, T);

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

顯然我的方向上完全錯誤，題目的意思是兩邊的每種字元個數應該會一樣，唯獨T會多插入一個隨機字元，找出那一個隨機字元，且與排序無關。

原本分別統計S與T包含的每個字元個數後，比較個數不一樣的即是多出來的(程式就不寫了，這種暴力破解法大家都會)，但總覺得哪裡不對，參考了LeetCode上面大大的答案後果然有更好的解法

將S與T的每個字元用ASCII內碼對應的數字相加後，差即為多出來的數字

1
2
3
4
5
6
7
8
9
10
11
12
13
public char FindTheDifference(string s, string t)
{
    int sumS = 0;
    foreach (char c in t)
    {
        sumS += c;
    }
    foreach (char c in s)
    {
        sumS -= c;
    }
    return (char)(sumS);
}

在這邊我學習到了

  • String直接Foreach即是Char的型別(我一開始還在那拆解)
  • Char可以直接與Int相加，無須轉換

#優化

既然都知道T一定只比S多一個字元，那這樣雙迴圈其實也可以省略掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public char FindTheDifference(string s, string t)
{
    //先加T的最後一個字元
    int sum = t[t.Length -1];

    for (int i = 0; i < t.Length - 1; i++)
    {
        //T加總
        sum += t[i];
        //扣掉S
        sum -= s[i];

    }
    //相差的值
    return (char)(sum);
}

透過 ^= 運算子

這邊也看到另一種做法，是透過**^= ** (XOR)的運算

Wiki

在數位邏輯中，邏輯算符互斥或閘（exclusive or）是對兩個運算元的一種邏輯分析類型，符號為XOR或EOR或⊕。與一般的邏輯或OR不同，當兩兩數值相同為否，而數值不同時為真。

二進位舉例

1111 ^ 1111 = 0000

0000 ^ 0000 = 0000

0101 ^ 1101 = 1000

1
2
3
4
5
6
var a = 1;
a ^= 5;
//a:4

a ^= 5;
//a:1
1
2
3
4
5
6
var a = 1;
a ^= 2;
//a:3 

a ^= 2;
//a:1

所以碰到相同的數字會被返回來的特性下，可以將程式改成

1
2
3
4
5
6
7
8
9
10
11
12
13
public char FindTheDifference(string s, string t)
{
    //先加T的最後一個字元
    int sum = t[t.Length -1];

    for (int i = 0; i < t.Length - 1; i++)
    {
        sum ^= t[i];
        sum ^= s[i];

    }
    return (char)(sum);
}

這題雖然被標註為Easy，但果然一些基礎還是要多加強，否則對弱弱的我來說還是不Easy

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