爬楼梯_小米集团笔试题

C/C++

广州市民林先生

首先这个题目的模型是斐波那契数列（参考剑指offer的青蛙跳台阶），思路是很清晰的，但是有一个很棘手的问题：这个题C++没有大整数类，而题目的用例太大了，long long也只能通过55%的用例，所以只能通过字符串来显示。所以整道题的重点就是如何进行字符串相加，手写字符串相加函数、

下面的注释很详细了，可以参考

#include <iostream>
#include <string>
using namespace std;

string BigData(string s1, string s2){
    string res = "";
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int carry = 0;  //进位
    while (i >= 0 || j >= 0){
        // s2一定大于s1（斐波那契数列的后者 > 前者）
        if(i < 0){
            //当小的字符串先走完时，就剩大字符串了，同理进行逐位添加
            res = to_string((s2[j] - '0') + carry) + res;
            carry = 0;  //只剩一个字符串就不存在进位了，因为都是个位数
        } else{
            //从后往前进行逐位相加，如123+567,从3+7开始往前加，别忘了加上进位
            int tmp = (s1[i] - '0') + (s2[j] - '0') + carry;
            carry = tmp / 10;  //得到进位
            tmp = tmp % 10;    //得到余数
            res = to_string(tmp) + res; //这里顺序记得不能颠倒，不然就错了
        }
        --i; --j;
    }
    //为什么下面还要判定呢？因为比如3+7应该等于10，但是
    //上面的计算出的res只有0(余数)，所以这里要考虑周全
    if(carry == 1)
        res = '1' + res;
    return res;
}
int main(){
    int n;
    cin >> n;
    //斐波那契
    if(n == 1){
        cout << 1 << endl;
        return 0;
    } else if(n == 2){
        cout << 2 << endl;
        return 0;
    }
    string i = "1";
    string j = "2";
    string ans = "";
    for(int k = 1; k <= n - 2; ++k){
        ans = BigData(i, j);  // i + j
        i = j;   
        j = ans;
    }
    cout << ans << endl;
    return 0;
}

编辑于 2020-06-03 21:22:49 回复(0)

C/C++

Andrew_Y

递推公式很简单，f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2.
值得注意的是本题还有大整数问题，所以使用转化为字符串形式，额外写一个大整数相加函数
#include<iostream>
using namespace std;
//大整数相加函数
string add(string a,string b)
{
    int i=a.size()-1;
    int j=b.size()-1;
    string res="";
    int carry=0;
    while(i>=0&&j>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
        j--;
    }
    while(i>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
    }
    while(j>=0)
    {
        char tmp;
        int num;
        num=(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        j--;
    }
    if(carry>0)
    {
        res=char(carry+48)+res;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    string a[n+1];
    for(int i=0;i<n+1;i++)
    {
        a[i]='0';
    }
    a[0]='1';
    a[1]='1';
    for(int i=2;i<n+1;i++)
    {
        a[i]=add(a[i-1],a[i-2]);
    }
    cout<<a[n];
}

发表于 2019-10-28 12:14:22 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int num[103][30] = {0};
    num[1][29] = 1;//第一项
    num[2][29] = 2;//第二项 
    for (int i = 3; i <= n; i++)
    {
        for (int j = 29; j >= 0; j--)//循环，数组行是从1开始，列是从0开始
        {
            if ((num[i - 1][j] + num[i - 2][j]+num[i][j]) >= 10)//进位，占多一个元素
                num[i][j - 1] += 1;
            num[i][j] = (num[i - 1][j] + num[i - 2][j] + num[i][j]) % 10;
        }
    }
    int j = 0;
    while (num[n][j] == 0)
        j++;
    for (int i = j; i < 30; i++)
        cout << num[n][i];
    return 0;
}

发表于 2019-07-03 22:07:12 回复(2)

Python

Sheerloock

import sys
def diffroad(n):
    res =[1,2]
    if n<3:
        return res[n-1]
    for i in range(3,n+1):
        res[(i-1)%2] += res[i%2]
    return res[(i-1)%2]
    
if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))

发表于 2019-09-07 22:41:08 回复(0)

给我offer我要offer

import java.util.*;
import java.math.*;
public class Main{
    static BigInteger func(int n){
        if(n==0)
            return new BigInteger("0");
        if(n==1)
            return new BigInteger("1");
        BigInteger[] ll=new BigInteger[n];
        ll[0]=new BigInteger("1");
        ll[1]=new BigInteger("2");
        for(int i=2;i<n;i++){
            ll[i]=ll[i-1].add(ll[i-2]);
        }
        return ll[n-1];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(func(n));
    }
}

发表于 2020-08-25 00:09:06 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[101][30] = {0};
    a[1][29] = 1;
    a[2][29] = 2;
    for(int i=3;i<=n;i++)
        for(int j=29;j>=0;j--){
            int t = a[i-1][j]+a[i-2][j]+a[i][j];
            if(t >= 10)
                a[i][j-1] += 1;
            a[i][j] = t%10;
        }
    bool zero = true;
    for(int j=0;j<30;j++){
        if(zero && a[n][j]!=0)
            zero = false;
        if(!zero)
            cout<<a[n][j];
    }
    cout<<endl;
    return 0;
}

发表于 2019-12-30 00:56:26 回复(1)

北雷北雷

这里有一个超大数，CPP会溢出。直接用递归 cpp会超时，引入滚动数组，从低位开始计算，避免重复运算

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1,2,0]
    if n<=2:
        print(n)
    else:
        for i in range(3, n+1):
            dp[-1]= dp[0]+dp[1]
            dp[0] = dp[1]
            dp[1]=dp[2]
        print(dp[2])

发表于 2019-07-22 11:05:42 回复(0)

lentolove

考察斐波那契数列
题目要求：只能跳1阶或者2阶。
定义 $n$ 阶有 $f(n)$ 种跳法

假定第一次跳的是一阶，那么剩下的是 n-1 个台阶，跳法是 $f(n-1)$ ;
假定第一次跳的是2阶，那么剩下的是 n-2 个台阶，跳法是 $f(n-2)$ ；
总跳法为: $f(n) = f(n-1) + f(n-2)$
$f(1) = 1,f(2) = 2$ .

初次提交这个题会发现通过率只有 50%,是因为没有考虑到整数溢出的问题，用BigInteger处理就Ok了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        if (n < 3) {
            System.out.println(n);
            return;
        }
        BigInteger one = BigInteger.valueOf(1);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger ret = BigInteger.valueOf(0);

        for (int i = 3; i <= n; i++) {
            ret = one.add(two);
            one = two;
            two = ret;
        }
        System.out.println(ret);
    }
}

发表于 2019-07-28 13:59:23 回复(2)

C/C++

折子渝

写一个c语言比较简洁的大整数加法

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 5, vector<int> (100, 0));
    dp[1][0] = 1;
    dp[2][0] = 2;
    int len = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < len; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i - 2][j];
            if (dp[i][j] > 9) {
                dp[i][j + 1] += dp[i][j] / 10;
                dp[i][j] %= 10;
                len += (j == len - 1);
            }
        }
    }
    for (int i = 0; i < len; i++) cout << dp[n][len - i - 1];
    cout << endl;
    return 0;
}

编辑于 2020-03-11 19:45:54 回复(2)

Java

谁的电脑

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<BigInteger> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            BigInteger temp = (i <= 2) ? BigInteger.valueOf(i) : list.get(i - 2).add(list.get(i - 3));
            list.add(temp);
        }
        System.out.println(list.get(list.size() - 1));
    }
}

发表于 2019-07-08 16:16:43 回复(0)

Python

ElonB

""""
台阶问题，考虑动态规划
设dp[n]为n阶台阶的方法数，
每次只能上1、2阶台阶，要想到达n，则只能由n-1，n-2到达
dp[n] = dp[n-1] + dp[n-2]
边界 dp[0] = dp[1] = 1
"""

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])

发表于 2019-07-13 14:54:55 回复(1)

牛客555584396号

JS要用大数api实现

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
// Write your code here
while(line = await readline()){
let num = parseInt(line)
if(num == 0) {
console.log(1)
return
}
if(num == 1) {
console.log(1)
return
}
let prev1 = BigInt(1),prev2 = BigInt(1)
let total = 0
for(let i = 1;i < num;i++) {
total = (prev1 + prev2).toString()
prev2 = prev1
prev1 = BigInt(total)
}
console.log(total)
}
}()

发表于 2025-02-03 17:42:15 回复(0)

Python3

尘__1__

def climbstar(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        pre = 2
        prepre = 1
        for x in range(n - 2):
            result = pre + prepre
            prepre = pre
            pre = result
        return result


n = int(input())
print(climbstar(n))

不了解什么大数，用递归又超时，只能跑循环了

发表于 2024-04-29 20:50:46 回复(0)

JavaScript Node

牛客944083017号

这道题不考虑大数相加的话是这样的思路，和斐波拉一样

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = dp[i-1] + dp[i-2]
        }
        console.log(dp[num])
    }
}()

但是这道题，必须得考虑大数相加

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = numAdd(dp[i-1].toString(), dp[i-2].toString())
        }
        console.log(dp[num])
    }
    /**
     * 这个函数是用来进行大数相加的，可以反复阅读一下
     */
    function numAdd(first, second) {
        // 取两个数字的最大长度
        let maxLength = Math.max(first.length, second.length);
        // 用 0 去补齐长度
        first = first.padStart(maxLength , 0);
        second = second.padStart(maxLength , 0); 
        // 定义加法过程中需要用到的变量
        let temp = 0;
        let carry = 0;   // "进位"
        let sum = "";
        for(let i = maxLength-1; i >= 0; i--){
            temp = parseInt(first[i]) + parseInt(second[i]) + carry;
            carry = Math.floor(temp / 10);
            sum = temp % 10 + sum;
        }
        if(carry == 1){
            sum = "1" + sum;
        }
        return sum;
    }
}()

发表于 2023-04-16 21:01:07 回复(0)

Java

等一个offer的河老师很想踩缝纫机

import java.math.BigDecimal;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        if (sum == 1) {
            System.out.println(1);
            return;
        } else if (sum == 2) {
            System.out.println(2);
            return;
        } else if (sum <= 0) {
            System.out.println();
            return;
        }
        BigDecimal[] ary = new BigDecimal[sum];
        ary[0] = BigDecimal.valueOf(1);
        ary[1] = BigDecimal.valueOf(2);
        for (int i = 2; i < sum; i++) {
            ary[i] = ary[i - 2].add(ary[i - 1]);
        }
        System.out.println(ary[sum - 1].toString());
    }
}

发表于 2023-02-17 15:56:49 回复(0)

Winun

这题python倒在了内存上

前面的大佬的方法也不好使,.我这边加了字典缓存一下可以了

n = int(input())

cache = dict()

def foo(x):
    if x in cache:
        return cache[x]
    if x == 1:
        return 1
    elif x == 2:
        return 2
    res = foo(x - 1) + foo(x - 2)
    cache[x] = res
    return res


print(foo(n))

发表于 2023-02-11 20:40:08 回复(0)

Python3

牛客128887458号

需要自己找到上楼梯次数的规律

阶梯：1,2,3,4,5,6,

需要的次数：1,2,3,5,8,13

规律为第n梯需要的步数为(n-1)梯的步数加上（n-2）梯的步数

另外，改题会验证大量的步数，对内存要求特别高，需要导入了一个lru_cache

import sys

from functools import lru_cache

@lru_cache

def work(n):

if n ==1 or n == 2:

return n

else:

return work(n-1) + work(n-2)

for line in sys.stdin:

a = line.strip("\r\n")

res = work(int(a))

print(res)

发表于 2022-11-26 19:20:07 回复(0)

C++

Hank丶涵

#include <bits/stdc++.h>
using namespace std;

string strAdd(string a, string b) {
    int level = 0;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int aIndex = 0;
    int bIndex = 0;
    string res = "";
    while (aIndex < a.size() || bIndex < b.size() || level != 0) {
        int val = (aIndex < a.size() ? a[aIndex++] - '0' : 0) + (bIndex < b.size() ? b[bIndex++] - '0' : 0) + level;
        level = val / 10;
        res += to_string(val % 10);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<string> dp(101, "0");
    dp[1] = "1";
    dp[2] = "2";
    for (int i = 3; i < 101; i++) {
        dp[i] = strAdd(dp[i - 1], dp[i - 2]);
    }
    cout << dp[n] << endl;
    return 0;
}

发表于 2022-07-31 14:54:10 回复(0)

Java

RanYe_749815285

本题结果用long类型存放也会超出范围，只能使用字符串存放。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] dp = new String[101]; // 楼梯的台阶数小于等于100
        dp[1] = String.valueOf(1);
        dp[2] = String.valueOf(2);
        for (int i = 3; i <= 100; i++) {
            dp[i] = add(dp[i - 1], dp[i - 2]); // 两个字符串相加
        }

        int n = sc.nextInt();
        System.out.println(dp[n]);
    }

    public static String add(String s1, String s2) {
        int n1 = s1.length() - 1;
        int n2 = s2.length() - 1;
        int add = 0; // 记录进位
        StringBuffer sb = new StringBuffer(); // 存放结果
        while (n1 >= 0 || n2 >= 0) {
            int x = (n1 >= 0) ? s1.charAt(n1) - '0' : 0;
            int y = (n2 >= 0) ? s2.charAt(n2) - '0' : 0;
            int sum = x + y + add;
            if (sum > 9) {
                sb.insert(0, sum % 10);
                add = 1;
            } else {
                sb.insert(0, sum);
                add = 0;
            }
            n1--;
            n2--;
        }
        if (add == 1) sb.insert(0, 1); // 最后查看是否有进位
        return sb.toString();
    }
}

发表于 2021-09-09 21:45:39 回复(0)

Java

徐瑾麓

import java.util.*;
import java.math.BigInteger;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
BigInteger[] a = new BigInteger[n+1];
if(n<3) System.out.println(n);
if(n>=3){
a[1]=new BigInteger("1");
a[2]=new BigInteger("2");
for(int i = 3;i<=n;i++){
a[i]=a[i-1].add(a[i-2]);
}
System.out.println(a[n]);
}
}
}

发表于 2021-09-07 20:52:59 回复(0)

爬楼梯

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题