2021春季每日一题【week6 未完结】

28. 实现 strStr()【KMP】141. 周期【KMP 未完成】91. 解码方法【未完成】821. 跳台阶363. 矩形区域不超过 K 的最大数值和【前缀和】3412. 邻域均值【前缀和】368. 最大整除子集【未完成】12. 背包问题求具体方案【DP】377. 组合总和 Ⅳ【DP】3382. 整数拆分【DP】897. 递增顺序搜索树【模拟】47. 二叉树中和为某一值的路径【dfs】

class Solution {
public:
    int strStr(string s, string p) {
        if(p.empty()) return 0;
        int n=s.size(),m=p.size();
        s=' '+s,p=' '+p;
        
        vector next(m+1);
        for(int i=2,j=0;i<=m;i++)
        {
        	while(j&&p[i]!=p[j+1]) j=next[j];
        	if(p[i]==p[j+1]) j++;
        	next[i]=j;
        }
        
        for(int i=1,j=0;i<=n;i++)
        {
        	while(j&&s[i]!=p[j+1]) j=next[j];
        	if(s[i]==p[j+1]) j++;
        	if(j==m) return i-m;
        }
        return -1;
    }
};

#include
#include
using namespace std;
int n;
int f(int n)
{
    return (n==1||n==2)?1:f(n-1)+f(n-2);
}
int main(void)
{
    cin>>n;
    cout< 
363. 矩形区域不超过 K 的最大数值和【前缀和】 
 
class Solution {
public:
    int maxSumSubmatrix(vector>& matrix, int k)
    {
        int s[105][105]={0};
        int n=matrix.size();
        int m=matrix[0].size();
        for(int i=0;i 
3412. 邻域均值【前缀和】 
 
#include
using namespace std;
const int N=1010;
int s[N][N],n,L,r,t;
int main(void)
{
    cin>>n>>L>>r>>t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            cin>>s[i][j],s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x=max(1,i-r),y=max(1,j-r);
            int xx=min(n,i+r),yy=min(n,j+r);
            int sum=s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];
            int m=(xx-x+1)*(yy-y+1);
            if(m*t>=sum) cnt++;
        }
    cout< 
368. 最大整除子集【未完成】 
 
12. 背包问题求具体方案【DP】 
 
#include
using namespace std;
const int N=1010;
int f[N][N],w[N],v[N],n,m;
int path[N];
int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i+1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    }
    int cnt=0;
    for(int i=1,j=m;i<=n;i++)
    {
        if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
        {
            path[cnt++]=i;
            j-=v[i];
        }
    }
    for(int i=0;i 
377. 组合总和 Ⅳ【DP】 
 
class Solution {
public:
    int combinationSum4(vector& nums, int target) 
    {
        unsigned int f[100005]={0};
        f[0]=1;
        for(int i=1;i<=target;i++)
        {
            for(int j=0;j=nums[j]) f[i]+=f[i-nums[j]];
        }
        return f[target];
    }
};
 
3382. 整数拆分【DP】 
 
#include
using namespace std;
const int mod=1e9;
int a[25],n;
void init()
{
    a[1]=1;
    for(int i=2;i<=21;i++) a[i]=a[i-1]*2;
}
int f[10000005];
int main(void)
{
    init();
    cin>>n;
    f[0]=1;
    for(int i=1;i<=21;i++)
    {
        for(int j=a[i];j<=n;j++)
        {
            f[j]=(f[j]+f[j-a[i]])%mod;
        }
    }
    cout< 
897. 递增顺序搜索树【模拟】 
 
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) 
    {
        TreeNode* head=new TreeNode(-1);
        auto temp=head;
        dfs(root,temp);
        return head->right;
    }
    void dfs(TreeNode* root,TreeNode* &temp)
    {
        if(!root) return;
        if(root->left) dfs(root->left,temp);
        temp->right=new TreeNode(root->val);
        temp=temp->right;
        if(root->right) dfs(root->right,temp);
    }
};
 
47. 二叉树中和为某一值的路径【dfs】 
 
class Solution {
public:
    vector< vector >ans;
    vectorpath;
    void dfs(TreeNode* root,int sum,int x)
    {
        if(!root) return;
        sum+=root->val;
        
        if(!root->left&&!root->right)
        {
            path.push_back(root->val);
            if(sum==x) ans.push_back(path);
            path.pop_back();
            return;
        }
        
        path.push_back(root->val);
        if(root->left) dfs(root->left,sum,x);
        path.pop_back();
        
        path.push_back(root->val);
        if(root->right) dfs(root->right,sum,x);
        path.pop_back();
    }
    vector> findPath(TreeNode* root, int x) 
    {
        dfs(root,0,x);
        return ans;
    }
};