力扣每日一题(+日常水几道题)

每日一题1333. 餐厅过滤器 - 力扣（LeetCode）

简单的按规则排序,去除几个不满足的条件然后排序返回即可

#include
class Solution {
public:
    vector<int> filterRestaurants(vectorint>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) 
    {
        vector<int>ans;
        std::sort(restaurants.begin(),restaurants.end(),[](vector<int>& a,vector<int>& b)
        {
            return a[1] == b[1] ? a[0] > b[0] : a[1] > b[1]; 
        	return true;
        });
        if(veganFriendly)
        for(auto x : restaurants)
        {
            if(!x[2] || x[3] > maxPrice || x[4] > maxDistance)continue;
            ans.emplace_back(x[0]);
        }
        else
        for(auto x : restaurants)
        {
            if( x[3] > maxPrice || x[4] > maxDistance)continue;
            ans.emplace_back(x[0]);
        }
        return ans;
    }
};

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

一题简单的递推,也是没什么好说的

class Solution {
public:
    int tribonacci(int n) {
        std::array<int,3> ans = {0, 1, 1};
        if(n <= 2)
        return ans[n];
        // 0 1 1 2 4 7
        for(int i = 0; i <= n - 3; i++)
        {
            int d = 0;
            for(int j = 0; j < 3; j++)
            {
               // std::cout << ans[j] << " ";
                d += ans[j];
                if(2 - j)ans[j] = ans[j + 1];
            }
          //  std::cout << "\n" << d << " " << "\n";
            ans[2] = d;
        }
        return ans[2];
    }
};

790. 多米诺和托米诺平铺 - 力扣（LeetCode）

方法一:状态压缩dp

class Solution {
public:
    int mod = 1e9 + 7;
    int numTilings(int n) 
    {
        using i64 = int64_t;
        //按列表达状态 00 10 01 11
        i64 dp[n + 1][12];//平铺到第i 列时状态为 …… 的方案数
        memset(dp, 0, sizeof dp);
        dp[0][1 << 1 | 1] = 1;
        for(int i = 1; i <= n;i++)
        {
            dp[i][0] = dp[i - 1][1 << 1 | 1];
            dp[i][1 << 1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1 << 1]) % mod;
            dp[i][1 << 1 | 1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][1 << 1 | 1] + dp[i - 1][1 << 1]) % mod;
        }
        return dp[n][1 << 1 | 1] % mod;
    }
};

主要是方法二:学习别人的想法和写法

作者：灵茶山艾府
链接：https://leetcode.cn/problems/domino-and-tromino-tiling/submissions/
来源：力扣（LeetCode）

class Solution {
    const int MOD = 1e9 + 7;
public:
    int numTilings(int n) {
        if (n == 1) return 1;
        long f[n + 1];
        f[0] = f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; ++i)
            f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;
        return f[n];
    }
};