【笔试】小米2023校招前端笔试
浏览 244 | 评论 0 | 字数 1751
TTQ
2022年10月01日
  • 第一题

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

    /**
     * @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]为打印ij区间的最少打印次数,此时若区间两端的字符是相同的,显然当我们打印左方字符时,可以顺便将右方字符也打印好,而不会影响[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://ponder.fun/archives/161.html
    最后修改时间:2022-10-01 11:48:17
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论