[C#][LeetCode][Easy] 500. Keyboard Row

心得

鍵盤共有三行[qwertyuiop, asdfghjkl, zxcvbnm]，找出在同行字母拼湊出來的單字。

問題

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

keyboard

 

Example 1:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

  1. You may use one character in the keyboard more than once.
  2. You may assume the input string will only contain letters of alphabet.

答案

public class Solution {
    public string[] FindWords(string[] words) {
        string row_1 = "qwertyuiop";
        string row_2 = "asdfghjkl";
        string row_3 = "zxcvbnm";

        return words.Where(x =>
        {
            var str = x.ToLower().ToArray();
            return !str.Any(y => !row_1.Contains(y)) || !str.Any(y => !row_2.Contains(y)) || !str.Any(y => !row_3.Contains(y));
        }).ToArray();
    }
}
       

[C#][LeetCode][Easy] 455. Assign Cookies

心得

題目詢問說共可以滿足幾個小孩所期望的蛋糕數，例如總共有三個小孩A, B, C，A希望獲得1片蛋糕；B希望獲得2片蛋糕；C希望獲得3片蛋糕，而總共有兩塊蛋糕Z, X，Z可以切成1片，X可以切成兩片，這樣的話答案是2，因為最多只能滿足兩個小孩的需求。依照這個思路去撰寫Code就容易得多了。

問題

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

答案

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
        Array.Sort(s);

        int ans = 0;

        for (int i = 0; ans < g.Length && i < s.Length; i++)
        {
            if (g[ans] <= s[i])
            {
                ans++;
            }
        }
        
        return ans;
    }
}

 

       

[C#][LeetCode][Easy] 492. Construct the Rectangle

心得

簡單來說就是輸入數字x，找出x的因數並找出相乘會等於x的兩個數字且兩數字相減最接近0的組合，大的放前面小的放後面以int[]的型態回傳。

問題

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1. The area of the rectangular web page you designed must equal to the given target area.

2. The width W should not be larger than the length L, which means L >= W.

3. The difference between length L and width W should be as small as possible.

You need to output the length L and the width W of the web page you designed in sequence.

Example:

Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

Note:

  1. The given area won’t exceed 10,000,000 and is a positive integer
  2. The web page’s width and length you designed must be positive integers.

答案

  1. 我的笨方法 
    public class Solution {
    public int[] ConstructRectangle(int area) {
        int num1 = Enumerable
            .Range(1, (int)Math.Sqrt(area))
            .Where(x => area % x == 0)
            .OrderBy(x => Math.Abs((area / x) - x))
            .FirstOrDefault();
        int num2 = area / num1;
        return num1 > num2 ? new int[] { num1, num2 } : new int[] { num2, num1 };
    }
}
  2. Top Solution的神方法 
    public class Solution {
    public int[] ConstructRectangle(int area) {
        int w = (int)Math.Sqrt(area);
        while( area % w != 0){
            w--;
        }
        return new int[] { area / w, w };
    }
}

     

       

[VS Code] 好用套件 (2017/01/19)

紀錄一下好用套件：

  1. HTML CSS Support Extension
    CSS自動輸入

    • ext install vscode-html-css
  2. Bootstrap 4 & Font awesome snippets
    BootStrap v4 快速套版

    • ext install bootstrap4-vscode
  3. Bootstrap 3 Snippets
    BootStrap v3 快速套版

    • ext install bootstrap-3-snippets
  4. Angular 2 TypeScript Snippets
    開發 Angular 2 的時候經常有許多語法糖，對初學者來說經常會打錯，有了這些 Code Snippets 就可以降低打錯字的機會。

    • ext install Angular2
  5. Auto Import
    在開發 TypeScript 的時候由於會經常用到 ES2015 的 import 語法匯入另一個模組的型別，透過 Auto Import 可以將許多型別自動化載入，大幅縮短開發時間。

    • ext install autoimport
  6. Google Complete Me
    開發宣告變數時，會利用Google來建議變數名稱。
    按Ctrl + Shift + i控制開關。

    • ext install google-complete-me
  7. JS-CSS-HTML Formatter
    JS, CSS, HTML排版

    • ext install vscode-JS-CSS-HTML-formatter
  8. VS Code Plugin for the Angular Language Service

參考：

  1. 開發 Angular 2 推薦的 VS Code 擴充套件
       

[C#][LeetCode][Easy] 485. Max Consecutive Ones

心得

傳入一個二進位的陣列，找出1最多連續出現的次數。

問題

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

答案

public class Solution {
    public int FindMaxConsecutiveOnes(int[] nums) {
        int maxcount = 0, count = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == 1)
            {
                count++;
            }
            else
            {
                if (maxcount < count)
                {
                    maxcount = count;
                }
                count = 0;
            }
        }
        return maxcount < count ? count : maxcount;
    }
}

 

       

[Windows] Win10 關閉自動更新

Win10的擾人自動更新讓我很頭痛，試了很多方法只有這個有效，不過還是會不定期地提醒你更新，但至少不會幫你更新了QQ

  1. 首先在桌面同時按下 win+R 叫出 執行 視窗
    並輸入 gpedit.msc 按 確定
  2. 電腦設定 → 系統管理範本 → Windows 元件 → Windows Update → 設定自動更新
    2017-01-16-23_37_30-dev_win10-vmware-workstation
  3. 完成。

 

參考：

  1. Win10 如何永久關閉 Windows Update 自動更新
       

[MySQL][LeetCode][Medium] 180. Consecutive Numbers

心得

這題要找出連續三次重複出現的數字，我原本一直在想如果中間有斷層(中間有資料被刪除)的話是否要先自己排序一次，結果看了一下Top Solutions才發現根本不用考慮這個問題，直接ID+1尋找下筆資料即可，既然這麼單純的話也沒什麼問題了。

問題

Write a SQL query to find all numbers that appear at least three times consecutively.

+----+-----+
| Id | Num |
+----+-----+
| 1  |  1  |
| 2  |  1  |
| 3  |  1  |
| 4  |  2  |
| 5  |  1  |
| 6  |  2  |
| 7  |  2  |
+----+-----+

For example, given the above Logs table, 1 is the only number that appears consecutively for at least three times.

答案

  1. 方法對，但會TimeOut 
    # Write your MySQL query statement below
SELECT DISTINCT(a.Num) AS ConsecutiveNums
FROM Logs AS a
WHERE ( SELECT z.Num
        FROM Logs AS z
        WHERE z.Id = a.Id + 1) = a.Num
AND (   SELECT z.Num
        FROM Logs AS z
        WHERE z.Id = a.Id + 2) = a.Num
  2. 通過 
    # Write your MySQL query statement below
SELECT DISTINCT(a.Num) AS ConsecutiveNums
FROM Logs AS a
JOIN Logs AS b
ON a.Id = b.Id - 1
JOIN Logs AS c
ON b.Id = c.Id - 1
WHERE a.Num = b.Num
AND b.Num = c.Num

     

       

[MySQL][LeetCode][Hard] 185. Department Top Three Salaries

心得

這題是 184. Department Highest Salary 的衍生題，但如果直接套用其方法的話會TimeOut，不過還是記錄一下方法：

# Write your MySQL query statement below
SELECT  b.Name AS Department,
        a.Name AS Employee,
        a.Salary AS Salary
FROM Employee AS a
JOIN (  SELECT z.*, (SELECT MAX(y.Salary)
                     FROM Employee AS y
                     WHERE z.Id = y.DepartmentId
                     LIMIT 0, 1) AS TopSalary,
                    (SELECT MAX(y.Salary)
                     FROM Employee AS y
                     WHERE z.Id = y.DepartmentId
                     AND y.Salary < TopSalary
                     LIMIT 0, 1) AS TwoSalary,
                    (SELECT MAX(y.Salary)
                     FROM Employee AS y
                     WHERE z.Id = y.DepartmentId
                     AND y.Salary < TwoSalary
                     LIMIT 0, 1) AS ThreeSalary
        FROM Department AS z) AS b
ON a.DepartmentId = b.Id
WHERE ( a.Salary = b.TopSalary
OR      a.Salary = b.TwoSalary
OR      a.Salary = b.ThreeSalary)

問題

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

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
+----+-------+--------+--------------+

The Department table holds all departments of the company.

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

Write a SQL query to find employees who earn the top three salaries in each of the department. For the above tables, your SQL query should return the following rows.

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

答案

  1. 這個方法是在Top Solutions看到的，在WHERE裡面統計有幾個其他同部門的人大於自己的薪水，把小於三個的都列出來，就是答案。 
    # Write your MySQL query statement below
SELECT  b.Name AS Department,
        a.Name AS Employee,
        a.Salary AS Salary
FROM Employee AS a
JOIN Department AS b
ON a.DepartmentId = b.Id
WHERE ( SELECT COUNT(DISTINCT(z.Salary)) 
        FROM Employee AS z
        WHERE a.DepartmentId = z.DepartmentId
        AND a.Salary < z.Salary) < 3
  2. 同上，只是改成WHERE IN效能較佳 
    # Write your MySQL query statement below
SELECT  b.Name AS Department,
        a.Name AS Employee,
        a.Salary AS Salary
FROM Employee AS a
JOIN Department AS b
ON a.DepartmentId = b.Id
WHERE ( SELECT COUNT(DISTINCT(z.Salary)) 
        FROM Employee AS z
        WHERE a.DepartmentId = z.DepartmentId
        AND a.Salary < z.Salary) IN (0, 1, 2)

     

       

[MySQL][LeetCode][Hard] 262. Trips and Users

心得

這題只是看起來比較多欄位其實沒有多難，題目要求找出除了已經被封鎖的客戶以外的取消率。

問題

The Trips table holds all taxi trips. Each trip has a unique Id, while Client_Id and Driver_Id are both foreign keys to the Users_Id at the Users table. Status is an ENUM type of (‘completed’, ‘cancelled_by_driver’, ‘cancelled_by_client’).

+----+-----------+-----------+---------+--------------------+----------+
| Id | Client_Id | Driver_Id | City_Id |        Status      |Request_at|
+----+-----------+-----------+---------+--------------------+----------+
| 1  |     1     |    10     |    1    |     completed      |2013-10-01|
| 2  |     2     |    11     |    1    | cancelled_by_driver|2013-10-01|
| 3  |     3     |    12     |    6    |     completed      |2013-10-01|
| 4  |     4     |    13     |    6    | cancelled_by_client|2013-10-01|
| 5  |     1     |    10     |    1    |     completed      |2013-10-02|
| 6  |     2     |    11     |    6    |     completed      |2013-10-02|
| 7  |     3     |    12     |    6    |     completed      |2013-10-02|
| 8  |     2     |    12     |    12   |     completed      |2013-10-03|
| 9  |     3     |    10     |    12   |     completed      |2013-10-03| 
| 10 |     4     |    13     |    12   | cancelled_by_driver|2013-10-03|
+----+-----------+-----------+---------+--------------------+----------+

The Users table holds all users. Each user has an unique Users_Id, and Role is an ENUM type of (‘client’, ‘driver’, ‘partner’).

+----------+--------+--------+
| Users_Id | Banned |  Role  |
+----------+--------+--------+
|    1     |   No   | client |
|    2     |   Yes  | client |
|    3     |   No   | client |
|    4     |   No   | client |
|    10    |   No   | driver |
|    11    |   No   | driver |
|    12    |   No   | driver |
|    13    |   No   | driver |
+----------+--------+--------+

Write a SQL query to find the cancellation rate of requests made by unbanned clients between Oct 1, 2013 and Oct 3, 2013. For the above tables, your SQL query should return the following rows with the cancellation rate being rounded to two decimal places.

+------------+-------------------+
|     Day    | Cancellation Rate |
+------------+-------------------+
| 2013-10-01 |       0.33        |
| 2013-10-02 |       0.00        |
| 2013-10-03 |       0.50        |
+------------+-------------------+

答案

# Write your MySQL query statement below
SELECT  a.Request_at AS Day,
        ROUND(SUM(IF(a.Status = 'completed',0 ,1)) / COUNT(1), 2) AS 'Cancellation Rate'
FROM Trips AS a
JOIN Users AS b
ON a.Client_Id = b.Users_Id
WHERE b.Banned = 'No' 
AND b.Role = 'client'
AND (a.Request_at BETWEEN '2013-10-01' AND '2013-10-03')
GROUP BY a.Request_at

 

       

[MySQL][LeetCode][Medium] 177. Nth Highest Salary

心得

這題非常有趣，題目要求寫一預存程式輸入N並取出排名第N名的薪水為多少，這題與178. Rank Scores差不多，所以可以直接套用。

題目

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

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

For example, given the above Employee table, the nth highest salary where n = 2 is 200. If there is no nth highest salary, then the query should return null.

答案

  1. 這題我是拿178. Rank Scores的解法直接套上去取N 
    CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  RETURN (
      # Write your MySQL query statement below.
      SELECT a.Salary
      FROM (SELECT (@row_number:=@row_number + 1) AS Rank, z.Salary
            FROM (  SELECT x.* 
                    FROM Employee AS x 
                    GROUP BY x.Salary
                    ORDER BY x.Salary DESC) AS z
            JOIN (SELECT @row_number := 0) AS y) AS a
      WHERE a.Rank = N
  );
END

     

  2. 這解法是由高至低排序了所有的薪水，再用LIMIT來獲取Nth(因為LIMIT是從0開始所以N必須先減一)，非常易懂的解法。 
    CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    DECLARE M INT;
    SET M = N - 1;
    RETURN (
        # Write your MySQL query statement below.
        SELECT Salary
        FROM Employee
        GROUP BY Salary
        ORDER BY Salary DESC
        LIMIT M, 1
  );
END

     

參考：

  1. [MySQL][LeetCode][Medium] 178. Rank Scores