|
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不为null
27 //2. l2.next不为null
28 //3. l1.next,l2.next都为null
29
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 SecondHighestSalary 2 FROM Employee 3 ORDER BY Salary DESC 4 LIMIT 1,1; 但是这样的话, 如果没有第二高的薪水, 返回的是空而不是null, 就这一部分我是想了半天, 最后还是看了答案, 确实是SQL练得太少 答案给了两种方式: 1 SELECT 2 (SELECT DISTINCT 3 Salary 4 FROM 5 Employee 6 ORDER BY Salary DESC 7 LIMIT 1 OFFSET 1) AS SecondHighestSalary 8 ; 或者 1 SELECT 2 IFNULL( 3 (SELECT DISTINCT Salary 4 FROM Employee 5 ORDER BY Salary DESC 6 LIMIT 1 OFFSET 1), 7 NULL) AS SecondHighestSalary 8 ; 看过之后也是恍然大悟, 其实并没有没有学过的内容, 还是练习太少缺乏技巧 再补充一个答案, 也很酷炫: 1 select max(Salary) as SecondHighestSalary 2 from Employee 3 where Salary!=(select max(Salary) 4 from Employee) 来源：http://www./content-4-25361.html |
|
|
