瀏覽分類：

心得筆記

[C#][LeetCode][Easy] 476. Number Complement

心得：

題目要求將數字轉換為其補數，看起來滿單純的我就想不開硬幹了，由於不想借助C#內建的方法，所以自己實作二進位與十進位之間轉換。

題目：

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

  1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
  2. You could assume no leading zero bit in the integer’s binary representation.

答案：

  1. Normal – 硬幹 
    public class Solution {
    public int FindComplement(int num) {
        string str = ConvertMethod(num);
        string ans = "";
        for(int i = 0; i < str.Length; i++){
            if(str[i] == '0'){
                ans += "1";
            }else{
                ans += "0";
            }
        }
        
        return ConvertMethod(ans);
    }
    
    private string ConvertMethod(int num){
        string str = "";
        while (num > 1)
        {
            str = num % 2 + str;
            num = num / 2;
            if (num == 1)
            {
                str = num + str;
                num = 0;
            }
        }
        
        return str;
    }
    
    private int ConvertMethod(string str)
    {
        int ans = 0;
        for (int i = 0; i < str.Length; i++)
        {
            int tmp = 1;
            for (int j = 1; j < (str.Length - i); j++)
            {
                tmp *= 2;
            }
            ans += tmp * int.Parse(str[i].ToString());
        }

        return ans;
    }
}
  2. LinQ 
    public class Solution {
    public int FindComplement(int num) {
        return Convert.ToInt32(new string(Convert.ToString(num, 2).Select(x => x == '1' ? '0' : '1').ToArray()), 2);
    }
}

參考：

  1. http://www.sggs.hc.edu.tw/sggsnew/comp/bccto2816.htm
  2. [C#] 轉2進位 / 10進位 / 16進位
       

[C#][LeetCode][Easy] 226. Invert Binary Tree

心得：

這題也是典型的遞迴，題目要求把二元樹整個翻轉過來。

問題：

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

答案：

  1. 遞迴 
    /**
 * 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 Solution {
    public TreeNode InvertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        
        var left = root.left;
        var right = root.right;
        root.left = InvertTree(right);
        root.right = InvertTree(left);
        
        return root;
    }
}

     

       

[C#][LeetCode][Easy] 136. Single Number

心得：

從數字陣列中找出只有出現過一次的數字並傳出，這題原本我想說很簡單用一句LinQ就可以交差了，結果一個超時QQ…
最後看了Top Solution還是不太懂只好求助古狗大神並尋求朋友協助，最後才理解了數學的奇妙 !!

解題思路：

2017-01-08-23_04_32-%e9%82%8f%e8%bc%af%e7%95%b0%e6%88%96-%e7%b6%ad%e5%9f%ba%e7%99%be%e7%a7%91%ef%bc%8c%e8%87%aa%e7%94%b1%e7%9a%84%e7%99%be%e7%a7%91%e5%85%a8%e6%9b%b8
根據XOR的真值表，我們用陣列[1, 2, 3, 4, 1, 2, 3]來測試，轉換為二進位的話則是[001, 010, 011, 100, 001, 010, 011]接著運算如下：
^ = 運算子 = XOR

  1. 001 ^ 010 = 011
  2. 011 ^ 011 = 000
  3. 000 ^ 100 = 100
  4. 100 ^ 001 = 101
  5. 101 ^ 010 = 111
  6. 111 ^ 011 = 100
  7. 100 轉十進位則是 4，由此可知答案是4

問題：

Given an array of integers, every element appears twice except for one. Find that single one.

答案：

  1. Normal 
    public class Solution {
    public int SingleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.Length; i++)
        {
            ans ^= nums[i];
        }
        return ans;
    }
}
  2. LinQ (Time Out) 
    public class Solution {
    public int SingleNumber(int[] nums) {
        return nums.Where(x => nums.Count(y => x == y) == 1).SingleOrDefault();
    }
}

參考：

  1. 邏輯異或
  2. 大神朋友
       

[C#][LeetCode][Easy] 258. Add Digits

心得：

題目要求將每一位數相加，直到剩下個位數。

問題：

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

答案：

  1. For + 遞迴 
    public class Solution {
    public int AddDigits(int num) {
        string str = num.ToString();
        if (str.Length < 2)
        {
            return int.Parse(str);
        }
        else
        {
            int tmp = 0;
            for (int i = 0; i < str.Length; i++)
            {
                tmp += int.Parse(str[i].ToString());
            }
    
            return AddDigits(tmp);
        }
    }
}
  2. LinQ + 遞迴 
    public class Solution {
    public int AddDigits(int num) {
        string str = num.ToString();
        if (str.Length < 2)
        {
            return int.Parse(str);
        }
        else
        {
            return AddDigits(str.Sum(x => int.Parse(x.ToString())));
        }
    }
}
  3. Normal 
    public class Solution {
    public int AddDigits(int num) {
        string str = num.ToString();
        while (str.Length > 1)
        {
            int tmp = 0;
            for (int i = 0; i < str.Length; i++)
            {
                tmp += int.Parse(str[i].ToString());
            }

            str = tmp.ToString();
        }

        return int.Parse(str);
    }
}
       

[C#][LeetCode][Easy] 389. Find the Difference

心得：

題目要求找出字串變數s與t差異的字母，變數t一定大於變數s且都為小寫，跑兩個迴圈就解決了。

問題：

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.

答案：

public class Solution {
    public char FindTheDifference(string s, string t) {
        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < t.Length; j++)
            {
                if (s[i] == t[j])
                {
                    t = t.Remove(j, 1);
                    break;
                }
            }
        }

        return t.Length == 1 ? t[0] : new char();
    }
}
       

[Windows] 開機時自動啟用數字鍵

不知為何Win10開機預設都沒有啟用數字鍵，變成每次開機都要先按一下NumLock感覺有點麻煩，今天終於受不了找了兩個方法解決。

方法如下：

  • 修改註冊檔
    1. Win+R輸入regedit開啟登陸編輯器
    2. 找到\HKEY_USERS\.DEFAULT\Control Panel\Keyboard
    3. 將InitialKeyboardIndicators修改為80000002
    4. 重開機即可。
  • 重新開機後再登入畫面先開啟NumLock，不登入直接在重開機一次即可。

來源：

  1. 技巧｜Windows 10筆電開機時自動啟用數字鍵
  2. NB win10如何使開機後於登入輸入密碼前num lock on
       

[C#][LeetCode][Easy] 104. Maximum Depth of Binary Tree

心得：

這題是典型的遞迴題目，題目要求找到二元樹最深的層級為多少。

這題的解法很簡單，先宣告兩個變數分別來儲存左邊與右邊的層級，首先判斷左邊是否為空，若非為空值則會繼續搜尋此節點的子節點是否為空，搜尋完畢後再一併回傳至第一層的left變數裡，右邊反之，最後在比較左右兩邊哪個最大，最大的數字即為二元樹的層級。

問題：

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

答案：

/**
 * 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 Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null)
        {
            return 0;
        }

        int left = 1;
        int right = 1;

        if (root.left != null)
        {
            left += MaxDepth(root.left);
        }

        if (root.right != null)
        {
            right += MaxDepth(root.right);
        }

        return right > left ? right : left;
    }
}

參考：

  1. https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/104md.html
       

[C#] 基礎複習 – 遞迴練習

好久沒用遞迴了，趕快找個簡單的題目複習一下，不然都要忘光光了，熟悉一下之前的Feel ~
順便練習一下簡單工廠模式，首先設計介面ICompute.cs：

interface ICompute
{
    /// <summary>
    /// 1 + ... + N = ?
    /// </summary>
    /// <param name="n"></param>
    /// <returns>Answer</returns>
    Int64 Iterative(Int64 n);

    /// <summary>
    /// 1 - 2 + 3 ... + N = ?
    /// </summary>
    /// <param name="n"></param>
    /// <returns>Answer</returns>
    Int64 AdvancedIterative(Int64 n);

    /// <summary>
    /// 1 x 2 x ... x N = ?
    /// </summary>
    /// <param name="n"></param>
    /// <returns>Answer</returns>
    Int64 Factorial(Int64 n);

    /// <summary>
    /// Fn = Fn-1 + Fn-2
    /// </summary>
    /// <param name="n"></param>
    /// <returns>Answer</returns>
    Int64 Fibonacci(Int64 n);
}

接著建立兩個類別Recursive.cs與ForLoop.cs並繼承ICompute.cs實作其方法：

  • Recursive.cs 
    public class Recursive : ICompute
{
    public Int64 Iterative(Int64 n)
    {
        if (n == 1)
        {
            return n;
        }
        else
        {
            return n + Iterative(n - 1);
        }
    }

    public Int64 AdvancedIterative(Int64 n)
    {
        if (n == 1)
        {
            return n;
        }
        else
        {
            return n % 2 == 0 ? -n + AdvancedIterative(n - 1) : n + AdvancedIterative(n - 1);
        }
    }

    public Int64 Factorial(Int64 n)
    {
        if (n == 1)
        {
            return n;
        }
        else
        {
            return n * Factorial(n - 1);
        }
    }

    public Int64 Fibonacci(Int64 n)
    {
        if (n < 3)
        {
            return 1;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
}
  • ForLoop.cs 
    public class ForLoop : ICompute
{

    public Int64 Iterative(Int64 n)
    {
        int ans = 0;

        for (int i = 1; i <= n; i++)
        {
            ans += i;
        }

        return ans;
    }

    public Int64 AdvancedIterative(Int64 n)
    {
        int ans = 0;

        for (int i = 1; i <= n; i++)
        {
            if (i % 2 == 0)
            {
                ans -= i;
            }
            else
            {
                ans += i;
            }
        }

        return ans;
    }

    public Int64 Factorial(Int64 n)
    {
        int ans = 1;

        for (int i = 1; i <= n; i++)
        {
            ans *= i;
        }

        return ans;
    }

    public Int64 Fibonacci(Int64 n)
    {
        int ans = 0;
        int[] arr = new int[2] { 1, 1 };

        for (int i = 1; i <= n; i++)
        {
            if (i < 3)
            {
                ans = 1;
            }
            else
            {
                ans = arr[0] + arr[1];
                arr[0] = arr[1];
                arr[1] = ans;
            }
        }

        return ans;
    }
}

接著在Program.cs裡面寫一個Run的方法來呼叫剛剛寫好的兩個類別：

static void Run(int n, ICompute compute)
{
    Console.WriteLine("1 + ... + N = {1}", n, compute.Iterative(n));
    Console.WriteLine("1 - 2 + 3 ... + N = {1}", n, compute.AdvancedIterative(n));
    Console.WriteLine("N! = {1}", n, compute.Factorial(n));
    Console.WriteLine("Fn = Fn-1 + Fn-2, n = {0}, Ans = {1}", n, compute.Fibonacci(n));
}

這樣就完成囉 !!

2017-01-05-20_15_29-file____c__users_developer_documents_recursiveeample_recursiveeample_recursiveea

 

原始碼：https://github.com/shuangrain/RecursiveEample

       

[C#] Convert(轉型)、Parse(強制轉型)、TryParse(安全轉型)與運算子轉型的差別、效能

最近再磨練基本功的時候複習了常用到的「轉型」，找一找資料後統整了一下才比較搞懂這些差異。

轉型別基本上分為下列五種：

  1. Convert(轉型) 
    Convert.ToInt32("5.5");
  2. Parse(強制轉型) 
    (int)(5.5);
int.Parse("5.5");
  3. TryParse(安全轉型) 
    int i = 0;
int.TryParse("5.5", out i)
  4. 運算子 – as 
    CustomModel model = obj as CustomModel
  5. 運算子 – is 
    CustomModel model = obj is CustomModel

根據參考資料差異如下：

  1. Convert 是將值轉換成最接近的 32 位元帶正負號的整數 
    Console.WriteLine(Convert.ToInt32("4.5")); //result = 4
Console.WriteLine(Convert.ToInt32("4.51"));//result = 5
Console.WriteLine(Convert.ToInt32("5.4")); //result = 5
Console.WriteLine(Convert.ToInt32("5.5")); //result = 6
  2. Parse 則是無條件捨去( long、float、double、或 decimal ) 
    Console.WriteLine((int)(4.5)); //result = 4
Console.WriteLine((int)(4.51));//result = 4
Console.WriteLine((int)(5.4)); //result = 5
Console.WriteLine((int)(5.5)); //result = 5
  3. TryParse 會回傳一布林值來判斷是否轉換成功 
    string s1 = "1234"; 
string s2 = "1234.65"; 
string s3 = null; 
string s4 = "123456789123456789123456789123456789123456789"; 
bool success = false;    
int result = 0; 
success = Int32.TryParse(s1, out result); //-- success => true;  result => 1234 
success = Int32.TryParse(s2, out result); //-- success => false; result => 0 
success = Int32.TryParse(s3, out result); //-- success => false; result => 0 
success = Int32.TryParse(s4, out result); //-- success => false; result => 0
  4. as 若轉型失敗會回傳null，且只能用於參考類型，不能應用於值類型(除非是Nullable的值類型)。 
    CustomModel model = obj as CustomModel;
if(model  != null)
{
    //轉型成功
}
else
{
    //轉型失敗
}
  5. is 若轉型失敗則會跳Exception 
    try
{
    CustomModelt = obj is CustomModel;
}
catch
{
    //轉型失敗
}

2017/09/24 更新

(Net Core 2.0)效能上 Parse > TryParse > Convert。

測試程式碼：

class Program
{
    static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();

        sw.Start();
        for (int i = 0; i < 10000000; i++)
        {
            Convert.ToInt32(i.ToString());
        }
        sw.Stop();

        Console.WriteLine(string.Format("Convert.ToInt32 = {0} ms", sw.ElapsedMilliseconds));
        sw.Reset();

        sw.Start();
        for (int i = 0; i < 10000000; i++)
        {
            int.Parse(i.ToString());
        }
        sw.Stop();

        Console.WriteLine(string.Format("int.Parse = {0} ms", sw.ElapsedMilliseconds));
        sw.Reset();

        sw.Start();
        for (int i = 0; i < 10000000; i++)
        {
            int.TryParse(i.ToString(), out int tmp);
        }
        sw.Stop();

        Console.WriteLine(string.Format("int.TryParse = {0} ms", sw.ElapsedMilliseconds));
        sw.Reset();

        object model = new TestModel
        {
            Tmp = 100
        };

        sw.Start();
        for (int i = 0; i < 10000000; i++)
        {
            var tmp = model as TestModel;
        }
        sw.Stop();

        Console.WriteLine(string.Format("as = {0} ms", sw.ElapsedMilliseconds));
        sw.Reset();

        sw.Start();
        for (int i = 0; i < 10000000; i++)
        {
            var tmp = model is TestModel;
        }
        sw.Stop();

        Console.WriteLine(string.Format("is = {0} ms", sw.ElapsedMilliseconds));
        sw.Reset();

        Console.ReadKey();
    }

    public class TestModel
    {
        public int Tmp { get; set; }
    }
}

 

參考：

  1. Convert(轉型)與Int32(強制轉型)的差別、效能
  2. [C#]Convert.ToInt32()與int.Parse()的差別
  3. [C#]Convert、Parse、TryParse 差異
  4. [C#]Effective C# 條款三： 運算子is或as優於強制轉型
       

[C#][LeetCode][Easy] 204. Count Primes

心得：

題目要求找出小於N(不包括N)的所有質數，由於N從3開始才會有質數(1非質數)所以直接回傳0，但是嘗試了很多方法都TimeOut，最後只好拜狗大神了。

最後找到了Eratosthenes演算法，小於等於根號N的所有質數去除N，若均無法整除則N為質數，有了這個觀念程式速度就快多了！

問題：

Count the number of prime numbers less than a non-negative number, n.

答案：

  1. Eratosthenes演算法 
    public class Solution {
    public int CountPrimes(int n) {
        if (n < 3) { return 0; }

        int count = 0;
        for (int i = 2; i < n; i++)
        {
            bool IsPrime = true;
            //開根號取最大值+1
            int sqrt = Convert.ToInt32(Math.Sqrt(i)) + 1;
            for (int j = 2; j <= sqrt; j++)
            {
                if (i != j && i % j == 0)
                {
                    IsPrime = false;
                    break;
                }
            }

            if (IsPrime) { count++; }
        }

        return count;
    }
}
  2. LinQ (Time Limit Exceeded) 
    public class Solution {
    public int CountPrimes(int n) {
        if(n < 3){ return 0; }
        var arr = Enumerable.Range(2, n);
        return arr.Count(x => x < n && !arr.Where(y => x > y).Any(y => x % y == 0));
    }
}
  3. Nomal –  硬幹(Time Limit Exceeded) 
    public class Solution
{
    public int CountPrimes(int n)
    {
        if (n < 3) { return 0; }

        int count = 0;
        for (int i = 2; i < n; i++)
        {
            bool IsPrime = true;
            for (int j = 2; j < i; j++)
            {
                if (i % j == 0)
                {
                    IsPrime = false;
                    break;
                }
            }

            if (IsPrime) { count++; }
        }

        return count;
    }
}
  4. Nomal –  稍微聰明一點的硬幹(Time Limit Exceeded)
    由於可以知道只要是2的倍數絕對不會是質數，所以迴圈就直接i+=2了，殊不知還是Time Out…

    public class Solution {
    public int CountPrimes(int n) {
        if (n < 3) { return 0; }

        int count = 1;
        for (int i = 3; i < n; i += 2)
        {
            bool IsPrime = true;
            for (int j = 3; j < i; j += 2)
            {
                if (i % j == 0)
                {
                    IsPrime = false;
                    break;
                }
            }

            if (IsPrime) { count++; }
        }

        return count;
    }
}

參考：

  1. https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/204md.html
  2. [C#]輸出數字範圍內所有的質數