斐波那契数列及优化和计算字符串中最长非重复子串长度

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

青蛙每次只会跳1级或2级，则跳n级必定是所有的1级和2级之和
设f(0)=1
跳上1级只有1种跳法（0->1） => f(1)=1
跳上2级有2种跳法（0->1->2,0->2）=> f(2)=f(1)+f(0) => f(2)=2
跳上3级有3种跳法（0->1->2->3,0->1->3,0->2->3）=> f(3)=f(2)+f(1)
跳上4级有5种跳法（0->1->2->3->4,0->1->2->4,0->1->3->4,0->2->3->4,0->2->4）=> f(4)=f(3)+f(2)
...
跳上n级有:f(n)=f(n-1)+f(n-2)
结果是斐波那契数列

斐波那契数列及优化（不考虑大数）

• 常见递归实现

int fibon(int n) {
    if (n <= 2) {
        return 1;
    }
    return fibon(n-1) + fibon(n-2);
}

• 优化1

int fibonacci(int n) {
    if (n <= 1) {
        return 1;
    } else {
        //动态创建一个长度为(n+1)的数组
        int *arr = new int[n+1];
        arr[0]=1;
        arr[1]=1;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        int result = arr[n];
        
        delete [] arr;
        return result;
    }
}

• 优化2

int fibonaccii(int n) {
    if (n <= 1) {
        return 1;
    } else {
        //当n>=2时，初始化pre=f(0)=0,post=f(1)=1,f(n)=0;
        int pre = 0;
        int post = 1;
        int fn = 0;
        //采用循环计算斐波那契数列，通过两个临时变量pre和post保存中间结果，避免重复计算
        for (int i = 2; i <= n; i++) {
            //fn等于其前面两个元素值的和,然后让pre和post分别直线他们后面的元素。
            fn = pre + post;
            pre = post;
            post = fn;
        }
        return fn;
    }
}

• 优化3

是优化2的递归版本

int fibonac(int a, int b, int n) { // a、b都取1
    if (n > 2) {
        return fibonac(a+b, a, n-1);
    }
    return a;
}

拓展： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

设f(0)=1
跳上1级只有1种跳法（0->1） => f(1)=1
跳上2级有2种跳法（0->1->2,0->2）=> f(2)=f(1)+f(0) => f(2)=2*f(1)
跳上3级有4种跳法（0->1->2->3,0->1->3,0->2->3,0->3）=> f(3)=f(2)+f(1)+f(0) => f(3)=2*f(2)
跳上4级有8种跳法（0->1->2->3->4,0->1->2->4,0->1->3->4,0->1->4,0->2->3->4,0->2->4,0->3->4,0->4）=> f(4)=f(3)+f(2)+f(1)+f(0) => f(4)=2*f(3)
...
跳上n级有:f(n)=f(n-1)+f(n-2)+...+f(0) => f(n)=2*f(n-1)

解法：

// 递归方式
unsigned int f(unsigned int n) {
    if (n <= 1) {
        return n;
    }
    return 2 * f(n-1);
}

// 递推方式
unsigned int f1(unsigned int n) {
    if (n <= 1) {
        return n;
    }
    unsigned int res = 1;
    for (unsigned int i = 2; i <= n; ++i) {
        res = 2 * res;
    }
    return res;
}

计算字符串中最长非重复子串长度

给定一个字符串，找到最长子串的长度，而不重复字符。
例子:
给定“abcabcbb”，答案是“abc”，长度为3。
给定“bbbbb”，答案是“b”，长度为1。
给定“pwwkew”，答案是“wke”，长度为3.请注意，答案必须是子字符串，“pwke”是子序列而不是子字符串。

• 正常解法

#include <vector>

int longestSubStringLength(string s) {
    int index = 0, len = 0;
    unordered_map<char, int> map1;
    for (int i = 0; i < s.size(); ++i) {
        auto res = map1.find(s[i]);
        if (res != map1.end()) {
            index = max(res->second, index);
            res->second = i + 1;
        } else {
            map1.insert(make_pair(s[i], i+1));
        }
        len = max(len, i-index+1);
    }

    return len;
}

因为字符串中字符大、小写字母都是在ASCII码中前128位里，于是产生了优化算法。

• 优化

int longestSubStringLength1(const char *str) {
#define MAX(a, b) (a) > (b) ? (a) : (b)
    
    char *temp = (char *)str;
    int i = 0, j = 0, len = 0; // i为子串开始索引，j为子串终止索引
    int indexs[128] = {0};
    char t;
    while ((t = *(temp + j)) != '\0') {
        i = MAX(indexs[t], i); // 字符t若有记录，则将i赋值为t在indexs中存储的索引
        len = MAX(len, j - i + 1); // 计算子串的长度
        indexs[t] = j + 1; //存储值为t索引值为j+1
        j++; // check下一个字符
    }
    return len;
}