LeetCode做题笔记

1. Add two numbers：给定一个数集合和一个数，已知集合中有两个数的和是给定数，求这两个加数的index

方法1：暴力，n^2时间复杂度，不推荐

方法2：快速排序nlogn。按集合里数的两倍与target的大小关系对分。对每一个第一部分的数，在另外一个部分二分搜索第二个数：500~ms

方法3：hash，n的时间复杂度，最高纪录420ms

方法3源码：

    public int[] twoSum(int[] numbers, int target) {
//index Map
        Map<Integer, Short> indexMap = new HashMap<>();
        int x;
//hash value and indices
for (short i = 0; i < numbers.length; i++){
    x = numbers[i];
if (indexMap.get(x) == null)
indexMap.put(x, i);
else {
if (target == x * 2){
return new int[] {indexMap.get(x) + 1, i + 1};
}
}
}
for (short i = 0; i < numbers.length; i++){
    x = numbers[i];
if (target != x * 2 && indexMap.get(target - x) != null){
int int1 = indexMap.get(x) + 1;
int int2 = indexMap.get(target - x) + 1;
if (int1 > int2)
return new int[] {int2, int1};
else {
return new int[] {int1, int2};
}
}
}
return null;
    }

经验1：对hashMap的get和put都是非常耗时间的，尽量少做

经验2：方法2最好使用随机化快排，效率很高

1. 把两个链表表示的数加起来：最佳624ms，3%

用长一点的链表做基础，最多只需要new一个新节点

优化建议：进位尽量用数字。如果一个链到头了，另一个没到，应该沿着长链前进。如果进位是0就可以即刻返回，不需要继续前进。

         源码：

public class Solution {
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           int sum, progress = 0;
           ListNode tmp1 = l1, tmp2 = l2;
           for (;;){
                sum = l1.val + l2.val +progress;
                progress = sum >= 10 ?1 : 0;
               
                l1.val = l2.val = sum>= 10 ? sum - 10 : sum;
                if (l1.next == null){
                    if (l2.next == null){
                              if (progress ==1)
                                            l2.next= new ListNode(1);
                              return tmp2;
                    }
                    else {
                                         l2 =l2.next;
                                }
                    for (; ;){
                              if (progress ==0)
                                       returntmp2;
                              ++l2.val;
                              progress =l2.val >= 10 ? 1 : 0;
                              l2.val = l2.val>= 10 ? 0 : l2.val;
                             
                               if(l2.next == null){
                                       if(progress == 1)
                                                l2.next= new ListNode(1);
                                       break;
                              }
                              else
                                       l2 =l2.next;
                    }
                    return tmp2;
                }
                if(l2.next == null){
                          l1 = l1.next;
                          for (; ;){
                                   if(progress == 0)
                                            returntmp1;
                              ++l1.val;
                              progress =l1.val >= 10 ? 1 : 0;
                              l1.val = l1.val>= 10 ? 0 : l1.val;
 
                              if(l1.next == null){
                                       if(progress == 1)
                                                l1.next= new ListNode(1);
                                       break;
                              }
                              else
                                       l1 =l1.next;
                    }
                    return tmp1;
                }
                l1 = l1.next;
                l2 = l2.next;
                         
       }
    }
}

         经验2：leetcode不靠谱啊，速度不一定对

1. 把一个整数数位逆转，注意符号，不能溢出

最好记录404ms，前5%

public static int reverse(int x) {
        StringBuilder string = new StringBuilder(x + "");
        int flag = 1;
        if (string.charAt(0) == ‘-‘){
        flag = -1;
        string.reverse().deleteCharAt(string.length()-1);
       
        }
        else {
        string.reverse();
}
        try{
        return flag == 1 ? Integer.parseInt(string.toString()) : -1 *Integer.parseInt(string.toString());
        }
        catch (Exception e){
        return 0;
        }
    }

经验3：类库比较快。而且好像早上/翻墙以后机器运算比较快？

官方提示：

To check for overflow/underflow, we could checkif ret > 214748364 or ret < –214748364 before multiplying by 10. On theother hand, we do not need to check if ret == 214748364, why? 溢出是2147483647，214748364乘10不溢出

第一篇博文，leetcode3道题