比如，中国人在餐厅或咖啡厅，会说：“我想要一个汉堡包”或者“我想要一杯咖啡”。但是，如果直接把这些话翻译成英语“I want to have a hamburger.”或“I want to have a coffee.”老外们会觉得这样说话很没有礼貌，当然他们也不会直接告诉你。而在西方国家，老外们一般会说：“Could I have a hamburger, please?”或“Can I have a coffee, please?”在这里joy同学又提到一个需要注意的问题，“打工的孩子最容易不注意的是see you. See u应该是客人说的，隐含了他觉得不错他会再来的意思，而店员最好用低调一点的bye，用see u太强势了。另外人家说谢谢，你也不用说you are welcome, 这实在是太正式了，有点真把自己当回事觉得帮了人家的味道。回答 cheers 或 no worries 就好，如果仅仅是对方爱说谢，你甚至可以不回应他的谢，直接说你要说的就好，如果是买了他的东西他谢你，更不能说you r welcome了
再比如，中国人在拒绝别人邀请的午宴或晚宴时，会说：“抱歉，我不能去，我还有别的安排。”翻译成英文就是“Sorry，I can’t. I have another appointment.”如果这样说，那别人第二次也许不会再邀请你了。老外们一般会这样说：“**That is a good idea! I would like to join in but I have another appointment today.**”
先是了解了下 Cache replacement policies，其中提及 General implementations of Least recently used (LRU) require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits.
题目里提示 Could you do both operations in O(1) time complexity? ，又了解了下Time complexity。又在kindle上翻了下《算法图解》，了解了下散列表、链表等数据结构，也算加强了下对哈希表的认识。
Typically LRU cache is implemented using a doubly linked list and a hash map.
An LRU Cache should support fast lookup. Apparently, in order to achieve fast lookup, we need to use Hashtable or HashMap.Also, an LRU Cache requires that insert and delete operations should be in O(1) time. The obvious choice for this requirement is Linked List. Linked List support insert/delete operations in O(1) time if we have the reference of element. While building an LRU cache requires that you think in terms of these two data structures. The reality is that these two data structures actually work coherently to achieve the design.So, we are finalizing on these data structures: HashMap and Doubly Linked List. HashMap holds the keys and values as reference of the nodes (entries) of Doubly Linked List.Doubly Linked List is used to store list of nodes (entries) with most recently used node at the head of the list. So, as more nodes are added to the list, least recently used nodes are moved to the end of the list with node at tail being the least recently used in the list.
Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
classSolution { publicintreverse(int x) { intr=0; if (x>Integer.MAX_VALUE || x<Integer.MIN_VALUE) { return r; } Strings= Integer.toString(x); if (s!=null && !s.isEmpty()) { Stringss=""; charc=0; if (x<0) s = s.substring(1); for(int i=s.length()-1;i>=0;i--) { c = s.charAt(i); ss += c; } if (x<0) ss = '-'+ss; System.out.println("ss="+ss); try { r = Integer.parseInt(ss); } catch (NumberFormatException ex) { r = 0; } } return r; } }
Submission Detail
1032 / 1032 test cases passed.
2
做 9. Palindrome Number ，提示Coud you solve it without converting the integer to a string? 发现人家的方法更直接利落，温故而知新，重新实现下，结果被卡在 java int out of range 的问题里，1534236469 逆序数超过Integer.MAX_VALUE 返回 1056389759，题目里就提示了 Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. 最后想到不如把逆序数变量定义为 long类型，再判断是否超过2147483647(0x7fffffff, 2^31-1)，再把long 安全地转换为int返回，java的long安全转换为int的小问题，google关键字 java long to int 参考了下 Safely casting long to int in Java 这样就ok了，在leetcode上运行通过。
一个多月前就看了下，这题label为Easy，跟 7. Reverse Integer 有关系，自己做7. Reverse Intege时就简单把整数转为字符串来解决，而这题提示Coud you solve it without converting the integer to a string，自己对c语言为例的过程化编程还是欠差，google 关键字 Palindrome Number，出来
又 google 关键字 longest unique substring in a string，搜到 How To Find Longest Substring Without Repeating Characters In Java?，这个终于看懂了，用到了个LinkedHashMap数据结构来存储无重复字符的substring，从左往右扫描字符数组，一旦字符与HashMap里的字符有重复，就把循环变量i置为那个重复字符在原字符串中的位置，HashMap清空，如果字符不重复，就继续往右扫，如果HashMap的size大于最大无重复子串长度，就更新最大无重复子串长度这个int变量，直到字符串末尾为止。会者不难，难者不会，其实也就这么简单。思路是人家的，自己不过照着人家的解决方案写的，最后写下来代码倒也没几行，LeetCode运行通过了。基本理解了，但要达到了然于胸的程度，还得继续慢慢消化理解。
高超的“破题”范本。以第五课《青年》（Youth）为例，作者在讨论代沟问题、为年轻人辩护时，开篇就指明了问题的根本所在：Let’s get down to fundamentals and agree that the young are after all human beings—-people just like their elders。作者接着指明两者之间的唯一差别就是：年轻人前程似锦，而老年人一切辉煌都已成过眼云烟。这样，下文的论证就有了坚实的基础。我们在写作时，可以参考这种方法，在开篇把问题的根本所在讲明白，这样下文就有话可说，而且容易让人信服。
第19课《话说梦的本质》（The stuff of dreams）、十四课《蝴蝶效应》（The Butterfly Effect） ：“以退为进”法 这种技巧适用于驳论。
第31课中的“先抑后扬”法
第28课的“例证——极度例证”法
第5课《青年》（Youth）的修辞：两个future第一个future前用了glorious来修饰，在第二个future前则用splendid。再看下一句话：He may be conceited, ill-mannered, presumptuous, or fatuous, ……。这句话中，作者一连串用的四个形容词恰倒好处，令人叫绝。
第24课中可以学到典型的排比句用法
第31课中作者则巧妙地使用了倒装句式
第23课中的长句很多
第11课《如何安度晚年》（How to grow old）是修辞格使用的经典范例。作者在文中把人生比作河流(An individual human existence should be like a river), small at first指的是人的儿童期，rushing passionately指的是人的青年期，boulders 和waterfalls则喻指人生中的坎坷，而become merged in the sea则是指死亡。某种程度上来说，正是这绝妙的比喻使这段话成为英语散文中的经典语段。
我自己就是语感党，以前考试从来都靠语感，从来不会去记忆具体的语法规则。至于效果… 我高二托福考了673（当时满分677），上海高考 146/150，还拿了个英语比赛的一等奖，高考可以加20分的那种。高中毕业后直接来美国读本科（参加高考是为了防止签证签不出），读硕士，工作，除了本科时候 Liberal Arts 的恐怖阅读量有点累，其他时候英语上从来没有什么障碍。
classSolution { publicint[] twoSum(int[] nums, int target) { inta=0, b = 0; Map<Integer, Integer> map = newHashMap<Integer, Integer>(); for (inti=0; i < nums.length; i++) { intcomplement= target - nums[i]; if (map.containsKey(complement)) { a = i; b = map.get(complement); } else { map.put(nums[i], i); } } returnnewint[]{a, b}; } }
Submission Detail
29 / 29 test cases passed.
Runtime: 2 ms, faster than 72.04% of Java online submissions for Two Sum.
Memory Usage: 39.2 MB, less than 98.23% of Java online submissions for Two Sum.
Database
175. Combine Two Tables
mysql
1 2 3
select p.FirstName FirstName,p.LastName LastName,a.City City, a.State State from Person p leftouterjoin Address a on p.PersonId=a.PersonId
Submission Detail
7 / 7 test cases passed.
Your runtime beats 84.70 % of mysql submissions.
Transact-SQL
1 2 3
SELECT P.firstName AS'firstName', P.lastName AS'lastName', A.city AS'city', A.state AS'state' FROM Person AS P LEFTOUTERJOIN Address AS A ON A.personId = P.personId
Submission Detail
8 / 8 test cases passed.
Your runtime beats 44.40 % of mssql submissions.
176. Second Highest Salary
mysql
1
1 2
select IF(count(distinct Salary)>1,min(t.Salary),null) SecondHighestSalary from (select Salary from Employee orderby Salary desc limit 2) t
Submission Detail
7 / 7 test cases passed.
Your runtime beats 90.90 % of mysql submissions.
2
1 2 3 4
select ( selectdistinct Salary from Employee orderby Salary desc limit 1,1 ) AS SecondHighestSalary
Submission Detail
7 / 7 test cases passed.
Your runtime beats 88.73 % of mysql submissions.
Transact-SQL
1 2 3 4 5 6 7 8 9 10 11 12 13
SELECT CASE WHENCOUNT(V.salary) >1THENMIN(V.salary) ELSENULL ENDAS'SecondHighestSalary'FROM ( SELECT TOP 2 SA.salary FROM ( SELECTDISTINCT EM.salary FROM Employee AS EM ) AS SA ORDERBY SA.salary DESC ) AS V
Submission Detail
8 / 8 test cases passed.
Runtime: 603 ms, faster than 85.83% of MS SQL Server online submissions for Second Highest Salary.
Memory Usage: 0B, less than 100.00% of MS SQL Server online submissions for Second Highest Salary.
177. Nth Highest Salary
1 2 3 4 5 6
CREATEFUNCTION getNthHighestSalary(N INT) RETURNSINT BEGIN DECLARE fromRow INT; SET fromRow = N-1; RETURN (select (selectdistinct Salary from Employee orderby Salary desc limit 1offset fromRow)); END
Submission Detail
14 / 14 test cases passed.
Your runtime beats 86.66 % of mysql submissions.
178. Rank Scores
1 2 3 4 5 6 7 8 9
select a.Score,b.`Rank` from Scores a, ( select t.Score,(@row_number:=@row_number+1) as `Rank` from ( selectdistinct Score from Scores orderby Score desc ) t,(SELECT@row_number:=0) t2 ) b where a.Score=b.Score orderby a.Score desc
Submission Detail
10 / 10 test cases passed.
Your runtime beats 98.24 % of mysql submissions.
181. Employees Earning More Than Their Managers
1
select t.Name as Employee from Employee t where t.Salary>(select e.Salary from Employee e where e.Id=t.ManagerId)
Submission Detail
14 / 14 test cases passed.
Your runtime beats 39.24 % of mysql submissions.
182. Duplicate Emails
1 2
select t.Email as Email from (select Email,count(Email) from Person groupby Email havingcount(Email)>1) t
Submission Detail
15 / 15 test cases passed.
Your runtime beats 76.83 % of mysql submissions.
183. Customers Who Never Order
1
1 2
select c.Name as Customers from Customers c where c.Id notin (selectdistinct o.CustomerId from Orders o)
Submission Detail
12 / 12 test cases passed.
Your runtime beats 84.65 % of mysql submissions.
2
1 2 3
select c.Name as Customers from Customers c leftouterjoin Orders o on c.Id=o.CustomerId where o.Id isnull
delete p from Person as p, Person as t where p.Id>t.Id and p.Email=t.Email;
Submission Detail
22 / 22 test cases passed.
Your runtime beats 18.50 % of mysql submissions.
2
1
delete p from Person as p, Person as t where p.Email=t.Email and p.Id>t.Id;
Submission Detail
22 / 22 test cases passed.
Your runtime beats 83.82 % of mysql submissions.
3
1
delete p from Person as p innerjoin Person as t where p.Email=t.Email and p.Id>t.Id;
Submission Detail
22 / 22 test cases passed.
Your runtime beats 80.14 % of mysql submissions.
180. Consecutive Numbers
被卡了好几天，百思不得其解，又开始怀疑是不是select还不足以，难道要用到游标与临时表之类，再琢磨下去也是浪费时间，遇到什么问题，就去问google，尤其是这种自己不会别人会的技术问题，搜 mysql consecutive queries 定位到 MySQL query for 3 consecutive integers between records，冥思苦想就是想不对路，一看到人家的解就恍然大悟，自己怎么会想不到这一点，看来自己的sql还是需要外部启发，没有点拨，自己就迷失在思维定势里了。
不过这题有点让人犯糊涂，如果id不连续呢？那是不是还得用计算列row_num?反正题意是id连续
1 2 3
selectdistinct t.Num as ConsecutiveNums from Logs t whereexists (select1from Logs x where x.Id-1=t.Id and x.Num=t.Num) and exists(select1from Logs x where x.Id+1=t.Id and x.Num=t.Num);
select d.Name as Department,e.Name as Employee,b.Salary as Salary from ( select a.DepartmentId,a.Salary from ( select t.DepartmentId,t.Salary,(@num:=if(@deptId= t.DepartmentId, @num+1, if(@deptId := t.DepartmentId, 1, 1))) as row_number from ( selectdistinct DepartmentId,Salary from Employee ) t CROSSJOIN (select@num:=0, @deptId:=null) c orderby t.DepartmentId,t.Salary desc ) a where a.row_number<=3 ) b leftouterjoin Employee e using(DepartmentId,Salary) innerjoin Department d on e.DepartmentId=d.Id orderby b.DepartmentId,b.Salary desc;
select d.Name as Department,e.Name as Employee,t.Salary from Department d leftouterjoin (select DepartmentId,Max(Salary) as Salary from Employee groupby DepartmentId) t on t.DepartmentId=d.Id innerjoin Employee e on t.Salary=e.Salary and t.DepartmentId=e.DepartmentId orderby t.Salary desc;
Submission Detail
15 / 15 test cases passed.
Your runtime beats 77.87 % of mysql submissions.
2
1 2 3 4
select d.Name as Department,e.Name as Employee,t.Salary from Department d leftouterjoin (select DepartmentId,Max(Salary) as Salary from Employee groupby DepartmentId) t on d.Id=t.DepartmentId innerjoin Employee e on e.DepartmentId=t.DepartmentId and e.Salary=t.Salary orderby t.Salary desc;
Submission Detail
15 / 15 test cases passed.
Your runtime beats 87.87 % of mysql submissions.
3
1 2 3 4
select d.Name as Department,e.Name as Employee,t.Salary from Department d leftouterjoin (select DepartmentId,Max(Salary) as Salary from Employee groupby DepartmentId) t on d.Id=t.DepartmentId innerjoin Employee e using(DepartmentId,Salary) orderby t.Salary desc;
select b.Request_at asDay,round(IFNull(a.cancel_num,0)/b.total_num,2) as `Cancellation Rate` from ( select t.Request_at,count(*) as cancel_num from Trips t where t.Client_Id in (select Users_Id from Users where Role='client'and Banned='No') and t.Driver_Id in (select Users_Id from Users where Role='driver'and Banned='No') and t.Status in ('cancelled_by_driver','cancelled_by_client') and t.Request_at betweenDATE'2013-10-01'andDATE'2013-10-03' groupby t.Request_at ) a rightouterjoin ( select t.Request_at,count(*) as total_num from Trips t where t.Client_Id in (select Users_Id from Users where Role='client'and Banned='No') and t.Driver_Id in (select Users_Id from Users where Role='driver'and Banned='No') and t.Request_at betweenDATE'2013-10-01'andDATE'2013-10-03' groupby t.Request_at ) b on b.Request_at=a.Request_at;
Submission Detail
9 / 9 test cases passed.
Your runtime beats 82.92 % of mysql submissions.
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14
select a.Request_at asDay,round(IFNull(b.cancel_num,0)/a.total_num,2) as `Cancellation Rate` from ( select t.Request_at,count(*) as total_num from Trips t where t.Client_Id in (select Users_Id from Users where Role='client'and Banned='No') and t.Driver_Id in (select Users_Id from Users where Role='driver'and Banned='No') and t.Request_at betweenDATE'2013-10-01'andDATE'2013-10-03' groupby t.Request_at ) a leftouterjoin ( select t.Request_at,count(*) as cancel_num from Trips t where t.Client_Id in (select Users_Id from Users where Role='client'and Banned='No') and t.Driver_Id in (select Users_Id from Users where Role='driver'and Banned='No') and t.Status in ('cancelled_by_driver','cancelled_by_client') and t.Request_at betweenDATE'2013-10-01'andDATE'2013-10-03' groupby t.Request_at ) b on b.Request_at=a.Request_at;
Submission Detail
9 / 9 test cases passed.
Your runtime beats 61.34 % of mysql submissions.
595. Big Countries
这题确实Easy，or条件或用据说性能更好的 union (Set operations)
1
1
select name,population,area from World where area>3000000or population>25000000;
Submission Detail
4 / 4 test cases passed.
2
1 2 3
select name,population,area from World where area>3000000 union select name,population,area from World where population>25000000;
Submission Detail
4 / 4 test cases passed.
596. Classes More Than 5 Students
这题也Easy，group by + having子句
1 2 3 4
select t.`class` as `class` from ( select `class`,count(distinct student) as n from courses groupby `class` having n>=5 ) t;
Submission Detail
9 / 9 test cases passed.
601. Human Traffic of Stadium
这题又被卡了好几天，google也没搜到什么直接的线索，PL/SQL与T-SQL有分析函数ROW_NUMBER(), RANK(), and DENSE_RANK()，还以为需要mysql模拟这种功能。
卡在这一步里
select s.* from stadium s where s.people>=100
and exists(select 1 from stadium t2 where t2.people>=100 and t2.`date`=DATE_SUB(s.`date`,INTERVAL 1 DAY))
and exists(select 1 from stadium t3 where t3.people>=100 and t3.`date`=DATE_ADD(s.`date`,INTERVAL 1 DAY));
select x.*from ( select a.*from (select s.*from stadium s where s.people>=100) a, ( select s.*from stadium s where s.people>=100 andexists(select1from stadium t2 where t2.people>=100and t2.id=s.id-1) andexists(select1from stadium t3 where t3.people>=100and t3.id=s.id+1) ) b where a.id=b.id-1
union
select s.*from stadium s where s.people>=100 andexists(select1from stadium t2 where t2.people>=100and t2.id=s.id-1) andexists(select1from stadium t3 where t3.people>=100and t3.id=s.id+1)
union
select c.*from ( select s.*from stadium s where s.people>=100 andexists(select1from stadium t2 where t2.people>=100and t2.id=s.id-1) andexists(select1from stadium t3 where t3.people>=100and t3.id=s.id+1) ) b, (select s.*from stadium s where s.people>=100) c where c.id=b.id+1 ) x orderby x.id;
select*from ( select t1.id,t2.student from (select*from seat where id%2=1) t1 join (select*from seat where id%2=0) t2 on t1.id=t2.id-1
union
select IFNULL(t2.id,t1.id) as id,t1.student from (select*from seat where id%2=1) t1 leftouterjoin (select*from seat where id%2=0) t2 on t1.id=t2.id-1 ) t orderby id;
Submission Detail
12 / 12 test cases passed.
Your runtime beats 58.11 % of mysql submissions.
627. Swap Salary
算是Easy吧，不过还是看了下mysql的update语法，用IF()函数或者 case 都可以。
1
1
update salary set sex=IF(sex='m','f','m');
Submission Detail
8 / 8 test cases passed.
Your runtime beats 53.28 % of mysql submissions.
2
1
update salary set sex=case sex when'm'then'f'when'f'then'm'end;