bysz71 / leetcodeincsharp Goto Github PK

Same idea as that in this repo. Just more functional style. Perhaps it may be a start to get used to lambda and Linq.

    public int SingleNumber(int[] nums) 
    {
        var dic = new Dictionary<int, int>();
        new HashSet<int>(nums).ToList().ForEach(n => dic[n] = 0);
        nums.ToList().ForEach(n => ++dic[n]);
        return dic.Where(p => p.Value == 1).First().Key;
    }

Please note the fact that the size of the dictionary you used, which has been deleted in a8627ed, has nothing to do with argument size. Hence the solution using dictionaries takes only O(1) time and O(1) extra space. Actually, as used in the current implementation, multiple if else statements are considered to be slower than Hash Table and switch cases statement. Basically, if else takes O(n) time. A reference can be found here : If else vs switch on SO.

That said, the version deleted in a8627ed still can be improved, because dictionaries are good at lookup rather than iteration, wherras array (i.e. String s) good at iteration rather than lookup.

I implemented another version with same idea as that deleted, like following:

public class Solution 
{
    public int RomanToInt(string s) 
    {
        var twos = new Dictionary<string, int>()
        {
             { "CM", 900 }, { "CD", 400 }, { "XC", 90 }, { "XL", 40 }, { "IX", 9 }, { "IV", 4 }
        };
        var ones = new Dictionary<string, int>()
        {
            { "I", 1 }, { "V", 5 }, { "X", 10 }, { "L", 50 }, { "C", 100 }, { "D", 500 }, { "M", 1000 }
        };

        int sum = 0;
        for(int i = 0; i < s.Length;)
        {
            if(i + 1 == s.Length || !twos.ContainsKey(s.Substring(i, 2)))
            {
                sum += ones[s[i].ToString()];
                i += 1;
            }
            else
            {
                sum += twos[s.Substring(i, 2)];
                i += 2;
            }
        }
        return sum;
    }
}

Please notice the semantics of method AddRange. Basically, it copies items from source collections. The source items will be reclaimed by CLR some time later. So the current implementation in this repo wastes a lot of spaces.

Like following, I wrote another implementation using Concat to reduce this overhead.

    public IList<int> PreorderTraversal(TreeNode root) 
    {
        if (root == null) 
            return new List<int>();
        else
            return new List<int>{ root.val }
                .Concat(PreorderTraversal(root.left))
                .Concat(PreorderTraversal(root.right))
                .ToList();
    }

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

Generated by VS, such statements can be found in almost every file in this repo. Just suggest to remove these using NeverUsedNameSpace. I think this should be a good practice.