第一题

最长公共前缀
力扣原题
我先把传入字符串数组从短到长排序，以最短的字符串为基准，不断对其他字符串进行比对，每比对完一轮则向后移动一位比对位，直至出现不匹配或到达最短字符串末尾则跳出。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  if (strs.length === 1) return strs[0];
  else {
    strs.sort((a, b) => a.length - b.length);
    let flag = true;
    let pos = 0;
    const cmp = strs[0];
    while (flag) {
      for (let i = 1; i < strs.length; i++) {
        if (pos >= cmp.length || strs[i][pos] !== cmp[pos]) {
          flag = false;
          break;
        }
      }
      pos++;
    }
    return cmp.slice(0, pos - 1);
  }
};

第二题

有台奇怪的打印机有以下两个特殊要求：

• 打印机每次只能打印由 同一个字符 组成的序列。
• 每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串s，你的任务是计算这个打印机打印它需要的最少打印次数。
力扣原题
区间dp。令dp[i][j]为打印i到j区间的最少打印次数，此时若区间两端的字符是相同的，显然当我们打印左方字符时，可以顺便将右方字符也打印好，而不会影响[i,k-1]的区间的最小操作数，因此此时dp[i,j]=dp[i,j-1]。而当区间两端的字符是不相同的，则需要分别完成区间左右两边的打印，记为区间[i,k]和[k+1,j]，很明显此时dp[i,j]应当为分割区间打印次数和的最小值，即min(k=i,j−1)dp[i][k]+dp[k+1][j]。

/**
 * @param {string} s
 * @return {number}
 */
var strangePrinter = function(s) {
const n = s.length;
  const dp = new Array(n).fill(0).map((i) => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;
  for (let len = 1; len < n; len++) {
    for (let i = 0; i + len < n; i++) {
      dp[i][i + len] = len + 1;
      for (let j = i; j < i + len; j++) {
        let tol = dp[i][j] + dp[j + 1][i + len];
        if (s[j] === s[i + len]) tol--;
        dp[i][i + len] = Math.min(dp[i][i + len], tol);
      }
    }
  }
  return dp[0][n - 1];
};

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/161.html
最后修改时间：2022-10-01 11:48:17
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！