LeetCode-Algorithms #002 Add Two Numbers, Database #176 Second Highest Salary

LeetCode-Algorithms #002 Add Two Numbers

给定两个非空的以链表结构表示的非负整数, 这个结构长这样:

1 public class ListNode {2     int val;3     ListNode next;4     ListNode(int x) { val = x; }5 }

这个结构中从低位到高位由外向内存储, 每一层存储一位数, 题目要求把给定的两个数求和, 然后用同样的结构返回结果.

我的思路:

作为一个头脑淳朴(简单)的人, 我还是本能的想, 把这两个数取出来, 加一加, 然后存回去就好了, 事实也是这么做了

提交代码...

运行超时...

是的, 看来蠢人不配通过提交, 这种做法应该是慢得令人发指了.

那么, 只好换个想法, 既然这个结构是个位数存在最外面, 一层一层向里进位, 那么我们也就一层一层从外往里加就好了, 尝试一下:

 1 class Solution { 2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 3         //先创建一个ListNode作为答案 4         ListNode ans = new ListNode(0); 5         //再创建另一个引用指向同一个对象 6         ListNode temp = ans; 7         //当l1和l2内层都不为空的时候 8         while (l1.next != null && l2.next != null) { 9             //计算当前层的和:l1和l2该位的值加上上一位的进位10             int sum = l1.val   l2.val   temp.val;11             //因为l1和l2内层都不为空, 使l1和l2都等于其内层12             l1 = l1.next;13             l2 = l2.next;14             //对和取10的余数, 获得结果中这一位的值15             int val = sum % 10;16             //把和除以10, 获得进位的值17             int carry = sum / 10;18             //对temp赋值19             temp.val = val;20             //把进位的值添加到temp的内层21             temp.next = new ListNode(carry);22             //使temp的引用向内指一层23             temp = temp.next;24         }25         //上面的循环结束后, 只剩下三种可能, 26         //1. l1.next不为null27         //2. l2.next不为null28         //3. l1.next,l2.next都为null29         30         //在第一种情况下, l2.next虽然为null, 但l2.val还没有被加入最后的结果中31         while (l1.next != null) {32             //所以, 我们还是令三者相加33             int sum = l1.val   l2.val   temp.val;34             //但是在第一次加过之后就令l2.val = 0, 以免影响后面的循环35             l2.val = 0;36             //之后l2就不用管了, 令l1等于其内层37             l1 = l1.next;38             //后面的部分和第一个循环意思一样39             int val = sum % 10;40             int carry = sum / 10;41             temp.val = val;42             temp.next = new ListNode(carry);43             temp = temp.next;44         }45         46         //第二种情况下和上面一样47         while (l2.next != null) {48             int sum = l1.val   l2.val   temp.val;49             l1.val = 0;50             l2 = l2.next;51             int val = sum % 10;52             int carry = sum / 10;53             temp.val = val;54             temp.next = new ListNode(carry);55             temp = temp.next;56         }57         58         //到了这里l1.next和l2.next都为null, 但l1.val和l2.val至少还有一个没有加入最后的结果中,59         //也有可能两个都没有, 因此还要最后再做一次 60         int sum = l1.val   l2.val   temp.val;61         int val = sum % 10;62         int carry = sum / 10;63         temp.val = val;64         //最后这次要判断一下,只有要进位的值不为零的情况下才进位, 否则最后的结果可能会多一个0出来65         if(carry != 0) {66             temp.next = new ListNode(carry);67         }68         //返回结果69         return ans;70     }71 }

过程中其实碰到了不少预想之外的问题, 感觉写得也比较啰嗦, 但是总归是顺利实现了:

 

 测试一下大致是个平均水平, 和第一梯队差距倒是不算太过明显, 不过看一看强者的提交, 还是让人心碎:

 1 class Solution { 2    public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 3         int carry = 0; 4         ListNode p = l1; 5         ListNode q = l2; 6         ListNode end = l1; 7         while (p != null || q != null) { 8             int sum = carry; 9             if (p!= null && p.next == null) end = p;10             if (q != null) sum  = q.val;11             if (p != null) sum  = p.val;12             int remainder = sum % 10;13             carry = sum / 10;            14             if (p!= null) {15                 p.val = remainder;16             } else {17                 end.next = new ListNode(remainder);18                 end = end.next;                 19             }20             if (p != null) p = p.next;21             if (q != null) q = q.next;            22         }23         if (carry != 0) end.next = new ListNode(carry);24         return l1;25     }26 }

总体思路上有一些相通之处(所以也就没有额外加注释), 但是完成质量就是天差地别了😂

 

 

LeetCode-Database #176 Second Highest Salary

要求从Employee表格中获取第二高的薪水, 如果没有第二高的薪水则返回null

获得第二高的薪水本身很简单:

1 SELECT DISTINCT Salary As SecondHighestSalary2 FROM Employee3 ORDER BY Salary DESC4 LIMIT 1,1;

但是这样的话, 如果没有第二高的薪水, 返回的是空而不是null, 就这一部分我是想了半天, 最后还是看了答案, 确实是SQL练得太少

答案给了两种方式:

1 SELECT2     (SELECT DISTINCT3             Salary4         FROM5             Employee6         ORDER BY Salary DESC7         LIMIT 1 OFFSET 1) AS SecondHighestSalary8 ;

或者

1 SELECT2     IFNULL(3       (SELECT DISTINCT Salary4        FROM Employee5        ORDER BY Salary DESC6         LIMIT 1 OFFSET 1),7     NULL) AS SecondHighestSalary8 ;

看过之后也是恍然大悟, 其实并没有没有学过的内容, 还是练习太少缺乏技巧

再补充一个答案, 也很酷炫:

1 select max(Salary) as SecondHighestSalary2 from Employee3 where Salary!=(select max(Salary)4 from Employee) 

 

来源：http://www.icode9.com/content-4-25361.html