2020-07-30

343. 整数拆分

题解: 动态规划， 对于 n 来说，当第一个被拆的数为 i 时， 他能够被拆成 i * (n-i) (i=1 ... n-1) , 也能够拆成更多的数。

即 dp[n] = max(i*(n-i) , i*dp[n-i]) i=1,...n-1 ,记忆化搜索即可。

class Solution {
public:
    int dp[60];
    int integerBreak(int n) {
        if(n==1) return dp[1] = 1;
        if(dp[n]) return dp[n];
        int & ans = dp[n];
        for(int i=1;i<n;i++){
            ans = max(ans , max(i*(n-i),i*integerBreak(n-i)));
        }
        return ans;
    }
};

 1477. 找两个和为目标值且不重叠的子数组

题解： 双指针+DP ， 由于要更新DP数组，所以这题需要让 j 先走。

class Solution {
public:
    int dp[100005]; /// dp[i] 表示 1~i 中满足条件的子数组最小
    int minSumOfLengths(vector<int>& arr, int target) {
        int i=0,j=0;
        int sum = 0, ans = 1e9;
        for(int i=0;i<arr.size();i++) dp[i] = 1e9;
        while(i<arr.size()){
            while(j<arr.size() && sum < target){
                sum+=arr[j++];
            }
            j--;
            if(sum==target){
                dp[j] = j-i+1;
                if(i>0) ans = min(ans , dp[j] + dp[i-1]);
            }
            if(j) dp[j] = min(dp[j], dp[j-1]);
            j++;
        }
        return ans==1e9?-1:ans;
    }
};

1324. 竖直打印单词

class Solution {
public:
    vector<string> printVertically(string s) {
        vector<string> strs;
        string t;
        int maxlen = 0;
        for(int i=0;i<s.size();i++){
             if(s[i]==' ') {
                if(t.size()) 
             strs.push_back(t), maxlen = max(maxlen, (int)t.size()); t="";}
             else t+=s[i];
        }
        if(t.size())strs.push_back(t), maxlen = max(maxlen, (int)t.size());
        //printf("%d
",maxlen);
        vector<string> ans;
        for(int i=0;i<maxlen;i++){
            string t;
            for(int j=0;j<strs.size();j++){
                //cout<<strs[j] <<endl;
                if(i< strs[j].size() ) t+=strs[j][i];
                else t+=" ";
            }
            reverse(t.begin(), t.end());
            //cout << t<<endl;
            int j=0;
            while(j<t.size() && t[j]==' ') j++;
            t = t.substr(j);
            reverse(t.begin(), t.end());
            ans.push_back(t);
        }
        return ans;
    }
};

632. 最小区间

题解: 双指针，首先要把所有的数字放到一个数组，以(数字，数组编号)的方式存储，按照数字从小到大排序。选取的一段需要覆盖所有的数组编号。

class Solution {
public:
    int cnt[4500];
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector <pair<int,int> > a;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums[i].size();j++){
                a.push_back({nums[i][j], i});
            }
        }    
        sort(a.begin(), a.end());
        //printf("%d
",a.size());
        int l = 0, r = 0, cntnum = 0;
        int ansl = 0, ansr=1e9;
        while(l<a.size()){
            while(r<a.size() && cntnum < nums.size()){
               // printf("%d
",a[r].second);
                if(cnt[a[r].second]==0) cntnum++;
                cnt[a[r++].second]++;
            }
           // printf("%d %d %d
",a[l].first,a[r-1].first,cntnum);
            if(cntnum == nums.size()){
                if(ansr-ansl > a[r-1].first - a[l].first || ansr-ansl == a[r-1].first - a[l].first && a[l].first < ansl) {ansl = a[l].first, ansr = a[r-1].first;}
            }
            cnt[a[l].second]--;
            if(cnt[a[l++].second]==0) cntnum--;
        }
        return {ansl, ansr};
    }
};