牛客刷题系列(汽水瓶,跳台阶扩展问题,斐波那契凤尾)

#include 
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int count = 0;
        if(n == 0)
        break;
        while (n != 0) {
            if (n == 2) 
            {
                count += 1;
                n = 0;
            } 
            else if(n == 1)
                break;
            else 
            {
                count += n / 3;
                n = n / 3 + n % 3;
            }
        }
       cout<< count<

• 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

即按照题目的常规思路写下去

简便写法

• 注意题目要求：

某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。

• 所以我们可以将二个空瓶子 + 借老板的一个 -> 换得 一瓶
• 再归还这一瓶
• 所以我们等于 两个 空瓶子 == 喝一瓶

二.跳台阶扩展问题

• 题目链接：链接

• 代码实现：

class Solution {
public:
    int jumpFloorII(int number) {
         return pow(2,number-1);
        }
    
};
1
2
3
4
5
6
7

• 改进写法：

class Solution {
public:
    int jumpFloorII(int number) {
         return 1<<(number-1);
        }
    
};
1
2
3
4
5
6
7

• 总结：

以后遇到2的次方运算时，应用位运算来提高效率

三：斐波那契凤尾

• 题目：[链接](斐波那契凤尾__牛客网 (nowcoder.com))

• 代码：

// write your code here cpp
#include 
#include 
using namespace std;

int main() {
    int board = -1;
    long long ans[100000];
    ans[0] = 1;
    ans[1] = 2;
    for (int i = 2; i < 100000; i++) {
        long long next = ans[i - 1] + ans[i - 2];
        if( board == -1 && next >= 1000000 ) //首次出现
        {
            board  = i+1;
        }
        ans[i] = next % 1000000;
    }
    
    int n;
    while (cin >> n) {
        long long f = ans[n - 1];
        if(n>=board)
            printf("%06d\n",f);
        else
        printf("%d\n", f);
        }
    
}
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

• 思路：

1. 利用一个数组来保存从1~100000的数
2. 用的时候再去取就好了
3. 时间复杂度低，空间复杂度高。属于用空间来换时间

• 注意事项：

1. 注意首次出现大于1000000的数，后面的数就要输出后6位了，假如不做处理，后面的数有可能低于6位。if( board == -1 && next >= 1000000 ) //首次出现