题解 | #数列# c语言 写法 思路易懂

这题数列输出要先输入n个k值的个数，在输入k值；
我第一思路是下面的第一种，但是发现一直时间超出；
后面看其他人的题解和讨论，才发现我想的太简单了，
这题的测试用例是比较极端的，用第一种思路完全过不了，只能开始下面第二种思路；

//一、 每个k值都从0开始循环一遍
//时间复杂度 O(n*k)    n表示n行数据，k表示每次k值循环需要时间;
//空间复杂度 O(1)      没有用到格外空间;
//这样写不行，时间会超出
// #include <stdio.h>
// int main() {  
//     int n = 0;
//     scanf("%d",&n);               //输入k的数量 n；

//     while(n--)                    //开始n次循环；
//     {
//         int  k = 0;
//         scanf("%d",&k);           //读取当次k值；
//         if(k < 3)
//         {
//             printf("%d\n",k);     //k值小于3，直接输入k。因为第一项为1，第二项2；
//             continue;             //直接下一个k值循环；
//         }

//         int a1 = 1, a2 = 2, a3 = 0;
//         for(int i = 3; i<=k; ++i)  //从3开始到k的循环，其中a3表示当前项
//         {                          //a2表示前一项的值，a1表示前二项的值
//             a3 = (2*a2 + a1);
//             a3 = a3 % 32767;
//             a1 = a2;
//             a2 = a3;
//         }

//         printf("%d\n", a3);        //输出当次k项的值；

//     }
//     return 0;
// }


//二、 先循环完这10万数的k值放数组，需要每个k值直接读数组
//这样写行， 只要走一遍数组，后面每次访问都超级快；
//时间复杂度 O(1)    每次都是先循环10万次，但是常数次为看做1;
//空间复杂度 O(100000)    用了一个10万长度的整形数组;
#include <stdio.h>

int main() {
    int arr[100000] = {0};
    arr[0] = 1;
    arr[1] = 2;
    for(int i = 2; i<100000; ++i)         //10万次循环把arr数组提前存好对应k值；
    {
        arr[i] = arr[i-1]*2 + arr[i-2];   //根据前两项算出当前项的值
        arr[i] = arr[i]%32767;            //防止溢出，每次都对32767取余数；
    }

    int n = 0;
    scanf("%d",&n);                      //输入n次
    while(n--)                           //开始n次循环；
    {
        int  k = 0;
        scanf("%d",&k);
        printf("%d\n",arr[k-1]);         //直接读数组对应的输出，其中第一项 为arr[0], 
    }                                    //第二项 为arr[1], 第k项 为arr[k-1]；
    return 0;
}

//最后感谢大家看到这，谢谢大家!     (如果可以，请大家点个赞吧）