瀏覽標籤：

Easy

[MySQL][LeetCode][Easy] 181. Employees Earning More Than Their Managers

心得：

題目要求找出有哪些人的薪水比主管高，找出名字並修改欄位名稱為Employee。

題目：

The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.

+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+

Given the Employee table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.

+----------+
| Employee |
+----------+
| Joe      |
+----------+

答案：

  1. Sub Select 
    # Write your MySQL query statement below
SELECT  a.Name AS Employee
FROM    Employee AS a
WHERE   a.Salary > (SELECT  z.Salary 
                    FROM    Employee AS z
                    WHERE   z.Id = a.ManagerId);
  2. Join 
    # Write your MySQL query statement below
SELECT  a.Name AS Employee
FROM    Employee AS a
JOIN    Employee AS b
ON      a.ManagerId = b.Id
WHERE   a.Salary > b.Salary
  3. From 
    # Write your MySQL query statement below
SELECT  a.Name AS Employee
FROM    Employee AS a, Employee AS b
WHERE   a.ManagerId = b.Id
AND     a.Salary > b.Salary

     

       

[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();
    }
}
       

[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#][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#]輸出數字範圍內所有的質數
       

[C#][LeetCode][Easy] 242. Valid Anagram

心得：

這題要比較兩個字串是否具有相同字母(不管順序)，因為這題比較簡單，所以就嘗試用了許多方式解答。

問題：

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

答案：

  • LinQ – OrderBy 
    public class Solution {
    public bool IsAnagram(string s, string t) {
        return new string(s.OrderBy(x => x).ToArray()) == new string(t.OrderBy(x => x).ToArray());
    }
}
  • LinQ – Sort 
    public class Solution {
    public bool IsAnagram(string s, string t) {
        var arr_1 = s.ToList();
        var arr_2 = t.ToList();
        arr_1.Sort();
        arr_2.Sort();
        return new string(arr_1.ToArray()) == new string(arr_2.ToArray());
    }
}
  • Normal – Array.Sort 
    public class Solution {
    public bool IsAnagram(string s, string t) {
        var arr_1 = s.ToArray();
        var arr_2 = t.ToArray();
        Array.Sort(arr_1);
        Array.Sort(arr_2);
        return new string(arr_1) == new string(arr_2);
    }
}
  • Normal – 硬幹 (會 Time Limit Exceeded) 
    public class Solution {
    public bool IsAnagram(string s, string t) {
        return Sort(s) == Sort(t);
    }
    
    private string Sort(string str){
        string result = "";
         for(int i = 0; i < 25; i++){
            char c = Convert.ToChar(Convert.ToInt16('a') + i);
            for(int j = 0; j < str.Length; j++){
                if(c == str[j]){
                    result += c;
                }
            }
        }
        
        return result;
    }
}

參考：

  1. (C#)用迴圈印出字母A到Z
       

[C#][LeetCode][Easy] 292. Nim Game

心得：

一次可以拿1~3顆石頭，最後一個把石頭拿完的人就算勝利，很簡單的一支小程式判斷是否可以贏得這場遊戲，而且有先手優勢，所以只要是除不滿4就一定會贏。

問題：

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

答案：

public class Solution {
    public bool CanWinNim(int n) {
        if(n < 4){
            return true;
        }
        else{
            return n % 4 > 0;
        }
    }
}