瀏覽標籤:

LeetCode

[MySQL][LeetCode][Easy] 183. Customers Who Never Order

心得

這題要show出沒有訂過東西的客戶,所以可以使用LEFT JOIN來關聯兩張表。

問題

Suppose that a website contains two tables, the Customers table and the Orders table. Write a SQL query to find all customers who never order anything.

Table: Customers.

+----+-------+
| Id | Name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+

Table: Orders.

+----+------------+
| Id | CustomerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+

Using the above tables as example, return the following:

+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+

答案

  1. LEFT JOIN
    # Write your MySQL query statement below
    SELECT      a.Name AS Customers
    FROM        Customers AS a
    LEFT JOIN   Orders AS b
    ON          a.Id = b.CustomerId
    WHERE       b.CustomerId IS NULL
  2. Sub Query
    # Write your MySQL query statement below
    SELECT  a.Name AS Customers
    FROM    Customers AS a
    WHERE   (   SELECT  COUNT(1)
                FROM    Orders AS z
                WHERE   z.CustomerId = a.Id) = 0
       

[MySQL][LeetCode][Easy] 176. Second Highest Salary

心得:

找出該資料表內第二高薪水的筆數,若無則回傳null。

問題:

Write a SQL query to get the second highest salary from the Employee table.

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

For example, given the above Employee table, the second highest salary is 200. If there is no second highest salary, then the query should return null.

答案:

  1. Sub Query
    # Write your MySQL query statement below
    SELECT  MAX(a.Salary) AS SecondHighestSalary
    FROM    Employee AS a
    WHERE   a.Salary < (SELECT  MAX(z.Salary)
                        FROM    Employee AS z)
  2. DISTINCT > 不重複
    # Write your MySQL query statement below
    SELECT
    (
        SELECT DISTINCT Salary
        FROM            Employee
        ORDER BY        Salary DESC
        LIMIT           1, 1
    ) AS SecondHighestSalary
  3. GROUP BY > 不重複
    # Write your MySQL query statement below
    SELECT
    (
        SELECT          Salary
        FROM            Employee
        GROUP BY        Salary
        ORDER BY        Salary DESC
        LIMIT           1, 1
    ) AS SecondHighestSalary

     

       

[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

     

       

[MySQL][LeetCode][Easy] 175. Combine Two Tables

心得:

題目要求找出Person表內所有人員的地址,就算是空的也無所謂,所以不用理會Address表內是否有Person表的資料,這題必須使用LEFT JOIN來關聯。

問題:

Table: Person

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId is the primary key column for this table.

Table: Address

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId is the primary key column for this table.

Write a SQL query for a report that provides the following information for
each person in the Person table, regardless if there is an address for each
of those people:

FirstName, LastName, City, State

答案:

# Write your MySQL query statement below
SELECT      a.FirstName, a.LastName, b.City, b.State
FROM        Person AS a
LEFT JOIN   Address AS b
ON          a.PersonId = b.PersonId

參考:

  1. [SQL] 一張圖片解釋 JOIN
       

[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