【leetcode】第 74 场双周赛

Tb 字符串中最多数目的子字符串

• 
• 题目链接：字符串中最多数目的子字符串
• 题目分析：我们只能向字符串插入一个字符。当在某个位置插入字符pattern[0], 那么增加的子序列数是该位子右边的pattern[1]的数量。当在某个位置插入字符pattern[1], 那么增加的子序列数就是该位子左边pattern[0]的个数。通过这个分析，我们要使得子序列数更多，要么在字符串头部插入 patter[0], 要么在尾部插入pattern[1]. 当 pattern[1] == pattern[0], 特殊处理，任意两个构成一个组合。
• 解题代码

  • 
    	/**
    	 * @param {string} text
    	 * @param {string} pattern
    	 * @return {number}
    	 */
    	var maximumSubsequenceCount = function(text, pattern) {
    	    if (pattern[0] == pattern[1]) {
    	        let a = 0;
    	        for (const c of text)
    	            if (c == pattern[0])
    	                a ++;
    	        // 插入一个字符
    	        a ++;
    	        // 组合公式 a中选任意两个数组合
    	        return a * (a - 1) / 2;
    	    } else {
    	        let a = 0, b = 0;
    	        let ans = 0;
    	        for (const c of text) {
    	            if (c == pattern[0])
    	                a ++;
    	            else if (c == pattern[1]){
    	                b ++;
    	                // 当出现一个pattern[1] 的时候必然可以和前面的数组成pattern[0] 组成子序列
    	                ans += a;
    	            }
    	        }
    	        // 判断插入头还是尾，看哪个数最大
    	        ans += Math.max(a, b);
    	        return ans;
    	    }
    	};
    

用地毯覆盖后的最少白色砖块

*

• 题目链接：用地毯覆盖后的最少白色砖块
• 题目分析：
  • 我们可以根据动态规划求出答案。用dp[i][j] 表示 i 块地毯 覆盖 0~j 块砖的未被覆盖的白砖。
  • 状态转移
    • 当新添加的砖块不覆盖
      • dp[i][j] = d[i][j - 1] + (f[j] == '1');（f表述砖块字符串）
    • 当新添加的砖块被覆盖
      • dp[i][j] = d[i - 1][j - l];(l 表示地毯长度)
  • 边界：用0块地毯覆盖的白砖等于0~j的白砖数
    *解题代码

  • 
    	/**
    	 * @param {string} floor
    	 * @param {number} numCarpets
    	 * @param {number} carpetLen
    	 * @return {number}
    	 */
    	var minimumWhiteTiles = function(f, m, l) {
    	    const n = f.length;
    	    let dp = new Array(m + 1).fill(0).map(()=>new Array(n));
    
    	    // 初始化边界
    	    for (let j = 0, cnt = 0; j < n; ++ j) {
    	        cnt += (f[j] == '1');
    	        dp[0][j] = cnt;
    	    }
    
    	    // 状态转移
    	    for (let i = 1; i <= m; ++ i) {
    	        for (let j = 0; j < n; ++ j) {
    	            if (j < l)
    	                dp[i][j] = 0;
    	            else {
    	                dp[i][j] = Math.min(dp[i][j - 1] + (f[j] == '1'), dp[i - 1][j - l]);
    	            }
    	        }
    	    }
    
    	    return dp[m][n - 1];
    	};