leetcode day12 贪心 605+44

605种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

解题思路1：贪心

思考什么情况下可以种花？不能相邻种 那就是 当前位置的前后都要为0

最容易想到的就是前中后都是0，把花种在中间。

如果到了左右边界怎么办？

比如到了左边界，那么前是没有数的，就不需要考虑前面的数。比如0 0，中后为0，可以把花种在中间位置。右边界与此类似，不需要考虑后边的数。

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    int len=flowerbedSize;
    int cnt=0;
    for(int i=0;i<len;i++){
        if(flowerbed[i]==0&&(i==0||flowerbed[i-1]==0)&&(i==len-1||flowerbed[i+1]==0)){
            cnt++;
            flowerbed[i]=1;
        }
    }
    if(cnt>=n)return true;
    else return false;
}

解题思路2：滑动窗口法 

滑动窗口是双指针算法的一种，基本思路为维护一个窗口，然后从前往后遍历元素进行运算。维护一个固定大小为3的窗口，left左边界，right右边界，花种在[left,right-1]中间。右指针不断向右移动。当右边界为1时，left追上right.当能种植新花时，cnt++,同时更新窗口左边界的值+2;

注意考虑花坛边界情况。也就是上面方法。比如到了左边界，那么前是没有数的，就不需要考虑前面的数。比如0 0，中后为0，可以把花种在中间位置。右边界与此类似，不需要考虑后边的数。

解决方法：设置left初始值为-1，花坛为001时可在第一个位置种花，right=2，left=-1满足题意。

如[0,0,1,0,1] n =1输出true。如果设置left初始值为0，那这个样例就会输出false。

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
   int left=-1,right=0,len=flowerbedSize,cnt=0;
   while(right<=len){
       int value;//右边的值
       if(right==len)value=0;//到右边界
       else value=flowerbed[right];
       right++;
       if(value==1)left=right;
       if(right-left==3){
         cnt++;
         left+=2;
       }
   }
   if(cnt>=n)return true;
   else return false;
}

44通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

解题思路：动态规划

dp[i][j]=1表示s的前i个字符与p的前j个字符匹配

1、初始化，dp[0][0]=1

dp[i][0]=0，即空模式无法匹配非空字符串；

dp[0][j] ：只有当模式 p 的前 j 个字符均为星号时，dp[0][j] 才为1。

2、确定动规方程

对于字符串 p 而言，有三种字符：

普通字符：需要和 s 中同一位置的字符完全匹配

?：能够匹配 s 中同一位置的任意字符

*：能够匹配任意字符串

（1）p为普通字符，dp[i][j]=dp[i-1][j-1]&&s[i-1]==p[j-1]

（2）p为?,dp[i][j]=dp[i-1][j-1]

（3）p为*,dp[i][j]=dp[i][j-1]||dp[i-1][j]

理由如下：分析当出现 '*' 这种字符时，是匹配 0 个字符、还是 1 个字符、还是 2 个字符 ...

dp[i][j]=dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]……||dp[i-k][j-1]

这意味着我们要对 k 种情况进行枚举检查吗？(关键点）

其实并不用，对于这类问题，我们通常可以通过代数进简化，将 i - 1 代入上述的式子：

当i=i-1时，dp[i-1][j]=dp[i-1][j-1]||dp[i-2][j-1]……||dp[i-k][j-1]，与dp[i][j]后半部分相同。

所以，dp[i][j]=dp[i][j-1]||dp[i-1][j];

情况一和情况二有共同的条件 dp[i][j]=dp[i-1][j-1]，可以合到一起来做

bool isMatch(char* s, char* p) {
    int m=strlen(s),n=strlen(p);
    //dp[i][j]=1表示s的前i个字符与p的前j个字符匹配
    int dp[m+1][n+1]={};
    dp[0][0]=1;
    for(int j=1;j<=n;j++){
        if(p[j-1]=='*')dp[0][j]=1;
        else break;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
          if(p[j-1]=='*')dp[i][j]=dp[i][j-1]||dp[i-1][j];
          else{
                if(p[j-1]==s[i-1]||p[j-1]=='?')dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=0;
          }
        }
    }
    return dp[m][n];
}

解题思路：贪心算法

用i_star和j_star表示星号在s和p中匹配的位置。

如何表示*匹配多个的情况呢,考虑之后发现增加回溯的步骤即可。

发现字符不匹配且没有星号出现,但是istar>0，说明*匹配的字符数可能出错 回溯。

i_star++,i=i_star,j=j_star+1

bool isMatch(char* s, char* p) {
    int m=strlen(s),n=strlen(p);
    //用i_star和j_star表示星号在s和p中匹配的位置
    //i和j表示当前匹配的位置
    int i=0,j=0,i_star=-1,j_star=-1;
    while(i<m){
        if(j<n&&(s[i]==p[j]||p[j]=='?')){
            i++;//指针同时往后自增1，表示匹配
            j++;
        }else if(j<n&&p[j]=='*'){
             i_star=i;//记录星号
             j_star=j;
             j++;//并且j移到下一位,准备下个循环s[i]和p[j]的匹配
        }else if(i_star>=0){
          /*发现字符不匹配且没有星号出现,但是istar>0 
             说明*匹配的字符数可能出错 回溯
          */
          i_star+=1;
          i=i_star;//匹配字符的量出错，现在多匹配一个，且自身加一
          j=j_star+1;//重新使用p串*后的部分开始对齐s串i_star
        }else return false;
    }
    while(j<n&&p[j]=='*')j++;//去掉多余星号
    //匹配到最后一个
    return j==n;
}