[TOC]

1s 内能解决问题的数据规模：10^6 ~ 10^7

• O(n^2) 算法可以处理 10^4 级别的数据规模(保守估计，处理 1000 级别的问题肯定没问题)
• O(n) 算法可以处理 10^8 级别的数据规模(保守估计，处理 10^7 级别的问题肯定没问题)
• O(nlog n) 算法可以处理 10^7 级别的数据规模(保守估计，处理 10^6 级别的问题肯定没问题)

一些具有迷惑性的例子：

void hello (int n){
    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello" << endl;
}

上面这段代码的时间复杂度是 O(nlog n) 而不是 O(n^2)

bool isPrime (int n){
    for( int x = 2 ; x * x <= n ; x ++ )
        if( n % x == 0 )
            return false;
    return true;
}

上面这段代码的时间复杂度是 O(sqrt(n)) 而不是 O(n)。

再举一个例子，有一个字符串数组，将数组中的每一个字符串按照字母序排序，之后再将整个字符串数组按照字典序排序。两步操作的整体时间复杂度是多少呢？

如果回答是 O(n*nlog n + nlog n) = O(n^2log n)，这个答案是错误的。字符串的长度和数组的长度是没有关系的，所以这两个变量应该单独计算。假设最长的字符串长度为 s，数组中有 n 个字符串。对每个字符串排序的时间复杂度是 O(slog s)，将数组中每个字符串都按照字母序排序的时间复杂度是 O(n * slog s)。

将整个字符串数组按照字典序排序的时间复杂度是 O(s * nlog n)。排序算法中的 O(nlog n) 是比较的次数，由于比较的是整型数字，所以每次比较是 O(1)。但是字符串按照字典序比较，时间复杂度是 O(s)。所以字符串数组按照字典序排序的时间复杂度是 O(s * nlog n)。所以整体复杂度是 O(n * slog s) + O(s * nlog n) = O(nslog s + snlogn) = O(ns(log s + log n)) = O(nslog(n*s)）。

递归调用是有空间代价的，递归算法需要保存递归栈信息，所以花费的空间复杂度会比非递归算法要高。

int sum( int n ){
    assert( n >= 0 )
    int ret = 0;
    for ( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

上面算法的时间复杂度为 O(n)，空间复杂度 O(1)。

int sum( int n ){
    assert( n >= 0 )
    if ( n == 0 )
        return 0;
    return n + sum( n - 1 );
}

上面算法的时间复杂度为 O(n)，空间复杂度 O(n)。

如果递归函数中，只进行了一次递归调用，且递归深度为 depth，在每个递归函数中，时间复杂度为 T，那么总体的时间复杂度为 O(T * depth)

举个例子：

int binarySearch(int arr[], int l, int r, int target){
	if( l > r )
	    return -1;
    int mid = l + ( r - l ) / 2; // 防溢出
    if(arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearch(arr,l,mid-1,target);
    else
        return binarySearch(arr,mid+1,r,target);
}

在二分查找的递归实现中，只递归调用了自身。递归深度是 log n ，每次递归里面的复杂度是 O(1) 的，所以二分查找的递归实现的时间复杂度为 O(log n) 的。

针对多次递归调用的情况，就需要看它的计算调用的次数了。通常可以画一颗递归树来看。举例：

int f(int n){
    assert( n >= 0 );
    if( n == 0 )
        return 1;
    return f( n - 1 ) + f ( n - 1 );
}

上述这次递归调用的次数为 2^0^ + 2^1^ + 2^2^ + …… + 2^n^ = 2^n+1^ - 1 = O(2^n)

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

思路：

这个问题的解决方案实际上就是模拟了我们手动相加两个数的过程。首先，我们创建一个空链表来存储每一位的相加结果。在每一步中，我们将对应的节点值相加，并加上可能存在的进位（carry）。然后，我们将相加的结果对10取余数，这个余数就是新的节点的值。最后，我们通过将相加的结果除以10，得到的商就是下一步的进位。如果最后还有进位，我们会在链表的末尾添加一个新的节点

答案：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    current , n1 ,n2 , carray := head, 0,0,0
    for l1 != nil || l2 != nil || carray != nil{
        if l1 == nil{
            n1 = 0
        }else{
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 == nil{
            n2 = 0
        }else{
            n2 = l2.Val
            l2 = l2.Next
        }
        current.Next = &ListNode{Val:(n1 + n2 +carray)%10}
        carray := (n1 + n2 +carray) /10
    }
    return current.Next
}

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

解法一：

创建空的结果链表，然后每次比较l1 和l2 中的节点val大小，将结果指针节点指向结果较小的节点，当某个list为空的时候，将结果指针指向其余的节点

func mergeTwoList(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	current := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			current.Next = l1
			l1 = l1.Next
		} else {
			current.Next = l2
			l2 = l2.Next
		}
		current = current.Next
	}
	if l1 == nil {
		current.Next = l2
	} else {
		current.Next = l1
	}
	return head.Next
}

解法二： 使用递归

func mergeTwoList(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	} else if l1.Val < l2.Val {
		l1.Next = mergeTwoList(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoList(l1, l2.Next)
		return l2
	}
}

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

解法：

使用递归进行中序排序

func inorderTraversal(root *TreeNode) []int {
	var result []int
	inorder(root, &result)
	return result
}

func inorder(root *TreeNode, output *[]int) {
	if root != nil {
		inorder(root.Left, output)
		*output = append(*output, root.Val)
		inorder(root.Right, output)
	}
}