圆环回原点

C 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-06-25

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int circle(int n ) {
    int dp[10] = { 0 }, ndp[10];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        ndp[0] = (dp[9] + dp[1]) % 1000000007;
        for (int j = 1; j < 9; j++) {
            ndp[j] = (dp[j-1] + dp[j+1]) % 1000000007;
        }
        ndp[9] = (dp[8] + dp[0]) % 1000000007;

        for (int j = 0; j < 10; j++) {
            dp[j] = ndp[j];
        }
    }
    
    return dp[0];
}

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-06-18

class Solution {
  public:
    int circle(int n) {
        int a[2][9] = {0};
        a[0][0] = 1;
        int k = 1000000007;
        int x = 0, y = 0;//顺，逆
        for (int i = 1; i <= n; ++i) {
            x = (i + 2) % 2;
            y = (i + 1) % 2;
            for (int j = 0; j < 10; ++j) {
                a[x][j] = ((a[y][(j - 1 + 10) % 10] % k) + (a[y][(j + 1) % 10] % k)) % k;
            }
        }
        return a[x][0];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-05-27

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int circle(int n) {
        // write code here
        int arr[2][10] = {0};
        arr[0][0] = 1;
        int mod = 1000000007;
        int l = 0,r = 0;
        for(int i = 1; i <= n; ++i){
            l = (i + 2) % 2;
            r = (i + 1) % 2;
            for(int j = 0; j < 10; ++j){
                arr[l][j] = ((arr[r][(j - 1 + 10) % 10] % mod) + (arr[r][(j + 1) % 10] % mod)) % mod;
            }
        }
        return arr[l][0];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-07-21

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

class Solution
{
private:
    const int mod = 1e9 + 7;

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int circle(int n)
    {
        const int m = 10;

        vector<int> f(m);

        f[0] = 1;

        for (int i = 0; i < n; ++i)
        {
                vector<int> t = f;
            for (int j = 0; j < m; ++j)
            {
                int l = (j + m - 1) % m, r = (j + 1) % m;
                f[j] = (t[l] + t[r]) % mod;
            }
        }
        return f[0];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 416KB, 提交时间: 2022-07-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int circle(int n) {
        // write code here
        vector<vector<int>> dp(10,vector<int>(2,0));
        dp[0][0]=1; // 从0到0走0步有一种走法
        for(int m=1;m<=n;m++)
        {
            for(int i=0;i<10;i++)
            {
                dp[i][1]=(dp[(i+9)%10][0]+dp[(i+1)%10][0])%1000000007;
            }
            for(int i=0;i<10;i++)
                dp[i][0]=dp[i][1];
        }
        return dp[0][1];
    }
};

详情