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

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

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

#include<algorithm>
class Solution {
public:vector<int> filterRestaurants(vector<vector<int>>& 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]);}elsefor(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 7for(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 11i64 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];}
};