专栏首页算法修养LeetCode 321. Create Maximum Number

LeetCode 321. Create Maximum Number

题目

动态规划

class Solution {
public:
    string dp1[100005];
    string _dp1[100005];
    string dp2[100005];
    string bp1[100005];
    string _bp1[100005];
    string bp2[100005];
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        
        int n = nums1.size();
        int m = nums2.size();
        
        dp2[0]="";
        for(int i=1;i<=n&&i<=k;i++)
        {
            dp2[i]="";
            for(int j=n-1;j>=0;j--)
            {
                dp1[j]="";
                if(j>n-i)
                {
                    continue;
                }
                char x = '0'+nums1[j];
                dp1[j] = max(dp1[j+1],x+_dp1[j+1]);
                dp2[i]= max(dp2[i],dp1[j]);
            }
            
            for(int j=0;j<=n-1;j++)
            {
                _dp1[j]=dp1[j];
            }
        }
        
        bp2[0]="";
        for(int i=1;i<=m&&i<=k;i++)
        {
            bp2[i]="";
            for(int j=m-1;j>=0;j--)
            {
                bp1[j]="";
                if(j>m-i)
                {
                    continue;
                }
                char x = '0' +nums2[j];
                bp1[j] = max(bp1[j+1],x+_bp1[j+1]);
                bp2[i]=max(bp2[i],bp1[j]);
            }
            
            for(int j=0;j<=m-1;j++)
            {
                _bp1[j]=bp1[j];
            }
        }
        
        string ans="";
        for(int i=0;i<=k;i++)
        {
            string x = dp2[i];
            string y = bp2[k-i];
            
            string str="";
            int p=0;
            int q=0;
            while(p<x.length()||q<y.length())
            {
                if(p<x.length()&&q<y.length()&&x[p]>y[q])
                {
                    str+=x[p];
                    p++;
                    continue;
                }
                
                if(p<x.length()&&q<y.length()&&x[p]<y[q])
                {
                    str+=y[q];
                    q++;
                    continue;
                }
                
                if(p<x.length()&&q<y.length()&&x[p]==y[q])
                {
                    int p1=p;
                    int q1=q;
                    
                    int tag=0;
                    while(p1<x.length()||q1<y.length())
                    { 
                        if(x[p1]<y[q1])
                        {
                            tag=1;
                            break;
                        }
                        
                        if(x[p1]>y[q1])
                        {
                            tag=0;
                            break;
                        }
                        
                        if(p1==x.length()-1&&q1==y.length()-1)
                        {
                            tag=0;
                            break;
                        }
                        
                        if(p1<x.length()-1)
                            p1++;
                        if(q1<y.length()-1)
                            q1++;
                    }
                    if(tag==0)
                    {
                        str+=x[p];
                        p++;
                    }
                    else
                    {
                        str+=y[q];
                        q++;
                    }
                    continue;
                }
                
                if(p<x.length())
                {
                    str+=x[p];
                    p++;
                    continue;
                }
                 if(q<y.length())
                 {
                    str+=y[q];
                     q++;
                 }
            }
           
            if(ans.length()<str.length())
            {
                ans = str;
            }
            else if(ans.length()==str.length())
            {
                ans=max(ans,str);
            }    
            
        }
        
        
        vector<int> res;
        for(int i=0;i<ans.length();i++)
        {
            res.push_back(ans[i]-'0');
        }
        
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 321. Create Maximum Number

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan
  • Golang Leetcode 321. Create Maximum Number.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89068831

    anakinsun
  • LeetCode 0321 - Create Maximum Number

    Given two arrays of length m and n with digits 0-9 representing two numbers. Cre...

    Reck Zhang
  • Leetcode 414. Third Maximum Number

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • leetcode-414-Third Maximum Number

    chenjx85
  • 关关的刷题日记80 – Leetcode 7. Reverse Integer

    关关的刷题日记80 – Leetcode 7. Reverse Integer 题目 Given a 32-bit signed integer, revers...

    WZEARW
  • Python反转三位整数有几种方法?

    小猿会从最基础的面试题开始,每天一题。如果参考答案不够好,或者有错误的话,麻烦大家可以在留言区给出自己的意见和讨论,大家是要一起学习的 。

    程序IT圈
  • Leetcode 算法 - 7. Reverse Integer

    注意点: 此问题在2014-11-10有更新, 加入了对溢出的控制, 当出现溢出则返回为0. 而Python中没有溢出的行为, 所以为了Accepted, 加入...

    用户1416054
  • Leetcode 1937. Maximum Number of Points with Cost

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan
  • C#版 - Leetcode 414. Third Maximum Number题解

    在线提交: https://leetcode-cn.com/problems/third-maximum-number

    Enjoy233
  • Leetcode 1561. Maximum Number of Coins You Can Get

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan
  • Codeforces 777B Game of Credit Cards

    B. Game of Credit Cards time limit per test:2 seconds memory limit per test:256 ...

    Angel_Kitty
  • Python3实现个位数字和十位数字对调, 其乘积不变

    答:这是leetcode上的一道编程算法题,感觉还是蛮经典的,今天就拿出来给大家分享一下!给出一个3位的正整数,你需要将这个整数中每位上的数字进行反转。例如:输...

    砸漏
  • 关关的刷题日记13——Leetcode 414. Third Maximum Number

    关小刷刷题13 – Leetcode 414. Third Maximum Number 题目 Given a non-empty array of integ...

    WZEARW
  • 常用算法整理

    王磊-AI基础
  • LeetCode Weekly Contest 44解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 38解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 42解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 48解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券