There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

找到两个有序数组的中位数，LeetCode第二题，但是难度远大于第一题

正常思路会想到，将两个数组归并，返回中间数。归并操作耗时O(m+n),显然达不到题目要求。
那么就要深挖题目中的条件。数组有序，往往会联想到二分的思路，每次排除掉一半的结果集。在这道题中，可以利用“寻找第k小的数”的思路，这样本题转化为寻找第(m+n)/2小的数：

先来看下两个有序数组中，寻找第k小的数的做法:
不妨假设两个数组升序排列，且长度均大于k/2，则我们比较AB中第k/2个数的大小，有如下几种情况:

• A[k/2-1] < B[k/2-1]
• A[k/2-1] < B[k/2-1]
• A[k/2-1] < B[k/2-1]

当A[k/2-1] < B[k/2-1]时，在AB数组归并后，A[0]至A[k/2-1]之间的数必定都在B[k/2-1]的左边，也就是说我们可以排除掉这么长一段结果集，继续在剩下的元素组成的序列中寻找第(k - k/2)大小的数。
由于每次排除掉k/2，也就是(m+n)/4大小的结果集，所以此方式下，时间复杂度为O(log(m+n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public double findMedianSortedArrays(int A[], int B[]) {
    int sum = A.length + B.length;
    if (sum % 2 != 0) {
        return findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2 + 1);
    } else {
        return (findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2)
                + findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2 + 1)
        ) / 2.0;
    }
}

private int findKth(int A[], int startA, int endA,
                    int B[], int startB, int endB,
                    int k) {
    int m = endA - startA + 1;
    int n = endB - startB + 1;
    if (m > n) return findKth(B, startB, endB, A, startA, endA, k); //只考虑a <= b的情况
    if (m < 1) return B[startB + k - 1];
    if (k == 1) return Math.min(A[startA], B[startB]);

    int midA = Math.min(k / 2, m), midB = k - midA;
    //如果a的第midA大的元素比b的第midB大的元素小，
    //那么删掉a的前midA个元素，在剩余的数中找第k-midA大的。
    if (A[startA + midA - 1] < B[startB + midB - 1])
        return findKth(A, startA + midA, endA, B, startB, endB, k - midA);
    else if (A[startA + midA - 1] > B[startB + midB - 1])
        return findKth(A, startA, endA, B, startB + midB, endB, k - midB);
    else
        return A[startA + midA - 1];
}

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

很基础的链表操作题目，一次循环依次对节点进行加法运算即可，要注意进位与边界条件，时间复杂度O(n)

为了可理解性，在我的实现中把加法与进位运算拆开分别处理了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }

    ListNode p = new ListNode(l1.val + l2.val);
    ListNode head = p;
    while (l1.next != null && l2.next != null) { // 加法操作
        l1 = l1.next;
        l2 = l2.next;
        p.next = new ListNode(l1.val + l2.val);
        p = p.next;
    }
    l1 = l1.next;
    l2 = l2.next;
    p.next = l1 == null ? l2 : l1;

    p = head;
    while (p != null) { // 处理进位
        if (p.val > 9) {
            if (p.next == null) {
                p.next = new ListNode(p.val / 10);
            } else {
                p.next.val += p.val / 10;
            }
            p.val %= 10;
        }
        p = p.next;
    }
    return head;
}

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

直观做法是使用二重for循环，外循环遍历集合所有元素，内循环从当次被遍历元素的下一个，遍历至结尾，判断两个数sum后是否为target，耗时O(n²), 这样会超时。

可以考虑使用HashMap/HashTable，使用一重for循环，以numbers[i]为key，i作为value存入，这样只需遍历Map判断key=target-numbers[i]是否存在即可

两次for循环，一次插入，一次遍历判断，时间空间复杂度均为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> m = new HashMap<Integer, Integer>();// num => index

    Integer[] result = new Integer[2];
    for (int i = 0; i < numbers.length; i++) {
        if (target % 2 == 0 && numbers[i] == target / 2) {
            if (result[0] == null) {
                result[0] = i + 1;
            } else {
                result[1] = i + 1;
                return new int[]{result[0], result[1]};
            }
            continue;
        }
        m.put(numbers[i], i);
    }

    for (int num : m.keySet()) {
        if (m.containsKey(target - num)) {
            int a = m.get(num) + 1;
            int b = m.get(target - num) + 1;
            return a > b ? new int[]{b, a} : new int[]{a, b};
        }
    }
    return null;
}

在此基础上还可以进一步简化,让插入与判断可在一轮for循环内全部完成。原因如下：

题目说结果一定存在且唯一，不妨假设结果为a和b,a在前。虽然在遍历到a的时候b还不存在，但是遍历到后面的b时，a已经存在了，必然会达成判断条件map.contains(target-b)为true。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int[] twoSum(int[] numbers, int target) {
    int[] a = new int[2];
    Map<Integer, Integer> nums = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        //put number into hash table (if it's not already there)
        Integer n = nums.get(numbers[i]);
        if (n == null) nums.put(numbers[i], i); //subtract array element from target number
        n = nums.get(target - numbers[i]);
        if (n != null && n < i) {//if such number exists in the table return the indicies
            a[0] = n + 1;
            a[1] = i + 1;
            return a;
        }
    }
    return a;
}

Swallows may have gone, but there is a time of return; willow trees may have died back, but there is a time of regreening; peach blossoms may have fallen, but they will bloom again. Now, you the wise, tell me, why should our days leave us, never to return? - If they had been stolen by someone, who could it be? Where could he hide them? If they had made the escape themselves, then where could they stay at the moment?

I don’t know how many days I have been given to spend, but I do feel my hands are getting empty. Taking stock silently, I find that more than eight thousand days have already slid away from me. Like a drop of water from the point of a needle disappearing into the ocean, my days are dripping into the stream of time, soundless, traceless. Already sweat is starting on my forehead, and tears welling up in my eyes.

Those that have gone have gone for good, those to come keep coming; yet in between, how swift is the shift, in such a rush? When I get up in the morning, the slanting sun marks its presence in my small room in two or three oblongs. The sun has feet, look, he is treading on, lightly and furtively; and I am caught, blankly, in his revolution. Thus–the day flows away through the sink when I wash my hands, wears off in the bowl when I eat my meal, and passes away before my day-dreaming gaze as reflect in silence. I can feel his haste now, so I reach out my hands to hold him back, but he keeps flowing past my withholding hands. In the evening, as I lie in bed, he strides over my body, glides past my feet, in his agile way. The moment I open my eyes and meet the sun again, one whole day has gone. I bury my face in my hands and heave a sigh. But the new day begins to past in the sigh.

What can I do, in this bustling world, with my days flying in their escape? Nothing but to hesitate, to rush. What have I been doing in that eight-thousand-day rush, apart from hesitating? Those bygone days have been dispersed as smoke by a light wind, or evaporated as mist by the morning sun. What traces have I left behind me? Have I ever left behind any gossamer traces at all? I have come to the world, stark naked; am I to go back, in a blink, in the same stark nakedness? It is not fair though: why should I have made such a trip for nothing!

You the wise, tell me, why should our days leave us, never to return？

我们常听到这一类名词：强类型/弱类型，静态类型/动态类型，其实它们都属于语言的类型模型这个范畴。通常来说，这些术语没有一个明确固定的结论，下面以我自身的理解一一介绍下：

强类型和弱类型

　 通常我们所说的强类型/弱类型，指强类型定义语言和弱类型定义语言

1 强类型定义语言：强制数据类型定义的语言。也就是说，一个变量被赋值后，这个变量的类型就固定了，不能转换成另一个类型(通常只允许以不丢失信息为前提的自动类型转换)。如Java/Python/Ruby

举例：如果你定义了一个整型变量a,那么程序根本不可能将a当作字符串类型处理。强类型定义语言是类型安全的语言。

2 弱类型定义语言：数据类型可以被忽略的语言。它与强类型定义语言相反，一个变量可以赋不同数据类型的值。如js/vbs

举例：js中’’ [] 会被隐式转换成 0 0，结果是 0；js中字符串’123’和整数456是可以比较大小的

注意: 有一类流传的错误的说法是： “强类型语言是指需要进行变量/对象类型声明的语言，一般情况下需要编译执行”／“弱类型语言是指不需要进行变量/对象类型声明的语言，一般情况下不需要编译”

其实，是否需要对变量进行类型声明跟语言的强弱类型无关。上面的错误说法实际上指向了另一个概念：变量是显示声明还是隐式暗示，注意不要混淆。

这里也举个例子: c/Java中，要求对变量进行显示的声明，编写者必须以指定类型明确地关系到每一个变量上。也有些语言如Scala/Haskell支持类型推断，通过编译器帮你猜测变量的类型，从而省略了你在代码中写类型的麻烦。（不知”类型推断”这个特性算不算语法糖） 而python/ruby这类动态语言，往往使用隐式暗示的方式，给变量赋值3.14这个变量就是浮点类型，给变量赋值[1,2,3]就是数组类型。 个人觉得这个概念不必细究，大致了解即可。

小结：

1. 强类型语言，由于类型检查的区别，变量会在编译期确定，或运行中动态确定。但是一旦确定便不可更改，除非使用强制转换。

2. 即使在强类型语言中，也有所谓的“隐式类型转换”（自动类型转换）机制让用户在书写语法上自由一些。比如在Java中，将整数123赋值给一个double变量，并不会导致语法错误，而是会引发隐式类型转换。但即使是隐式类型转换，也如定义中括号内部分所述，通常只允许以不丢失信息为前提的自动类型转换。Java中的转换规则是，存储范围小的类型到存储范围大的类型byte→short(char)→int→long→float→double，本质上，只是将赋的值的类型在规则允许前提下向变量所具有/所定义的类型靠拢，而不会改变变量的类型。“隐式类型转换”这个操作由JVM在编译期自动完成。

动态语言和静态语言

　 通常我们所说的动态语言、静态语言是指动态类型语言和静态类型语言。

1 动态类型语言：动态类型语言是指在运行期间才去做数据类型检查的语言。动态类型语言在编码期间，永远也不用给任何变量指定数据类型，该语言会在你第一次赋值给变量时，在内部将数据类型记录下来。Python/Ruby就是一种典型的动态类型语言。

2 静态类型语言：与动态类型语言相反，它的数据类型是在编译期确定的。大多数静态类型语言要求编码时显示声明所有变量的数据类型，如前文所述的一些高级语言可以不在编码期声明，编译器会进行类型推断。Java/C++是静态类型语言的典型代表。

对于动态语言与静态语言的区分，套用一句流行的话就是：Static typing where possible, dynamic typing when needed。

总结:

1. 综上可知，python/ruby是强类型的动态语言, Java/C++是强类型的静态语言,JS是弱类型的动态语言

2. “静态语言/动态语言”与“强/弱类型”之间是没有必然联系的

3. 强类型语言的类型系统在设计上存在更强的约束，这降低了编程的灵活性。但是强类型定义语言带来的严谨性能够有效的避免许多错误。

4. 静态类型语言因为在编译期进行类型检查，可以较早发现错误，而且还可增进运行时期的性能。

5. 静态语言多为编译型语言，而动态语言都是解释型语言，不管它们是不是面向对象。

一句话总结：弱/强类型指的是语言类型系统的类型检查的严格程度。后两者指的是变量与类型的绑定方式。 其实这些概念都是语言的类型系统在设计上的取舍。就类型来说，静态语言因为编译期的存在，在编译期间（甚至智能IDE在编码期）通过语义分析可以处理类型检查，捕获一系列错误，加快运行期的速度。而动态语言类型检查的开销往往会落在运行期，因为动态语言的灵活性(python/ruby可以在运行时把类改的面目全非，甚至绕过类型检查，静态语言惯用的语义分析在动态语言中基本无从发挥)。