5674. Largest Merge Of Two Strings

周赛的题目3

算法:

明显是贪心,但我贪错了!

一开始想着比较两个字符创的开头字符,选择字典序大的字符加入。如果两个字符相等就放着比较下一个,直到有不同的就可以全部加入。然后wa了4发。

正确的思路是:比较剩下的字符串,选择字典序大的字符创的的首个字符加入即可。

Read more

665. Non-decreasing Array

665. Non-decreasing Array

思路:

对于任意一个$A[i]>A[i+1]$,$A[i]$和$A[i+1]$分别代表两个non-decreasing array,而合并两个的方法只有:A[i] = A[i - 1]A[i +1 ] = A[i + 2]

接下来只需要讨论边界条件和合并次数即可。

代码:


class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int ansnum = 0;
        int n = nums.size();
        for(int i = 0; i < n - 1; ++i){
            if(nums[i] > nums[i + 1]){
                if(i ==0 || nums[i - 1] <= nums[i + 1] || i == n - 2 || nums[i] <= nums[i + 2]){
                    ansnum++;
                    if(ansnum > 1) return false;
                }   
                else return false;
                    
            }
        }
        return true;;;;;;;;;;
    }
};

763. Partition Labels

思路:

题目不错,贪心到最晚出现的字符就行了。

代码:


class Solution {
public:
    vector<int> partitionLabels(string S) {
        int vis[26] = {0}, num[26] = {0};
        vector<int> par;
        int k = 0, n = S.size(), last = -1;
        
        for(int i = 0; i < n; ++i)
            num[S[i] - 'a']++;

        while(k < n){
            memset(vis, 0, sizeof(vis));
            for(k; k < n; ++k){                
                int idx = S[k] - 'a';
                vis[idx]++;
                int flag = 0;
                if(vis[idx] == num[idx] ){
                    for(int j = 0; j < 26; ++j){                        
                        if(vis[j] && vis[j] != num[j]){
                            flag = 1;
                            break;
                        }
                    }
                    if(!flag){
                        break;
                    }
                }
            }
            par.push_back(k - last);
            last = k;
            k++;
        }
        return par;
    }
};

py版:实现更优雅


class Solution(object):
    def partitionLabels(self, S):
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            j = max(j, last[c])
            if i == j:
                ans.append(i - anchor + 1)
                anchor = i + 1
            
        return ans

作者:LeetCode
链接:https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

455. Assign Cookies

455. Assign Cookies

贪心 + 二分

思路:

贪心

代码:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
            sort(g.begin(), g.end(), less<int>());
            sort(s.begin(), s.end(), less<int>());
            vector<bool> vis(s.size(), 0);
            int ans = 0;
            for(int i = 0; i < g.size(); ++i){
                int l = 0, r = s.size(), mid;
                while(l < r){
                    mid = (l + r) / 2;
                    if(s[mid] >= g[i]) r = mid;
                    else l = mid + 1;
                    
                }
                mid = r;
                while(mid < s.size() && vis[mid]) ++mid;
                if(mid < s.size()){
                    vis[mid] = 1;
                    ++ans;

                }
                
            }        
            return ans;
    }
};

错误之处:

  • sort的默认按升序拍戏,使用greater按降序排序
  • 二分后mid为暂存值,lr才是最后目的地。

面试题 DP 贪心

收集贪心、DP面试题

面14:剪绳子

题面:

将一串长为K的绳子剪成mm>=2,各段长度取整数值)段,各段的长度大于0,求出最大的各段绳子长度之积。

思路1:

由乘法交换律可知绳子的乘积可以分解,提取出来。所以有f(m+n)=f(n)*f(m),其中f(n)是长度n的绳子的最大乘积。分析具体问题可以了解到初始条件比较特殊,它对于小数字来说,分解还不如其本身大,所以定义边界条件f(1) = 1, f(2) = 2, f(3) = 3。同时在DP表示式为:

f(n)=maxif(n−i)∗f(i)f(n)=maxif(n−i)∗f(i)

所以时间复杂度为O(N2)O(N2),空间复杂度为O(N)O(N)。

思路2:

另一种就是贪心,对于长度m大于5的绳子尽可能的剪成长度为3的绳子,同时如果m%3==1,那么就少剪一段绳子,剪成两段长为2的绳子。证明如下:
$$
if \ n \geq 5

3*(n-3) \geq n

2*(n-2) \geq n

3*(n -3 ) \geq 2*(n-2)
$$

测试:

2
2
,
3
2
,
5
6
,
6
9

代码:

DP

int maxProduct_DP(int length){
    if(length < 2) return 0;
	if(length == 2) return 1;
    if(length == 3) return 2;
    int* products = new int[length + 1];
    //初试条件比较特殊,小于4的大于1的数的分段乘积不如其本身大
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    for(int i = 4; i <= length; i++){
        int mavV = 0;
        for(int j = 1; j <= i / 2; j++){
            maxV = max(maxV, products[i - j] * products[j]);
        }
        products[i] = maxv;
    }
    int res = products[length];
    //防止内存泄漏
    del[] products;
    return res;
}

贪心

int maxProduct_greedy(int length){
 if(length < 2) return 0;
	if(length == 2) return 1;
    if(length == 3) return 2;
    int timesOf3 = length / 3;
    if(legnth % 3 == 1) timesOf3 -= 1;
    int timesOf2 = (length - timesOf3 * 3) / 2;
    return (int)pow(3, timeOf3) * (int)pow(2, timesOf2);
}

面42:最大子数组和

题面:

如题

思路:

DP思想。数组之间的选择与历史无关,可以采取DP的方法。记f(i)为以A[i]为结尾的最大数组和。转移方程为:

f(i)={A[i],if f(i-1)<0 A[i]+f(i−1),if f(i-1)>0f(i)={A[i],if f(i-1)<0 A[i]+f(i−1),if f(i-1)>0

当然也可以直接从数据的角度理解,代码都是相同的。

代码:

int MaxSumOfSubArray(int A[], int length){
    int dp[] = new int(length);
	int maxSum = A[0];
    dp[0] = A[0];   
    for(int i = 1; i < length; i++){
        dp[i] = max(A[i], A[i] + dp[i-1]);
        maxSum = max(dp[i], maxSum);
    }
    delete[] dp;
    return maxSum;
    
}

当然这里的dp数组也可以不要。

面45:把数字排成最小的数字

题目:

给定一串数字,组合成的一个数字。求出组合后最小数字的

思路:

可以直接贪心+反证。按字典序排序数字即可。

代码:

就不写了,直接string排序输出即可。

面46:数字翻译成字符串

题目:

把一串数字翻译成数字对应的字母,并按原顺序组成字符串。由于数字分裂的不同,翻译方法有许多,求出翻译的方法的个数。

思路:

第一种就是直接递归分割字符串。显然有子问题重叠的现象,可以考虑使用DP。

第二种用DP思想,考虑dp[i]为从0i的字符串翻译方法。状态转移方程为:

dp[i]={dp[i−1],if 10<=S[i-1] *10 + S[i] <26 dp[i−1]+dp[i−2],else dp[i]={dp[i−1],if 10<=S[i-1] *10 + S[i] <26 dp[i−1]+dp[i−2],else

代码:

int GetTranslateCount(int A[], int length){
    if(A == nullptr || length <= 0) return 0;
    int dp[] = new int(length);
    dp[0] = 1;
    for(int i = 1; i < length; i++){
		int add = A[i - 1] * 10 + A[i];
        if( add > 9 && add < 26){
            if(i < 2) dp = dp[i - 1] + 1;
            else dp[i] = dp[i - 1] + dp[i - 2];
        } 
        else dp[i] = dp[i - 1];
    }
    delete[] dp;
    return dp[length - 1];    
}

面47:礼物的最大价值

题目:

从一在格子上装满礼物的m*n的矩形棋盘上,从左上角向下或者向右移动一格到右下角,求出路径上礼物价值的最大值。

思路:

明显就是DP

代码:

不写了。

面48:最长不含重复字符的子字符串

题目:

如题

思路:

暴力不可取。

采用用DP思想,考虑dp[i]为以S[i]为结尾的最长不重复字符串。一个不含重复字符的字符串可以在由另一个不同的字符组成另一个不含重复字符的字符串。可以在dp过程中,记录下最新的字符的位置POS,判断S[i]的前一个相同字符是否在上一个S[i-1]为结尾的最长不重复字符串之内。记上一个字符与S[i-1]的长度di - POS

状态转移方程为:

dp[i]={dp[i−1]+1,if d > dp[i - 1] d,else dp[i]={dp[i−1]+1,if d > dp[i - 1] d,else

代码:

int MaxSubStr(String s){
    int dp[] = new int(s.length());
    int pos[26];
    for(int i = 0; i < 26; i++) pos[[i] = -1;
	
	int maxL = 1;
	dp[0] = 1;
	for(int i = 1; i < s.length(); i++){
		int d = i - pos[s[i] - 'a'];
        if(dp[i - 1] < d){
            dp[i] = dp[i - 1] + 1;
        }else dp[i] = d;
        maxL = max(maxL, dp[i]);
        pos[s[i] - 'a'] = i;
    }
	delete[] dp;    
   return maxL;            
    
}